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

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

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

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

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

Определение

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

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

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

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

${\mbox{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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}}}$

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

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

Алгоритмы

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

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

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

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

Приложения

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

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

Речные сети

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

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

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

См. также

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

Библиография

• Баррат, А.; и др. (2004). «Архитектура комплексно-взвешенных сетей» . Труды Национальной академии наук Соединенных Штатов Америки . 101 (11): 3747–3752. arXiv : cond-mat/0311416 . Бибкод : 2004PNAS..101.3747B . дои : 10.1073/pnas.0400087101 . ISSN   0027-8424 . ПМЦ   374315 . ПМИД   15007165 .
• Борасси, Микеле; Натале, Эмануэле (2019). «КАДАБРА — это адаптивный алгоритм посредничества посредством случайного приближения» . Журнал экспериментальной алгоритмики ACM . 24 : 1,2:1–1,2:35. arXiv : 1604.08553 . дои : 10.1145/3284359 . ISSN   1084-6654 . S2CID   67871875 .
• Брандес, Ульрик (2001). «Более быстрый алгоритм централизации по посредничеству» (PDF) . Журнал математической социологии . 25 (2): 163–177. CiteSeerX   10.1.1.11.2024 . дои : 10.1080/0022250x.2001.9990249 . hdl : 10983/23603 . S2CID   13971996 . Архивировано (PDF) из оригинала 29 марта 2021 г. Проверено 29 марта 2021 г.
• Берт, Рональд (2009). Структурные дыры: социальная структура конкуренции . Кембридж: Издательство Гарвардского университета . ISBN  978-0-674-02909-5 . OCLC   1041149426 . Проверено 29 марта 2021 г.
• Фриман, Линтон (1977). «Набор мер центральности, основанный на посредничестве». Социометрия . 40 (1): 35–41. дои : 10.2307/3033543 . JSTOR   3033543 .
• Гох, К.-И.; Канг, Б.; Ким, Д. (2001). «Универсальное поведение распределения нагрузки в безмасштабных сетях». Письма о физических отзывах . 87 (27): 278701. arXiv : cond-mat/0106565 . Бибкод : 2001PhRvL..87A8701G . doi : 10.1103/PhysRevLett.87.278701 . ISSN   0031-9007 . ПМИД   11800921 . S2CID   15746304 .
• Мантрах, Амин; и др. (2010). «Ядро ковариации суммы по путям: новая мера ковариации между узлами ориентированного графа». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 32 (6): 1112–1126. дои : 10.1109/tpami.2009.78 . ПМИД   20431135 . S2CID   4807216 .
• Моксли, Роберт Л.; Моксли, Нэнси Ф. (1974). «Определение точечной централизации в ненадуманных социальных сетях». Социометрия . 37 (1): 122–130. дои : 10.2307/2786472 . JSTOR   2786472 .
• Ньюман, Марк Э.Дж. (2010). Сети: Введение . Оксфорд: Издательство Оксфордского университета . ISBN  978-0-19-920665-0 . OCLC   964511577 .
• Пиравинан, Махендра; Прокопенко Михаил; Хоссейн, Лиакат (2013). Холм, Петтер (ред.). «Центральность перколяции: количественная оценка теоретико-графового влияния узлов во время перколяции в сетях» . ПЛОС ОДИН . 8 (1): e53095. Бибкод : 2013PLoSO...853095P . дои : 10.1371/journal.pone.0053095 . ISSN   1932-6203 . ПМК   3551907 . ПМИД   23349699 .
• Саркер, Шиблу; и др. (2019). «Критические узлы речных сетей» . Научные отчеты . 9 (1): 11178. Бибкод : 2019НатСР...911178С . дои : 10.1038/s41598-019-47292-4 . ISSN   2045-2322 . ПМК   6672004 . ПМИД   31371735 .
• Штольц, Саймон; Шлерет, Кристиан (2021). «Прогнозирование силы связи с сетевыми структурами эго». Журнал интерактивного маркетинга . 54 (май): 40–52. дои : 10.1016/j.intmar.2020.10.001 . S2CID   229403802 .