PageRank алгоритм ранжирования страниц¶

PageRank — алгоритм оценки авторитетности веб-страниц, разработанный сооснователями компании Google Ларри Пейджем и Сергеем Брином в 1996 году в Стэнфордском университете. Алгоритм лежит в основе одноимённой технологии ранжирования результатов поисковой выдачи Google и стал первым методом, позволившим учитывать не содержание документа, а структуру ссылок в интернете. Название алгоритма является игрой слов: фамилия Пейджа (Page) совпадает с английским словом «страница».

¶История создания

Разработка PageRank началась в рамках исследовательского проекта по созданию поисковой системы BackRub. Пейдж и Брин исходили из идеи, что значимость научной публикации можно оценить по количеству и качеству цитирований; аналогичный принцип они применили к веб-страницам. В 1998 году вышла основополагающая статья «The Anatomy of a Large-Scale Hypertextual Web Search Engine», где был формализован алгоритм. В том же году была основана компания Google Inc., и PageRank стал ядром её поисковой системы. Патент на алгоритм был выдан Стэнфордскому университету, который получил за него акции Google на сумму около 336 миллионов долларов.

¶Математическая модель

PageRank основан на модели случайного блуждания. Предполагается, что «пользователь» бесконечно переходит по ссылкам с одной страницы на другую, при этом с некоторой вероятностью (коэффициентом затухания, обычно 0,85) он переходит по ссылке, а с вероятностью 0,15 — переходит на случайную страницу. Ранг страницы вычисляется итеративно по формуле:

\[ PR(A) = (1-d) + d \left( \frac{PR(T_1)}{C(T_1)} + \ldots + \frac{PR(T_n)}{C(T_n)} \right) \]

где \(PR(A)\) — вес страницы A, \(d\) — коэффициент затухания, \(T_i\) — страницы, ссылающиеся на A, а \(C(T_i)\) — количество исходящих ссылок на странице \(T_i\). Таким образом, вес страницы распределяется поровну между всеми страницами, на которые она ссылается. Итерации повторяются до сходимости значений.

¶Особенности вычисления

Коэффициент затухания (damping factor) моделирует вероятность того, что пользователь продолжит переходы по ссылкам, а не закроет браузер. Значение 0,85 подобрано эмпирически.
Алгоритм устойчив к «паутине» ссылок: страницы, не имеющие входящих ссылок, получают минимальный вес (1-d), что предотвращает обнуление рангов.
Для учёта страниц без исходящих ссылок вводится поправка: такие страницы считаются ссылающимися на все страницы системы.

¶Трактовка и применение

В контексте поисковой выдачи PageRank интерпретируется как вероятность того, что случайный пользователь, бесконечно кликающий по ссылкам, окажется на данной странице. Чем выше эта вероятность, тем более «важной» считается страница. Изначально Google использовал PageRank как основной фактор ранжирования, комбинируя его с релевантностью текста запроса. Позже алгоритм стал лишь одним из сотен сигналов в сложной системе ранжирования.

С 2000 по 2016 год компания Google публиковала для веб-мастеров дискретное значение PageRank от 0 до 10 через панель инструментов Google Toolbar. Значения обновлялись несколько раз в год и были логарифмическими: рост на единицу означал примерно десятикратное увеличение веса. В марте 2016 года публичная индикация была полностью прекращена, хотя сам алгоритм продолжает использоваться внутри поисковой системы.

¶Влияние и критика

PageRank стал революцией в поисковых технологиях, поскольку позволил ранжировать страницы без анализа их содержания, опираясь на коллективный «голос» ссылок. Это породило целую индустрию поисковой оптимизации (SEO), направленную на искусственное увеличение ссылочной массы.

¶Основные недостатки

Спам по ссылкам: создание ферм ссылок и покупка ссылок для искусственного завышения ранга.
«Утечка веса»: страницы с большим числом исходящих ссылок передают каждой из них незначительную долю своего веса.
Устаревание: алгоритм не учитывает время публикации и динамику изменения ссылок.
Парадокс новых страниц: новые качественные страницы изначально имеют низкий ранг из-за отсутствия входящих ссылок.

Для борьбы с этими недостатками Google ввёл алгоритмы Penguin и Panda, а также перешёл к использованию более сложных методов машинного обучения, таких как RankBrain и BERT, которые частично вытеснили чистый PageRank.

¶Наследие

Несмотря на снижение роли в ранжировании, PageRank остаётся классическим примером применения теории графов в информационном поиске. Его математическая модель используется вне веба: в анализе социальных сетей (алгоритм Twitter-ранжирования), в биоинформатике для анализа сетей взаимодействия белков, в рекомендательных системах и при оценке значимости научных публикаций. Название «PageRank» стало нарицательным для любого алгоритма, оценивающего важность узлов графа на основе структуры связей.

¶См. также

¶Источники

Brin S., Page L. The Anatomy of a Large-Scale Hypertextual Web Search Engine // Computer Networks and ISDN Systems, 1998.
Page L., Brin R., Motwani R., Winograd T. The PageRank Citation Ranking: Bringing Order to the Web // Stanford Digital Library Technologies Project, 1999.
Langville A., Meyer C. Google's PageRank and Beyond: The Science of Search Engine Rankings // Princeton University Press, 2006.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →