Конференции ИВТ СО РАН

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

1-3 ноября, г. Новосибирск, Россия

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

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

Сравнительный анализ алгоритмов расчета рангов вершин графа Веб

Шовкун А.В.

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

Под графом Веб понимается ориентированный граф, построенный на основе коллекции веб-документов [1]. Вершинами графа являются страницы коллекции, дугами -- ссылки между страницами. Одна из основных задач анализа графа Веб заключается в расчете рангов вершин графа, определяющих значимость страниц веб-коллекции. В настоящее время известно несколько алгоритмов ранжирования страниц веб-коллекций. Основными являются алгоритмы HITS и PageRank [2,3]. Предложен ряд модификаций указанных алгоритмов, в том числе алгоритмы, объединяющие алгоритмы HITS и PageRank в один алгоритм. Например, алгоритм BDG [4], построенный на основе модели баланса ориентированного графа.

Цель данной работы заключалась в проведении численных экспериментов с алгоритмами HITS, PageRank и BDG. Для решения данной задачи было написано программное обеспечение на языке Perl, позволяющее создавать тематические веб-коллекции по запросам пользователя к поисковым системам Интернета. Обработка веб-коллекций, построение графа, расчет рангов вершин, визуализация результатов, выполнялась с помощью системы научных и инженерных расчетов MATLAB.

Эксперименты проводились на тестовых примерах и реальных данных, полученных на основе запросов к поисковой системе AltaVista. Были построены коллекции, состоящие из нескольких тысяч веб-документов, для запросов : "Artificial Intelligence", "Open Source Software" и др. Был проведен сравнительный анализ работы алгоритмов ранжирования по скорости сходимости и совпадению оценок значимости страниц коллекций.

1. Некрестьянов И.С., Пантелеева Н.В. Системы текстового поиска для Веб // Программирование. -- 2002. -- Том 28. -- N4.

2. Kleinberg J.M. Authoritative sources in a hyperlinked environment// Journal of ACM. -- 1999. -- Vol. 46. -- N5.

3. Brin S., Page L. The anatomy of a large-scale hypertextual web search engine// Proceedings of the 7th International World Wide Web Conference. -- Brisbane, Australia, 1998.

4. Перепелкин Е.А. Модель баланса ориентированного графа// Информационные технологии. -- 2004. -- N10.

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

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

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