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

Центральность по посредничеству

Автор метода
Freeman, L. C.
Год
1977
Тип
Centrality measure
Семейство
Network science

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

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

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

Центральность по посредничеству, формализованная Линтоном К. Фрименом в 1977 году, измеряет, как часто узел лежит на кратчайшем пути, соединяющем каждую другую пару узлов в сети.

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

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

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

История

Линтон Фримен формализовал центральность по посредничеству в своей знаковой статье 1977 года в журнале Sociometry, опираясь на более ранние неформальные использования концепции Бавеласом (1948) в экспериментах по коммуникации. Формулировка Фримена объединила несколько расплывчатых интуиций о важности узлов в единую измеримую меру и стала каноническим определением, используемым в науке о сетях. Алгоритм Ульрика Брандеса 2001 года сократил вычисления с O(V^3) до O(VE), сделав центральность по посредничеству практичной для сетей с тысячами узлов и закрепив ее как стандартный инструмент в программном обеспечении для анализа социальных сетей.

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

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

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

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

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

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

  • Отражает структурное брокерство и роли мостов, которые полностью упускаются центральностью по степени и собственным векторам.
  • Применима к ориентированным, неориентированным, взвешенным и невзвешенным сетям с использованием одной и той же формулы.
  • Нормализованная оценка позволяет осмысленно сравнивать узлы внутри одной сети и между сетями разного размера.
  • Алгоритм Брандеса делает вычисления выполнимыми для сетей с миллионами узлов при реализации в оптимизированных библиотеках, таких как NetworkX или igraph.
  • Хорошо обоснованная теоретическая интерпретация: узлы с высоким посредничеством эмпирически связаны с контролем информации, властью и структурными дырами в организационных и социальных исследованиях.

Применение

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

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

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

1

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

2

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

Формула
\sigma(s,t) = \text{number of shortest paths from } s \text{ to } t
3

Для каждого кандидата узла v (где v не является ни s, ни t) подсчитывается количество тех кратчайших путей из sigma(s, t), которые фактически проходят через v, и обозначается как sigma(s, t | v). Отношение sigma(s, t | v) / sigma(s, t) дает долю трафика по кратчайшим путям между s и t, которая маршрутизируется через v.

Формула
\sigma(s,t|v) = \text{shortest paths from } s \text{ to } t \text{ passing through } v
4

Эти доли суммируются по всем допустимым парам (s, t) для получения необработанной оценки посредничества C_B(v). Узел, удаление которого нарушило бы множество кратчайших путей между парами, накапливает высокую сумму, сигнализируя о структурно критической брокерской позиции.

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

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

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

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

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

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

Чем центральность по посредничеству отличается от центральности по степени?

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

Следует ли использовать нормализованные или необработанные оценки посредничества?

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

Как обрабатывать взвешенные ребра?

Установите веса ребер так, чтобы они представляли расстояние или стоимость, а не сходство. Большинство реализаций (NetworkX, igraph) принимают параметр веса, интерпретируемый как расстояние; если ваши веса представляют силу или сходство, инвертируйте их (например, вес = 1/сходство) перед вычислением посредничества.

Имеет ли центральность по посредничеству смысл для несвязных сетей?

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

Моя сеть содержит миллионы узлов — могу ли я все еще вычислить центральность по посредничеству?

Точное вычисление с помощью алгоритма Брандеса имеет сложность O(VE) и может быть слишком медленным. Используйте рандомизированные аппроксимации (например, выборку k исходных узлов), доступные в NetworkX (betweenness_centrality с параметром k) или библиотеках графов, таких как graph-tool, которые предоставляют доверительные интервалы для аппроксимированных оценок.

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

Источники

  1. Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1), 35–41.

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

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