Метрика влияния узла

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

Происхождение и развитие [ править ]

Традиционный подход к пониманию важности узлов - это индикаторы центральности . Индексы центральности предназначены для составления рейтинга, который точно определяет наиболее влиятельные узлы. Однако с середины 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)}\right)}$

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

Приложения [ править ]

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

Ожидаемая сила [ править ]

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

Определение [ править ]

Ожидаемая сила узла определяется выражением${\displaystyle i}$

${\displaystyle \kappa _{i}=-\sum _{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}$

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

Приложения [ править ]

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

Другие подходы [ править ]

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

Ссылки [ править ]