Как работает алгоритм PageRank на простом примере?

Коллега, для кандидата технических наук по специальности 05.13.17 объяснять «на пальцах» — это преступление. Поэтому давай заглянем под капот PageRank и посмотрим на него так, как его видят Ларри Пейдж и Сергей Брин — через теорию графов, марковские цепи и линейную алгебру.

Давай смоделируем микро-интернет из 4 сайтов: A, B, C и D.

Шаг 1: Карта ссылок (Граф)

Сконструируем интересную топологию:

• Сайт A (Хаб): ссылается на все остальные сайты (B, C, D).
• Сайт B: ссылается на C и D.
• Сайт C (Авторитет): ссылается только на A.
• Сайт D: ссылается только на C.

Правило передачи веса (SEO-база): Если страница имеет \(N\) исходящих ссылок, она передает каждой из них \(1/N\) своего веса.

Шаг 2: Строим матрицы (Матрица Google)

Сначала запишем столбцовую стохастическую матрицу смежности (M). Столбцы — это сайты, откуда идет ссылка, строки — сайты, куда идет ссылка.

Как это читать: Первый столбец — это сайт A. Он передает по 1/3 веса сайтам B, C и D (2, 3 и 4 строки). Столбец C (третий) передает 100% веса сайту A (первая строка).

Но чистая матрица \(M\) имеет проблему: циклы и «висячие узлы» (spider traps), где вес зацикливается. Чтобы алгоритм сошелся, вводится коэффициент затухания (Damping Factor, \(d = 0.85\)). Он означает вероятность того, что случайный серфер кликнет по ссылке, а \(1 - d\) (0.15) — что он закроет вкладку и откроет случайный сайт из закладок.

Так получается Матрица Google (G):

Где \(E\) — матрица из единиц, а \(N = 4\) (количество сайтов). Дробь \(\frac{1-d}{N} = \frac{0.15}{4} = 0.0375\) — это базовая вероятность перехода на любую страницу "из ниоткуда".

Шаг 3: Запускаем алгоритм (Степенной метод)

PageRank — это поиск собственного вектора матрицы \(G\), соответствующего собственному значению \(\lambda = 1\). Мы ищем такой вектор \(V\), при котором \(G \cdot V = V\). Машинно это решается итеративно (Степенным методом): \(V_{k+1} = G \cdot V_k\).

В начале (Итерация 0) вес распределен поровну:

Итерация 1 (\(V_1 = G \cdot V_0\)): Сначала умножаем \(M\) на \(V_0\):

Применяем Damping Factor (\(0.85 \cdot (M \cdot V_0) + 0.0375\)):

Уже на первой итерации видно, что сайт C рванул вверх (0.427), потому что получил ссылки от A, B и D.

Итерация 2 (\(V_2 = G \cdot V_1\)):

Сайт C передал весь свой огромный вес сайту A (0.4005).

Результат: Финальный собственный вектор

Алгоритм крутится десятки раз (обычно около 50-100 итераций), пока разница между \(V_{k}\) и \(V_{k+1}\) не станет меньше \(\epsilon\) (достигается сходимость Марковской цепи).

После сходимости мы получаем Финальный вектор PageRank (Steady State):

Итог ранжирования Google

Смотрим на математику и переводим ее на язык SEO:

1 место: Сайт C (PageRank = 0.348) Почему? У него меньше всего исходящих ссылок (концентрирует вес) и в него летят ссылки почти ото всех (от B, D и A). Это типичная трастовая страница-монополист (как Википедия).

2 место: Сайт A (PageRank = 0.333) У сайта A вообще нет входящих ссылок, кроме одной! Но эта единственная ссылка — сквозная со сверхтрастового Сайта C, который отдает ему 100% своего веса (так как больше никуда не ссылается). SEO-вывод: Одна ссылка с авторитетной страницы, где мало других ссылок, бьет десяток ссылок с помоек.

3 место: Сайт D (PageRank = 0.188) Получает часть веса от A и B.

4 место: Сайт B (PageRank = 0.132) Хотя на B ссылается самый "жирный" хаб A, сайт A ссылается еще на 2 сайта. Вес размывается на 3 части (\(1/3\)). В итоге B получает крохи. SEO-вывод: Если ты покупаешь ссылку на странице, где висит еще 100 ссылок на другие ресурсы, передаваемый вес (\(1/N\)) стремится к нулю.

Вот так линейная алгебра и Марковские цепи стали основой корпорации стоимостью в 2 триллиона долларов, Никита!