Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf

106 ГЛАВА 5
Еще раз повторим этот же процесс. На самом деле мы будем повторять его снова и снова. В результате голоса (то есть важность каждой веб-страницы) будут изменяться так, как показано в следующей таблице. Вы можете видеть начальные значения и результаты после каждого тура голосования.
Тур
Страница 1
Страница 2
Страница 3
Страница 4
Страница 5
начало
0,20 0,20 0,20 0,20 0,20 1
0,17 0,27 0,27 0,13 0,17 2
0,16 0,22 0,26 0,14 0,22 3
0,16 0,23 0,26 0,16 0,20 4
0,17 0,22 0,26 0,15 0,20 5
0,16 0,23 0,25 0,15 0,20 6
0,16 0,23 0,26 0,15 0,20
Если провести еще один, седьмой по счету тур голосования, ситуация не поменяется по сравнению с предыдущим туром. Голоса и, следовательно, важность веб-страниц останутся прежними. Таким образом мы получим ко- нечный результат. Согласно вычисленному рейтингу, самой важной является страница 3; за ней идет страница 2, затем страница 5, затем 1 и в самом конце страница 4.
Давайте остановимся на минуту и подумаем о том, что мы только что сде- лали. Мы отталкивались от двух принципов, которые определили правила для вычисления важности веб-страниц на основе важности их обратных ссы- лок. Прежде чем начинать вычисления, мы назначили n веб-страницам оди- наковый рейтинг, равный 1/n. Затем мы посчитали важность каждой веб- страницы, сложив те доли голосов, которые они получили от своих обратных ссылок. Это дало нам новые рейтинги веб-страниц, которые отличались от из- начальных, 1/n. Мы повторили весь процесс, но уже с новыми значениями, и получили еще один набор рейтингов. После ряда повторений обнаружи- лось, что ситуация стабилизировалась: степень важности перестала меняться при последующих повторениях. В этот момент мы остановились и сообщили о найденных нами значениях.
Вопрос, конечно в том, работает ли описанный нами подход в целом, а не только в этом конкретном примере. И, что еще важнее, дает ли он осмыс- ленные результаты?

PAGERANK 107
Матрица гиперссылок и степенной метод
У метода вычисления важности страницы на основе важности ее обратных ссылок есть элегантное определение. Все начинается с графа, который опи- сывает связи между нашими веб-страницами. Этот граф можно предста- вить в виде матрицы чисел; назовем ее матрицей смежности. Создать ее довольно просто. Количество ее строк и столбцов должно быть равно числу узлов в графе. Затем каждое пересечение, относящееся к ссылке, будет обо- значено единицей, а все остальные пересечения — нолями. Матрица смеж- ности для нашего примера выглядит так:
1 2
3 4
5 0
1 0
0 0
0 0
1 0
1 1
0 0
1 1
1 0
1 0
0 0
1 1
1 0
Важность веб-страниц можно представить с помощью отдельной строки или вектора.
r P
r P
r P
r P
r P
( )
( )
( )
( )
( )
1 2
3 4
5
[
]
Поскольку мы начали рассматривать внутреннее устройство алгоритма
PageRank, давайте будем называть важность веб-страницы рейтингом.
В уместности этого термина вы сможете убедиться, когда мы вычислим рей- тинги (то есть важность) всех страниц, доступных онлайн. Поскольку наша строка содержит все рейтинги, мы будем называть ее рейтинговым векто-
ром графа.
Важность каждой веб-страницы разделена между ресурсами, на которые она ссылается. Теперь, когда у нас есть матрица смежности, мы можем прой- тись по каждой строке и поделить каждую единицу на количество единиц в этой строке. Это то же самое, что разделить голос каждой страницы между всеми ее исходящими ссылками. Если это сделать, получится следующая ма- трица.

108 ГЛАВА 5 0
1 0
0 0
0 0
1 2 0
1 2 1 3 0
0 1 3 1 3 1 2 0
1 2 0
0 0
1 3 1 3 1 3 0
/
/
/
/
/
/
/
/
/
/
⎡
⎣
⎢
⎢
⎢
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
⎥⎥
⎥
⎥
Назовем ее матрица гиперссылок.
Если внимательно присмотреться к этой матрице, можно заметить, что каждый ее столбец иллюстрирует вычисление важности страницы на основе рейтингов страниц, ссылающихся на нее. Возьмем первый столбец, кото- рый относится к странице 1; ее важность основана на страницах 3 и 4. Стра- ница 3 дает ей 1/3 своего рейтинга, а страница 4 — 1/2, так как она ссылается на две страницы. Страница 1 не получает рейтинг ни от каких других страниц в графе, поскольку они на нее не ссылаются. Это можно выразить так:
r P
r P
r P
r P
r P
r P
r P
( )
( )
( )
( )
( )
( )
( )
1 2
3 4
5 3
4 0
0 3
2 0
3 2
× +
× +
+
+
× =
+
Но это точное определение r(P
1
), рейтинга страницы 1. Мы получили рей- тинг, сложив произведения элементов рейтингового вектора с соответствую- щими элементами первого столбца матрицы гиперссылок.
Давайте посмотрим, что получится, если взять рейтинговый вектор и сло- жить произведения его элементов с соответствующими элементами второго столбца матрицы гиперссылок.
r P
r P
r P
r P
r P
r P
r P
( )
( )
( )
( )
( )
( )
( )
1 2
3 4
5 1
5 1
0 0
0 3
3
× +
× +
× +
× +
=
+
Это точное определение r(P
2
), рейтинга страницы 2. Аналогичным обра- зом сумма произведений элементов рейтингового вектора и содержимого третьего столбца матрицы гиперссылок даст нам r(P
3
), рейтинг страницы 3.
r P
r P
r P
r P
r P
r P
r P
r P
( )
( )
( )
( )
( )
( )
( )
( )
1 2
3 4
5 2
4 5
0 2
0 2
3 2
2 3
× +
+
× +
+
=
+
+
Можете убедиться в том, что четвертый и пятый столбцы матрицы ги- перссылок получат r(P
4
) и, соответственно, r(P
5
). Операция сложения произ- ведений элементов рейтингового вектора и содержимого каждого столбца матрицы в действительности является произведением этой матрицы и рей- тингового вектора.

PAGERANK 109
Если вы незнакомы с матричными операциями, этот процесс может пока- заться запутанным, поскольку, когда речь идет о произведении, обычно име- ется в виду умножение двух чисел, а не таких вещей, как векторы и матрицы.
Математические операции при желании можно проводить и с другими сущ- ностями, а не только с числами. Примером таких операций является произве- дение вектора и матрицы. В этом нет ничего таинственного: это просто опе- рация, которую мы выполняем с элементами вектора и матрицы.
Представьте, что мы выпекаем рогалики и круассаны, продавая их по $2 и, соответственно, $1,5. У нас есть два магазина; за отдельно взятый день один магазин продает 10 рогаликов и 20 круассанов, а другой — 15 рогали- ков и 10 круассанов. Как вычислить общие продажи в каждом из магазинов?
Чтобы узнать доход первого магазина, умножим цену рогалика на коли- чество проданных рогаликов в этом магазине. То же самое сделаем с круасса- нами и затем сложим эти два результата:
2 × 10 + 1,5 × 20 = 50
Проведем те же вычисления для второго магазина:
2 × 15 + 1,5 × 10 = 45
Это можно выразить более лаконично, если записать цены рогаликов и круассанов в виде вектора:
[
]
2 00 1 50
,
,
Теперь запишем в виде матрицы суточные продажи. Матрица будет состо- ять из двух столбцов, по одному на магазин, и двух строк, по одной для рога- ликов и круассанов:
10 15 20 10
⎡
⎣⎢
⎤
⎦⎥
Теперь, чтобы найти общие продажи в каждом магазине, умножим эле- менты вектора на каждый столбец матрицы продаж и результаты просумми- руем. Таким образом получится произведение вектора и матрицы:
2 00 1 50 10 15 20 10 2 00 10 1 50 20 2 00 15 1 50 10
,
,
[ ,
,
,
,
]
[
]
× ⎡
⎣⎢
⎤
⎦⎥
=
×
+
×
×
+
×
== [
]
50 45

110 ГЛАВА 5
Произведение вектора и матрицы — это частный случай произведения двух матриц. Давайте расширим наш пример и заменим вектор с ценами ро- галиков и круассанов матрицей с ценами и прибылью для каждой продажи:
2 00 1 50 0 20 0 10
,
,
,
,
⎡
⎣
⎤
⎦⎥
Чтобы найти общие продажи и прибыль для каждого магазина, создадим такую матрицу, в которой записи i-й строки и j-го столбца будут суммой про- изведений i-й строки в матрице с ценами и прибылью и j-го столбца матрицы продаж. Это определение произведения двух матриц:
2 00 1 50 0 10 0 20 10 15 20 10 2 00 10 1 50 20 2
,
,
,
,
,
,
,
⎡
⎣
⎤
⎦⎥
× ⎡
⎣⎢
⎤
⎦⎥
=
×
+
×
000 15 1 50 10 0 10 10 0 20 20 0 10 15 0 20 10 50 45 5
3
×
+
×
×
+
×
×
+
×
⎡
⎣⎢
⎤
⎦
=
,
,
,
,
,
,55
⎡
⎣⎢
⎤
⎦⎥
Вернемся к рейтингам страниц. На каждом этапе вычисление рейтин- гового вектора в действительности является произведением этого вектора из предыдущего этапа и матрицы гиперссылок. Переходя от этапа к этапу, мы получаем последовательные оценки рейтингов, то есть последовательные оценки рейтингового вектора, который из них состоит.
Чтобы получить эти последовательные оценки рейтингового вектора, нам нужно лишь умножить его на каждом этапе на матрицу гиперссылок и полу- чить тем самым вектор для следующего этапа.
На первом этапе все элементы рейтингового вектора равны 1/n, где n — количество страниц. Если обозначить исходный рейтинговый вектор как π
1
, вектор в конце первого этапа как π
2
, а матрицу гиперссылок как H, получится
π
2
= π
1
× Η.
На каждом этапе мы берем текущий рейтинговый вектор и вычисляем его версию для следующего этапа. Во втором туре голосования, в котором мы по- лучили третий столбец с оценками рейтингов (то есть наш третий рейтинго- вый вектор), мы выполнили следующие вычисления:
π
π
π
π
π
3 2
1 1
1 2
=
×
=
×
× =
×
×
=
×
H
H
H
H
H
H .
(
)
(
)

PAGERANK 111
В третьем туре голосования мы получили наш четвертый рейтинговый вектор:
π
π
π
π
π
4 3
1 2
1 2
1 3
=
×
=
×
×
=
×
×
=
×
H
H
H
H
H
H .
(
)
(
)
На каждом этапе мы умножаем результат предыдущих вычислений на матрицы гиперссылок. В конце получается набор произведений после- довательных оценок этой матрицы и рейтингового вектора. Как видим, это эквивалент умножения начального рейтингового вектора на расту- щие степени матрицы гиперссылок. Такой подход к вычислению после- довательных приближенных значений называется степенным методом.
Поэтому вычисление рейтингов веб-страниц является практическим при- менением степенного метода к рейтинговому вектору и матрице гипер- ссылок снова и снова, пока этот вектор не перестанет изменяться — или, как еще говорят, пока он не придет к стабильному значению, нашим ито- говым рейтингам.
Итак, получили более точное определение того, как вычисляются рей- тинги в веб-графе.
1. Формируем на основе графа матрицу гиперссылок.
2. Начинаем с исходной оценки рейтингов, назначая каждой странице рейтинг 1/n, где n — общее количество страниц.
3. Применяем степенной метод, умножая рейтинговый вектор на матрицу гиперссылок до тех пор, пока значения вектора не сойдутся.
Эта сжатая формулировка позволяет переместить задачу в область линей- ной алгебры — раздела математики, посвященного матрицам и операциям с ними. Существуют устоявшиеся теоретические наработки, с помощью кото- рых можно исследовать степенной метод и высокопроизводительные реали- зации операций с матрицами, такие как описанное выше умножение. Опре- деление, основанное на матрицах, также поможет определить, всегда ли сходится степенной метод, то есть всегда ли мы можем найти рейтинги всех страниц в графе.
Висячие узлы и блуждающий пользователь
Давайте возьмем в качестве примера более простой граф, состоящий всего из трех узлов.

112 ГЛАВА 5 1
3 2
Нам нужно найти рейтинги этих трех узлов. Мы будем следовать тому же алгоритму. Инициализируем рейтинговый вектор путем назначения всем уз- лам одинакового рейтинга, 1/3. Затем умножим рейтинговый вектор на ма- трицу гиперссылок.
0 1 2 1 2 0
0 1
0 0
0
/
/
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥
Если приступить к выполнению степенного метода, поэтапно обновляя рейтинговый вектор путем его умножения на матрицу гиперссылок, ока- жется, что после четырех этапов все рейтинги свелись к нолю.
Тур
Страница 1
Страница 2
Страница 3
начало
0,33 0,33 0,33 1
0,00 0,17 0,50 2
0,00 0,00 0,17 3
0,00 0,00 0,00
Это явная проблема. Мы не рассчитывали на то, что все страницы будут иметь нулевую важность. В конце концов, у страницы 3 есть две обратные ссылки, а у страницы 2 только одна, поэтому можно было бы ожидать, что это как-то отразится на результатах, не говоря уже о том, что общая сумма всех рейтингов должна быть равна 1. Но все пошло совсем не так, как мы надеялись.
Проблема кроется в узле 3. Наличие обратных ссылок должно было дать ему какой-то рейтинг, но дело в том, что у него отсутствуют выходные ссылки.
Поэтому можно сказать, что он вобрал в себя рейтинги остальной части графа, но никуда их не распределил. Он ведет себя как эгоистичный узел или черная дыра: все, что в него заходит, никогда не выходит наружу. На протя- жении нескольких этапов он вел себя как слив, в котором очутились значе- ния всех рейтингов.
Такие узлы называются висячими, поскольку они висят (мертвым грузом) на окончаниях графа. В вебе существованию таких страниц ничто не препят- ствует. Конечно, страницы обычно содержат входные и выходные ссылки,

PAGERANK 113
но вам вполне может встретиться страница без выходных ссылок, которая приведет в негодность степенной метод, описанный ранее.
Чтобы обойти эту проблему, воспользуемся метафорой. Представьте себе пользователя, который бродит по Интернету, переходя с одной стра- ницы на другую. Для этого он обычно щелкает по ссылке. Но в какой-то мо- мент пользователь заходит на висячий узел — страницу, которая не ссыла- ется ни на какой другой ресурс. Мы не хотим, чтобы он там застрял, поэтому наделяем его возможностью перейти на любую другую страницу, доступ- ную онлайн. Например, мы ходим по Интернету и случайно попадаем в ту- пик. Но это нас не останавливает. Мы всегда можем ввести другой адрес в нашем браузере и перейти на любой другой ресурс, даже если висячая страница на него не ссылается. Именно этого мы хотим от нашего пользо- вателя. Если ему больше некуда идти, он выбирает произвольную страницу и переходит на нее, чтобы продолжить свое виртуальное путешествие. Поль- зователь становится блуждающим; у него в распоряжении есть устройство телепортации, с помощью которого он может мгновенно очутиться в совер- шенно любом месте.
Применим эту метафору к ранжированию страниц. Матрица гиперссылок дает нам вероятность, с которой пользователь перейдет по ссылке на опреде- ленную страницу. В нашем примере с тремя узлами первая строка матрицы гиперссылок говорит о том, что, находясь на странице 1, пользователь может в равной степени выбрать одну из двух страниц: 2 или 3. Во второй строке мы видим, что, находясь на странице 2, он всегда будет переходить на страницу 3.
Вернемся на секунду к нашему первому примеру. Если пользователь попадет на страницу 5, перед ним открывается возможность перехода на страницы 2,
3 и 4 с одинаковой вероятностью, 1/3.
Висячий узел проявляется в виде строки, состоящей из одних нолей. Веро- ятность перехода куда-либо является нулевой. Здесь нам поможет блуждаю- щий пользователь. Как уже отмечалось, он может перейти на любую стра- ницу графа. Это фактически означает, что в матрице гиперссылок больше не будет строк с нолями. Пользователь может выбрать любую веб-страницу с одинаковой вероятностью, поэтому вместо нолей эта строка будет содер- жать значения 1/n (в нашем примере это 1/3). Таким образом матрица при- мет следующий вид:
0 1 2 1 2 0
0 1
1 3 1 3 1 3
/
/
/
/
/
⎡
⎣
⎢
⎢
⎢
⎤
⎦
⎥
⎥
⎥

114 ГЛАВА 5
Теперь пользователь, очутившийся на странице 3, может перейти на лю- бую страницу графа с одинаковой вероятностью. Он даже может временно за- стрять на той же странице, но это неважно, так как он станет повторять свои попытки снова и снова, пока случайным образом не выберет другую стра- ницу.
Мы будем называть эту модифицированную матрицу, в которой нулевые строки заменены строками со значениями вида 1/n, S-матрицей. Если ис- пользовать ее в степенном методе, рейтинги изменятся следующим образом: