PageRank

На этом сайте три учебника: базовый курс программирования, «Царица наук» и каталог алгоритмов, который вы читаете. Вместе это 202 страницы и 1624 ссылки между ними. Какая страница самая важная, если судить только по ссылкам? Ниже каждая страница — кружок, его размер — важность по PageRank, а сам PageRank считается у вас на глазах: шаг за шагом важность перетекает по ссылкам, пока не перестанет меняться. Двигайте ползунок d и смотрите, куда она утекает.

При обычном d = 0,85 первые места занимают главы «Царицы наук»: «Последовательности и индукция», «Простые числа», «Корень из двух и действительные числа». У математики 46,6 % всей важности при 30 % страниц, у курса — 31,7 %, а у каталога — 21,7 %, хотя статей в нём больше всего. Уменьшите d до 0,5 — и вперёд выходят статьи каталога: «Двоичный поиск», «Двоичная куча», «Алгоритм Дейкстры», а доли почти выравниваются. Подвиньте d к единице — и вся важность стекает в «Царицу наук». При d = 0,99 у неё 90 %, при d = 1 — всё.

Причина видна в самих ссылках. Каталог ссылается и на курс, и на «Царицу наук», курс — на «Царицу наук», а она — ни на кого из них. Важность течёт по ссылкам вниз по течению и обратно не возвращается. В терминах графов «Царица наук» — компонента сильной связности, из которой нет выхода, и при d = 1 она забирает всё.

Идея

Представьте читателя, который бесконечно бродит по сайту. На каждой странице он с вероятностью d щёлкает по одной из её ссылок — выбирая случайно, — а с вероятностью 1 − d ему надоедает, и он открывает случайную страницу из всех. Если бродить долго, доля времени, проведённого на каждой странице, перестаёт меняться. Эта доля и есть PageRank страницы. Число d называют коэффициентом затухания, и у него простой смысл: между двумя прыжками читатель проходит в среднем d/(1 − d) ссылок подряд — при d = 0,85 это 5,7 ссылки, при d = 0,5 — одна, при d = 0,99 — 99. Чем больше d, тем дальше видит рейтинг.

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

Формулой: если на страницу p ссылаются страницы q с числом ссылок out(q), а всего страниц N, то

Это система из N линейных уравнений, и решать её можно хоть методом Гаусса. Но для графа из миллиардов страниц Гаусс немыслим, а повторение раздачи — степенной метод — стоит один проход по ссылкам за шаг. На языке линейной алгебры PageRank — собственный вектор матрицы переходов случайного читателя с собственным числом 1, а степенной метод — умножение вектора на эту матрицу снова и снова.

Переключите сцену на «Случайного читателя». Там тот же PageRank считается буквально: читатель ходит по ссылкам, сплошная линия — переход по ссылке, пунктир — прыжок, а размер кружка — доля визитов. Доли сходятся к тем же числам, но медленно: чтобы уменьшить ошибку вдвое, шагов нужно вчетверо больше. Степенной метод за каждый шаг уменьшает ошибку хотя бы в 1/d раз.

Тупики и ловушки

Зачем вообще прыжки? Без них определение ломается в двух местах. Вот шесть страниц: F — тупик, ссылок из неё нет; D и E ссылаются только друг на друга — ловушка, куда можно войти и откуда нельзя выйти.

При d = 1 важность тупика F пропадает на каждом шаге, и через 60 шагов от единицы остаётся 0,633 — всё в ловушке D — E. Если тупик раздаёт свою важность всем поровну, сумма сохраняется, но ловушка всё равно забирает всё, и числа не сходятся: D и E на каждом шаге меняются местами, 0,489 и 0,511. Прыжки с вероятностью 1 − d чинят всё сразу: из любой страницы можно попасть куда угодно, ни тупик, ни ловушка не удерживают важность, и при d = 0,85 числа сходятся к одному ответу, где у ловушки 0,709, а у тупика — 0,061. Тупики в настоящих данных есть всегда: в нашем графе пять статей каталога пока ни на одну написанную статью не ссылаются. Их важность раздают всем поровну, как прыжок.

Почему сходится и к одному ответу

При d = 1 сжатия нет, и всё зависит от устройства графа: ответ может быть не единственным, как с ловушкой, или не сходиться вовсе, как D и E. Точнее оценку d^k сделали Тахер Хавелвала и Сепандар Камвар в 2003 году: второе по модулю собственное число матрицы Google не больше d, а если в графе есть хотя бы две замкнутые части, из которых нельзя выйти, — равно d.

Код

Важности — массив, ссылки — списки соседей. Один шаг: всем по (1 − d)/N, потом каждая страница со ссылками раздаёт d своей важности по ссылкам, а важность тупиков копится и раздаётся всем поровну. Остановка — когда суммарное изменение за шаг меньше 10⁻¹². Суммы — простым циклом, без sum(): так вывод Python и Go совпадает до последнего знака.

При d = 0,5 доли трёх учебников — 34,0, 33,4 и 32,6 %, почти поровну, и лидируют статьи каталога: на «Двоичный поиск», «Двоичную кучу» и «Дейкстру» ссылаются многие соседи, а при частых прыжках важно именно это — у кого больше входящих ссылок поблизости. Чем больше d, тем дальше уходит читатель по цепочкам ссылок и тем важнее, куда эти цепочки в конце концов приводят. При d = 0,95 у «Царицы наук» уже 67 %, при 0,99 — 90 %.

Сколько это стоит

Один шаг — O(V + E): каждая ссылка просматривается один раз. Шагов до точности ε — не больше log(1/ε) / log(1/d). Для ε = 10⁻¹² при d = 0,85 оценка обещает 170 шагов, а нашему графу хватило 106; при d = 0,99 — 2749 шагов по оценке и 268 на деле. Оценка рассчитана на худший граф, наш сходится быстрее, но рост числа шагов при d → 1 виден и здесь: 34, 106, 189, 268. Так что d = 0,85 — компромисс: меньше d — рейтинг почти не учитывает дальние ссылки, больше — дольше считать, а важность всё сильнее стекает в ловушки.

Памяти — сам граф и два массива важностей. Граф веба в 1998 году уже не помещался в память, и в отчёте Пейджа, Брина, Мотвани и Винограда о PageRank, как его пересказывают университетские курсы, на базе из 322 миллионов ссылок хватило примерно 52 шагов. Шаги степенного метода легко делить между машинами: каждая раздаёт важность своей части страниц, — поэтому PageRank — классический пример для систем распределённой обработки графов.

Где работает

• Поиск. С PageRank начинался Google: в 1998 году Брин и Пейдж описали поисковую машину, которая сочетала совпадение слов запроса с важностью страницы по ссылкам. Сегодня это лишь один из многих сигналов ранжирования. Как устроен поиск целиком, с индексом и ранжированием текста, — в главе курса о поисковике.
• Рекомендации. Если прыгать не на любую страницу, а только на «свои», получается персонализированный PageRank: важность глазами одного читателя. Twitter в 2013 году описал сервис «кого читать», где «круг доверия» пользователя строился случайными блужданиями от него самого. Это задача статьи.
• Тексты. TextRank (2004) строит граф из слов или предложений текста, где рёбра — соседство или похожесть, и выбирает ключевые слова и главные предложения по PageRank.
• Наука. Важность журналов по цитированиям, когда ссылка из влиятельного журнала весит больше, считает Eigenfactor — тем же способом.

История

Идея «важен тот, на кого ссылаются важные» старше веба. В 1953 году социолог Лео Кац предложил индекс статуса в социальных сетях, где учитываются все цепочки знакомств, а длинные весят меньше, — это и есть коэффициент затухания, только для цепочек. В 1965 году Чарльз Хаббелл ранжировал людей по важности тех, кто их поддерживает, а в 1976 году Габриэль Пински и Фрэнсис Нарин назвали журнал влиятельным, если его цитируют влиятельные журналы. В 1998 году Сергей Брин и Ларри Пейдж описали PageRank для веба, а Джон Клейнберг в те же годы — алгоритм HITS с двумя оценками у каждой страницы: насколько она авторитетна и насколько хорошо собирает ссылки на авторитетные. Подробнее о самом Google и о фермах ссылок, которыми пытались обмануть PageRank, — в главе курса «Ферма ссылок».

Задача

Читатель отметил любимые страницы — посоветуйте, что читать дальше. Нужен персонализированный PageRank, и один из тестов — граф этого сайта.