Центральность промежуточности

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

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

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

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

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

где — общее количество кратчайших путей от узла до узла , а — количество тех путей, которые проходят через (а не конечная точка). ^[2]${\displaystyle \сигма _{ст}}$${\displaystyle с}$${\displaystyle т}$${\displaystyle \sigma _{st}(v)}$${\displaystyle 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{нормальный}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}}$

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

${\displaystyle \max({\mbox{нормальный}})=1}$

${\displaystyle \min({\mbox{нормальный}})=0}$

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

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

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

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

${\displaystyle s(k)\approx k^{\beta }}$

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

${\displaystyle s(b)\approx b^{\alpha }}$

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

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

${\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^{t}}_{v}}}}$

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

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

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

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

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

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

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

Посредническая центральность использовалась для анализа топологической сложности речных сетей , а также их использования в морской торговле. ^{[11] [12]}

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

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