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

Мера центральности графа, основанная на кратчайших путях

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

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

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

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

Определение

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

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

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

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

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

${\displaystyle \min({\mbox{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 }}$

Исследование среднего значения силы для вершин с промежуточностью показывает, что функциональное поведение можно аппроксимировать масштабной формой: ^[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}$

Присоединенные веса к путям перколяции зависят от уровней перколяции, назначенных исходным узлам, исходя из предпосылки, что чем выше уровень перколяции исходного узла, тем важнее пути, исходящие из этого узла. Поэтому узлы, которые лежат на кратчайших путях, исходящих из узлов с высокой степенью просачивания, потенциально более важны для просачивания. Определение ПК также можно расширить, включив в него веса целевых узлов. Расчеты централизации перколяции выполняются вовремя благодаря эффективной реализации, заимствованной из алгоритма Брандеса . Если при расчете необходимо учитывать веса целевых узлов, время наихудшего случая равно . ${\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]}

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

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

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

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

Рекомендации

1. Фриман (1977), с. 39.
2. «Вычисление централизации посредничества в Gephi». YouTube .
3. Баррат и др. (2004).
4. Пиравенан, Прокопенко и Хоссейн (2013).
5. Брандес (2001), с. 1.
6. Брандес (2001), с. 9.
7. Мантрач и др. (2010).
8. Борасси и Натале (2019).
9. Берт (2009).
10. Штольц и Шлерет (2021).
11. Саркер и др. (2019).
12. Эйланд, Мюррей (2020). «Сети Рима, Византии и Китая». Антикввс . 4 (1). Интервью с Йоханнесом Прейзер-Капеллером: 41–45.

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

• Баррат, А.; и другие. (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. PMID  11800921. S2CID  15746304.
• Мантрах, Амин; и другие. (2010). «Ядро ковариации суммы по путям: новая мера ковариации между узлами ориентированного графа». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 32 (6): 1112–1126. дои : 10.1109/tpami.2009.78. PMID  20431135. S2CID  4807216.
• Моксли, Роберт Л.; Моксли, Нэнси Ф. (1974). «Определение точечной централизации в ненадуманных социальных сетях». Социометрия . 37 (1): 122–130. дои : 10.2307/2786472. JSTOR  2786472.
• Ньюман, Марк Э.Дж. (2010). Сети: Введение . Оксфорд: Издательство Оксфордского университета . ISBN 978-0-19-920665-0. ОКЛК  964511577.
• Пиравинан, Махендра; Прокопенко Михаил; Хоссейн, Лиакат (2013). Холм, Петтер (ред.). «Центральность перколяции: количественная оценка теоретико-графового влияния узлов во время перколяции в сетях». ПЛОС ОДИН . 8 (1): e53095. Бибкод : 2013PLoSO...853095P. дои : 10.1371/journal.pone.0053095 . ISSN  1932-6203. ПМК  3551907 . ПМИД  23349699.
• Саркер, Шиблу; и другие. (2019). «Критические узлы речных сетей». Научные отчеты . 9 (1): 11178. Бибкод : 2019NatSR...911178S. дои : 10.1038/s41598-019-47292-4. ISSN  2045-2322. ПМК  6672004 . ПМИД  31371735.
• Штольц, Саймон; Шлерет, Кристиан (2021). «Прогнозирование силы связи с сетевыми структурами эго». Журнал интерактивного маркетинга . 54 (май): 40–52. doi :10.1016/j.intmar.2020.10.001. S2CID  229403802.