CODEWITHSUNDEEP
graph-theory
Matt
Matt

Reputation: 21

Guided Random Walk on 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?

thanks in advance

====

it is true that general graph can not have such property. sorry for the incomplete description, what I'm considering is only scale-free (preferential attachment/power law) graphs, which is common in social networks. thanks. And very importantly, each step of walking can only be taken along existing edge of the graph. So "Teleportation" is too fancy for it, sorry...

Upvotes: 2

Views: 325

Answers (1)

job
job

Reputation: 9253

In general, this is not possible. Consider the case of a cyclical graph where every node N is only connected to N-1 and N+1. Getting to the other side of the graph would required 1500 steps in the same direction. Also, if the graph is clustered then nodes outside the cluster that you started in will have a much lower probability of being visited.

In most cases I think it is desirable to simply have all nodes be reachable by the random walk. The way this is usually handled is by introducing a small "teleportation" probability in the random walk, so at each step there is a chance of randomly moving to any other node in the network instead of simply a neighbor of the current node. This ensure that all nodes have a non-zero probability of being the final node, even when distant or disconnected.

I can't find a reference for it, but I think this is what Google's PageRank algorithm does to model the activity of someone surfing the web as a random walk.

Upvotes: 1

Related Questions