Paseo aleatorio sesgado en un grafo

En la ciencia de redes , un paseo aleatorio sesgado en un grafo es un proceso de trayectoria temporal en el que una variable en evolución salta de su estado actual a uno de varios estados nuevos potenciales; a diferencia de un paseo aleatorio puro , las probabilidades de los estados nuevos potenciales son desiguales.

Los paseos aleatorios sesgados en un grafo proporcionan un enfoque para el análisis estructural de grafos no dirigidos con el fin de extraer sus simetrías cuando la red es demasiado compleja o cuando no es lo suficientemente grande como para ser analizada mediante métodos estadísticos . El concepto de paseos aleatorios sesgados en un grafo ha atraído la atención de muchos investigadores y empresas de datos durante la última década, especialmente en el ámbito del transporte y las redes sociales . ^{[ 1 ]}

Se han escrito muchas representaciones diferentes de los paseos aleatorios sesgados en grafos según el propósito particular del análisis. Una representación común del mecanismo para grafos no dirigidos es la siguiente: ^{[ 2 ]}

En un grafo no dirigido , un caminante da un paso desde el nodo actual,${\displaystyle j,}$al nodo${\displaystyle i.}$Suponiendo que cada nodo tiene un atributo${\displaystyle \alpha _{i},}$la probabilidad de saltar de un nodo a otro${\displaystyle j}$a${\displaystyle i}$está dado por:

${\displaystyle T_{ij}^{\alpha }={\frac {\alpha _{i}A_{ij}}{\sum _{k}\alpha _{k}A_{kj}}},}$

dónde${\displaystyle A_{ij}}$representa el peso topológico de la arista que va desde${\displaystyle j}$a${\displaystyle i.}$

De hecho, los pasos del caminante están sesgados por el factor de${\displaystyle \alpha }$que pueden diferir de un nodo a otro. ^{[ 3 ]}

Dependiendo de la red, el atributo${\displaystyle \alpha }$puede interpretarse de diferentes maneras. Podría implicar la atracción de una persona en una red social , podría ser la centralidad de intermediación o incluso podría explicarse como una característica intrínseca de un nodo. En el caso de un paseo aleatorio justo en un grafo${\displaystyle \alpha }$es uno para todos los nodos.

En caso de caminos más cortos, caminatas aleatorias ^{[ 4 ]}${\displaystyle \alpha _{i}}$es el número total de caminos más cortos entre todos los pares de nodos que pasan por el nodo${\displaystyle i}$De hecho, el caminante prefiere los nodos con mayor centralidad de intermediación , que se define como se indica a continuación:

${\displaystyle C(i)={\tfrac {{\text{Número total de caminos más cortos a través de }}i}{\text{Número total de caminos más cortos}}}}$

Según la ecuación anterior, el tiempo de recurrencia a un nodo en el paseo sesgado viene dado por: ^{[ 5 ]}

${\displaystyle r_{i}={\frac {1}{C(i)}}}$

Existen diversas aplicaciones que utilizan paseos aleatorios sesgados en grafos. Dichas aplicaciones incluyen el control de la difusión, ^{[ 6 ]} la publicidad de productos en redes sociales , ^{[ 7 ]} la explicación de la dispersión y la redistribución de poblaciones de animales y microorganismos, ^{[ 8 ]} la detección de comunidades, ^{[ 9 ]} las redes inalámbricas, ^{[ 10 ]} y los motores de búsqueda. ^{[ 11 ]}

• Centralidad de intermediación
• Estructura de la comunidad
• Divergencia de Kullback-Leibler
• cadena de Markov
• Paseo aleatorio de máxima entropía
• centro de cercanía de paseo aleatorio
• Análisis de redes sociales
• El problema del viajante

• Gábor Simonyi, "Entropía de grafos: una revisión" . En Optimización combinatoria (eds. W. Cook, L. Lovász y P. Seymour). Providence, RI: Amer. Math. Soc., págs.  399–441, 1995.
• Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola, Gilles Trédan, "Evaluación de la calidad de una topología de red mediante paseos aleatorios" en Gadi Taubenfeld (ed.) Computación distribuida