How many random walks to start from each node?
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-&gt;\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.