В данной статье я разберу принцип работы алгоритма Page Rank, который был предложен Лари Пейдж и Сергеем Брином для ранжирования веб-страниц для поискового сервиса Google.
Фундаментальная идея заключалась в том, что значимость страниц в интернете неравноценна. Некоторые страницы очевидно были важнее остальных и возникла необходимость в их ранжировании по значимости.
На момент изобретения алгоритма, в 1998 году, WWW по большей части состоял из страниц, доступных для индексирования, т.е. большинство ссылок было навигируемыми. Сеть можно было представить как большую марковскую цепь или граф, в котором веб-страницы являлись состояниями (нодами), а гиперссылки переходами между состояниями (ребрами графа). В этой концепции любая страница имела конечное число исходящих ссылок. Если предполагать, что пользователь (серфер) переходит по ссылкам (серфит) случайным образом, а вероятности перехода по любой из исходящих ссылок равновероятны, то вероятность такого перехода со страницы \(i\) на страницу \(j\) выражается как \(P_(ij) = \frac{1}{m}\), где \(m\) - число исходящих ссылок для данной страницы. Для страниц без ссылок вероятность принимается, как равная нулю. На этом простом принципе строился алгоритм ранжирования page rank.
Для реализации идеи алгоритма необходимо принять несколько обобщений:
- все страницы имеют разную значимость
- ссылки передают сообщения (голоса) от одной страницы к другой. Страница более важна, если она собирает больше голосов
- голоса более важных страниц более важны
Реализация page rank
Как посчитать важность страниц и важность голосов, которые передают страницы через ссылки?
- каждая ссылка голосует пропорционально важности ссылающейся страницы
- важность страницы делится между исходящими ссылками пропорционально количеству этих ссылок. Если страница \(i\) имеет важность \(R_i\) и \(d_i\) исходящих ссылок, то каждая такая ссылка получает \(\frac{R_i}{d_i}\) важность
- каждая страница имеет важность, равную сумме входящих голосов (важностей входящих в страницу ссылок)
В примере: \(R_j = \frac{R_i}{3} + \frac{R_k}{4}\)
Иными словами, ранг \(R_j\) страницы можно посчитать так: \(R_j = \underset{j \rightarrow i}\sum \frac{R_i}{d_i}\), где \(d_i\) - исходящая степень (out degree) ноды \(i\)
Очевидно, что для подсчета ранга каждой страницы в сети нам необходимо знать весь граф со всеми связями. Кроме того, необходимо решить, будем ли мы учитывать петли (ссылки страниц на самих себя). Модель алгоритма выглядит так: нам необходимо построить граф сети, инициализировать ноды некими значениями, а затем в итеративном режиме обновлять значения для каждой ноды до тех пор, пока значения рангов не стабилизируются (перестанут изменяться либо их изменения не будут превышать некое заранее известное значение).
Мы можем реализовать идею алгоритма в векторном виде. Пусть страница \(j\) имеет \(d_j\) исходящих связей. Если \(j \rightarrow i\), тогда мы можем сформулировать стохастическую матрицу \(\mathbf{M}_{ij} = \frac{1}{d_j}\), такую, что сумма по каждой колонке равна 1. Для страницы \(i\) мы имеем вектор важности \(r_i\), такой что выполняется \(\underset{i}\sum r_i = 1\). Тогда на каждой итерации \(\mathbf{r}_{next time} = \mathbf{M} \times \mathbf{r}_{previous time}\), где \(r = \underset{j \rightarrow i}\sum \frac{R_i}{d_i}\)
Алгоритм так же можно интерпретировать с точки зрения концепции случайного блуждания по графу;
- в момент \(t\) серфер находится на странице \(i\)
- в момент \(t+1\) он переходит на случайную страницу по исходящей ссылке
- повторить заданное число раз
При такой реализации можно полагать, что в момент времени \(t\) есть некая вероятность \(P(t)\) перехода серфера со страницы \(i\) на следующую страницу. Тогда \(P(t+1) = \mathbf{M} \times P(t)\) и \(P(t)\) - это не что иное, как вероятностное распределение через все страницы сети.
В этой (и предыдущей) интерпретации нетрудно заметить, что \(\mathbf{M}\) в каждый момент времени остается неизменной, что позволяет сформулировать вычислительно разрешимый алгоритм оценки page rank.
Для реализации подсчета page rank используется power iteration. Выглядит это так:
- инициализировать все ноды графа значением \(r^{(0)} = [\frac{1}{N}, \frac{1}{N}, ...\frac{1}{N}]^T\), где \(N\) - число нод в графе
- проитерировать по \(\mathbf{r}^{(t+1)} = \mathbf{M} \times \mathbf{r}^{(t)}\), где \(\mathbf{r}_{j}^{(t+1)} = \underset{j \rightarrow i}\sum \frac{r_{i}^{(t)}}{d_i}\)
- остановиться, когда \(\vert\mathbf{r}^{(t+1)} - \mathbf{r}^{(t)}\vert_1 < \varepsilon\), где \(\varepsilon\) некое заранее известное значение (можно использовать и другую норму)
Такой подход показывает сходимость примерно на 50 итерациии.
Проблемы page rank
- некоторые страницы - это dead ends (нет исходящих ссылок)
- часть страниц - это spider traps (исходящие ссылки двигаясь от страницы к странице приводят к образованию цикла)
Первая проблема ведет к утечке важности. Вторая к незапланированному сбору важности страницами, находящимися в цикле.
Решение для spider trap: в каждый момент времени серфер, который перемещается по сети, имеет две опции:
- с вероятностью \(\beta\) перейти по случайной ссылке далее в соответствии с основным сценарием алгоритма
- с вероятностью \(1 - \beta\) переместиться на случайную ноду в графе (телепорт)
На практике \(\beta \approx 0.8 ... 0.9\). Для dead ends необходимо принять \(\beta = 1\).
Именно такое решение было предложено в оригинальном решении (см. публикацию) Лари Пейджа и Сергея Брина в 1998 году.
\(r_j = \underset{j \rightarrow i}\sum \beta \frac{r_i}{d_i} + (1 - \beta)\frac{1}{N}\) или в матричном представлении \(A = \beta M + (1 - \beta)[\frac{1}{N}]_{N \times N}\), где \([\frac{1}{N}]_{N \times N}\) - матрица, в которой все значения равны \(\frac{1}{N}\)
Как на самом деле считается page rank
\(r^{new} = A \times r^{old}\). Матрица \(A\) содержит \(N^2\) значений. Каждое значение стоит 4 байта памяти. Это означает матрица \(A\) для миллиона страниц (а в современном интернете содержится несколько миллиардов веб-сайтов и сотни миллиардов страниц) начинает занимать пространственно-неразрешимое место в памяти. К счастью, эта матрица разреженная. Мы можем использовать разреженную матрицу \(A\), предварительно выкинув из нее dead ends.
Такой подход существенно сокращает место для хранения матрицы, однако появляется новая проблема: \(\sum r_{ji} < 1\) т.к. мы выкинул dead ends. Решением является ренормализация.
В итоге алгоритм page rank выглядит так (реализация взята из лекций стэндфордского курса cs224w):
Подробную реализацию алгоритма можно посмотреть на странице в wiki, где представлены имплементации на разных языках программирования.
Варианты и применение page rank
Существует несколько дополнительных реализаций page rank. Например можно задать разную вероятность телепорта для разных нод. Так можно локализовать телепорт в области, близкой к ноде, из которой осуществляется перемещение - это в свою очередь ранажирует ноды в локальной близости. Другой подход - телепортировать “серфера” всегда в одну и ту же ноду (random walk with restart).
В настоящий момент page rank для ранжирования интернет-страниц - это уже история. В таком контексте алгоритм не используется google начиная с 2007 года. На смену page rank и подобным схемам пришли смешанные модели ранжирования, основанные на поведенчиских признаках и удовлетворенности пользователя. Да и сам интернет сильно изменился. Теперь большинство страниц не индексируется, а большинство ссылок - это лайки, посты, коментарии, внутренняя навигация и т.д.
Тем не менее page rank по-прежнему активно используется в исследованиях графов и сетей, а в интернете применяется в ранжировании для составления рекомендаций.