На сайте Американского математического общества опубликовано подробное объяснение математических принципов, которые используются в PageRank и других подобных алгоритмах. Формулы довольно простые, а объяснение очень толковое и понятное.

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

Конечным результатом работы PageRank является целочисленный показатель "важности" страницы PR, который принимает значения от PR0 до PR10 и вычисляется путем анализа входящих ссылок. Их количество и качество говорит о важности данной страницы для интернет-сообщества. Например, сайт www.kv.by имеет PR5.

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

Какие же формулы используются для вычисления PR? Об этом рассказывается в подробной статье на сайте Американского математического общества (www.ams.org/featurecolumn/archive/pagerank.html).

Вот как работает PageRank. Предположим, что на странице P_j размещено l_j ссылок. Если одна из этих ссылок ведет на страницу P_i, то P_j передаст 1/l_j своей "важности" странице P_i.

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

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

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

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

Сформируем вектор I = [I(P_i)], элементами которого являются значения PR, то есть "важность" всех страниц. По нашим условиям вектор получается стационарным.

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

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

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

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

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

Анатолий АЛИЗАР