Показатель влияния узла

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

Истоки и развитие

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

Обзорная статья 2006 года Богатти и Эверетта^[2] показала, что аккуратность индексов центральности сильно зависит от топологии сети. Это заключение с тех пор было неоднократно подтверждено (например, ^[3][4]). В 2012 Бауэр с коллегами напомнил нам, что индексы центральности лишь ранжируют узлы, но не дают числовой оценки разницы между ними^[5]. В 2013 году Сикик с коллегами представили строгое свидетельство, что индексы центральности сильно недооценивают силу нехабовых узлов^[6]. Причина вполне ясна — аккуратность меры центральности зависит от топологии сет, а сложные сети имеют неоднородную топологию. Вследствие этого меры центральности, пригодные для идентификации высоковлиятельных узлов, будут наиболее вероятно быть непригодными для остатка сети^[4].

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

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

Доступность

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

Определение

Иерархическая степень измеряет число узлов, достижимых из стартового узла путём блужданий длины ${\displaystyle h}$. Для фиксированного ${\displaystyle h}$ и типа блужданий каждый из этих соседей достигается с (возможно, различными) вероятностями ${\displaystyle p_{j}^{(h)}}$. Если задан вектор таких вероятностей, доступность узла ${\displaystyle i}$ для значения ${\displaystyle h}$ определяется формулой

${\displaystyle \kappa _{i}^{(h)}=\exp \left(-\sum _{j}p_{j}^{(h)}\log p_{j}^{(h)}\right)}$

Вероятности могут быть использованы для случайных блужданий с однородной вероятностью и, дополнительно, подправлены весом рёбер и/или явной (для рёбер) вероятностью прохождения^[8].

Приложения

Доступность, как было показано на примере выявления структуры городских сетей^[7], соответствует числу узлов, которые могут быть посещены за определённый период времени^[8] и является предсказанием of the outcome of эпидемиологическая SIR-модель^[англ.] процесса распространения на сети с большим диаметром и низкой плотностью^[3].

Ожидаемая сила

Ожидаемая сила измеряет влияние узла с точки зрения эпидемиологии. Она равна математическому ожиданию силы инфекции^[англ.], образованную узлом после двух transmissions.

Определение

Ожидаемая сила узла ${\displaystyle i}$ задаётся формулой

${\displaystyle \kappa _{i}=-\sum _{j=1}^{J}d_{j}\log(d_{j})}$,

где сумма берётся по множеству ${\displaystyle J}$ всех возможных transmission clusters resulting from two transmissions starting from ${\displaystyle i}$, а ${\displaystyle d_{j}}$ является нормализованной степенью кластера ${\displaystyle j\in J}$.

Определение естественным образом распространяется на ориентированные сети путём сужения упорядочения ${\displaystyle J}$ направлением рёбер. Аналогично, распространение на взвешенные сети или сети с разнородной передачей вероятностей, is a matter of adjusting the normalization of ${\displaystyle d_{j}}$ to include the probability, которую образует кластер. Также можно использовать более двух переносов для определения множества ${\displaystyle J}$^[4].

Приложения

Ожидаемая сила, как было показано, сильно коррелирует с исходами SI, SIS и SIR моделей эпидемии на широком диапазоне сетевых топологий, как моделируемых, так и эмпирических^[4][9]. Она была также использована для измерения пандемического потенциала мировых аэропортов,^[10], и упоминалась в контексте цифровых платежей^[11], экологии^[12], фитнеса^[13] и управления проектами^[14].

Другие подходы

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

Примечания

1. Статья, в основном, относится к теории сетей, а в ней принято употреблять слово узел вместо слова вершина.
2. Borgatti, Everett, 2006, с. 466–484.
3. da Silva, Viana, da F. Costa, 2012, с. P07005.
4. Lawyer, 2015, с. 8665.
5. Bauer, Lizier, 2012, с. 68007.
6. Sikic, Lancic, Antulov-Fantulin, Stefanic, 2013, с. 1–13.
7. Travencolo, da F. Costa, 2008, с. 89–95.
8. Viana, Batista, da F. Costa, 2012, с. 036105.
9. Lawyer, 2014.
10. Lawyer, 2016, с. 70.
11. Milkau, Bott, 2015.
12. Jordan, Maguire, Hofmann, Kohda, 2016, с. 20152359.
13. Pereira, Gama, Sousa и др., 2015, с. 10489.
14. Ellinas, Allan, Durugbo, Johansson, 2015, с. e0142469.
15. Klemm, Serrano, Eguiluz, Miguel, 2012, с. 292.

Литература

• Steve Borgatti, Martin Everett. A graph-theoretic perspective on centrality // Social Networks. — 2006. — Т. 28. — doi:10.1016/j.socnet.2005.11.005.
• Renato da Silva, Matheus Viana, Luciano da F. Costa. Predicting epidemic outbreak from individual features of the spreaders // J. Stat. Mech.: Theory Exp.. — 2012. — Т. 2012, № 07. — doi:10.1088/1742-5468/2012/07/p07005. — Bibcode: 2012JSMTE..07..005A. — arXiv:1202.0024.
• Glenn Lawyer. Understanding the spreading power of all nodes in a network: a continuous-time perspective // Sci Rep. — 2015. — Т. 5. — doi:10.1038/srep08665. — Bibcode: 2015NatSR...5E8665L. — arXiv:1405.6707. — PMID 25727453. — PMC 4345333.
• Travencolo B. a. N., Luciano da F. Costa. Accessibility in complex networks // Phys Lett A. — 2008. — Т. 373, № 1. — doi:10.1016/j.physleta.2008.10.069.
• Frank Bauer, Joseph Lizier. Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: A walk counting approach // Europhys Lett. — 2012. — Т. 99, № 6. — doi:10.1209/0295-5075/99/68007. — Bibcode: 2012EL.....9968007B. — arXiv:1203.0502.
• Mile Sikic, Alen Lancic, Nino Antulov-Fantulin, Hrvoje Stefanic. Epidemic centrality - is there an underestimated epidemic impact of network peripheral nodes? // The European Physical Journal B. — 2013. — Т. 86, № 10. — doi:10.1140/epjb/e2013-31025-5. — arXiv:1110.2558.
• Matheus Viana, Joao Batista, Luciano da F. Costa. Effective number of accessed nodes in complex networks // Phys Rev E. — 2012. — Т. 85, № 3.2.
• Glenn Lawyer. Technical Report: Performance of the Expected Force on AS-level Internet topologies. — 2014. — Bibcode: 2014arXiv1406.4785L. — arXiv:1406.4785.
• Glenn Lawyer. Measuring the potential of individual airports for pandemic spread over the world airline network // BMC Infectious Diseases. — 2016. — Т. 16. — doi:10.1186/s12879-016-1350-4. — PMID 26861206. — PMC 4746766.
• Udo Milkau, Jürgen Bott. Digitalisation in payments: From interoperability to centralised models? // Journal of Payments Strategy & Systems. — 2015. — Т. 9, вып. 3.
• Lyndon Jordan, Sean Maguire, Hans Hofmann, Masanori Kohda. The social and ecological costs of an ‘over-extended' phenotype // Proceedings of the Royal Society B. — 2016. — Т. 283, вып. 1822. — doi:10.1098/rspb.2015.2359. — PMID 26740619. — PMC 4721094.
• Vanessa Pereira, Maria Gama, Filipe Sousa, Theodore Lewis, Claudio Gobatto, Fúlvia Manchado-Gobatto. Complex network models reveal correlations among network metrics, exercise intensity and role of body changes in the fatigue process // Scientific Reports. — 2015. — Т. 5. — doi:10.1038/srep10489. — Bibcode: 2015NatSR...510489P. — PMID 25994386. — PMC 4440209.
• Christos Ellinas, Neil Allan, Christopher Durugbo, Anders Johansson. How Robust Is Your Project? From Local Failures to Global Catastrophes: A Complex Networks Approach to Project Systemic Risk // PLoS One. — 2015. — Т. 10. — doi:10.1371/journal.pone.0142469. — Bibcode: 2015PLoSO..1042469E. — PMID 26606518. — PMC 4659599.
• Konstantin Klemm, M. Angeles Serrano, Victor Eguiluz, Maxi San Miguel. A measure of individual role in collective dynamics // Sci Rep. — 2012. — Т. 2. — doi:10.1038/srep00292. — Bibcode: 2012NatSR...2E.292K.