ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В АЛГОРИТМЕ ССЫЛОЧНОГО РАНЖИРОВАНИЯ PAGERANK

Введение

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

Постановка проблемы

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

Основные определения

Введем некоторые определения, которые будут использованы в работе.

Определение 1. Граф – совокупность двух множеств, где первое множество V не пустое и конечное, элементы этого множества назовем вершинами. Второе множество – множество  всевозможных  пар  различных  элементов множества V:

Определение 2. Ориентированный граф (орграф) – пара (V,E), где V – множество вершин (узлов), E – множество ребер (дуг),

Определение 3. Сток (в ориентированном графе) – вершина, из которой не выходит ни одного ребра.

Определение 4. Вес вершины (применительно к данному алгоритму) – числовая величина, которая характеризует степень значимости объекта (вершины графа).

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

История алгоритма

В 1996 году Сергей Брин и Ларри Пейдж, аспиранты Стэнфордского университета, начали работу над научным проектом — поисковой системой по сети Интернет, которая использовала новую идею о том, что веб-страница считается тем приоритетнее, чем больше на неё ссылается других страниц, и чем более приоритетными являются эти страницы.  Впервые алгоритм PageRank был описан в 1998 году в научной статье. Позже вышла статья с описанием строения созданной поисковой системы, которая существенно превосходила уже существующие поисковые системы. Осознав перспективы поисковой системы и используемого алгоритма, Брин и Пейдж основали компанию Google Inc.

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

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

Описание алгоритма

PageRank — алгоритм ссылочного ранжирования, применяющийся к набору документов, связанных между собой гиперссылками. Алгоритм присваивает каждому из них некоторое численное значение, определяющее приоритет объекта относительно других. В частности, алгоритм применяется не только к веб-страницам, но и к любому набору объектов, связанных между собой взаимными ссылками, то есть к любому графу. В качестве объектов можно представить вершины графа, а ссылки будут являться его ребрами (рисунок 1).

Рисунок 1. Представление алгоритма PageRank в виде графа.

Для того чтобы понять суть алгоритма, рассмотрим его реализацию. Основополагающая формула расчёта веса PageRank для страницы, возможно, уже не используется в поисковых системах Google повсеместно, но она представляется достаточно корректной для решения широкого круга актуальных задач. Это и определяет универсальность алгоритма.

Пусть u – вершина графа. Тогда  – множество вершин, на которые ссылается u, и  – множество вершин, которые, в свою очередь ссылаются на u. Пусть   – набор ребер из u. Введем коэффициент затухания c <1. Чаще всего с принимают равным 0.85. Это необходимо для того, чтобы вершина, которая являются стоком, не перенимала полный вес той вершины, с которой она соединена дугой. Для удобства будем говорить, что вершина А ссылается на вершину B, если A – начало дуги (A,B), а B – её конец.

Таким образом, чтобы вычислить вес PageRank вершины A нам необходимо знать веса всех вершин, соединенных дугой с вершиной A. Их веса будут частично зависеть от вершины A или каких-то других вершин, которые, в свою очередь, будут являться началами дуг, соединенных с данной вершиной.

Вес PageRank, передаваемый на вершину A с вершины B, которая является началом дуги (B,A), уменьшается с каждой ссылкой на какую-либо вершину. Это означает, что PageRank, по существу, является мерой ее голоса; страница может разделить этот голос между одной, двумя или многими вершинами, но общий вес всех вершин остается неизменным.

Пример реализации алгоритма

Рассмотрим принцип работы алгоритма на конкретном примере. Нарисуем граф показывающий работу алгоритма (рисунок 2).

Рисунок 2. Начальное состояние графа.

На первом шаге алгоритма присваиваем начальные веса каждой из вершин.

Для простоты вычислений, выбираем вес вершин равный единице (рисунок 3).

Рисунок 3. Первый шаг выполнения алгоритма.

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

Таким образом, значение веса, который может передать вершина А после затухания равно 1*0,85=0,85. Вершина А является началом двух дуг, поэтому, по окончании итерации, мы разделим 0,85 на 2, и прибавим результат 0,425 к весам вершин B и С соответственно. Следует отметить, что при расчетах необходимо учитывать все ссылки вершины, иначе конечный результат измерений будет заведомо неверным.

Рассмотрим вершину B. Она является началом только одной дуги, поэтому B передаст 1 * 0,85 = 0,85 вершине C в конце второго шага.

Вершина C тоже является началом одной дуги. Следовательно, она передаст вес 1 * 0,85 = 0,85 вершине A.

Аналогично вершина D передаст вес 0,85 вершине C.

Добавим результаты вычислений к весам всех страниц и получим исходные веса для третьей итерации. Представим результаты вычислений в виде графа (рисунок 4).

Рисунок 4. Второй шаг выполнения алгоритма.

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

Рассмотрим вершину A. Ее вес равен 1,85. Вес, доступный для передачи, после применения коэффициента затухания составит1,85 * 0,85 = 1,5725. Так как из вершины А выходят 2 дуги, по окончанию итерации мы прибавим по 0,78625 к весу вершины B и C.

Вершина B, имеющая одну исходящую дугу передаст 1,425 * 0,85 = 1,21125 странице C, по завершению итерации.

Вершина C тоже является началом одной дуги, но обладает весом 3,125. Поэтому она передает 3,125 * 0,85 = 2,65625 вершине A.

Вершина D имеет одну дугу, поэтому она передаст 0,85 вершине C.

Результирующий граф изображен на рисунке 5.

Рисунок 5. Результат работы алгоритма.

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

Применение PageRank для решения практических задач.

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

1. Доктор Стефано Аллесина (Stefano Allesina) из Чикагского университета применил PageRank в сфере экологии, чтобы определить, какие из особей являются жизненно важными для поддержания экосистемы. 

2. Twitter разработал сервис WTF (Who-to-Follow) – персонализированный вариант рекомендательной системы, основанной на PageRank, показывающий список людей, на которых стоит подписаться.

3. Бин Жэнь (Bin Jiang) из Гонконгского политехнического университета использовал вариант PageRank для предсказания перемещения людей на основании топологических метрик в Лондоне.

С другой стороны, этот алгоритм хорошо зарекомендовал себя при прогнозировании различных ситуаций в игровых видах спорта. Например, для определения лучших игроков матча на финале Чемпионата Европы по футболу в 2014 году использовался именно PageRank. Значимость игрока в данном случае определялась количеством пасов, которые тот совершал и получал.

Заключение

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

Список литературы:

1. Додонова Н.Л. Конспект лекций по дисциплине теория конечных графов и ее применения. Самара, 2010
2. Page L., Brin S., Rajeev M., and Winograd T. The PageRank Citation Ranking: Bringing Order to the Web // Technical Report. Stanford InfoLab. 1999. P.3-5.