# Guided Random Walk on scale-free graph to have a uniform distribution over all nodes as end-step

for example, we have a given graph of 3000 nodes, and we let every walk starts from node 19. Also max length of a walk is given, say 200 steps. Then how to guide the walk, so that every node on the graph is equally possible to be the end step of the walk.

I'm trying with some methods, but the result is not very bright. any ideas?

/// Hi all, thanks for your replies first. Sorry for the incomplete description, I'm concerning the graph representation of social networks which usually follow "Power Law"/"Preferencial Attachment" rules, which gives a scale-free graph. yes it's connected and usually have some "hubs"(with high degree) and the diameter is not that big, say under 10. an example graph

-
That rather depends on your graph. Consider what happens if it's disconnected or has large diameter. – Yuval Filmus Jun 25 '11 at 23:32
Hi all, thanks for your replies first. – Mat Jun 27 '11 at 9:42

One possibility is to just have a $K_{3000}$ with self-loops on each vertex in $V$. Give the transition probability for each edge, $e \in E(G)$, to be $\frac{1}{3000}$.

-
well, each step should only be taken along an existing edge. thanks – Mat Jun 27 '11 at 9:50

Let $k_{n}$ denote the degree of the node $n$, and let $k_\max = \max k_n$ be the maximum degree of any node. Consider the random walk defined by the rule:

Stay at node $n$ with probability $1-k_n/k_\max$, move to a random adjacent node otherwise.

It's easy to see that the uniform distribution over all nodes is a stationary distribution of this random walk, since the net probability flux over each edge will be zero. If the graph is connected, the random walk will also be ergodic, and therefore will converge to this stationary distribution from any initial distribution.

However, note that this is not quite an answer to your question, since this convergence only occurs in the limit as time goes to infinity. However, with sufficiently many steps, the distribution may still end up quite close to uniform. Whether, say, 200 steps might be enough for that will depend on the size and connectivity of your graph.

-