Pull to refresh

PageRank разобрали на формулы

Reading time 2 min
Views 7.3K
Примерно 95% текста в 25 млрд документов, проиндексированных Google, составлены из маленького словаря в десять тысяч слов. Это значит, что почти любой поисковый запрос выдаст миллионы документов. Таким образом, вычисление релевантности документа представляет собой нетривиальную математическую задачу. Для этого используется комбинация сложнейших математических методов. К тому же, содержимое веба постоянно изменяется, так что показатель релевантности нужно постоянно пересчитывать. Центральное место в системе ранжирования Google занимают алгоритмы PageRank.

Все мы знаем, что конечным результатом работы PageRank является некий показатель «важности» страницы PR, который принимает значения от PR0 до PR10 и вычисляется путем анализа входящих ссылок. Их количество и качество говорит о важности данной страницы для интернет-сообщества.

Тот уровень PR, который мы видим, является сильно округленным значением, а точный показатель известен только программистам Google. Показатель PR изменяется по логарифмической шкале, то есть значение PR5 на порядок больше, чем PR4.

Какие же формулы используются для вычисления PR? Об этом рассказывается в подробной статье на сайте Американского математического общества.

Вот как работает PageRank. Предположим, что на странице Pj размещено lj ссылок. Если одна из этих ссылок ведет на страницу Pi, то Pj передаст 1/lj своей «важности» странице Pi (примерно по такому же алгоритму работает передача кармы на «Хабре»).

Уровень важности (то есть, PR) страницы Pi есть сумма всех таких значений со всех входящих ссылок. Если представить набор страниц, ссылающихся на страницу Pi, как Bi, то «важность» Pi вычисляется по следующей формуле:



Все это похоже на проблему курицы и яйца. Чтобы узнать PR страницы, нам нужно сначала знать PR всех страниц, которые на нее ссылаются. Впрочем, математические методы позволяют решить и эту проблему.

Для этого создается матрица гиперссылок , в которой строка i столбца j будет иметь следующий вид:



Это стохастическая матрица, то есть матрица, в которой все столбцы и/или строки — ряды неотрицательных действительных чисел, дающих в сумме единицу.

Сформируем вектор , элементами которого являются значения PR, то есть «важность» всех страниц. По нашим условиям вектор получается стационарным.

Рассмотрим ситуация на примере небольшой матрицы из восьми веб-страниц, гиперссылки между которыми отображаются стрелками.



Этой ситуации соответствует такая матрица



и стационарный вектор



Расчет показывает, что страница 8 выигрывает конкурс по популярности. Вот та же самая картинка, где наиболее «авторитетные» страницы окрашены более светлым цветом.



Примерно так работает PageRank, с математической точки зрения. Это только базовые принципы работы алгоритма. С подробностями можно ознакомиться в оригинале статьи.
Tags:
Hubs:
+33
Comments 16
Comments Comments 16

Articles