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

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

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

Интуиция

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

Определение

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

{ Displaystyle M (я, j) ​​= { гидроразрыва {a_ {ij}} { sum _ {j = 1} ^ {n} a_ {ij}}}}

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

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

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

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

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

{ Displaystyle H (я, j) ​​= сумма _ {r = 1} ^ { infty} rP (i, j, r)}

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

{ Displaystyle P (я, j, r) = сумма _ {k neq j} ((M _ {- j} ^ {r-1})) _ {ik} m_ {kj}}

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

{ Displaystyle Н (я, j) ​​= сумма _ {г = 1} ^ { infty} г сумма _ {k neq j} ((M _ {- j} ^ {r-1})) _ { ik} m_ {kj}}

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

{ Displaystyle Н (я, j) ​​= сумма _ {к neq j} ((I-M _ {- j}) ^ {- 2}) _ {ik} m_ {kj}}

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

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

{ displaystyle H (., j) = (I-M _ {- j}) ^ {- 1} e}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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