Centralidades por paseo aleatorio

Centralidad de cercanía de paseo aleatorio 
Wikipedia

La centralidad de cercanía por camino aleatorio [random walk] es una medida de centralidad en una red, que describe la velocidad media con la que los procesos caminando al azar llegan a un nodo desde otros nodos de la red. El concepto fue propuesto por primera vez por Noh y Rieger (2004). [1]

Intuición

Considere una red con un número finito de nodos y un proceso de paseo aleatorio que se inicia en un determinado nodo y procede de un nodo a otro a lo largo de los enlaces. Desde cada nodo, se elige aleatoriamente el enlace a seguir. En una red no ponderada, la probabilidad de elegir un determinado enlace es igual en todos los enlaces disponibles, mientras que en una red ponderada es proporcional a la ponderación de los enlaces. Un nodo se considera para estar cerca de otros nodos, si el proceso de paseo aleatorio iniciado desde cualquier nodo de la red llega a este nodo particular en relativamente pocos pasos en promedio.

Definición

Considere una red ponderado - ya sea dirigido o no dirigido - con n nodos notados por j = 1, ..., n; y un proceso de paseo aleatorio en esta red con una matriz de transición M. El  elemento de M describe la probabilidad de que el caminante aleatorio que ha alcanzado el nodo i, procede directamente al nodo j. Estas probabilidades se definen de la siguiente manera.

 donde  es el (i, j) -ésimo elemento de la matriz de ponderación A de la red. Cuando no hay ningún borde entre dos nodos, el elemento correspondiente de la matriz A es cero.
La proximidad central paseo aleatorio de un nodo i es la inversa del tiempo medio primer pasaje media a ese nodo:

Primero tiempo de paso media

La media primera tiempo de paso del nodo i al nodo j es el número esperado de pasos que tarda el proceso para alcanzar el nodo j desde el nodo i por primera vez:
 
donde P (i, j, r) denota la probabilidad de que se necesita exactamente pasos r para alcanzar j de i por primera vez. Para calcular estas probabilidades de llegar a un nodo por primera vez en los pasos r, es útil considerar el nodo de destino como una absorción, e introducir una transformación de M mediante la supresión de su fila y la columna j-ésima y denotando por M_ { -j}. Como la probabilidad de un proceso a partir de i y estar en k después de r-1 pasos es simplemente dadas por el (i, k) th elemento de , P (i, j, r ) se puede expresar como
 
Sustituyendo esto en la expresión para medias rendimientos tiempo primero paso
 
Usando la fórmula para la suma de la serie geométrica para matrices nos da

donde I es la matriz identidad dimensional n-1.
Por conveniencia computacional, esta expresión puede ser vectorizada como

donde  es el vector para la primera tiempos de paso para un paseo termina en el nodo j, y e es un vector n-1dimensional de 1.
El tiempo medio primer pasaje no es simétrico, incluso para grafos no dirigidos.

Centralidad de cercanía por paseo aleatorio en modelos de redes 

Según las simulaciones realizadas por Noh y Rieger (2004), la distribución de paseo aleatorio cercanía centralidad en un modelo Barabási-Albert está determinada principalmente por el grado de distribución. En una red de este tipo, la proximidad central paseo aleatorio de un nodo es aproximadamente proporcional a, pero no aumenta monotónicamente con su grado.

Aplicaciones para redes reales

La centralidad de cercanía por paseo aleatorio es medida más relevante que la proximidad central sencilla en el caso de aplicaciones en las que el concepto de caminos más cortos no es significativo o es 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 para llegar a un cierto punto, o sin la capacidad de encontrar el camino más corto para alcanzar su objetivo. Un ejemplo de un paseo aleatorio en una red es la forma en que una cierta moneda circula en una economía: se pasa de una persona a otra a través de transacciones, sin ninguna intención de llegar a un individuo específico. Otro ejemplo donde el concepto de rutas más cortas no es muy útil es una red conectada densamente. Además, como los caminos más cortos no son influenciados por la libre bucles, proximidad central paseo aleatorio es más una medida más adecuada que proximidad central en el análisis de redes en la libre 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 está representado por una red ponderada densamente conectada con importantes libre bucles. [2]
El concepto es ampliamente utilizado en las ciencias naturales. Una aplicación biológica es el análisis de las interacciones proteína-proteína. [3]

Centralidad de intermediación por paseo aleatorio 

Un concepto relacionado, propuesto por Newman, [4] es la centralidad de intermediación por paseo aleatorio. Así como la centralidad cercanía por paseo aleatorio es una contraparte de la centralidad de cercanía, la centralidad de intermediación por paseo aleatorio es, del mismo modo, la contraparte de centralidad de intermediación tradicional. A diferencia de la medida habitual centralidad de intermediación, no sólo cuentan los caminos más cortos que pasan por el nodo dado, sino todos los caminos posibles que cruzan ella.
Formalmente, la centralidad de intermediación paseo aleatorio de un nodo es

 donde el elemento   de la matriz R contiene la probabilidad de un paseo aleatorio a partir de nodo j con absorción del nodo k, que pasa a través del nodo i.
El cálculo de intermediación por paseo aleatorio en grandes redes es computacionalmente muy intensivo. [5]

Referencias

1. J.-D. Noh and H. Rieger. Random walks on complex networks. Phys. Rev. Lett. 92, 118701 [1]
2. Blöchl F, Theis FJ, Vega-Redondo F, and Fisher E: Vertex Centralities in Input-Output Networks Reveal the Structure of Modern Economies, Physical Review E, 83(4):046127, 2011. [2] (Reproducido al final de esta entrada)
3. Aidong, Zhang: Protein Interaction Networks: Computational Analysis (Cambridge University Press) 2007 [3]
4. Newman, M.E. J.: A measure of betweenness centrality based on random walks. Social Networks, Volume 27, Issue 1, January 2005, Pages 39–54
5. Kang, U., Papadimitriou, S., Sun, J., and Tong, H.: Centralities in Large Networks: Algorithms and Observations. SIAM International Conference on Data Mining 2011, Mesa, Arizona, USA. [4]

Vertex Centrality

Leer más publicaciones en Calaméo