Показатель влияния узла

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

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

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

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

Приложения

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

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

Ожидаемая сила измеряет влияние узла с точки зрения эпидемиологии. Она равна математическому ожиданию силы инфекции, образованную узлом после двух transmissions.

Определение

Ожидаемая сила узла $i$ задаётся формулой

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

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

Определение естественным образом распространяется на ориентированные сети путём сужения упорядочения $J$ направлением рёбер. Аналогично, распространение на взвешенные сети или сети с разнородной передачей вероятностей, is a matter of adjusting the normalization of $d_{j}$ to include the probability, которую образует кластер. Также можно использовать более двух переносов для определения множества $J$.

Приложения

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

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

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