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

Взвешенная центральность по посредничеству

Автор метода
Opsahl, T.; Agneessens, F.; Skvoretz, J. (extending Freeman 1977 and Brandes 2001)
Год
2010
Тип
Centrality measure (path-based)
Семейство
Network science

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

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

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

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

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

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

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

История

Центральность по посредничеству была введена Линтоном Фрименом в 1977 году как мера роли узла в соединении других через кратчайшие пути. Ульрик Брандес разработал новаторский эффективный алгоритм в 2001 году, который сократил вычисления с O(n^3) до O(n + m) времени для невзвешенных графов. Взвешенное расширение было систематически формализовано Опсалом, Агнессенсом и Скворецем в 2010 году, которые предложили альфа-параметризованную трансформацию веса в расстояние и проверили ее на эмпирических сетях сотрудничества и авиаперелетов.

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

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

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

  • Точное вычисление составляет O(n^3) по пространству и времени для плотных графов, ограничивая масштабируемость для очень больших сетей.
  • Результаты чувствительны к выбору альфа; разные значения могут существенно изменить ранжирование узлов.
  • Предполагает, что информация или влияние распространяются только по геодезическим (кратчайшим) путям, что может не отражать реальные процессы диффузии.
  • Отрицательные или нулевые веса ребер требуют особого обращения и могут нарушить алгоритмы поиска кратчайших путей.
  • Разъединенные сети дают неопределенную центральность для пар в разных компонентах, требуя анализа на уровне компонентов.

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

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

  • Улавливает брокерство и контроль в сетях, где сила связи определяет предпочтительные пути.
  • Параметр настройки альфа позволяет аналитикам смешивать логику невзвешенных и полностью взвешенных путей, делая меру адаптируемой.
  • Напрямую идентифицирует узлы-бутылочные горлышки, удаление которых приведет к фрагментации или замедлению сети.
  • Совместим с эффективным алгоритмом Брандеса, что делает вычисления осуществимыми для сетей с десятками тысяч узлов.
  • Нормализованные оценки интерпретируемы в сетях разного размера.
  • Хорошо обоснована в рецензируемой общей системе (Opsahl et al. 2010) с широким цитированием.

Применение

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

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

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

1

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

Формула
d_{ij} = w_{ij}^{-\alpha}, \; \alpha \in [0,1]
2

Алгоритм Дейкстры (или линейно-алгебраический вариант Брандеса для эффективности) вычисляет набор кратчайших взвешенных путей между каждой парой исходных и целевых узлов в сети, используя преобразованные расстояния. Этот шаг определяет, какие маршруты являются геодезически оптимальными с учетом конфигурации весов.

3

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

4

Для каждого узла v, необработанная оценка посредничества представляет собой сумму по всем парам источник-цель доли их кратчайших путей, которые проходят через v. Узел, лежащий на всех кратчайших путях между парой, вносит 1.0 в свою оценку для этой пары; узел, пропущенный всеми путями, вносит 0.

Формула
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}
5

Необработанные оценки делятся на максимально возможное значение — которое составляет (n-1)(n-2)/2 для неориентированных сетей — так, чтобы оценки находились в диапазоне [0, 1] и были сопоставимы между сетями разного размера. Для ориентированных сетей знаменатель удваивается до (n-1)(n-2).

Формула
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}

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

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

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

Как выбрать параметр альфа?

Альфа контролирует, насколько вес влияет на выбор пути. При альфа=0 вы получаете классическую невзвешенную центральность по посредничеству; при альфа=1 более сильные связи полностью определяют кратчайшие пути. Распространенной практикой является тестирование альфа=0, 0.5 и 1 и сообщение о чувствительности. Если ранжирование узлов стабильно при разных значениях, любой выбор обоснован; если они существенно различаются, обоснуйте свой выбор теоретически, исходя из того, следует ли отдавать предпочтение сильным связям.

В чем разница между взвешенной и невзвешенной центральностью по посредничеству?

Невзвешенная центральность по посредничеству считает шаги; каждое ребро имеет одинаковую длину. Взвешенная центральность по посредничеству использует веса ребер (преобразованные в расстояния), так что пути преимущественно следуют более сильным или более коротким связям. В сетях, где сила связи имеет существенное значение — например, частота сотрудничества или объем торговли — взвешенная версия дает более точную картину того, какие узлы контролируют фактические потоки.

Подходит ли взвешенная центральность по посредничеству для очень больших сетей?

Точное вычисление становится дорогостоящим при количестве узлов более примерно 100 000. Для очень больших сетей используйте аппроксимирующие алгоритмы, такие как случайная выборка опорных точек (реализована в NetworkX как betweenness_centrality с параметром k) или используйте ускоренные на GPU инструменты, такие как cuGraph. Сообщите, использовали ли вы точное или аппроксимирующее вычисление.

Могу ли я использовать взвешенную центральность по посредничеству, если моя сеть имеет изолированные узлы или несколько компонентов?

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

Как следует сообщать о взвешенной центральности по посредничеству в рукописи?

Сообщите используемое программное обеспечение и его версию (например, NetworkX, igraph), значение альфа, были ли нормализованы оценки, как вы обрабатывали разъединенные компоненты, и сводную статистику (среднее, диапазон) вместе с узлами с наивысшим рангом. Диаграмма рассеяния степени против центральности по посредничеству или визуализация сети с размером узла, пропорциональным оценке, помогают интерпретации.

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

Источники

  1. Opsahl, T., Agneessens, F., & Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks, 32(3), 245–251.

    Открыть ссылку DOI
    Скопировано.
  2. Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.

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