Average length of s-t (simple) paths in a directed graph
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