Перейти к основному содержимому

PageRank — ранжирование на графе

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ
Разработчику Аналитику

Задача​

Интернет — огромный направленный граф: страницы — вершины, гиперссылки — рёбра. Как автоматически оценить, какие страницы важнее, если "важность" должна учитывать не только число ссылок на страницу, но и авторитет тех, кто ссылается?

PageRank (Ларри Пейдж, Сергей Брин, конец 1990-х) стал основой ранжирования в раннем Google. Идея проста для объяснения и опирается на линейную алгебру в инженерном, а не академическом, виде.

Модель "блуждающего пользователя"​

Play ITЗагрузка интерактивного демо…

Представьте пользователя, который:

  1. Случайно открывает любую страницу (или переходит по случайной ссылке с текущей).
  2. С вероятностью β (например, 0,85) переходит по одной из исходящих ссылок на равных правах.
  3. С вероятностью 1 − β "телепортируется" на случайную страницу (иначе застрянет на странице без исходящих ссылок).

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

СитуацияНазвание
Страница только с входящими ссылкамиВисячий узел (dangling)
Нет исходящих ссылокНужна телепортация или нормализация

Матрица переходов (интуиция)​

Строят матрицу гиперссылок H — строка i — с каких страниц можно перейти на страницу i, с весами, обратно пропорциональными числу исходящих ссылок у донора.

Добавляют "случайный прыжок" ко всем страницам — получают матрицу Google G. Вектор рейтингов r (сумма компонент = 1) удовлетворяет:

r = G × r

То есть r — стационарное распределение цепи Маркова: после многих шагов блуждания доли времени на страницах стабилизируются.

В линейной алгебре такой вектор связан с собственным вектором матрицы с собственным значением 1. На практике его не вычисляют формулами — используют итерацию.

Степенной метод​

Степенной метод — многократно умножать начальный вектор на G, пока значения не перестанут заметно меняться:

АЛГОРИТМ PAGERANK_ИТЕРАЦИЯ(G, β, ε)
  n := число страниц
  r[0..n−1] := 1/n                    // равномерный старт
  повторять
    r_новый := β · (G × r) + (1−β)/n · 1   // 1 — вектор из единиц
    если max |r_новый − r| < ε
      вернуть r_новый
    r := r_новый
  до бесконечности
КОНЕЦ

Число итераций обычно логарифмично по точности, а не линейно по размеру веба — поэтому алгоритм масштабируется на миллиарды страниц (с распределёнными вычислениями).

Почему это алгоритм, а не "магия"​

ПринципВ PageRank
Модель задачиВеб как граф
Подходящий инструментИтерация, а не полный перебор
ЭффективностьПолиномиальное время на разреженной матрице
ОграниченияНужна связность / телепортация; рейтинг — лишь один сигнал в поиске

Современный поиск учитывает сотни факторов; PageRank остаётся классическим примером связи структуры данных (граф) и ранжирования.

Где ещё встречается идея​

  • Рекомендации и соцсети — распространение влияния по связям.
  • Анализ цитирований — "важность" статей по ссылкам.
  • ML — сходство с обновлением весов в итеративных методах (подробнее — машинное обучение, нейросети).
Глубокое обучение — другой раздел

Нейросети и глубокое обучение разобраны в разделе ИИ — машинное обучение, нейросети. PageRank — пример классического алгоритма на графе без обучения по градиенту.

Связанные материалы​

Содержание