ApproximateFlowCommunity
2008-06-15 23:28ApproximateFlowCommunity - это алгоритм анализа ссылок между веб-страницами, позволяющий определить границы сообщества, которому принадлежит начальное приближение из нескольких веб-страниц. Алгоритм основан на поиске кластера веб-страниц, связанных с начальным приближением.
Словарь
| Основная форма: | Approximate Flow Community |
| Предметная область:: | |
| NeuralNetwork | |
| Синонимы: | |
| Exact Flow Community, Flow Community Identification | |
Будем называть веб-сообществом такое множество страниц, для каждой из которых количество ссылок, направленных на страницы сообщества больше, чем количество ссылок на другие страницы. Такое определение близко к понятию кластера в кластерном анализе. Существует оригинальный алгоритм определения границы веб-сообщества по начальному приближению, основанный на анализе связей между его страницами, а не их содержимом.
Идея алгоритма состоит в нахождении максимального потока из веб-сообщества во вне и, как следствие, нахождение минимального сечения графа. Алгоритм требует определить начальное приближение - т.е. несколько страниц, заведомо принадлежащих сообществу. Затем граф связности преобразуется к специальному виду: в частости, страницы начального приближения связываются с общим источником, остальные страницы с общим стоком. Для такого графа находится минимальное сечение при помощи алгоритма Ford-Fulkerson. Страницы, лежащие в части графа, отделенной таким сеченим и содержащей начальное приближение, удовлетворяют определению веб-сообщества. Подробное описание алгоритма и результатов его использования содержится в статье Flake, G., Lawrence, S., Lee Giles, C. and Coetzee, F. Self-organization and identification of Web communities. IEEE Computer, 35(3):66--71, 2002.



