Центральность посредничества - Betweenness centrality

An неориентированный граф окрашены в зависимости от промежуточной центральности каждой вершины от наименьшей (красный) до наибольшей (синий).

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

Центральность между посредничеством была разработана как общая мера центральности:^[1] он применим к широкому кругу проблем теории сетей, включая проблемы, связанные с социальными сети, биология, транспорт и научное сотрудничество. Хотя более ранние авторы интуитивно описывали центральность как основанную на промежуточности, Фримен (1977) дал первое формальное определение центральности промежуточности.

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

Определение

Центральность промежуточности узла ${ displaystyle v}$ дается выражением:

{ displaystyle g (v) = sum _ {s neq v neq t} { frac { sigma _ {st} (v)} { sigma _ {st}}}}

куда ${ displaystyle sigma _ {st}}$ это общее количество кратчайших путей от узла ${ displaystyle s}$ узел ${ displaystyle t}$ и ${ displaystyle sigma _ {st} (v)}$ это количество путей, которые проходят через ${ displaystyle v}$ .

Обратите внимание, что промежуточная центральность узла масштабируется с количеством пар узлов, как предполагается индексами суммирования. Следовательно, вычисление может быть изменено путем деления на количество пар узлов, не включая ${ displaystyle v}$ , так что ${ displaystyle g in [0,1]}$ . Деление осуществляется ${ Displaystyle (N-1) (N-2)}$ для ориентированных графов и ${ Displaystyle (N-1) (N-2) / 2}$ для неориентированных графов, где ${ displaystyle N}$ - количество узлов в гигантском компоненте. Обратите внимание, что это масштабируется для максимально возможного значения, когда один узел пересекает каждый кратчайший путь. Часто это не так, и нормализация может выполняться без потери точности.

{ Displaystyle { mbox {нормальный}} (г (v)) = { гидроразрыва {г (v) - мин (г)} { макс (г) - мин (г)}}}

что приводит к:

{ Displaystyle макс (нормальный) = 1}

{ Displaystyle мин (нормальный) = 0}

Обратите внимание, что это всегда будет масштабирование от меньшего диапазона к большему, поэтому точность не будет потеряна.

Взвешенные сети

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

{ displaystyle s_ {i} = sum _ {j = 1} ^ {N} a_ {ij} w_ {ij}}

С ${ displaystyle a_ {ij}}$ и ${ displaystyle w_ {ij}}$ быть матрицами смежности и веса между узлами ${ displaystyle i}$ и ${ displaystyle j}$ Аналогично степенному закону распределения степени в безмасштабных сетях, сила данного узла также подчиняется степенному закону распределения.

{ Displaystyle с (к) приблизительно к ^ { бета}}

Исследование среднего значения ${ displaystyle s (b)}$ силы для вершин с промежуточностью ${ displaystyle b}$ показывает, что функциональное поведение можно аппроксимировать масштабной формой ^[2]

{ Displaystyle с (Ь) приблизительно Ь ^ { альфа}}

Центральность перколяции

Централизация перколяции - это версия взвешенной центральности промежуточности, но она учитывает «состояние» исходного и целевого узлов каждого кратчайшего пути при вычислении этого веса. Распространение «заражения» происходит в сложных сетях по ряду сценариев. Например, вирусная или бактериальная инфекция может распространяться через социальные сети людей, известные как контактные сети. Распространение болезни также можно рассматривать на более высоком уровне абстракции, рассматривая сеть городов или населенных пунктов, связанных автомобильным, железнодорожным или воздушным сообщением. Компьютерные вирусы могут распространяться по компьютерным сетям. Слухи или новости о деловых предложениях и сделках также могут распространяться через социальные сети людей. Во всех этих сценариях «инфекция» распространяется по звеньям сложной сети, изменяя «состояния» узлов по мере своего распространения, с возможностью восстановления или иным образом. Например, в эпидемиологическом сценарии люди переходят из «восприимчивого» в «инфицированное» состояние по мере распространения инфекции. Состояния, которые отдельные узлы могут принимать в приведенных выше примерах, могут быть двоичными (например, получена / не получена новость), дискретными (восприимчивые / инфицированные / восстановленные) или даже непрерывными (например, доля инфицированных людей в городе ) по мере распространения заразы. Общей чертой всех этих сценариев является то, что распространение заражения приводит к изменению состояний узлов в сетях. Имея это в виду, была предложена центральность перколяции (PC), которая конкретно измеряет важность узлов с точки зрения помощи перколяции по сети. Эта мера была предложена Piraveenan et al.^[3]

Центральность перколяции определяется для данного узла в данный момент времени как доля «просачиваемых путей», которые проходят через этот узел. «Перколированный путь» - это кратчайший путь между парой узлов, где исходный узел пронизан (например, заражен). Целевой узел может быть перколированным, неперколированным или частично перколированным.

{ displaystyle PC ^ {t} (v) = { frac {1} {N-2}} sum _ {s neq v neq r} { frac { sigma _ {sr} (v)} { sigma _ {sr}}} { frac {{x ^ {t}} _ {s}} {{ sum {[{x ^ {t}} _ {i}}]} - {x ^ { телевидение}}}}

куда ${ displaystyle sigma _ {sr}}$ это общее количество кратчайших путей от узла ${ displaystyle s}$ узел ${ displaystyle r}$ и ${ displaystyle sigma _ {sr} (v)}$ это количество путей, которые проходят через ${ displaystyle v}$ . Состояние перколяции узла ${ displaystyle i}$ вовремя ${ displaystyle t}$ обозначается ${ Displaystyle {х ^ {т}} _ {я}}$ и два особых случая: когда ${ Displaystyle {х ^ {т}} _ {я} = 0}$ что указывает на неперколированное состояние во время ${ displaystyle t}$ тогда как когда ${ Displaystyle {х ^ {т}} _ {я} = 1}$ что указывает на полностью перколированное состояние во время ${ displaystyle t}$ . Значения между ними указывают на частично пропитанные состояния (например, в сети поселков это будет процент инфицированных в этом городе).

Прилагаемые веса к путям перколяции зависят от уровней перколяции, назначенных исходным узлам, исходя из предположения, что чем выше уровень перколяции исходного узла, тем более важны пути, исходящие от этого узла. Узлы, которые лежат на кратчайших путях, исходящих из узлов с высокой степенью перколяции, поэтому потенциально более важны для перколяции. Определение ПК также можно расширить, включив в него веса целевых узлов. Расчет центральности перколяции выполняется в ${ displaystyle O (NM)}$ время с эффективной реализацией, принятой из быстрого алгоритма Брандеса, и если в расчетах необходимо учитывать веса целевых узлов, время наихудшего случая равно ${ displaystyle O (N ^ {3})}$ .

Алгоритмы

Вычисление центральных значений промежуточности и близости всех вершины в графе включает в себя вычисление кратчайших путей между всеми парами вершин на графе, что требует ${ Displaystyle Theta (| V | ^ {3})}$ время с Алгоритм Флойда-Уоршолла, модифицированный, чтобы не только находить один, но и подсчитывать все кратчайшие пути между двумя узлами. На разреженном графе Алгоритм Джонсона или алгоритм Брандеса может быть более эффективным, оба принимают ${ Displaystyle O (| V | ^ {2} log | V | + | V || E |)}$ время. На невзвешенных графиках вычисление промежуточности центральности занимает ${ Displaystyle O (| V || E |)}$ раз по алгоритму Брандеса.^[4]

При вычислении центральностей промежуточности и близости всех вершин в графе предполагается, что графы неориентированы и связаны с учетом петель и кратных ребер. Когда мы конкретно имеем дело с сетевыми графами, часто графы не имеют петель или нескольких ребер для поддержания простых отношений (где ребра представляют собой связи между двумя людьми или вершинами). В этом случае использование алгоритма Брандеса разделит итоговые оценки центральности на 2, чтобы учесть, что каждый кратчайший путь учитывается дважды.^[5]

Другой алгоритм обобщает промежуточность Фримена, вычисленную на геодезических, и промежуточность Ньюмана, вычисленную на всех путях, путем введения гиперпараметра, контролирующего компромисс между разведкой и разработкой. Временная сложность - это количество ребер, умноженное на количество узлов в графе.^[6]

Концепция центральности была распространена и на групповой уровень.^[7] Центральность между группами показывает долю геодезических, соединяющих пары не входящих в группу членов, которые проходят через группу узлов. Алгоритм Брандеса для вычисления промежуточной центральности всех вершин был изменен для вычисления групповой промежуточности центральности одной группы узлов с одинаковым асимптотическим временем выполнения.^[7]

Приложения

Социальные сети

В анализ социальных сетей Центральность промежуточности может иметь разные последствия. С макроскопической точки зрения соединяющие позиции или «структурные дыры» (обозначенные высокой промежуточностью центральности) отражают власть, потому что они позволяют человеку в соединяющей позиции осуществлять контроль (например, решать, делиться ли информацией или нет) над людьми, которых она связывает. между.^[8] Однако с микроскопической точки зрения сетей эго (т. Е. С учетом только связей первой степени) в социальные сети онлайн высокая промежуточная центральность совпадает с назначениями ближайших друзей (т. е. сильных межличностные связи ), потому что он отражает социальный капитал инвестиции в отношения, когда далекие социальные круги (например, семья и университет) сближаются (часто в результате введения эго).^[9]

Связанные понятия

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

Смотрите также

Центральность

Примечания

^ Фримен (1977), п. 39.
^ А. Баррат, М. Бартелеми, Р. Пастор-Саторрас и А. Веспиньяни. Архитектура сложных весовых сетей. PNAS (2004) т. 101 нет. 11
^ Пиравинан, Махендра (2013). "Центральность перколяции: количественная оценка теоретико-графического влияния узлов во время перколяции в сетях". PLOS ONE. 8 (1): e53095. Bibcode:2013PLoSO ... 853095P. Дои:10.1371 / journal.pone.0053095. ЧВК 3551907. PMID 23349699.
^ Брандес (2001), п. 1.
^ Брандес (2001), п. 9.
^ Мантрах (2010).
^ ^а ^б Пузис, Р., Ягил, Д., Елович, Ю., Браха, Д. (2009)Совместная атака на анонимность пользователей Интернета В архиве 2013-12-07 в Wayback Machine, Интернет-исследования 19(1)
^ Берт (2009).
^ Штольц (2021 год).