Русская Википедия:Показатель влияния узла

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

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

Это послужило поводом для разработки новых методов измерения всех узлов сети. Наиболее общими мерами являются доступность, которая использует разного рода случайные блуждания для измерения достижимости остальной сети из начального узла Шаблон:Sfn, и ожидаемая сила, полученная из матожидания значения Шаблон:Не переведено 5 для узлаШаблон:Sfn.

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

Доступность

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

Определение

Иерархическая степень измеряет число узлов, достижимых из стартового узла путём блужданий длины <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.

Приложения

Доступность, как было показано на примере выявления структуры городских сетейШаблон:Sfn, соответствует числу узлов, которые могут быть посещены за определённый период времениШаблон:Sfn и является предсказанием of the outcome of Шаблон:Не переведено 5 процесса распространения на сети с большим диаметром и низкой плотностьюШаблон:Sfn.

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

Ожидаемая сила измеряет влияние узла с точки зрения эпидемиологии. Она равна математическому ожиданию Шаблон:Не переведено 5, образованную узлом после двух 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.

Приложения

Ожидаемая сила, как было показано, сильно коррелирует с исходами SI, SIS и SIR моделей эпидемии на широком диапазоне сетевых топологий, как моделируемых, так и эмпирическихШаблон:SfnШаблон:Sfn. Она была также использована для измерения пандемического потенциала мировых аэропортов,Шаблон:Sfn, и упоминалась в контексте цифровых платежейШаблон:Sfn, экологииШаблон:Sfn, фитнесаШаблон:Sfn и управления проектамиШаблон:Sfn.

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

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Статья, в основном, относится к теории сетей, а в ней принято употреблять слово узел вместо слова вершина.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Показатель_влияния_узла&oldid=10612629