Продолжаем говорить о визуализации графов GrahFrames. Сегодня поговорим о том, как ранжириуются сайты в поисковиках на основе алгоритма PageRank, и как он реализуется в GraphFrames. Читайте в этой статье: что такое PageRank, принципы работы, реализация его работы в библиотеке Apache Spark — GraphFrames.
Реализации PageRank в GraphFrames
Page Rank — это алгоритм ранжирования веб-страниц по результатам поискового запроса. В названии алгоритма присутствует, как имя со-основателя Google — Ларри Пейджа (Lary Page), так и название “веб-страницы” — web page. На основании этого алгоритма веб-страницы с бОльшим рангом появляются раньше.
В GraphFrames имеются две реализации PageRank:
- Использование метода
aggregateMessagesи выполнения ранжирования за фиксированное количество итерацийmaxIter. - Использование алгоритма Pregel до тех пор пока он не сойдется до значения
tol.
PageRank схож с индексом цитирования: чем больше на веб-странницу ссылаются, тем выше её ранг (вес).
Рассмотрим Page Rank, однако смотреть на голые значения не очень интересно, гораздо лучше результаты ещё и визуализировать.
Как работает PageRank
PageRank считается следующим образом:
Здесь важно понять, что вес графа будет зависеть от веса вершин, которые ссылаются на него: если у ссылающейся вершины большой вес, то и вершины-источника тоже будет большой. Это также защищает от клонов. Например, вы хотите, чтобы работающий по PageRank поисковик ставил ваш сайт на первое место, поэтому вы создали ещё сайты, которые ссылаются на первый. Так вот это не пройдет. Ведь у этих вторичных сайтов и так маленький рейтинг (вес), поэтому они не окажут значительного влияния на рейтинг первичного сайта. А вот если на вас будет ссылаться высокорейтинговый сайт, например, Википедия, то и ваш рейтинг возрастет.
Код курса
GRAF
Ближайшая дата курса
по запросу
Продолжительность
ак.часов
Стоимость обучения
0 руб.
Возьмем все тот же встроенный в 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]. С ним формула становится такой:
Обычно данный параметр делают равным 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, чтобы было видно, какая связь между вершинами. Ниже рисунок с результатом.
По умолчанию фильтр 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 изменением цвета
Значений весов слишком мало, поэтому на рисунке выше видим только, что вершины 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, чтобы залить цветом все содержимое вершины, а также цвет шрифта сделали белым. Ниже рисунок с результатом.
Ещё больше подробностей о работе с графами вы узнаете на наших образовательных курсах в лицензированном учебном центре обучения и повышения квалификации руководителей и ИТ-специалистов (менеджеров, архитекторов, инженеров, администраторов, Data Scientist’ов и аналитиков Big Data) в Москве:
