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

We present two complementary analytical approaches for calculating the distribution of shortest path lengths in Erd s-Rényi networks, based on recursion equations for the shells around a reference node and for the paths originating from it. The results are in agreement with numerical simulations for...

Full description

Saved in:
Bibliographic Details
Published in:Europhysics letters 2015-07, Vol.111 (2), p.26006-p1-26006-p5
Main Authors: Katzav, Eytan, Nitzan, Mor, ben-Avraham, Daniel, Krapivsky, P. L., Kühn, Reimer, Ross, Nathan, Biham, Ofer
Format: Article
Language:English
Subjects:
64.60.aq
89.75.Da
Asymptotic methods
Asymptotic properties
Extreme values
Mathematical analysis
Mathematical models
Networks
Nodes
Recursion
Rest
Shortest-path problems
Standard deviation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present two complementary analytical approaches for calculating the distribution of shortest path lengths in Erd s-Rényi networks, based on recursion equations for the shells around a reference node and for the paths originating from it. The results are in agreement with numerical simulations for a broad range of network sizes and connectivities. The average and standard deviation of the distribution are also obtained. In the case in which the mean degree scales as with the network size, the distribution becomes extremely narrow in the asymptotic limit, namely almost all pairs of nodes are equidistant, at distance from each other. The distribution of shortest path lengths between nodes of degree m and the rest of the network is calculated. Its average is shown to be a monotonically decreasing function of m, providing an interesting relation between a local property and a global property of the network. The methodology presented here can be applied to more general classes of networks.
ISSN:0295-5075
1286-4854
DOI:10.1209/0295-5075/111/26006