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

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику Аналитику

---

Задача

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

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

---

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

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

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 — пример классического алгоритма на графе без обучения по градиенту.

---

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

• Графы, Дейкстра
• Нотация Большое O — оценка итераций
• Алгоритмы — о разделе