Как ранжируются сайты с помощью PageRank

Продолжаем говорить о визуализации графов GrahFrames. Сегодня поговрим о том, как ранжириуются сайты в поисковиках на основе алгоритма PageRank, и как он реализуется в GraphFrames. Читайте в этой статье: что такое PageRank, приницпы работы, реализация его работы в библиотеке Apache Spark — GraphFrames.

Реализации PageRank в GraphFrames

Page Rank — это алгоритм ранжирования веб-страниц по результатам поискового запроса. В названии алгоритма присутствует, как имя со-основателя Google — Ларри Пейджа (Lary Page), так и название “веб-страницы” — web page. На основании этого алгоритма веб-страницы с бОльшим рангом появляются раньше.

В GraphFrames имеются две реализации PageRank:

  1. Использование метода aggregateMessages и выполнения ранжирования за фиксированное количество итераций maxIter.
  2. Использование алгоритма Pregel до тех пор пока он не сойдется до значения tol.

PageRank схож с индексом цитирования: чем больше на веб-странницу ссылаются, тем выше её ранг (вес).

Рассмотрим Page Rank, однако смотреть на голые значения не очень интересно, гораздо лучше результаты ещё и визуализировать.

Как работает PageRank

PageRank считается следующим образом:

Как работает PageRank
Формула PageRank

Здесь важно понять, что вес графа будет зависеть от веса вершин, которые ссылаются на него: если у ссылающейся вершины большой вес, то и вершины-источника тоже будет большой. Это также защищает от клонов. Например, вы хотите, чтобы работающий по PageRank поисковик ставил ваш сайт на первое место, поэтому вы создали ещё сайты, которые ссылаются на первый. Так вот это не пройдет. Ведь у этих вторичных сайтов и так маленький рейтинг (вес), поэтому они не окажут значительного влияния на рейтинг первичного сайта. А вот если на вас будет ссылаться высокорейтинговый сайт, например, Википедия, то и ваш рейтинг возрастет.

Графовые алгоритмы. Бизнес-приложения

Код курса
GRAF
Ближайшая дата курса
13 декабря, 2022
Длительность обучения
24 ак.часов
Стоимость обучения
45 000 руб.

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

  • На вершину a никто не ссылается, поэтому вес остается тем же самым.
  • На вершину b ссылаются c и a, поэтому вес будет равен сумме предыдущих веса, т.е. 1. В знаменателе обоих слагаемых будет также 1, так как каждый из них имеет по одной ссылке на вершины.
  • С вершиной c аналогично, но ссылаются на нее f и b.
  • На вершину d ссылается e, но в знаменателе будет 2, так как e ссылается на две вершины: d и f.
  • С вершиной f аналогично, ведь на неё ссылается e.
  • На e никто не ссылается, поэтому вес нулевой.

На второй итерации происходит то же самое, но предыдущие веса берутся из первой итерации (см. таблицу).

i=0 i=1 i=2
a 1 1 ½
b 1 2 3
c 1 2 5/2
d 1 ½ 0
e 1 0 0
f 1 ½ 0

В GraphFrames у метода pageRank имеется параметр resetProbability. Неизвестно почему разработчики его так назвали, но этот параметр более известен как damping factor [1]. С ним формула становится такой:

PageRank dumping factor
Формула PageRank с учетом dumping factor

Обычно данный параметр делают равным 0.85. Он предполагает, что с вероятностью 1-r среднестатистический пользователь не будет переходить по ссылкам на странице. Допусти, некая страница имеет 1000 баллов, 10 исходящих ссылок и damping factor составляет 85%. Каждая из этих ссылок не получает все 100 баллов. 15% от общего рейтинга исчезает, а оставшиеся баллы — 850 будут розданы 10 исходящим ссылкам. Таким образом, каждая ссылка получит только 85 баллов.

Библиотека Graphviz в Python

В прошлой статье мы говорили о визуализации графов с помощью пакета Graphviz. Мы использовали командную строку, записывали файл формата gv и вызывали через неё фильтры (dot, circo, neato). К счастью, Graphviz доступен в виде библиотеки Python. Благодаря нему очень просто задавать атрибуты графа. Устанавливается он через pip:

pip install graphviz

Направленные графы строятся через объект Digraph. Важным его параметром является engine, который задает программу-фильтр. По умолчанию используется dot. Атрибуты графа, вершин и ребер задаются параметрами graph_attr, node_attr, edge_attr в виде словаря, причем значениями должны быть строки:

import graphviz

node_attr = {'shape': 'box', 'fontsize': '14'}
digraph = graphviz.Digraph(engine='circo', node_attr=node_attr)

Построим связи Graphviz. Делается это через метод edge. А вершины задаются через метод node. Требуется указать откуда (head_hame) и куда идет (tail_name) связь. Например, так:

digraph = graphviz.Digraph()

rows = g.edges.collect() # g -- это граф GraphFrames
for row in rows:
    digraph.edge(tail_name=str(row.dst), 
                 head_name=str(row.src))

Поскольку параметры head_name и tail_name принимают в качестве значения строки (str), мы их преобразовали (это делать необязательно, если значениями уже являются строки). Чтобы посмотреть на сам граф, просто запустите объект Digraph в ячейке Jupyter Notebook:

digraph

Рассмотрим визуализацию графа на примере встроенного в GraphFrames графа под названием friends, который находится в модуле Graphs.

from graphframes.examples import Graphs

digraph = graphviz.Digraph()
g = Graphs(sqlContext).friends()

rows = g.edges.collect()
for row in rows:
    digraph.edge(tail_name=row.src,
                 head_name=row.dst,
                 label=row.relationship)

Мы добавили ещё и подпись label, чтобы было видно, какая связь между вершинами. Ниже рисунок с результатом.

Отображение графа Graphviz
Вид графа

По умолчанию фильтр dot располагает граф по вертикали сверху вниз. Мы можем изменить это поведение, изменив атрибут графа rankdir со значением TB (top, bottom) на LR (left, right). Опять же это, можно сделать передачей в конструктор соответствующего словаря, но мы сделаем это с помощью метода update, тогда не нужно будет снова создавать объект:

digraph.graph_attr.update(rankdir="LR")
Изменение ориентации графа
Горизонтальный граф

Визуализация PageRank изменением размера вершин

Итак, будем играться в размерами вершин графа на основании весов PageRank. Так, чьи веса больше, будут больше по размеру.

Сначала выполним алгоритм PageRank:

results = g.pageRank(maxIter=4)
results.vertices.show()

Результат:

+---+-------+---+------------------+
| id|   name|age|          pagerank|
+---+-------+---+------------------+
|  b|    Bob| 36|2.5724999999999993|
|  e| Esther| 32|              0.15|
|  a|  Alice| 34|         0.3316875|
|  f|  Fanny| 36|           0.21375|
|  d|  David| 29|           0.21375|
|  c|Charlie| 30|2.5183124999999995|
+---+-------+---+------------------+

Мы будем изменять размеры вершин с помощью атрибутов height(высота) и width (ширина) [1]. Их значениями будет тот самый ранг. Правда, мы проходимся только по ребрам, однако, зная, id ребра можно получить его ранг. Поэтому реализуем функцию get_rank, которая по значению id вернет ранг:

def get_rank(df, _id):
    return (df
           .vertices
           .filter(f'id = "{_id}"')
           .select("pagerank")
           .collect()[0].pagerank)

А дальше уже определим высоту и ширину вершины через метод node:

digraph = graphviz.Digraph()
digraph.graph_attr.update(rankdir="LR")


for row in rows:
    rank = get_rank(results, row.src)
    rank = scaled_value(rank, 1, 0.5)

    digraph.node(name=row.src,
                 height=str(rank),
                 width=str(rank))
    digraph.edge(tail_name=row.src, 
                 head_name=row.dst,
                 label=row.relationship)
Граф с учетом PageRank
Граф с учетом весов PageRank

Визуализация PageRank изменением цвета

Значений весов слишком мало, поэтому на рисунке выше видим только, что вершины a и b различаются. Мы можем пойти по-другому пути и менять не размеры вершин, а цвет. Делается это через атрибут fillcolor (атрибут color меняет цвет окружности, а не самого круга) . Будем задавать цвет в формате RGB: нужно передать 3 числа в диапазоне 0–1. Но веса PageRank точно не входят в этот диапазон, поэтому напишем свою функцию scaled_range.

def scaled_value(old_val, new_max=5, new_min=1): 
    return ((old_val - old_min) / (old_max - old_min)
            * (new_max - new_min) + new_min)

for row in rows:
    rank = get_rank(results, row.src)
    rank = scaled_value(rank, 0, 1)

    digraph.node(name=row.src,
                 fillcolor=f'{rank} {rank} {rank}',
                 style='filled',
                 fontcolor='white')
    digraph.edge(tail_name=row.src, 
                 head_name=row.dst,
                 label=row.relationship)

Мы также установили style=filled, чтобы залить цветом все содержимое вершины, а также цвет шрифта сделали белым. Ниже рисунок с результатом.

Граф с учетом PageRank
Цветной граф

Ещё больше подробностей о работе с графами вы узнаете на наших образовательных курсах в лицензированном учебном центре обучения и повышения квалификации руководителей и ИТ-специалистов (менеджеров, архитекторов, инженеров, администраторов, Data Scientist’ов и аналитиков Big Data) в Москве:

Записаться на курс

Смотреть раcписание

Источники
  1. https://graphviz.org/docs/attrs/height/

Добавить комментарий

Поиск по сайту