The distribution of shortest path lengths is of great importance for many dynamical processes taking place on networks such as communication, navigation and epidemic spreading. In this presentation an analytical approach based on recursion equations for calculating the distribution of shortest path lengths in random networks will be discussed. The results are found to be in agreement with numerical simulations for a broad range of network sizes and connectivities. Being analytical this approach allows putting the spotlight on various phenomena such as an interesting relation between the degree of a node and the mean distance of paths originating from it, or the sphericity of the network in the dense limit. The methodology presented could be applied to more general classes of networks.

Reference:

E. Katzav, M. Nitzan, D. ben-Avraham, P. L. Krapivsky, R. Kuhn, N. Ross and O. Biham, "Analytical results for the distribution of shortest path lengths in random networks", EPL 111, 26006 (2015).