Analytical results for the distribution of shortest path lengths in random networks

The increasing interest in network research in recent years is motivated by the realization that a large variety of systems and processes which involve interacting objects can be described by network models. In these models, the objects are represented by nodes and the interactions are expressed by edges. The interactions between non-adjacent pairs of nodes are facilitated by paths going through intermediate nodes and edges. The shortest paths between such pairs are of particular importance because they provide the strongest interactions and fastest response. Therefore, the distribution of shortest path lengths is of great relevance to many dynamical processes taking place on networks such as communication, navigation and epidemic spreading. While the average of this distribution has been studied extensively, the analytical calculation of the entire distribution has remained an open problem.

In this presentation a novel analytical approach for calculating the distribution of shortest path lengths in random networks will be discussed. This approach is based on the cavity method, and applies to a large family of network types, which includes Erdos-Renyi networks [1], regular graphs and more generally, configuration model networks [2]. The results are found to be in agreement with numerical simulations for a broad range of networks, sizes and connectivities. 

Being analytical this approach allows shedding light on various phenomena such as an interesting local-global relation between the degree of a specific node and the mean distance of paths originating from it. 

 

[1] 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).

[2] M. Nitzan, E. Katzav, R. Kuhn and O. Biham, Distance distribution in configuration model networks, PRE 93, 62309 (2016).