Урок 65. Случайные блуждания и PageRank

Поисковая система видит не «важные страницы», а огромный ориентированный граф. PageRank превращает структуру ссылок в вероятностный эксперимент: где окажется читатель, если очень долго переходить по ссылкам и иногда начинать путь заново?

Голоса, которые имеют разный вес

Пусть каждая веб-страница является вершиной, а гиперссылка — ориентированным ребром. Уже здесь возникает отличие от школьного голосования. Страница $A$ , на которую ссылаются сто никому не известных каталогов, не обязательно важнее страницы $B$ , на которую ведёт одна ссылка с главной страницы университета. Голос сам имеет вес, а этот вес ещё только предстоит найти.

Если из вершины $i$ выходит $d_i$ ссылок, простейший случайный читатель выбирает каждую с вероятностью $1/d_i$ . Переходы задаёт стохастическая матрица

P_{ij}= \begin{cases} 1/d_i,&\text{если }i\to j,\\ 0,&\text{иначе}. \end{cases}

Вектор-строка $p_t$ хранит вероятности положения после $t$ кликов, поэтому

p_{t+1}=p_tP.

Эта формула связывает тему с цепями Маркова, а способ многократно умножать вектор на матрицу — со степенным методом для собственных векторов. Никаких меток «хорошая страница» алгоритм не получает. Ранг рождается из геометрии графа и правила движения.

Ориентированный граф из шести страниц, его матрица переходов и распределение потока после одного шага — Рис. 65.1. Один граф, три разных представления
Слева показаны шесть страниц и направления ссылок; толщина стрелки равна вероятности перехода $P_{ij}$ . В центре та же система записана разреженной матрицей, справа поток $p_0\to p_1$ . Три панели переводят одну модель с языка графов на язык матриц, а затем — на язык вероятностного движения.

Неподвижное распределение

Если после долгого движения распределение перестаёт заметно меняться, его предел $\pi$ удовлетворяет

\pi=\pi P,\qquad \pi_i\ge 0,\qquad \sum_i\pi_i=1.

Это левый собственный вектор матрицы $P$ для собственного числа $1$ . Компонента $\pi_i$ имеет ясный частотный смысл: доля времени, которую длинная траектория проводит на странице $i$ . В отличие от отдельной прогулки, стационарное распределение описывает весь поток.

Рассмотрим три страницы: $A$ ссылается на $B$ и $C$ , $B$ — только на $C$ , $C$ — только на $A$ . Баланс потоков даёт

\pi_A=\pi_C,\qquad \pi_B=\tfrac12\pi_A,\qquad \pi_C=\tfrac12\pi_A+\pi_B.

После нормировки получаем $(\pi_A,\pi_B,\pi_C)=(0.4,0.2,0.4)$ . Входящая степень у $C$ равна двум, но один из входов несёт только половину потока. Поэтому просто считать ссылки недостаточно.

Тупики, ловушки и случайный прыжок

Реальный веб-граф неудобнее учебного. У страницы без исходящих ссылок строка матрицы состоит из нулей: вероятность «исчезает». Её заменяют равномерным переходом на любую вершину либо заданным распределением интересов $v$ .

Вторая неприятность тоньше. Группа страниц может ссылаться только друг на друга. Попав внутрь такого замкнутого множества, случайный читатель больше не выйдет. Тогда результат зависит от начальной точки, а несколько стационарных распределений конкурируют.

PageRank смешивает следование ссылкам с телепортацией:

G=\alpha P+(1-\alpha)\mathbf 1v^\top.

С вероятностью $\alpha$ читатель нажимает ссылку, а с вероятностью $1-\alpha$ выбирает новую страницу по $v$ . При положительных компонентах $v$ из любой вершины можно попасть в любую другую за один случайный прыжок.

Потоки вероятности в графе без телепортации и с телепортацией при альфа 0,85 — Рис. 65.2. Ловушка и её разрушение телепортацией
В верхней панели вершины $D,E,F$ образуют ловушку: весь поток со временем остаётся внутри неё. В нижней панели пунктирные рёбра показывают телепортационные переходы; рядом нанесены стационарные вероятности при $\alpha=0{,}85$ . Цвет кодирует величину $\pi_i$ , а не входящую степень.

Вычисление без полной матрицы

Для миллиарда страниц нельзя хранить плотную матрицу $10^9\times10^9$ . Но веб-граф разрежен: каждая страница содержит лишь небольшое число ссылок. На одной итерации достаточно пройти по списку рёбер и распределить массу $p_i$ между соседями. Цена шага близка к $O(|E|)$ , память — $O(|V|+|E|)$ .

Начинают, например, с $p_0=(1/n,\ldots,1/n)$ и останавливаются, когда

\lVert p_{t+1}-p_t\rVert_1 =\sum_i|p_{t+1,i}-p_{t,i}|<\varepsilon.

Малое $1-\alpha$ сильнее уважает ссылки, но медленнее забывает старт и дольше выходит из почти замкнутых сообществ. Большая телепортация ускоряет перемешивание, зато приближает ранг к $v$ . Это тот же конфликт смещения и устойчивости, который встречался при регуляризации моделей.

Остаток $\lVert p_{t+1}-p_t\rVert_1$ контролирует изменение вектора, но не сообщает, насколько полезен итоговый поиск. Алгоритмическая сходимость и качество продукта — разные вопросы.

Персонализация вместо единственного рейтинга

Вектор $v$ не обязан быть равномерным. Если сосредоточить телепортацию на страницах про биологию, получится тематический PageRank. Если $v$ описывает интересы пользователя, ранг станет персональным. Линейность даёт полезный факт: PageRank для смеси

v=\lambda v^{(1)}+(1-\lambda)v^{(2)}

равен той же смеси рангов для $v^{(1)}$ и $v^{(2)}$ . Поэтому можно заранее вычислить несколько тематических векторов и быстро комбинировать их.

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

Лаборатория: поток по живому графу

Сначала установите телепортацию в ноль и включите ловушку. Запустите несколько тысяч кликов из разных начальных вершин. Затем верните $\alpha=0{,}85$ и сравните эмпирические частоты с точным вектором. Наконец, измените $v$ : отдайте половину телепортационной массы одной вершине и проследите, как влияние распространяется дальше по рёбрам.

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

Реальный граф и честная проверка

Набор Web-Google из коллекции SNAP содержит около $875\,000$ вершин и более пяти миллионов рёбер. Это снимок веба 2002 года, а не современный интернет; дата входит в описание данных так же обязательно, как число рёбер. Для школьного эксперимента разумно взять достижимый подграф из $5\,000$ – $20\,000$ вершин.

Сравните входящую степень, PageRank и персонализированный PageRank. Рассчитайте коэффициенты корреляции и отдельно разберите страницы с самым большим расхождением рангов. Проверьте устойчивость верхней двадцатки при $\alpha=0{,}70$ , $0{,}85$ и $0{,}95$ . Если вершины обозначены анонимными номерами, не приписывайте им смысл, которого в данных нет.

Диаграмма рассеяния логарифма входящей степени и PageRank с отмеченными вершинами-исключениями — Рис. 65.3. Ранг не равен числу входящих ссылок
Каждая точка — вершина фрагмента Web-Google. По горизонтали отложен $\log(1+d_i^{in})$ , по вертикали — $\log \pi_i$ . Подписаны вершины, у которых PageRank особенно велик или мал относительно степени: именно они требуют объяснения через качество источников и число исходящих ссылок.

Мини-исследование: когда меняется первая тройка

Возьмите граф из 30–50 страниц одного небольшого тематического сайта и не вычисляйте ранг «один раз». Сначала зафиксируйте исходный граф и получите $\pi^{(0)}$ . Затем проведите три вмешательства: удалите одно ребро с вершины-лидера, добавьте ссылку с вершины среднего ранга на аутсайдера и превратите одну страницу в тупик. Для каждой версии считайте

\Delta_i=\pi_i^{(\mathrm{new})}-\pi_i^{(0)}

и расстояние Кендалла между полными порядками. Такое исследование отделяет два эффекта: абсолютное изменение вероятности и перестановку почти равных мест.

Особенно полезно заранее сделать прогноз стрелками на бумаге. Ссылка от сильной страницы делит её исходящий поток; поэтому новый адресат получает не «весь авторитет», а долю. Удаление ребра перераспределяет массу между оставшимися выходами. Тупик после исправления равномерным прыжком действует иначе, чем телепортация всего процесса. Сверьте эти качественные предсказания с расчётом.

Наконец, повторите вмешательства для персонализированного $v$ . Если рейтинг резко меняется от одного ребра, его нельзя подавать пользователю как устойчивую объективную шкалу. Здесь PageRank встречается с анализом чувствительности модели: вместе с ответом исследуйте, какие малые изменения данных способны его перевернуть.

Что унести с собой

PageRank — не магическая мера истины, а стационарный поток в выбранном графе. Телепортация одновременно чинит математику, ускоряет вычисление и вводит prior $v$ . Разреженный степенной метод делает задачу масштабируемой. А интерпретация результата требует знать, как собран граф, что означает ребро и для кого определена релевантность.

Задачи

3баллов

В ориентированном графе $A$ ссылается на $B$ и $C$ , $B$ ссылается только на $C$ , а $C$ только на $A$ ; переход по исходящим рёбрам равновероятен. В порядке $(A,B,C)$ составьте строко-стохастическую матрицу $P$ и вручную вычислите $p_{k+1}=P^\mathsf Tp_k$ для $p_0=(1,0,0)^\mathsf T$ и $k=0,1,2,3$ . Случайности и единиц измерения здесь нет. Ответ принимается, если все четыре вектора записаны точными дробями и для каждого явно проверено $\sum_i p_{k,i}=1$ .

5баллов

Граф состоит ровно из рёбер $A\to B$ , $B\to A$ , $C\to A$ , $D\to C$ . В порядке $(A,B,C,D)$ постройте строко-стохастическую матрицу $P$ ; если обнаружится вершина без исходящих рёбер, замените её строку на $v^\mathsf T$ , где $v=(1/4,1/4,1/4,1/4)^\mathsf T$ . Итерируйте $p_{k+1}=0{,}8P^\mathsf Tp_k+0{,}2v$ из точно заданного $p_0=(1/4,1/4,1/4,1/4)^\mathsf T$ . Остановитесь на первом $k$ , для которого $\lVert p_{k+1}-p_k\rVert_1<10^{-8}$ . Выведите $p_{k+1}$ , номер итерации, последнюю норму разности и невязку $\lVert p_{k+1}-(0{,}8P^\mathsf Tp_{k+1}+0{,}2v)\rVert_1$ ; компоненты должны быть верны с абсолютной ошибкой не более $10^{-4}$ . Случайности нет.

6баллов

Используйте снимок SNAP Wiki-Vote до января 2008 года: файл https://snap.stanford.edu/data/wiki-Vote.txt.gz с SHA-256 7d3e53626e14b8b09fb3b396bece9d481ad606bd64ceab066349ff57d4ada7fc (7 115 вершин, 103 689 рёбер). Отсортируйте все встреченные идентификаторы, возьмите первые 2 000 и оставьте только рёбра с обоими концами в этом наборе. Пусть $P$ строко-стохастична; каждую висячую строку замените равномерным $v^\mathsf T$ , где $v_i=1/2000$ . Для каждого $\alpha\in\{0{,}65;0{,}85;0{,}95\}$ начните с $p_0=v$ и считайте $p_{k+1}=\alpha P^\mathsf Tp_k+(1-\alpha)v$ до первого $\lVert p_{k+1}-p_k\rVert_1<10^{-8}$ . Случайности нет. Для проверки нужны число итераций, сама последняя $L_1$ -невязка, десять пар (id, PageRank) с разрешением ничьей по меньшему id и три коэффициента Жаккара между десятками.

7баллов

Постройте ориентированную сеть из 8–12 пронумерованных вершин, в которой вершина с максимальной входящей степенью не входит в первую тройку PageRank. Перечислите все рёбра и используйте $p_{k+1}=0{,}85P^\mathsf Tp_k+0{,}15v$ : висячие строки $P$ заменяются на $v^\mathsf T$ , базовый телепортационный вектор равномерен, $p_0=v$ , остановка происходит при $\lVert p_{k+1}-p_k\rVert_1<10^{-10}$ . Затем перечислите все компоненты нового персонализированного $v$ с $v_i\ge0$ , $\sum_i v_i=1$ и $\max_i v_i\le0{,}4$ , снова положите $p_0=v$ и поднимите выбранную вершину в первую двойку. Случайности нет; зачёт требует таблицу степеней и обоих PageRank, последнюю $L_1$ -невязку и объяснение через входящий поток.