Близость случайного блуждания по центру
Центральность случайных блужданий — это мера центральности в сети , которая описывает среднюю скорость, с которой случайно блуждающие процессы достигают узла из других узлов сети. Это похоже на центральность близости , за исключением того, что удаленность измеряется ожидаемой длиной случайного блуждания , а не кратчайшим путем .
Рассмотрим сеть с конечным числом узлов и процессом случайного блуждания, который начинается в некотором узле и продолжается от узла к узлу по ребрам. Из каждого узла он случайным образом выбирает ребро, которому нужно следовать. В невзвешенной сети вероятность выбора определенного ребра одинакова для всех доступных ребер, а во взвешенной сети она пропорциональна весам ребер. Узел считается близким к другим узлам, если процесс случайного блуждания, инициированный каким-либо узлом сети, достигает этого конкретного узла в среднем за относительно небольшое число шагов.
Рассмотрим взвешенную сеть — либо направленную, либо ненаправленную — с n узлами, обозначенными как j=1, …, n; и процесс случайного блуждания в этой сети с матрицей переходов M. Элемент M описывает вероятность того, что случайный блуждающий игрок, достигший узла i, переходит непосредственно к узлу j. Эти вероятности определяются следующим образом.
где – (i,j)-й элемент весовой матрицы A сети. Когда между двумя узлами нет ребра, соответствующий элемент матрицы A равен нулю.
Центральность близости случайного блуждания узла i обратно пропорциональна среднему среднему времени первого прохода к этому узлу:
Среднее время первого перехода от узла i к узлу j — это ожидаемое количество шагов, которое требуется процессу, чтобы достичь узла j из узла i в первый раз: