PageRank на пальцах

Важность веб-страницы — это собственный вектор матрицы ссылок: степенной метод находит его, и так рождается ранжирование Google.

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

Это, пожалуй, самое знаменитое применение собственных векторов. Идея: вес страницы определяется не количеством ссылок, а их «качеством» — ссылками с важных страниц. Получается рекурсивное определение, которое элегантно решается степенным методом из прошлого раздела.

Модель случайного сёрфера

Представим пользователя, который кликает по случайным ссылкам. С вероятностью $d$ (обычно $0{,}85$) он переходит по одной из ссылок текущей страницы, а с вероятностью $1 - d$ — перепрыгивает на случайную страницу (это спасает от «тупиков» и зацикливаний). PageRank страницы — это доля времени, которое сёрфер на ней проводит в долгой перспективе. Вектор этих долей — собственный вектор матрицы переходов с собственным значением 1, и его ищут итерациями.

def pagerank(links, d=0.85, iters=50):
    n = len(links)
    out = [sum(row) for row in links]      # сколько ссылок выходит
    rank = [1 / n] * n                     # равный старт
    for _ in range(iters):
        new = [(1 - d) / n] * n
        for i in range(n):
            for j in range(n):
                if links[i][j] and out[i]:
                    new[j] += d * rank[i] / out[i]
        rank = new
    return rank

# 0->1, 0->2, 1->2, 2->0
L = [[0, 1, 1], [0, 0, 1], [1, 0, 0]]
r = pagerank(L)
print("ранги:", [round(x, 4) for x in r])
print("сумма:", round(sum(r), 4))

Вывод:

ранги: [0.3878, 0.2148, 0.3974]
сумма: 1.0

Кто победил

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

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

Каждая итерация распределяет текущий вес каждой страницы поровну между страницами, на которые она ссылается (делим на out[i] — число исходящих ссылок), домножая на коэффициент затухания $d$. Слагаемое $(1 - d)/n$ — это вклад «телепортации» случайного сёрфера, оно же гарантирует, что процесс сходится к единственному решению независимо от старта. По сути pagerank — это степенной метод для матрицы переходов: повторное применение матрицы притягивает вектор к доминирующему собственному направлению с $\lambda = 1$. Для миллиардов страниц матрица разреженная, и именно такой итерационный подход делает задачу вычислимой.

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

Забывать делить на число исходящих ссылок. Страница раздаёт свой вес поровну, а не целиком каждой цели.
Опускать коэффициент затухания $d$. Без телепортации «висячие узлы» и циклы ломают сходимость.
Думать, что PageRank считает просто число входящих ссылок. Он учитывает важность ссылающихся — отсюда рекурсия и собственный вектор.

Итог

PageRank — доминирующий собственный вектор матрицы ссылок (переходов).
Вес страницы зависит от важности ссылающихся на неё страниц — рекурсивно.
Коэффициент затухания $d$ моделирует случайные прыжки и обеспечивает сходимость.
Алгоритм — это степенной метод; ранги суммируются в 1 как вероятности.