PageRank как марковская цепь

В конце 1990-х вопрос «какая страница важнее?» решил алгоритм PageRank. Его идея гениально проста: представьте человека, который бесконечно бродит по ссылкам наугад. Страницы, где он проводит больше всего времени, и есть самые важные. А это — обычная марковская цепь.

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

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

Веб как граф ссылок

Представим интернет как граф: страницы — вершины, ссылки — направленные рёбра. Зададим маленький веб из четырёх страниц: links[p] — список страниц, на которые ссылается p.

  0 --> 1      links = {0: [1, 2],
  0 --> 2               1: [2],
  1 --> 2               2: [0],
  2 --> 0               3: [2]}
  3 --> 2

Страница 0 ссылается на 1 и 2; страница 1 — на 2; страница 2 — обратно на 0; страница 3 — на 2. Обратите внимание: на страницу 2 ведут целых три ссылки (от 0, 1 и 3), а на страницу 3 не ссылается никто.

Случайный сёрфер

Сёрфер стоит на какой-то странице и решает, куда пойти. С вероятностью d он переходит по случайной исходящей ссылке текущей страницы. С вероятностью (1 - d) он телепортируется на случайную страницу всего веба. Это и есть наша марковская цепь: следующая страница зависит только от текущей.

Коэффициент d называют коэффициентом затухания (damping factor), классическое значение — 0.85. Зачем телепортация? Чтобы сёрфер не застрял. Без неё он мог бы попасть в «ловушку» — группу страниц, ссылающихся только друг на друга, — и провести там вечность. Телепортация гарантирует, что из любой точки можно выбраться, делая цепь эргодической, а значит, имеющей единственное стационарное распределение.

Итеративный PageRank

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

links = {0: [1, 2], 1: [2], 2: [0], 3: [2]}
n = 4
d = 0.85
rank = [1 / n] * n
for _ in range(40):
    new = [(1 - d) / n] * n
    for p in range(n):
        outs = links[p]
        if outs:
            share = d * rank[p] / len(outs)
            for q in outs:
                new[q] += share
        else:
            for q in range(n):
                new[q] += d * rank[p] / n
    rank = new
print("PageRank:", [round(r, 4) for r in rank])
print("Сумма:", round(sum(rank), 4))

Вывод:

PageRank: [0.3725, 0.1958, 0.3941, 0.0375]
Сумма: 1.0

Результат говорит сам за себя. Страница 2 получила наибольший ранг (0.3941): на неё ссылаются целых три страницы, в том числе важная страница 0. Страница 3 — наименьший (0.0375): на неё не ссылается никто, она держится лишь на телепортации. Сумма всех рангов равна 1 — это всё то же стационарное распределение, только теперь оно означает «доля важности».

Как работает под капотом

Разберём механику строки за строкой.

Базовая доля от телепортации. Строка new = [(1 - d) / n] * n заранее раздаёт каждой странице её долю от случайных прыжков: с вероятностью (1 - d) = 0.15 сёрфер телепортируется равномерно на любую из n страниц. Это «пол», ниже которого ранг не опустится, — он и спасает страницу 3 от нулевого ранга.

Раздача ранга по ссылкам. Если у страницы p есть исходящие ссылки, она отдаёт долю своего ранга d * rank[p] / len(outs) каждой странице, на которую ссылается. Делёж поровну отражает идею «сёрфер выбирает любую ссылку с равной вероятностью».

Висячие узлы. Ветка else обрабатывает страницы без исходящих ссылок (так называемые dangling nodes). Сёрфер на такой странице обязан телепортироваться, поэтому её ранг распределяется поровну по всем n страницам. В нашем наборе таких страниц нет, но код корректно их учитывает.

Связь с прошлым уроком. По сути мы снова умножаем вектор (ранги) на матрицу переходов случайного сёрфера и итерируем до сходимости. Просто матрица здесь задана неявно — через словарь ссылок и формулу затухания, а не таблицей. PageRank — это стационарное распределение марковской цепи, и точка.

Частые ошибки

Забыть про висячие узлы. Страница без исходящих ссылок «поглощает» вероятность: без специальной обработки ранги перестают суммироваться в 1. Ветка else обязательна.
Убрать телепортацию (d = 1). Тогда сёрфер может застрять в замкнутой группе страниц, цепь перестаёт быть эргодической, а стационарное распределение — единственным.
Раздавать весь ранг, а не его долю. По ссылкам уходит только d * rank[p]; оставшаяся часть (1 - d) идёт через телепортацию. Если раздать 100%, баланс нарушится.
Не делить на число ссылок. Ранг раздаётся поровну между исходящими ссылками, то есть делится на len(outs). Иначе страница с многими ссылками раздаёт слишком много.
Слишком мало итераций. Рангам нужно время на сходимость. На большом вебе требуется больше шагов; критерий — когда изменения между итерациями становятся пренебрежимо малы.

Итоги

PageRank моделирует «случайного сёрфера», бесконечно бродящего по ссылкам; важность страницы — доля времени, проведённого на ней.
Это в точности стационарное распределение марковской цепи на графе ссылок — мост между теорией прошлого урока и реальным алгоритмом.
Коэффициент затухания d (обычно 0.85): с вероятностью d сёрфер идёт по ссылке, с вероятностью (1 - d) телепортируется на случайную страницу.
Телепортация делает цепь эргодической: сёрфер не застревает в ловушках, а стационарное распределение единственно.
Страница тем важнее, чем больше на неё качественных ссылок; страница без входящих ссылок (как наша 3) получает лишь базовую долю и ранг около нуля.