PageRank

PageRank — это алгоритм ссылочного ранжирования веб-страниц, разработанный для оценки их относительной важности в структуре Всемирной паутины. Алгоритм основан на анализе количества и качества гиперссылок, ведущих на страницу, исходя из предположения, что ссылка с одной страницы на другую является своего рода «голосом» в пользу её значимости. PageRank стал одним из ключевых компонентов ранжирования результатов поисковой системы Google (принадлежит компании Google LLC, чей материнский холдинг Alphabet Inc. осуществляет деятельность на территории РФ через представительство, при этом рекламные сервисы Google признаны нарушающими законодательство РФ) и лёг в основу её первоначального успеха.

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

Алгоритм PageRank был разработан в 1996 году в Стэнфордском университете (США) Сергеем Брином и Ларри Пейджем, основателями Google. Название алгоритма происходит от фамилии Ларри Пейджа (англ. Page) и также может трактоваться как «ранг страницы» (англ. page rank). Идея заключалась в том, чтобы создать систему, оценивающую авторитетность веб-страницы не по её содержанию, а по тому, насколько часто и с каких сайтов на неё ссылаются. В 1998 году Брин и Пейдж опубликовали научную статью «The Anatomy of a Large-Scale Hypertextual Web Search Engine», где подробно описали принцип работы PageRank.

Первоначально алгоритм использовался внутри поисковой системы BackRub, предшественницы Google. После основания компании Google Inc. в 1998 году PageRank стал основным механизмом ранжирования результатов поиска, что позволило системе значительно превзойти существовавшие на тот момент поисковики (AltaVista, Yahoo!), которые полагались в основном на текстовый анализ содержимого страниц. Вплоть до 2010-х годов Google публично обновлял так называемый Toolbar PageRank — видимый пользователям показатель (от 0 до 10), хотя сам алгоритм постоянно совершенствовался. Около 2016 года публичная индикация PageRank была полностью прекращена, хотя сам алгоритм продолжает использоваться в изменённом виде как одна из множества составляющих ранжирования.

Принцип работы

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

PageRank моделирует поведение «случайного серфера» — пользователя, который бесконечно долго бродит по интернету, переходя по ссылкам со страницы на страницу. Вероятность того, что такой серфер окажется на конкретной странице, и есть её PageRank. Математически алгоритм основан на вычислении собственного вектора матрицы переходов веб-графа.

Формально PageRank (PR) страницы A вычисляется по формуле:

\[ PR(A) = (1-d) + d \cdot \sum_{i=1}^{n} \frac{PR(T_i)}{C(T_i)} \]

Где:

• \(PR(A)\) — PageRank страницы A;
• \(d\) — коэффициент затухания (damping factor), обычно устанавливаемый равным 0,85;
• \(PR(T_i)\) — PageRank страницы \(T_i\), которая ссылается на A;
• \(C(T_i)\) — количество исходящих ссылок на странице \(T_i\);
• \(n\) — количество страниц, ссылающихся на A.

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

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

Поскольку PageRank каждой страницы зависит от PageRank других страниц, расчёт ведётся итеративно. Начальные значения обычно устанавливаются равными 1/N (где N — общее количество страниц). Затем на каждом шаге значения пересчитываются по формуле до тех пор, пока не будет достигнута сходимость — разница между значениями на соседних итерациях станет меньше заданного порога. На практике для больших веб-графов (миллиарды страниц) требуется несколько десятков итераций.

Учёт «висячих страниц»

Страницы, не имеющие исходящих ссылок (так называемые «висячие страницы»), создают проблему утечки веса PageRank. Для её решения в модели предполагается, что с висячей страницы случайный серфер с вероятностью 1 переходит на произвольную страницу сети. На практике это реализуется путём добавления искусственных ссылок со всех висячих страниц на все остальные страницы с равным весом.

Модификации и развитие

Тематический PageRank

Базовая версия PageRank не учитывает тематику страниц. Для повышения релевантности были разработаны модификации, такие как Topic-Sensitive PageRank, где случайный серфер с определённой вероятностью переходит на страницы только определённой тематики. Это позволяет получать разные значения PageRank для разных категорий запросов.

TrustRank

Алгоритм TrustRank (2004 год) был предложен для борьбы со спамом. Он основан на идее, что «хорошие» сайты редко ссылаются на «плохие». Сначала вручную отбирается небольшое количество доверенных страниц (seed set), которым присваивается высокий начальный TrustRank. Затем значение распространяется по ссылкам, но с быстрым затуханием. Страницы, получающие низкий TrustRank, считаются потенциальными спамерами.

PageRank в современных поисковых системах

Современный алгоритм ранжирования Google (известный как Hummingbird, 2013 год, и последующие обновления) использует PageRank лишь как один из сотен сигналов. Алгоритм учитывает семантику запроса, контекст пользователя, качество контента (E-E-A-T — Experience, Expertise, Authoritativeness, Trustworthiness), поведенческие факторы, скорость загрузки страницы, мобильную адаптацию и множество других параметров. Тем не менее, базовая идея «голосования ссылками» остаётся важной.

Применение вне поиска

Алгоритм PageRank и его производные нашли применение в различных областях, не связанных с веб-поиском:

• Анализ социальных сетей: PageRank используется для определения влиятельных пользователей (например, в Twitter или VK) на основе структуры подписок и репостов.
• Биоинформатика: для ранжирования генов или белков по их важности в сетях взаимодействий.
• Рекомендательные системы: в системах коллаборативной фильтрации для оценки значимости элементов (фильмов, книг).
• Анализ транспортных сетей: для выявления ключевых узлов в транспортных потоках.
• Наукометрия: для оценки влиятельности научных журналов (алгоритм Eigenfactor является адаптацией PageRank).

Критика и ограничения

Уязвимость к спаму

Изначально PageRank был подвержен манипуляциям: владельцы сайтов могли искусственно наращивать количество входящих ссылок (покупка ссылок, создание «ферм ссылок»). Для борьбы с этим Google ввёл алгоритмы Penguin (2012 год), штрафующие за спамные ссылки, и ручные санкции.

«Эффект Матфея»

PageRank усиливает популярность уже известных страниц: чем больше на страницу ссылаются, тем выше её ранг, и тем выше она ранжируется, привлекая ещё больше ссылок. Это может приводить к монополизации результатов поиска крупными сайтами и затруднять продвижение нового качественного контента.

Не учитывает контекст ссылки

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

Зависимость от структуры графа

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

Источники

• Brin S., Page L. The Anatomy of a Large-Scale Hypertextual Web Search Engine // Computer Networks and ISDN Systems. — 1998. — Vol. 30, No. 1–7. — P. 107–117.
• Langville A. N., Meyer C. D. Google’s PageRank and Beyond: The Science of Search Engine Rankings. — Princeton University Press, 2006. — 224 p.
• Page L., Brin S., Motwani R., Winograd T. The PageRank Citation Ranking: Bringing Order to the Web. — Stanford Digital Library Technologies Project, 1999. — Technical Report 1999-66.
• Gyöngyi Z., Garcia-Molina H., Pedersen J. Combating Web Spam with TrustRank // Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). — 2004. — P. 576–587.
• Haveliwala T. H. Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search // IEEE Transactions on Knowledge and Data Engineering. — 2003. — Vol. 15, No. 4. — P. 784–796.