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

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

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

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

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

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

Доступность

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

Определение

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

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

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

Приложения

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

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

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

Определение

Ожидаемая сила узла $i$ дается

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

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

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

Приложения

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

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

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