Словарь Advogato Trust Metric Квантизация

ApproximateFlowCommunity

Андрей Орлов  2008-06-15 23:28

ApproximateFlowCommunity - это алгоритм анализа ссылок между веб-страницами, позволяющий определить границы сообщества, которому принадлежит начальное приближение из нескольких веб-страниц. Алгоритм основан на поиске кластера веб-страниц, связанных с начальным приближением.

Словарь

Основная форма: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.

Эпицентр Zope3 Учат тут DreamBot Репозиторий Статистика Редакторам
Официальный сайт Zope3 Московская группа изучения реактивного движения The Dream Bot Site