Просмотр кода страницы Показатель влияния узла

'''Показатель влияния узла''' — это мера, которая ранжирует или количественно выражает влияние каждого [[Вершина (теория графов)|узла]] (называемого также вершиной)<ref>Статья, в основном, относится к [[Наука о сетях|теории сетей]], а в ней принято употреблять слово '''узел''' вместо слова '''вершина'''.</ref> в графе. Показатели имеют связь с [[Центральность|индексами центральности]]. Приложения показателя включают меры влияния каждого лица в [[Социальная сеть (социология)|социальной сети]], понимание роли узлов в [[Транспортная сеть|транспортных сетях]],  [[интернет]]е, или [[Городская сеть|городских сетях]] и  роль данного узла в динамике заболевания.

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

Обзорная статья 2006 года Богатти и Эверетта{{sfn|Borgatti, Everett|2006|с=466–484}} показала, что аккуратность индексов центральности сильно зависит от топологии сети.
Это заключение с тех пор было неоднократно подтверждено (например, {{sfn|da Silva, Viana, da F. Costa|2012|с=P07005}}{{sfn|Lawyer|2015|с=8665}}).
В 2012 Бауэр с коллегами напомнил нам, что индексы центральности лишь ранжируют узлы, но не дают числовой оценки разницы между ними{{sfn|Bauer, Lizier|2012|с=68007}}.
В 2013 году Сикик с коллегами представили строгое свидетельство, что индексы центральности сильно недооценивают силу нехабовых узлов{{sfn|Sikic, Lancic, Antulov-Fantulin, Stefanic|2013|с=1–13}}.
Причина вполне ясна — аккуратность меры центральности зависит от топологии сет, а сложные сети имеют неоднородную топологию. Вследствие этого меры центральности, пригодные для идентификации высоковлиятельных узлов, будут наиболее вероятно быть непригодными для остатка сети{{sfn|Lawyer|2015|с=8665}}.

Это послужило поводом для разработки новых методов измерения всех узлов сети. Наиболее общими мерами являются '''доступность''', которая использует разного рода случайные блуждания для измерения достижимости остальной сети из начального узла {{sfn|Travencolo, da F. Costa|2008|с=89–95}}, и '''ожидаемая сила''', полученная из матожидания значения {{не переведено 5|Сила инфекции|силы инфекции||force of infection}} для узла{{sfn|Lawyer|2015|с=8665}}.

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

== Доступность ==
'''Доступность''' происходит из теории случайных блужданий. Показатель измеряет разброс {{не переведено 5|Невозвратное блуждание|невозвратных блужданий||self-avoiding walk}}, начинающихся с данного узла. Блуждание на сети — это последовательность смежных вершин. Невозвратное блуждание посещает каждую вершину лишь раз. 
Оригинальная работа использовала моделирование блужданий длины 60 для описания сети городских улиц бразильского города{{sfn|Travencolo, da F. Costa|2008|с=89–95}}.
Позднее доступность была формализована как форма иерархической степени, которая контролирует как вероятность прохождения, так и многообразие блужданий заданной фиксированной длины{{sfn|Viana, Batista, da F. Costa|2012|с=036105}}.

=== Определение ===
Иерархическая степень измеряет число узлов, достижимых из стартового узла путём блужданий длины <math>h</math>. Для фиксированного <math>h</math> и типа блужданий каждый из этих соседей достигается с (возможно, различными) вероятностями <math>p_j^{(h)}</math>.
Если задан вектор таких вероятностей, доступность узла <math>i</math> для значения <math>h</math> определяется формулой

:<math>\kappa_i^{(h)}=\exp \left( - \sum_j p_j^{(h)} \log p_j^{(h)} \right) </math>

Вероятности могут быть использованы для случайных блужданий с однородной вероятностью и, дополнительно, подправлены весом рёбер и/или явной (для рёбер) вероятностью прохождения{{sfn|Viana, Batista, da F. Costa|2012|с=036105}}.

=== Приложения ===
Доступность, как было показано на примере выявления структуры городских сетей{{sfn|Travencolo, da F. Costa|2008|с=89–95}}, соответствует числу узлов, которые могут быть посещены за определённый период времени{{sfn|Viana, Batista, da F. Costa|2012|с=036105}} и является предсказанием of the outcome of {{не переведено 5|Компараментная модель в эпидемиологии|эпидемиологическая SIR-модель||Compartmental models in epidemiology}} процесса распространения на сети с большим [[Наука о сетях#Диаметр сети|диаметром]] и низкой [[Наука о сетях#Плотность|плотностью]]{{sfn|da Silva, Viana, da F. Costa|2012|с=P07005}}.

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

'''Ожидаемая сила''' измеряет влияние узла с точки зрения эпидемиологии. Она равна [[Математическое ожидание|математическому ожиданию]] {{не переведено 5|Сила инфекции|силы инфекции||force of infection}}, образованную узлом после двух transmissions.

=== Определение ===

Ожидаемая сила узла <math>i</math> задаётся формулой

:<math>\kappa_i=- \sum_{j=1}^J d_j \log(d_j)</math>,

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

Определение естественным образом распространяется на ориентированные сети путём сужения упорядочения <math>J</math> направлением рёбер.
Аналогично, распространение на взвешенные сети или сети с разнородной передачей вероятностей, is a matter of adjusting the normalization of <math>d_j</math> to include the probability, которую образует кластер.
Также можно использовать более двух переносов для определения множества <math>J</math>{{sfn|Lawyer|2015|с=8665}}.

=== Приложения ===

Ожидаемая сила, как было показано, сильно коррелирует с исходами SI, SIS и SIR моделей эпидемии на широком диапазоне сетевых топологий, как моделируемых, так и эмпирических{{sfn|Lawyer|2015|с=8665}}{{sfn|Lawyer|2014}}.
Она была также использована для измерения пандемического потенциала мировых аэропортов,{{sfn|Lawyer|2016|с=70}}, и упоминалась в контексте цифровых платежей{{sfn|Milkau, Bott|2015}}, экологии{{sfn|Jordan, Maguire, Hofmann, Kohda|2016|с=20152359}}, фитнеса{{sfn|Pereira, Gama, Sousa и др.|2015|с=10489}} и управления проектами{{sfn|Ellinas, Allan, Durugbo, Johansson|2015|с=e0142469}}.

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

Другие предлагаемые метрики явно кодируют динамику специфичного процесса, разворачивающегося на сети.  '''Динамическое влияние''' — это пропорция неограниченных блужданий, начинающихся в каждом узле, где шаги блуждания масштабируются так, что линейные динамики системы, как ожидается, сходятся к ненулевому устойчивому состоянию{{sfn|Klemm, Serrano, Eguiluz, Miguel|2012|с=292}}. В результате при увеличении длины блужданий появляется вероятность переноса на конечный узел блуждания, который не был бы посещён при более коротких блужданиях{{sfn|Bauer, Lizier|2012|с=68007}}.
Хотя обе меры хорошо предсказывают выход динамических систем, которые они кодируют, в каждом случае авторы соглашаются, что результаты динамики не переносятся на другие динамики.

== Примечания ==
{{примечания|2}}

== Литература ==
{{refbegin|colwidth=30em}}
* {{статья
|автор=Steve Borgatti, Martin Everett
|ref=Borgatti, 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
|ref=da Silva, Viana, 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
|arxiv=1202.0024
|bibcode=2012JSMTE..07..005A
}}
* {{статья
|автор=Glenn Lawyer
|ref= Lawyer
|год= 2015
|заглавие= Understanding the spreading power of all nodes in a network: a continuous-time perspective
|издание=Sci Rep
|том=5
|doi=10.1038/srep08665
|pmid=25727453
|pmc=4345333
|arxiv=1405.6707
|bibcode=2015NatSR...5E8665L
}}
* {{статья
|автор=Travencolo B. a. N., Luciano da F. Costa
|ref=Travencolo, 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
|ref=Bauer, 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
|arxiv=1203.0502
|bibcode=2012EL.....9968007B
}}
* {{статья
|автор=Mile Sikic, Alen Lancic, Nino Antulov-Fantulin, Hrvoje Stefanic
|ref=Sikic, Lancic, Antulov-Fantulin, Stefanic
|заглавие=Epidemic centrality - is there an underestimated epidemic impact  of network peripheral nodes?
|издание=The European Physical Journal B
|том=86
|номер=10
|год=2013
|doi=10.1140/epjb/e2013-31025-5
|arxiv=1110.2558
}}
* {{статья
|автор=Matheus Viana, Joao Batista, Luciano da F. Costa
|ref=Viana, Batista, da F. Costa
|заглавие=Effective number of accessed nodes in complex networks
|издание=Phys Rev E|год=2012
|том=85
|номер=3.2
}}
* {{статья
|ref= Lawyer
|автор= Glenn Lawyer
|год= 2014
|заглавие= Technical Report: Performance of the Expected Force on AS-level Internet topologies
|ссылка= https://archive.org/details/arxiv-1406.4785
|arxiv=1406.4785
|bibcode= 2014arXiv1406.4785L
}}
* {{статья
|ref= Lawyer
|автор= 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
|ссылка=https://bmcinfectdis.biomedcentral.com/articles/10.1186/s12879-016-1350-4
|pmc=4746766
}}
* {{статья
|автор=Udo Milkau, Jürgen Bott
|ref=Milkau, Bott
|заглавие=Digitalisation in payments: From interoperability to centralised models?
|издание=Journal of Payments Strategy & Systems
|год=2015
|том=9
|выпуск=3
|ссылка=http://www.ingentaconnect.com/content/hsp/jpss/2015/00000009/00000003/art00008
}}
* {{статья
|автор=Lyndon Jordan, Sean Maguire, Hans Hofmann, Masanori Kohda
|ref=Jordan, Maguire, Hofmann, 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
|ref=Pereira, Gama, Sousa и др.
|заглавие=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
|pmid=25994386
|pmc=4440209
|bibcode=2015NatSR...510489P
}}
* {{статья
|автор=Christos Ellinas, Neil Allan, Christopher Durugbo, Anders Johansson
|ref=Ellinas, Allan, Durugbo, Johansson
|заглавие=How Robust Is Your Project? From Local Failures to Global Catastrophes: A Complex Networks Approach to Project Systemic Risk
|издание=PLoS One
|год=2015
|doi=10.1371/journal.pone.0142469
|pmid=26606518
|ссылка=http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0142469
|том=10
|pmc=4659599
|bibcode=2015PLoSO..1042469E
}}
* {{статья
|автор=Konstantin Klemm, M. Angeles Serrano, Victor Eguiluz, Maxi San Miguel
|ref=Klemm, Serrano, Eguiluz, Miguel
|заглавие= A measure of individual role in collective dynamics
|издание =Sci Rep
|год=2012
|том=2
|doi=10.1038/srep00292
|bibcode=2012NatSR...2E.292K
}}
{{refend}}

[[Категория:Теория графов]]
[[Категория:Анализ сетей]]
{{rq|checktranslate|style}}