Метрика влияния узла - Node influence metric

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

Происхождение и развитие

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

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

Это вдохновило на разработку новых методов, предназначенных для измерения влияния всех сетевых узлов. Самыми общими из них являются доступность, который использует разнообразие случайных блужданий для измерения доступности остальной части сети с заданного начального узла,^[6]и ожидаемая сила, полученный из ожидаемого значения сила заражения генерируется узлом.^[3]Обе эти меры могут быть осмысленно вычислены только на основе структуры сети.

Доступность

В Доступность выводится из теории случайных блужданий. Он измеряет разнообразие прогулки с самоуправлением которые начинаются с данного узла. Прогулка по сети - это последовательность смежных вершин; Самоисключающаяся прогулка посещает (перечисляет) каждую вершину не более одного раза. В оригинальной работе для характеристики сети городских улиц в бразильском городе использовались моделируемые прогулки длиной 60 метров.^[6]Позже он был формализован как модифицированная форма иерархической степени, которая контролирует как вероятности передачи, так и разнообразие блужданий заданной фиксированной длины.^[7]

Определение

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

Вероятности могут быть основаны на случайных блужданиях с равномерной вероятностью или могут дополнительно модулироваться весовыми коэффициентами по краям и / или явными (по краям) вероятностями передачи.^[7]

Приложения

Было показано, что доступность позволяет выявить структуру сообщества в городских сетях,^[6] соответствует количеству узлов, которые можно посетить за определенный период времени,^[7] и предсказывает исход эпидемиологическая модель SIR распространение процессов в сетях с большими диаметр и низкий плотность.^[2]

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

В ожидаемая сила измеряет влияние узла с эпидемиологической точки зрения. Это ожидаемое значение из сила заражения генерируется узлом после двух передач.

Определение

Ожидаемая сила узла ${ displaystyle i}$ дан кем-то

${ Displaystyle каппа _ {я} = - сумма _ {j = 1} ^ {J} d_ {j} log (d_ {j})}$

где сумма берется по множеству ${ displaystyle J}$ всех возможных кластеров передачи в результате двух передач, начиная с ${ displaystyle i}$. То есть узел ${ displaystyle i}$ и двое его соседей или ${ displaystyle i}$, один из его соседей (называемый зараженным) и сосед зараженного соседа. ${ displaystyle J}$ содержит все возможные порядки событий передачи, поэтому два кластера могут содержать одни и те же узлы, если они заразились в другом порядке. ${ displaystyle d_ {j}}$ нормализованная кластерная степень кластера ${ displaystyle j in J}$, то есть количество ребер с одной конечной точкой в ​​кластере ${ displaystyle j}$.

Определение естественным образом распространяется на направленные сети, ограничивая перечисление ${ displaystyle J}$ по направлению края. Аналогичным образом, расширение на взвешенные сети или сети с неоднородными вероятностями передачи - это вопрос корректировки нормализации ${ displaystyle d_ {j}}$ чтобы включить вероятность образования этого кластера. Также можно использовать более двух передач для определения набора ${ displaystyle J}$.^[3]

Приложения

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

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

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

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