I want to calculate the average path length between any two nodes in a directed graph that contains cycles.

The reason this is not trivial is because there is an infinitive number of paths between most nodes due to the cycles, even though longer paths become increasingly unlikely.

One "empirical" solution is to run a long random walk and count the average number of steps that occurred between two states.

My question: is there an analytical solution that integrates over the possible paths and their likelihood, or a good approximation?

  • 2
    $\begingroup$ you could exponentiate the graph laplacian - that gives you the probability that an arbitrarily long walk starting at A terminates at B. $\endgroup$ – Sycorax says Reinstate Monica Jan 11 '17 at 21:07
  • $\begingroup$ What do you "average" over, i.e. what are the weights on individual paths? Of the infinitely many paths, infinitely many have length $\geq N$ for any fixed $N$... $\endgroup$ – Thales Jan 12 '17 at 0:00
  • $\begingroup$ Thanks @Sycorax. Can you explain that a bit? What do you mean by exponentiating the laplacian? If $L$ is the laplacian, then the entry at position $(i, j)$ of $L^k$ is the probability that a walk of length $k$ starting at $i$ terminates at $j$? But you mentioned arbitrarily long walks ... whats the exponent? $\endgroup$ – Nicolas Schuck Jan 12 '17 at 3:47
  • $\begingroup$ @Thales: The paths should be weighted by the probability of their occurrence. Imagine starting an infinitive number of random walks at node $i$ and terminating each walk as soon as it reaches node $j$. What is the expected average length of all the paths in the resulting list of walks? The more likely a path is to occur, the more often it will appear as a walk, and the more it will influence the path length. $\endgroup$ – Nicolas Schuck Jan 12 '17 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.