Примерно 95% текста в 25 млрд документов, проиндексированных Google, составлены из маленького словаря в десять тысяч слов. Это значит, что почти любой поисковый запрос выдаст миллионы документов. Таким образом, вычисление релевантности документа представляет собой нетривиальную математическую задачу.
Центральное место в системе ранжирования Google занимают алгоритмы PageRank.
Все мы знаем, что конечным результатом работы PageRank является некий показатель «важности» страницы PR, который принимает значения от PR0 до PR10 и вычисляется путем анализа входящих ссылок. Их количество и качество говорит о важности данной страницы для интернет-сообщества.
Показатель PR изменяется по логарифмической шкале, то есть значение PR5 на порядок больше, чем PR4.
 |
| Вот как работает PageRank. Предположим, что на странице Pj размещено lj ссылок. Если одна из этих ссылок ведет на страницу Pi, то Pj передаст 1/lj своей «важности» странице Pi. |
Уровень важности (то есть, PR) страницы Pi есть сумма всех таких значений со всех входящих ссылок. Если представить набор страниц, ссылающихся на страницу Pi, как Bi, то «важность» Pi вычисляется по следующей формуле:
Все это похоже на проблему курицы и яйца. Чтобы узнать PR страницы, нам нужно сначала знать PR всех страниц, которые на нее ссылаются. Впрочем, математические методы позволяют решить и эту проблему.
Для этого создается матрица гиперссылок
,
в которой строка i столбца j будет иметь следующий вид:
Для этого создается матрица гиперссылок
,
Сформируем вектор
,Рассмотрим ситуация на примере небольшой матрицы из восьми веб-страниц, гиперссылки между которыми отображаются стрелками.
Этой ситуации соответствует такая матрица
и стационарный вектор
Расчет показывает, что страница 8 выигрывает конкурс по популярности. Вот та же самая картинка, где наиболее «авторитетные» страницы окрашены более светлым цветом.
Примерно так работает PageRank, с математической точки зрения.
--
