Информационная система "Конференции"

VI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых)

29-31 октября 2005 года, г. Кемерово, Россия

Тезисы докладов

информационные технологии

Свойства комбинированного алгоритма ранжирования вершин графа Веб

Шовкун А.В.

Алтайский Государственный Технический Университет (Барнаул)

В работе [1] представлен алгоритм упорядочения вершин графа Веб по степени их значимости, который является обобщением хорошо известных алгоритмов расчета рангов вершин графа Веб - PageRank и HITS. Алгоритм описывается уравнением

p(k+1)=alpha*A*B*p(k)+(1-alpha)*e/n, 0 где (n) - число вершин в графе, (p) - (n)-мерный вектор рангов вершин, (e) - (n)-мерный вектор, составленный из единиц, матрицы (A) и (B) строятся на основе матрицы смежности графа (L).

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

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

Литература:

Перепелкин Е.А., Шовкун А.В. Комбинированный алгоритм расчета рангов вершин графа Web// Автоматика и вычислительная техника. -- 2005. -- N1.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]