Статья:

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

Журнал: Научный журнал «Студенческий форум» выпуск №17(68)

Рубрика: Физико-математические науки

Выходные данные
Витальев А.В. Исследование масштабируемых алгоритмов анализа графов на основе фреймворка Apache Spark // Студенческий форум: электрон. научн. журн. 2019. № 17(68). URL: https://nauchforum.ru/journal/stud/68/51639 (дата обращения: 07.06.2020).
Журнал опубликован
Мне нравится
на печатьскачать .pdfподелиться

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

Витальев Александр Владимирович
магистрант, Самарский национальный исследовательский университет им. академика С.П. Королева, РФ, г. Самара

 

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

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

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

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

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

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

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

https://upload.wikimedia.org/wikipedia/commons/e/e5/Hubs_and_authorities.jpg

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

 

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

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

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

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

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

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

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

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

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

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

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

 

../Downloads/graph.png

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

 

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

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

Таблица 1.

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

Название страницы

Оценка посредника

Оценка авторитетности

List of American television programs by date

List of biographical films

2010 in film

2009 in film

List of film score composers

 

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

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

Таблица 2.

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

Количество итераций

Затраченное время, мин

10

1.8

50

2.03

100

2.4

 

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

Таблица 3.

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

Количество итераций

Затраченное время, мин

10

4.19

50

7.35

100

8.32

 

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

 

Список литературы:
1 Риза, C. Spark для профессионалов: современные паттерны обработки больших данных [Текст] / С. Риза, У. Лезерсон, Ш. Оуэн, Д. Уиллс. – Спб.: Питер, 2017. – 272 с.
2 Ландэ, Д. Интернетика. Навигация в сложных сетях. Модели и алгоритмы [Текст] / Д. Ландэ, А. Снарский, И. Безсуднов. – Мск.: Либро-ком, 2009. – 264 с.
3 Duvvuri, S. Spark for Data Science [Text] / S. Duvvuri, B. Singhal. – Birmingham: Packt Publishing Ltd, 2016. – 344 p.
4 Официальный веб-сайт Apache Spark [Электронный ресурс] / The Apache Software Foundation. – URL: https://spark.apache.org (дата обращения: 23.11.2018). 
5 Официальный веб-сайт Amazon EMR [Электронный ресурс] / Amazon Web Services, Inc. – URL: https://aws.amazon.com/ru/emr (дата обращения: 02.12.2018).