Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

thanks in advance

/// 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

share|improve this question
    
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
    
Do you have any more information to describe your graph? (As Yuval suggests, the answer depends on the graph you're thinking of. Is it connected, e.g.?, complete?... If you have a particular graph in mind, and can create an image file of it, you can click "edit" to add more info, and use the image link on the menu at the top to insert an image directly into your question. It would also be helpful to provide a little info about the methods you've tried... –  amWhy Jun 26 '11 at 0:36
    
Hi all, thanks for your replies first. –  Mat Jun 27 '11 at 9:42

2 Answers 2

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}$.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.