Центральность близости случайного блуждания

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

Концепция была впервые предложена Уайтом и Смитом (2003) под названием « центральность Маркова» . ^[1]

Интуиция

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

Определение

Рассмотрим взвешенную сеть – направленную или ненаправленную – с n узлами, обозначенными j=1, …, n; и процесс случайного блуждания в этой сети с матрицей перехода M. $m_{ij}$ элемент M описывает вероятность того, что случайный блуждающий человек, достигший узла i, перейдет непосредственно к узлу j. Эти вероятности определяются следующим образом.

m_{ij}={\frac {a_{ij}}{\sum _{k=1}^{n}a_{ik}}}

где $a_{ij}$ является (i,j)-м элементом весовой матрицы A сети. Когда между двумя узлами нет ребра, соответствующий элемент матрицы A равен нулю.

Центральность случайного блуждания узла i является обратной величиной среднего среднего времени первого прохождения к этому узлу:

C_{i}^{RWC}={\frac {n}{\sum _{j=1}^{n}H(j,i)}}

где $H(j,i)$ — среднее время первого прохождения от узла j к узлу i.

Среднее время первого прохода

Среднее время первого прохождения от узла i к узлу j — это ожидаемое количество шагов, которое необходимо процессу, чтобы впервые достичь узла j из узла i:

H(i,j)=\sum _{r=1}^{\infty }rP(i,j,r)

где P(i,j,r) обозначает вероятность того, что потребуется ровно r шагов, чтобы впервые достичь j из i.Чтобы вычислить эти вероятности достижения узла впервые за r шагов, полезно рассматривать целевой узел как поглощающий и ввести преобразование M, удалив его j-ю строку и столбец и обозначив его через $M_{-j}$ . Поскольку вероятность процесса, начинающегося в i и находящегося в k после r-1 шагов, просто задается (i,k)-м элементом $M_{-j}^{r-1}$ , P(i,j,r) можно выразить как

P(i,j,r)=\sum _{k\neq j}((M_{-j}^{r-1}))_{ik}m_{kj}

Подставив это в выражение для среднего времени первого прохождения, получим

H(i,j)=\sum _{r=1}^{\infty }r\sum _{k\neq j}((M_{-j}^{r-1}))_{ik}m_{kj}

Используя формулу суммирования геометрических рядов для матриц, получаем

H(i,j)=\sum _{k\neq j}((I-M_{-j})^{-2})_{ik}m_{kj}

где I — n-1-мерная единичная матрица .

Для удобства вычислений это выражение можно векторизовать как

H(.,j)=(I-M_{-j})^{-1}e

где $H(.,j)$ — вектор времени первого прохождения для прогулки, заканчивающейся в узле j, а e — n-1-мерный вектор из единиц.

Среднее время первого прохождения не симметрично даже для неориентированных графов.

В модельных сетях

Согласно моделированию, выполненному Но и Ригером (2004), распределение центральности близости случайного блуждания в модели Барабаши-Альберта в основном определяется распределением степеней . В такой сети центральность узла по случайному блужданию примерно пропорциональна, но не увеличивается монотонно с его степенью.

Приложения для реальных сетей

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

Важным приложением в области экономики является анализ модели «затраты-выпуск» экономики, которая представлена плотно связанной взвешенной сетью с важными замкнутыми циклами . ^[2]

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

Центральность между случайным блужданием

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

Формально центральность узла по случайному блужданию равна

C_{i}^{RWB}=\sum _{j\neq i\neq k}r_{jk}

где $r_{jk}$ элемент матрицы R содержит вероятность случайного блуждания, начинающегося в узле j с поглощающим узлом k, проходящего через узел i.

Вычисление случайного блуждания между большими сетями требует очень больших вычислительных ресурсов. ^[5]

Центральность второго порядка

Еще одна случайном блуждании, центральность, основанная на — это центральность второго порядка . ^[6] Вместо подсчета кратчайших путей, проходящих через данный узел (как в случае централизации случайных блужданий между собой), он фокусируется на другой характеристике случайных блужданий на графах. Ожидание стандартного отклонения случайного времен возврата блуждания к узлу составляет его центральность . Чем ниже это отклонение, тем более центральным является этот узел.

Вычисление взаимосвязи второго порядка на больших произвольных графах также требует больших усилий, поскольку его сложность очень велика. $O(n^{3})$ (худший случай достигается на графике Lollipop ).

См. также

Центральность

Ссылки

^ Уайт, Скотт; Смит, Падрайк (2003). Алгоритмы оценки относительной важности в сетях (PDF) . Международная конференция ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных. дои : 10.1145/956750.956782 . ISBN 1581137370 .
^ Блёхль Ф., Тайс Ф.Дж., Вега-Редондо Ф. и Фишер Э.: Центральность вершин в сетях ввода-вывода раскрывает структуру современной экономики, Physical Review E, 83(4):046127, 2011. [1]
^ Айдун Чжан : Сети взаимодействия белков: вычислительный анализ (Издательство Кембриджского университета), 2007 [2]
^ Ньюман, МЭД: Мера централизации посредничества, основанная на случайных блужданиях. Социальные сети, том 27, выпуск 1, январь 2005 г., страницы 39–54.
^ Канг У., Пападимитриу С., Сан Дж. и Тонг Х.: Центральности в больших сетях: алгоритмы и наблюдения. Международная конференция SIAM по интеллектуальному анализу данных 2011, Меса, Аризона, США. [3]
^ А.-М. Кермаррек, Э. Ле Меррер, Б. Серикола, Г. Тредан: Центральность второго порядка: распределенная оценка критичности узлов в сложных сетях. Elsevier Computer Communications 34(5):619-628, 2011.

[1] Уайт, Скотт; Смит, Падрайк (2003). Алгоритмы оценки относительной важности в сетях (PDF) . Международная конференция ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных. дои : 10.1145/956750.956782 . ISBN 1581137370 .

[2] Блёхль Ф., Тайс Ф.Дж., Вега-Редондо Ф. и Фишер Э.: Центральность вершин в сетях ввода-вывода раскрывает структуру современной экономики, Physical Review E, 83(4):046127, 2011. [1]

[3] Айдун Чжан : Сети взаимодействия белков: вычислительный анализ (Издательство Кембриджского университета), 2007 [2]

[4] Ньюман, МЭД: Мера централизации посредничества, основанная на случайных блужданиях. Социальные сети, том 27, выпуск 1, январь 2005 г., страницы 39–54.

[5] Канг У., Пападимитриу С., Сан Дж. и Тонг Х.: Центральности в больших сетях: алгоритмы и наблюдения. Международная конференция SIAM по интеллектуальному анализу данных 2011, Меса, Аризона, США. [3]

[6] А.-М. Кермаррек, Э. Ле Меррер, Б. Серикола, Г. Тредан: Центральность второго порядка: распределенная оценка критичности узлов в сложных сетях. Elsevier Computer Communications 34(5):619-628, 2011.

[1]

[2]

[3]

[4]

[5]

[6]