Skip to content
Назад к результатам поиска

Взвешенный PageRank

Автор метода
Xing, W. & Ghorbani, A.
Год
2004
Тип
Centrality measure / ranking algorithm
Семейство
Network science

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

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

Интуиция метода

Классический PageRank рассматривает каждую гиперссылку или связь идентично: узел получает одинаковый престиж как от слабой, так и от сильной связи. Взвешенный PageRank корректирует это, масштабируя каждый «голос» относительным весом ребра. Узел, который получает много «тяжелых» входящих связей от уже важных узлов, поднимается выше в рейтинге, в то время как узел с многочисленными, но слабыми связями остается скромным. Это отражает то, как влияние фактически накапливается в большинстве реальных сетей, где частота взаимодействия или объем транзакций сигнализируют об истинной важности.

История

PageRank был представлен Брином и Пейджем в 1998 году как основа Google Search, рассматривая все гиперссылки как равные «голоса». Взвешенный PageRank был формализован Сингом и Горбани в 2004 году, расширяя алгоритм для распределения ранга пропорционально весам ребер, опираясь на доли входящего и исходящего веса. С тех пор он применяется в анализе цитирования, биоинформатике, анализе социальных сетей и рекомендательных системах везде, где сила связи является значимым показателем влияния.

Когда применять

Используйте взвешенный PageRank, когда ваша сеть имеет значимые веса ребер и вам нужен глобальный, учитывающий потоки рейтинг важности узлов. Он идеально подходит для сетей цитирования с количеством совместных цитирований, веб-графов с объемами трафика, биологических сетей взаимодействий с уровнями экспрессии, социальных сетей с частотами взаимодействий и сетей финансовых транзакций. Отдавайте предпочтение взвешенному PageRank перед бинарным PageRank всякий раз, когда игнорирование силы ребра может исказить поток влияния. Избегайте его, когда веса ребер ненадежны или произвольно назначены, когда сеть очень разрежена и веса в основном бинарны (достаточно обычного PageRank), или когда вам нужна чисто локальная мера центральности, такая как взвешенная степень. Он не подходит для ненаправленных сетей, где направление потока концептуально бессмысленно.

Ограничения и замечания

  • Требует, чтобы веса ребер были значимыми и надежно измеренными; зашумленные или произвольные веса ухудшают качество ранжирования.
  • Коэффициент затухания (d) является свободным параметром; обычное значение 0.85 может быть неоптимальным для не-веб-сетей.
  • Чувствителен к выбранной схеме нормализации весов; результаты могут отличаться, если входящие и исходящие веса комбинируются по-разному.
  • Не различает разные типы ребер; модель с одним весом может нивелировать важные структурные различия.
  • Сходимость может быть медленной на очень больших, плотных сетях без эффективных реализаций разреженных матриц.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Непосредственно включает силу ребра в распространение важности, давая более реалистичные рейтинги, чем бинарный PageRank в взвешенных сетях.
  • Захватывает глобальный, общесетевой престиж, а не только локальную связность.
  • Сохраняет механизм телепортации PageRank, делая его устойчивым к висячим узлам и несвязным компонентам при коррекции.
  • Масштабируется до больших сетей за счет эффективных итерационных вычислений; операции с разреженными матрицами обеспечивают управляемое использование памяти.
  • Легко интерпретируется: высокая оценка означает, что узел получает сильную, взвешенную поддержку от других высокооцененных узлов.

Применение

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

Как это работает

Как это работает

1

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

2

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

Формула
W_{in}(v,u) = \frac{w(v,u)}{\sum_{k \in In(u)} w(k,u)}, \quad W_{out}(v,u) = \frac{w(v,u)}{\sum_{k \in Out(v)} w(v,k)}
3

Применяйте формулу взвешенного PageRank итеративно: ранг каждого узла равен базовому члену телепортации (1 минус коэффициент затухания d, обычно 0.85) плюс d, умноженное на сумму по всем входящим соседям их рангов, масштабированных двумя весовыми коэффициентами. Это распределяет ранг пропорционально силе ребра, а не равномерно.

Формула
WPR(u) = (1-d) + d \sum_{v \in In(u)} WPR(v) \cdot W_{in}(v,u) \cdot W_{out}(v,u)
4

Повторяйте обновление ранга до тех пор, пока изменение оценки каждого узла не станет меньше небольшого допуска (обычно 1e-6). Сходимость гарантирована для сильно связных графов; для графов с висячими узлами или изолированными компонентами примените стандартную коррекцию для висячих узлов перед итерацией.

5

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

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

  • Использование необработанных, ненормализованных весов ребер без проверки их масштаба — смешивание значений в десятках с миллионами искажает распространение ранга.
  • Забывание обрабатывать висячие узлы (узлы без исходящих ребер), которые могут истощать ранг из всей сети, если не скорректированы.
  • Предположение, что коэффициент затухания по умолчанию 0.85 универсально подходит; в сетях цитирования или биологических сетях другое значение может лучше отражать предметную область.
  • Интерпретация оценок взвешенного PageRank как абсолютных вероятностей, а не относительных рангов — только их порядок стабилен в разных запусках.
  • Сравнение оценок взвешенного PageRank между сетями разного размера без нормализации.

Часто задаваемые вопросы

Чем взвешенный PageRank отличается от стандартного PageRank?

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

Какой коэффициент затухания мне следует использовать?

Обычное значение составляет 0.85, полученное из предположений веб-графов о случайном серфинге. Для социальных, биологических или цитатных сетей в литературе исследуются значения от 0.5 до 0.9. Рекомендуется анализ чувствительности в диапазоне значений затухания.

Можно ли применять взвешенный PageRank к ненаправленным сетям?

Да, представляя каждое ненаправленное ребро как пару направленных ребер с одинаковым весом. Затем алгоритм генерирует симметричные коэффициенты входящего и исходящего веса, что упрощается до формулы, которая по-прежнему учитывает силу ребра.

Как обрабатывать ребра с нулевым весом?

Ребра с нулевым весом ничего не вносят в распространение ранга, поэтому их можно удалить перед анализом. Если нулевые веса структурно значимы (отсутствие против отсутствующих данных), четко задокументируйте различие перед их удалением.

Лучше ли взвешенный PageRank, чем центральность по взвешенной степени?

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

Похожие методы

Источники

  1. Xing, W., & Ghorbani, A. (2004). Weighted PageRank algorithm. Proceedings of the Second Annual Conference on Communication Networks and Services Research (CNSR '04), pp. 305–314. IEEE.

    Открыть ссылку DOI
    Скопировано.
  2. PageRank. Wikipedia.

    Открыть ссылку на публикацию
    Скопировано.