centro de cercanía de paseo aleatorio

La centralidad de cercanía de caminata aleatoria es una medida de centralidad en una red que describe la velocidad promedio con la que los procesos de caminata aleatoria alcanzan un nodo desde otros nodos de la red. Es similar a la centralidad de cercanía, excepto que la lejanía se mide por la longitud esperada de una caminata aleatoria en lugar de por el camino más corto .

El concepto fue propuesto por primera vez por White y Smyth (2003) bajo el nombre de centralidad de Markov . ^{[ 1 ]}

Consideremos una red con un número finito de nodos y un proceso de paseo aleatorio que comienza en un nodo determinado y avanza de nodo en nodo a lo largo de las aristas. Desde cada nodo, se elige aleatoriamente la arista a seguir. En una red no ponderada, la probabilidad de elegir una arista determinada es igual para todas las aristas disponibles, mientras que en una red ponderada es proporcional a los pesos de las aristas. Se considera que un nodo está cerca de otros nodos si el proceso de paseo aleatorio iniciado desde cualquier nodo de la red llega a ese nodo en particular en un número relativamente pequeño de pasos en promedio.

Consideremos una red ponderada –ya sea dirigida o no dirigida– con n nodos denotados por j=1, …, n; y un proceso de paseo aleatorio en esta red con una matriz de transición M.${\displaystyle m_{ij}}$El elemento de M describe la probabilidad de que el caminante aleatorio que ha llegado al nodo i proceda directamente al nodo j. Estas probabilidades se definen de la siguiente manera.

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

dónde${\displaystyle a_{ij}}$es el elemento (i,j) de la matriz de ponderación A de la red. Cuando no hay arista entre dos nodos, el elemento correspondiente de la matriz A es cero.

La centralidad de cercanía de caminata aleatoria de un nodo i es la inversa del tiempo medio de primer paso a ese nodo:

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

dónde${\displaystyle H(j,i)}$es el tiempo medio de primer paso desde el nodo j al nodo i.

Según las simulaciones realizadas por Noh y Rieger (2004), la distribución de la centralidad de cercanía de paseo aleatorio en un modelo de Barabási-Albert está determinada principalmente por la distribución de grados . En dicha red, la centralidad de cercanía de paseo aleatorio de un nodo es aproximadamente proporcional a su grado, pero no aumenta monótonamente con él.

La centralidad de cercanía de paseo aleatorio es una medida más relevante que la centralidad de cercanía simple en aplicaciones donde el concepto de caminos más cortos no es significativo o resulta muy restrictivo para una evaluación razonable de la naturaleza del sistema. Este es el caso, por ejemplo, cuando el proceso analizado evoluciona en la red sin ninguna intención específica de alcanzar un punto determinado, o sin la capacidad de encontrar el camino más corto para llegar a su objetivo. Un ejemplo de paseo aleatorio en una red es la forma en que una moneda circula en una economía: pasa de una persona a otra mediante transacciones, sin ninguna intención de llegar a un individuo específico. Otro ejemplo donde el concepto de caminos más cortos no es muy útil es una red densamente conectada. Además, dado que los caminos más cortos no se ven afectados por los bucles , la centralidad de cercanía de paseo aleatorio es una medida más adecuada que la centralidad de cercanía al analizar redes donde los bucles son importantes.

Una aplicación importante en el campo de la economía es el análisis del modelo de insumo-producto de una economía, que se representa mediante una red ponderada densamente conectada con importantes bucles propios . ^{[ 2 ]}

El concepto también se utiliza ampliamente en las ciencias naturales. Una aplicación biológica es el análisis de las interacciones proteína-proteína . ^{[ 3 ]}

Un concepto relacionado, propuesto por Newman, ^{[ 4 ]} es la centralidad de intermediación de paseo aleatorio . Así como la centralidad de cercanía de paseo aleatorio es la contraparte de la centralidad de cercanía de paseo aleatorio , la centralidad de intermediación de paseo aleatorio es, de manera similar, la contraparte de la centralidad de intermediación de paseo aleatorio . A diferencia de la medida habitual de centralidad de intermediación, no solo cuenta los caminos más cortos que pasan por el nodo dado, sino todos los caminos posibles que lo cruzan.

Formalmente, la centralidad de intermediación de paseo aleatorio de un nodo es

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

donde el${\displaystyle r_{jk}}$El elemento de la matriz R contiene la probabilidad de un paseo aleatorio que comienza en el nodo j con el nodo absorbente k, pasando por el nodo i.

Calcular la centralidad de intermediación de caminatas aleatorias en redes grandes es computacionalmente muy intensivo. ^{[ 5 ]}

Otra medida de centralidad basada en caminatas aleatorias es la centralidad de segundo orden . ^{[ 6 ]} En lugar de contar los caminos más cortos que pasan por un nodo dado (como en la centralidad de intermediación de caminatas aleatorias), se centra en otra característica de las caminatas aleatorias en grafos. La esperanza de la desviación estándar de los tiempos de retorno de una caminata aleatoria a un nodo constituye su centralidad . Cuanto menor sea esa desviación, más central será ese nodo.

Calcular la centralidad de segundo orden en grafos arbitrarios grandes también es intensivo, ya que su complejidad es${\displaystyle O(n^{3})}$(peor escenario alcanzado en el gráfico de piruleta ).

• Centralidad