La centralidad de la cercanía al caminar aleatorio es una medida de centralidad en una red , que describe la velocidad promedio con la que los procesos que recorren al azar llegan a 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]
Intuición
Considere una red con un número finito de nodos y un proceso de recorrido aleatorio que comienza en un cierto nodo y continúa de un nodo a otro a lo largo de los bordes. De cada nodo, elige aleatoriamente el borde a seguir. En una red no ponderada, la probabilidad de elegir un cierto borde es igual en todos los bordes disponibles, mientras que en una red ponderada es proporcional a los pesos de los bordes. Se considera que un nodo está cerca de otros nodos, si el proceso de recorrido aleatorio iniciado desde cualquier nodo de la red llega a este nodo en particular en relativamente pocos pasos en promedio.
Definición
Considere una red ponderada, 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. ElEl elemento de M describe la probabilidad de que el caminante aleatorio haya alcanzado el nodo i, proceda directamente al nodo j. Estas probabilidades se definen de la siguiente manera.
dónde es el (i, j) -ésimo elemento de la matriz de ponderación A de la red. Cuando no hay borde 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 promedio del primer pasaje a ese nodo:
Tiempo medio del primer paso
El tiempo medio del primer paso del nodo i al nodo j es el número esperado de pasos que necesita el proceso para llegar al nodo j desde el nodo i por primera vez:
donde P (i, j, r) denota la probabilidad de que se necesiten exactamente r pasos para llegar a j desde i por primera vez. Para calcular estas probabilidades de alcanzar un nodo por primera vez en r pasos, es útil considerar el nodo objetivo como uno absorbente e introducir una transformación de M eliminando su j-ésima fila y columna y denotándola por. Como la probabilidad de que un proceso comience en i y esté en k después de r-1 pasos está dada simplemente por el (i, k) -ésimo elemento de, P (i, j, r) se puede expresar como
Sustituyendo esto en la expresión del tiempo medio del primer paso, se obtiene
Usando la fórmula para la suma de series geométricas para matrices, se obtiene
donde I es la matriz identidad n-1 dimensional .
Por conveniencia computacional, esta expresión se puede vectorizar como
dónde es el vector de los tiempos de primer paso para una caminata que termina en el nodo j, ye es un vector n-1 dimensional de unos.
El tiempo medio del primer paso no es simétrico, incluso para gráficos no dirigidos.
En redes modelo
De acuerdo con las simulaciones realizadas por Noh y Rieger (2004), la distribución de la centralidad de cercanía de caminata aleatoria en un modelo de Barabási-Albert está determinada principalmente por la distribución de grados . En una red de este tipo, la centralidad de cercanía al caminar aleatoria de un nodo es aproximadamente proporcional a su grado, pero no aumenta monótonamente.
Aplicaciones para redes reales
La centralidad de cercanía de paseo aleatorio es una medida más relevante que la centralidad de cercanía simple en el caso de aplicaciones donde 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 concreta de llegar a un determinado punto, o sin la capacidad de encontrar el camino más corto para llegar a su objetivo. Un ejemplo de un paseo aleatorio en una red es la forma en que una determinada 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 en el que el concepto de rutas más cortas no es muy útil es una red densamente conectada. Además, dado que los recorridos más cortos no se ven influenciados por los auto-bucles , la centralidad de cercanía del paseo aleatorio es una medida más adecuada que la centralidad de cercanía cuando se analizan redes donde los auto-bucles son importantes.
Una aplicación importante en el campo de la economía es el análisis del modelo input-output de una economía, que está representado por una red ponderada densamente conectada con importantes bucles propios . [2]
El concepto también se usa ampliamente en las ciencias naturales. Una aplicación biológica es el análisis de interacciones proteína-proteína . [3]
Centralidad de intermediación de caminata aleatoria
Un concepto relacionado, propuesto por Newman, [4] es la centralidad de la intermediación del paseo aleatorio . Así como la centralidad de la cercanía del paseo aleatorio es una contraparte del paseo aleatorio de la centralidad de la cercanía , la centralidad de la intermediación del paseo aleatorio es, de manera similar, la contraparte del paseo aleatorio de la centralidad de la intermediación . A diferencia de la medida de centralidad de intermediación habitual, no solo cuenta las rutas más cortas que pasan por el nodo dado, sino todas las rutas posibles que lo cruzan.
Formalmente, la centralidad de intermediación aleatoria de un nodo es
donde el El elemento de la matriz R contiene la probabilidad de una caminata aleatoria comenzando en el nodo j con el nodo k absorbente, pasando por el nodo i.
El cálculo de la intermediación de caminatas aleatorias en redes grandes es computacionalmente muy intenso. [5]
Centralidad de segundo orden
Otra centralidad basada en el paseo aleatorio es la centralidad de segundo orden . [6] En lugar de contar los caminos más cortos que pasan a través de un nodo dado (como para la centralidad de intermediación de caminatas aleatorias), se enfoca en otra característica de las caminatas aleatorias en gráficos. La expectativa de la desviación estándar de los tiempos de retorno de un paseo aleatorio a un nodo constituye su centralidad . Cuanto menor sea esa desviación, más central será ese nodo.
El cálculo de la intermediación de segundo orden en grandes gráficos arbitrarios también es intensivo, ya que su complejidad es (peor caso logrado en el gráfico de Lollipop ).
Ver también
Referencias
- ^ Blanco, Scott; Smyth, Padhraic (2003). Algoritmos para estimar la importancia relativa en redes (PDF) . Conferencia Internacional ACM SIGKDD sobre Descubrimiento de Conocimiento y Minería de Datos. doi : 10.1145 / 956750.956782 . ISBN 1581137370.
- ^ Blöchl F, Theis FJ, Vega-Redondo F y Fisher E: Las centralidades de vértice en las redes de entrada y salida revelan la estructura de las economías modernas, Physical Review E, 83 (4): 046127, 2011. [1]
- ^ Aidong Zhang : Redes de interacción de proteínas: Análisis computacional (Cambridge University Press) 2007 [2]
- ^ Newman, MEJ: Una medida de centralidad de intermediación basada en paseos aleatorios. Redes sociales, volumen 27, número 1, enero de 2005, páginas 39–54
- ^ Kang, U., Papadimitriou, S., Sun, J. y Tong, H .: Centralidades en grandes redes: algoritmos y observaciones. Conferencia Internacional SIAM sobre Minería de Datos 2011, Mesa, Arizona, EE. UU. [3]
- ^ A.-M. Kermarrec, E. Le Merrer, B. Sericola, G. Trédan: Centralidad de segundo orden: evaluación distribuida de la crítica de los nodos en redes complejas. Comunicaciones por computadora de Elsevier 34 (5): 619-628, 2011.