Исследование масштабируемых алгоритмов анализа графов на основе фреймворка Apache Spark

Интернет является гипертекстовой базой данных огромной сложности, и она продолжает расширяться феноменальными темпами. Эту базу данных можно легко представить в виде веб-графа. Одной из основных трудностей, в анализе веб-графа, является точное моделирование авторитетности в контексте конкретной темы запроса.

Методы и алгоритмы теории графов активно используются в различных областях науки и техники. Один из данных алгоритмов: алгоритм HITS, который чаще всего используется для поиска Интернет-страниц, соответствующим запросу пользователя, на основе информации, заложенной в гиперссылки.

Ранжирование — сортировка сайтов в поисковой выдаче, применяемая в поисковых системах. Существует множество факторов для ранжирования, среди которых можно отметить авторитетность сайта, количество и качество внешних ссылок, релевантность текста к поисковому запросу.

Ранжирование гипертекстовых документов возможно также по свойствам, обуславливаемым сетевой структурой, гиперссылками. Чтобы определить авторитетность веб-страницы или документа как источника информации или посредника используется анализ веб-графа, образованного веб-документами и соответствующими гиперссылками. Наиболее известными алгоритмами для ранжирования веб-страниц, основанных на связях: HITS и PageRank.

Оба алгоритма предназначены для решения проблемы избыточности, свойственной широким запросам, увеличения точности результатов поиска на основе методов анализа сложных сетей. 

Алгоритм HITS (Hyperlink Induced Topic Search) является реализацией латентно-семантического индексирования к ранжированию выдачи информационно-поисковых систем. Он обеспечивает выбор из информационного массива лучших «авторов» и «посредников».

Страница, ссылающаяся на многие другие, является хорошим «посредником». При этом страница, на которую ведет множество ссылок с других страниц является хорошим «автором». Пример связанного набора двух типов ссылок показан на рисунке 1.

Рисунок 1. Пример связанного набора «посредников» и «авторов»

Данные утверждения являются основой для алгоритма HITS. В данном алгоритме для каждой веб-страницы итеративно вычисляются оценка авторитетности и посредническая оценка. То есть для каждой страницы рекурсивно рассчитывается её значимость как «автора» и «посредника».

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

Оценка авторитетности страницы определяется следующий образом

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

После определения оценки авторитетности следует шаг обновления оценки посредника, которая определяется следующим образом

где  – индекс искомой страницы,  – общее количество страниц, на которые ссылается искомая страница,  – индекс страницы на которую ссылается искомая страница. Другими словами, посредническая оценка страницы рассчитывается как сумма значений оценок авторитетности страниц, на которые она ссылается.

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

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

PageRank измеряет важность каждой вершины в графе, предполагая что связь между  и представляет собой подтверждение важности  над . Например, если на один сайт ссылаются множество других, то этот сайт получит более высокий ранг.

Пусть существует объект , на которую ссылаются объекты . Параметр  является коэффициентом затухания и находится между 0 и 1, а  – количество ссылок выходящих из объекта . Тогда PageRank считается по следующей формуле:

Для выполнения работы была использована частичная база данных гиперссылок Википедии, собранная в сентябре 2011 года. База данных содержит необходимую информацию для реализации распределенных алгоритмов ранжирования поиска. Для начала работы необходимо записать данные из файла в котором распространяется данный набор данных. Результат заполнения графа и построения связей между вершинами показан на рисунке 2.

Рисунок 2. Результат вывода 300 связанных  вершин  в интерфейсе Neo4j

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

После работы алгоритма формируется новый граф с новыми свойствами которые соответствуют оценке авторитетности и посредника. Результат работы данного алгоритма показан в таблице 1. В таблице указаны 5 страниц с лучшей оценкой посредника.

Таблица 1.

Результат работы алгоритма HITS

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

Время работы алгоритма зависит от количества итераций. Соотношение количества итераций к затраченному времени показано в таблице 2.

Таблица 2.

Отношение количества итераций к затраченному времени

По таблице видно, что затраченное время выполнения алгоритма растет нелинейно. Можно сравнить полученное время с алгоритмом PageRank, который входит в состав стандартных функций GraphX. Он так же требует на вход количество итераций. Соотношение количества итераций к затраченному времени алгоритма PageRank показано в таблице 3.

Таблица 3.

Затраченное временя алгоритмом PageRank

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