Holon Physics Seminar

---

 

 

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 Erdős-Rényi networks, regular graphs and, more generally, configuration model networks. The results are found to be in agreement with numerical simulations for a broad range of networks, sizes and connectivities. Recent extensions to other ensembles of random networks will also be discussed.