PageRank

Материал из MachineLearning.

Статья написана с использованием LLM GPT-5.5 Thinking и проверена участником Vladimir Garanin

PageRank — алгоритм ранжирования вершин ориентированного графа, предложенный Ларри Пейджем, Сергеем Брином, Радживом Мотвани и Терри Виноградом для оценки важности веб-страниц по структуре гиперссылок^[1]. Алгоритм стал одной из ключевых идей ранней поисковой системы Google^[1].

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

Идея случайного пользователя

Одна из популярных интерпретаций PageRank — модель случайного пользователя (англ. random surfer). Предполагается, что пользователь находится на некоторой странице и случайно переходит по одной из ссылок на ней. Иногда он прекращает следовать ссылкам и переходит на произвольную страницу.

Если такой процесс повторять очень долго, то PageRank страницы можно понимать как предельную вероятность того, что случайный пользователь окажется на этой странице.

Эта интерпретация важна потому, что она превращает задачу ранжирования страниц в задачу о стационарном распределении цепи Маркова.

Графовая постановка

Пусть задан ориентированный граф из $N$ вершин. В задаче веб-поиска вершины соответствуют веб-страницам, а ориентированное ребро из вершины $j$ в вершину $i$ означает, что страница $j$ содержит ссылку на страницу $i$ .

Обозначим через $B_i$ множество страниц, которые ссылаются на страницу $i$ . Пусть $L(j)$ — число исходящих ссылок со страницы $j$ . Тогда базовая идея PageRank записывается так:

$PR(i) = \sum_{j \in B_i} {PR(j) \over L(j)}.$

Каждая страница распределяет свой вес поровну между страницами, на которые она ссылается. Если на страницу ссылается много важных страниц, её ранг растёт.

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

Демпфирующий коэффициент

В стандартной версии PageRank вводится коэффициент демпфирования $d$ , обычно выбираемый около $0.85$ . На каждом шаге случайный пользователь:

с вероятностью $d$ переходит по одной из ссылок текущей страницы;
с вероятностью $1-d$ переходит на случайную страницу.

Итоговая формула имеет вид:

$PR(i) = {1-d \over N} + d \sum_{j \in B_i} {PR(j) \over L(j)}.$

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

Матричная форма

PageRank удобно записывать в матричной форме. Пусть $r$ — вектор рангов страниц, а $M$ — матрица переходов по ссылкам. Элемент $M_{ij}$ равен вероятности перехода со страницы $j$ на страницу $i$ .

Если страница $j$ ссылается на страницу $i$ , то

$M_{ij} = {1 \over L(j)}.$

Если такой ссылки нет, то $M_{ij}=0$ . Тогда PageRank можно записать как

$r = dMr + (1-d)v,$

где $v$ — вектор телепортации. В простейшем случае $v$ равномерный:

$v_i = {1 \over N}.$

Эта запись показывает, что PageRank является стационарным распределением модифицированного случайного блуждания по графу.

Тупиковые вершины

Тупиковой называется страница, у которой нет исходящих ссылок. Если случайный пользователь попадает на такую страницу, обычное правило перехода по ссылкам перестаёт работать.

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

Это техническое исправление существенно для больших графов: без него масса вероятности могла бы постепенно «утекать» в тупиковые вершины.

Вычисление PageRank

На практике PageRank обычно вычисляется методом простых итераций. Начинают с некоторого начального распределения рангов, например равномерного:

$r_i^{(0)} = {1 \over N}.$

Затем многократно применяют обновление:

$r^{(t+1)} = dMr^{(t)} + (1-d)v.$

Итерации продолжаются, пока изменение вектора рангов не станет достаточно малым:

$||r^{(t+1)} - r^{(t)}|| < \varepsilon.$

Для веб-графов матрица $M$ чрезвычайно разрежена: каждая страница ссылается только на небольшую часть всех страниц. Поэтому при реализации не нужно хранить полную матрицу размера $N \times N$ . Достаточно хранить списки ссылок и выполнять умножение на разреженную матрицу.

Малый пример

Рассмотрим три страницы $A$ , $B$ и $C$ . Пусть страница $A$ ссылается на $B$ и $C$ , страница $B$ ссылается на $C$ , а страница $C$ ссылается на $A$ .

Тогда страница $C$ получает вклад и от $A$ , и от $B$ . Но вклад от $A$ делится между двумя исходящими ссылками, а вклад от $B$ целиком передаётся странице $C$ . Поэтому важность входящей ссылки зависит не только от ранга ссылающейся страницы, но и от числа её исходящих ссылок.

Такое поведение отличает PageRank от простого подсчёта входящих ссылок.

Связь с собственными векторами

Без учёта телепортации PageRank можно рассматривать как задачу нахождения собственного вектора матрицы переходов:

$r = Mr.$

С демпфированием фактически рассматривается матрица переходов случайного блуждания с телепортацией. Вектор PageRank соответствует стационарному распределению этого процесса.

С точки зрения линейной алгебры метод простых итераций близок к степенному методу нахождения главного собственного вектора. Именно поэтому PageRank хорошо согласуется с большими разреженными графами: не требуется явно решать полную систему линейных уравнений.

Персонализированный PageRank

В обычном PageRank вектор телепортации $v$ часто считается равномерным. Но его можно выбрать иначе. Если вероятность телепортации сосредоточить на некотором множестве страниц, получится персонализированный PageRank.

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

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

Тематический PageRank

Тематический PageRank (англ. topic-sensitive PageRank) строит несколько векторов рангов для разных тематических областей^[1]. Вместо одного универсального ранжирования можно заранее вычислить ранги для разных тем, а затем комбинировать их в зависимости от запроса пользователя.

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

Применения

Хотя PageRank возник как алгоритм ранжирования веб-страниц, его идея применяется значительно шире:

Информационный поиск — ранжирование документов и веб-страниц;
Анализ веба — оценка важности сайтов и страниц;
анализ социальных сетей — поиск влиятельных участников;
библиометрия — оценка важности научных публикаций и журналов;
биоинформатика — анализ сетей взаимодействия белков и генов;
рекомендательные системы — ранжирование объектов в графах пользователей и товаров;
графовое машинное обучение — построение признаков вершин графа.

Во всех этих случаях PageRank используется как способ превратить структуру ссылок или связей в численную меру важности вершины.

Сравнение с HITS

Алгоритм PageRank часто сравнивают с алгоритмом HITS, предложенным Джоном Клейнбергом^[1]. HITS различает два типа важности: авторитетность и хабовость. Авторитетная страница — та, на которую ссылаются хорошие хабы; хороший хаб — тот, который ссылается на хорошие авторитеты.

PageRank, напротив, задаёт одну численную меру важности страницы и обычно вычисляется глобально для всего графа. HITS чаще рассматривается как алгоритм, зависящий от конкретного запроса или выбранного подграфа.

Ограничения

PageRank оценивает важность вершины только по структуре ссылок. Он не понимает содержание страницы и не проверяет качество текста напрямую. Поэтому высокий PageRank не обязательно означает, что страница полезна по конкретному запросу.

Кроме того, алгоритм чувствителен к манипуляциям со ссылками. В веб-поиске это привело к развитию ссылочного спама: искусственного создания сетей страниц, повышающих ранг друг друга.

Ещё одно ограничение связано с устареванием графа. Если ссылки давно не обновлялись, PageRank может отражать прошлую структуру сети, а не текущую полезность страниц.

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

См. также

Литература

Page, L., Brin, S., Motwani, R., Winograd, T. The PageRank Citation Ranking: Bringing Order to the Web. Stanford InfoLab Technical Report, 1999.
Brin, S., Page, L. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 1998, Vol. 30, No. 1–7, pp. 107–117.
Langville, A. N., Meyer, C. D. Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 2006.
Haveliwala, T. H. Topic-Sensitive PageRank. Proceedings of the 11th International World Wide Web Conference, 2002.
Kleinberg, J. M. Authoritative Sources in a Hyperlinked Environment. Journal of the ACM, 1999, Vol. 46, No. 5, pp. 604–632.

Источник — «http://83.149.227.45/wiki/index.php?title=PageRank»

Категории: Информационный поиск | Анализ веба | Ранжирование | Графовые алгоритмы | Энциклопедия анализа данных