Physics Department
 CATEGORY:
 Statistical & Bio Seminar
 TITLE:
 Analytical results for the distribution of shortest path lengths in random networks
 Speaker:
 Prof. Eytan Katzav
 Affiliation:
 HUJI
 WHEN:

Sunday
21/05/2017, 15:30  16:30  WHERE:
 Lewiner, Seminar Room (412)
 Organizer:
 Yariv Kafri
 Site:
 
 Remarks:
 
Abstract
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 nonadjacent 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 ErdosRenyi 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 localglobal relation between the degree of a specific node and the mean distance of paths originating from it.
[1] E. Katzav, M. Nitzan, D. benAvraham, 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).