Paseo al azar sin escala gráfica para tener una distribución uniforme sobre todos los nodos como paso final

Question

por ejemplo, tenemos un gráfico dado de 3000 nodos, y dejamos que cada paseo se inicia desde el nodo 19. También la longitud máxima de un paseo, digamos 200 pasos. Entonces, ¿cómo guía el pie, de modo que cada nodo en el gráfico es igualmente posible para ser el paso final de la caminata.

Estoy tratando con algunos de los métodos, pero el resultado no es muy brillante. alguna idea?

gracias de antemano

/// Hola a todos, gracias por sus respuestas en primer lugar. Lo siento por la descripción incompleta, estoy relativas a la representación gráfica de las redes sociales, que generalmente siguen la "Ley de potencias"/"Evaluación del Apego a reglas", lo que da un libre de escala gráfica. sí que está conectado y suelen tener un poco de "hubs"(con alto grado) y el diámetro no es muy grande, digamos de menos de 10. un ejemplo gráfico

Answer 1

Una posibilidad es que sólo un $K_{3000}$ con uno mismo-lazos en cada vértice en $V$. Dar la probabilidad de transición para cada borde, $e \in E(G)$, $\frac{1}{3000}$.

Answer 2

Deje $k_{n}$ denotar el grado del nodo $n$, y deje $k_\max = \max k_n$ ser el máximo grado de cualquier nodo. Considere la posibilidad de la caminata aleatoria definida por la regla:

Estancia en el nodo $n$ con una probabilidad de $1-k_n/k_\max$, se mueven al azar a una adyacente nodo de otra manera.

Es fácil ver que la distribución uniforme sobre todos los nodos es una distribución estacionaria de este paseo aleatorio, ya que la red de probabilidad de flujo a través de cada borde será de cero. Si el gráfico está conectado, el paseo aleatorio también se ergodic, y por lo tanto converge a esta distribución estacionaria de cualquier distribución inicial.

Sin embargo, tenga en cuenta que esto no es bastante una respuesta a su pregunta, ya que esta convergencia se produce sólo en el límite cuando el tiempo tiende a infinito. Sin embargo, con suficiente muchos pasos, la distribución puede terminar muy cerca de uniforme. Si, por ejemplo, 200 pasos podría ser suficiente para que dependerá del tamaño y la conectividad de su gráfica.