Центральность PageRank
- Автор метода
- Page, Brin, Motwani & Winograd
- Год
- 1999
- Тип
- Iterative link-based centrality algorithm
- Семейство
- Centrality
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
PageRank — это алгоритм центральности, основанный на ссылках, который присваивает каждому узлу в ориентированном графе показатель важности, измеряя, сколько высококачественных узлов на него ссылаются.
Разработанный Ларри Пейджем, Сергеем Брином, Радживом Мотвани и Терри Виноградом в Стэнфордском университете в 1999 году, он стал математической основой поисковой системы Google и остается одним из самых влиятельных алгоритмов в сетевой науке и информационном поиске.
Интуиция метода
Представьте себе случайного веб-серфера, который кликает по ссылкам наугад, иногда переходя на совершенно случайную страницу вместо того, чтобы следовать по ссылке. Доля времени, которую этот серфер проводит на каждой странице после бесконечного числа кликов, — это PageRank этой страницы. Страница, которую часто посещают — потому что на нее ссылается множество популярных страниц — получает высокий балл. Коэффициент затухания (обычно 0,85) моделирует вероятность продолжения кликов вместо случайного перехода.
История
PageRank был разработан в Стэнфордском университете Ларри Пейджем и Сергеем Брином как основной механизм ранжирования их поискового проекта BackRub, который стал Google в 1998 году. Фундаментальный технический отчет, написанный совместно с Радживом Мотвани и Терри Виноградом, был опубликован в 1999 году. Алгоритм популяризировал использование центральности, основанной на собственных векторах, в крупномасштабных ориентированных сетях и напрямую вдохновил последующие алгоритмы анализа ссылок, включая HITS и TrustRank.
Когда применять
PageRank подходит, когда необходимо ранжировать узлы в ориентированном графе по глобальной структурной важности, особенно когда направление ребер кодирует одобрение или влияние (гиперссылки, цитаты, социальные подписки). Он предполагает, что граф может быть смоделирован как цепь Маркова, и требует связного или сильно связного компонента для чистого схождения. Он менее подходит для неориентированных сетей, где могут быть предпочтительнее центральность HITS или междуузловая центральность, и может быть чувствителен к спаму ссылок или искусственно завышенному числу входящих связей.
Ограничения и замечания
- Требует ориентированного графа; применение к неориентированным сетям требует выбора соглашений
- Скорость сходимости зависит от спектрального зазора матрицы переходов и может быть медленной для плохо связанных графов
- Чувствителен к выбору коэффициента затухания d; разные значения могут существенно изменить ранжирование
- Уязвим для манипуляций с фермами ссылок и искусственно сконструированных входящих ссылок
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Принципиальная вероятностная основа через модель цепи Маркова случайного серфера
- Масштабируется до очень больших графов благодаря произведениям разреженных матриц на векторы и степенной итерации
- Учитывает глобальную топологию графа, вознаграждая узлы, одобренные другими узлами с высоким показателем
- Широко проверен в областях веб-графов, цитирования, биологических и социальных сетей
Применение
- Ранжирование в поисковых системах: упорядочивание результатов поиска по глобальному авторитету веб-страниц
- Анализ академических цитирований: выявление влиятельных статей или журналов в сетях научной литературы
- Измерение влияния в социальных сетях: ранжирование пользователей по престижу их подписчиков
- Анализ биологических сетей: поиск узловых белков или генов в сетях белковых взаимодействий и генной регуляции
- Рекомендательные системы: распространение сигналов предпочтений через двудольные графы пользователей и элементов
Как это работает
Как это работает
Каждый узел в графе начинает с одинаковым показателем PageRank, равным 1/N, где N — общее число узлов. Эта равномерная инициализация гарантирует, что ни один узел не имеет искусственного преимущества и обеспечивает допустимое распределение вероятностей по сети до первой итерации.
Формула
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}Строится стохастическая по столбцам матрица переходов M на основе структуры смежности графа. Каждый элемент M_ij равен 1, деленному на степень исходящих связей узла j, если существует ребро из j в i, и нулю в противном случае. Висячие узлы (без исходящих связей) обычно обрабатываются путем равномерного перераспределения их показателя по всем узлам.
Формула
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}Вектор PageRank итеративно обновляется с использованием формулы случайного серфера. С коэффициентом затухания d (по умолчанию 0,85) каждый узел получает базовую вероятность телепортации (1-d)/N плюс d, умноженное на взвешенную сумму показателей, вносимых всеми узлами, которые на него ссылаются. Этот шаг повторяется до тех пор, пока показатели не стабилизируются.
Формула
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}После каждой итерации L1-норма изменения вектора показателей сравнивается с небольшой погрешностью epsilon (например, 1e-6). Когда изменение падает ниже этого порога, алгоритм сошелся, и текущий вектор показателей возвращается как окончательное распределение PageRank.
Формула
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilonЧастые ошибки
- Игнорирование висячих узлов (узлов без исходящих связей) может нарушить стохастическое свойство матрицы переходов и привести к некорректным показателям
- Использование PageRank на неориентированных графах без преобразования в симметричную модель переходов может дать вводящие в заблуждение оценки центральности
- Установка слишком большой погрешности приводит к преждевременному сходимости; слишком маленькая увеличивает вычисления без значимых изменений показателей
- Интерпретация PageRank как абсолютной метрики важности, а не как относительного ранжирования в контексте конкретного графа
Часто задаваемые вопросы
Что представляет собой коэффициент затухания d и как его следует выбирать?
Коэффициент затухания d (обычно 0,85) — это вероятность того, что случайный серфер следует по ссылке, а не телепортируется на случайный узел. Значения, близкие к 1, делают алгоритм более чувствительным к структуре графа, но медленнее сходящимся и более склонным к ранговым стокам; значения, близкие к 0, приближаются к равномерному ранжированию. Значение 0,85 было эмпирически подтверждено Пейджем и Брином для веб-графа и является стандартным значением по умолчанию.
Чем PageRank отличается от центральности по степени?
Центральность по степени учитывает только прямое количество входящих ссылок на узел, рассматривая все источники как равные. PageRank взвешивает каждую входящую ссылку по показателю ссылающегося узла, поэтому одобрение от узла с высоким рейтингом вносит больший вклад, чем от узла с низким рейтингом. Это рекурсивное определение учитывает глобальную структуру графа, а не только локальную связность.
Можно ли применять PageRank к неориентированным графам?
Да, но с оговорками. Неориентированный граф должен быть преобразован в ориентированное представление путем замены каждого неориентированного ребра двумя ориентированными ребрами. Полученные показатели PageRank затем равны некоторой функции степени узла, сводя алгоритм к взвешенной центральности по степени. Для неориентированных сетей альтернативные меры центральности, такие как центральность по собственным векторам или междуузловая центральность, часто более информативны.
Похожие методы
Источники
Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.
Открыть ссылку на публикациюСкопировано.