[Solved]: Average length of s-t (simple) paths in a directed graph

Problem Detail: 

Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating them? What if paths are allowed to revisit vertices?

Relevant results on special graphs could also be helpful.

Asked By : liuyu

Answered By : vzn

calculating/estimating/approximating the average path length has been studied for some random graph models including the Erdos-Renyi model and the Barabasi-Albert scale free networks, and also the Strogatz small world graphs which may be suitable as approximations for your graphs. [it would be better if you could narrow down/detail some nature/characteristics of the graphs you're studying.]

• Computing the average path length and a label-based routing in a small-world graph — Philippe J. Giabbanelli, Dorian Mazauric, and Stephane Perennes

• Average path length in random networks — Agata Fronczak, Piotr Fronczak, Janusz A. Holyst

• The average distance in a random graph with given expected degrees — Fan Chung, Linyuan Lu

• AN ESTIMATION OF THE SHORTEST AND LARGEST AVERAGE PATH LENGTH IN GRAPHS OF GIVEN DENSITY — Laszlo Gulyas, Gabor Horvath, Tamas Cseri and George Kampis

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11146