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

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

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

Центральность между посредничеством была разработана как общая мера центральности: ^[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{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}}$

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

${\displaystyle \max(normal)=1}$

${\displaystyle \min(normal)=0}$

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

Взвешенные сети [ править ]

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

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

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

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

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

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

Центральность перколяции - это версия взвешенной центральности промежуточности, но она учитывает «состояние» исходного и целевого узлов каждого кратчайшего пути при вычислении этого веса. Распространение «заражения» происходит в сложных сетях по ряду сценариев. Например, вирусная или бактериальная инфекция может распространяться через социальные сети людей, известные как контактные сети. Распространение болезни также можно рассматривать на более высоком уровне абстракции, рассматривая сеть городов или населенных пунктов, соединенных автомобильным, железнодорожным или воздушным сообщением. Компьютерные вирусы могут распространяться по компьютерным сетям. Слухи или новости о деловых предложениях и сделках также могут распространяться через социальные сети людей. Во всех этих сценариях «инфекция» распространяется по звеньям сложной сети, изменяя «состояния» узлов по мере своего распространения,либо с возможностью восстановления, либо иным образом. Например, в эпидемиологическом сценарии люди переходят из «восприимчивого» в «инфицированное» состояние по мере распространения инфекции. Состояния, которые отдельные узлы могут принимать в приведенных выше примерах, могут быть двоичными (например, получена / не получена новость), дискретными (восприимчивые / инфицированные / восстановленные) или даже непрерывными (например, доля инфицированных людей в городе ) по мере распространения заразы. Общей чертой всех этих сценариев является то, что распространение заражения приводит к изменению состояний узлов в сетях. Имея это в виду, была предложена центральность перколяции (PC), которая, в частности, измеряет важность узлов с точки зрения содействия перколяции через сеть. Эта мера была предложеналюди переходят из «восприимчивого» в «инфицированное» состояние по мере распространения инфекции. Состояния, которые отдельные узлы могут принимать в приведенных выше примерах, могут быть двоичными (например, получена / не получена новость), дискретными (восприимчивые / инфицированные / восстановленные) или даже непрерывными (например, доля инфицированных людей в городе ) по мере распространения заразы. Общей чертой всех этих сценариев является то, что распространение заражения приводит к изменению состояний узлов в сетях. Имея это в виду, была предложена центральность перколяции (PC), которая, в частности, измеряет важность узлов с точки зрения содействия перколяции через сеть. Эта мера была предложеналюди переходят из «восприимчивого» в «инфицированное» состояние по мере распространения инфекции. Состояния, которые отдельные узлы могут принимать в приведенных выше примерах, могут быть двоичными (например, получена / не получена новость), дискретными (восприимчивые / инфицированные / восстановленные) или даже непрерывными (например, доля инфицированных людей в городе ) по мере распространения заразы. Общей чертой всех этих сценариев является то, что распространение заражения приводит к изменению состояний узлов в сетях. Имея это в виду, была предложена центральность перколяции (PC), которая, в частности, измеряет важность узлов с точки зрения содействия перколяции через сеть. Эта мера была предложенадискретный (восприимчивый / инфицированный / выздоровевший) или даже непрерывный (например, доля инфицированных в городе) по мере распространения инфекции. Общей чертой всех этих сценариев является то, что распространение заражения приводит к изменению состояний узлов в сетях. Имея это в виду, была предложена центральность перколяции (PC), которая, в частности, измеряет важность узлов с точки зрения содействия перколяции через сеть. Эта мера была предложенадискретный (восприимчивый / инфицированный / выздоровевший) или даже непрерывный (например, доля инфицированных в городе) по мере распространения инфекции. Общей чертой всех этих сценариев является то, что распространение заражения приводит к изменению состояний узлов в сетях. Имея это в виду, была предложена центральность перколяции (PC), которая, в частности, измеряет важность узлов с точки зрения содействия перколяции через сеть. Эта мера была предложенакоторый, в частности, измеряет важность узлов с точки зрения содействия прохождению через сеть. Эта мера была предложенакоторый, в частности, измеряет важность узлов с точки зрения содействия прохождению через сеть. Эта мера была предложенаПиравеенан, Прокопенко и Хоссейн (2013) . ^[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^{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}$

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

Алгоритмы [ править ]

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

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

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

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

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

Приложения [ править ]

Социальные сети [ править ]

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

Речные сети [ править ]

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

Понятия, связанные с данным [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Библиография [ править ]