Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Assume that we are given a real life graph, DBLP network in my case, where degree distribution of nodes follows a power law (many nodes have 1, 2 neighbors, and only a few nodes have hundreds of neighbors).

A random walk ends when it returns to the initial node or when the walk takes 3 steps. If we start random walks from each node on this graph, should we start equal number of walks from each node? If so, nodes with small degrees will often return to where they started, and we will not learn big portions of the network. This is because small degree nodes are neighbors of small degree nodes more often, so there will not be many paths to walk on.

I believe there should be a way to decide on the number of walks to minimize computational costs.

share|improve this question
2  
By DBLP graph, do you mean a citation graph? If so, it will be a DAG and will never have cycles. So, if you start a walk from any node, you will never come back to the same node! In fact, all 3 vertices in each random walk will be unique (of course, some vertices may be visited twice by two walks started from two different vertices). –  Paresh Nov 19 '12 at 7:53
    
Also, can you please clarify with precise explanations about what it is you are trying to achieve, and how? What do you mean by "... not learn big portions.." and "should we start equal number of walks from each node". –  Paresh Nov 19 '12 at 7:59
    
I think that cycles are possible. If $A$ cites $B$ and then $B$ cites $A$ (in another publication), we have a cycle. –  Nejc Nov 19 '12 at 8:18
    
@Nejc If $A$ cites $B$, then $B$ has been published before $A$, in which case, it could never cite $A$. Unless citation of unpublished papers is allowed/exists. –  Paresh Nov 19 '12 at 8:35
    
@Paresh Sorry, but it seems, I do not know how this dataset looks. Are $A$ and $B$ papers or persons? –  Nejc Nov 19 '12 at 8:38
show 4 more comments

1 Answer

If you consider given graph as a Markov chain, you can compute the steady-state distribution. With it, you can compute the mean-reccurence time $M_j$ (expected time to return to the starting node). See Mean recurrence time

$\pi_j=1/M_j$

If for some node $n_j$, the probability of going to each neighbour is equal to $1/out\_deg(n_j)$, then you can compute $\pi_j$ in constant time.

This does not assume, you stop after three steps (why do you actually need this?). From here you could do some experiments with damping factor $d$. Damping factor $d$ is the probability you end the walk at each step. Damping factor You can combine these two aproaches to get to your estimate.

-edit-

So here goes. Given an undirected graph $G=(V,E)$ you can find the stationary distribution of the corresponding Markov chain $M$ with transition matrix $P$ as follows:

$\pi_i=deg(v_i)/|E|$

where $deg(v_i)$ is the degree of vertex $i$, $|E|$ is the number of all edges in graph $G$ and $\pi_i$ is the $i$-th component of vector that satisfies:

$\lim_{k->\infty} P^k=1\pi$

Note that $\pi$ is unique if the Markov chain is irreducible and aperiodic.

  • Irreducibility essentially means, you can get from every vertex $i$ to every vertex $j$. If the graph is not connected, you can use the same approach on the connected components of the graph.
  • Aperiodicity means that greatest common divisor of cylce lengths in the Markov chain. This means that if you have at least one paper which was written by three authors (in one component), the condition is trivially satisfied.

Mean recurrence time is the computed by the formula above.

share|improve this answer
    
DBLP has 1M nodes and 8M edges (two authors coauthored a paper in any given year). I have to stop at path length 3 because during the algorithm I have some other computations and even for length 3 the run time of the code is 20 minutes. If I let it walk more I might never finish it. –  Cuneyt Nov 19 '12 at 15:27
    
I think mean recurrence time is what i needed. If mean recurrence time is higher i can start more walks from that node. –  Cuneyt Nov 19 '12 at 15:33
    
If you have problem with alot of computations, then you do not need to simulate the walks. If the probabilities are solely based on the degree of node, then you can compute the steady state probability of one node in constant time. Tomorrow I can extend my answer (because I do not have my notes with me) for the exact formula. –  Nejc Nov 19 '12 at 19:39
add comment

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.