The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks

Abstract

In the subcritical regime Erdős-Rényi (ER) networks consist of finite tree components, which are non-extensive in the network size. The distribution of shortest path lengths (DSPL) of subcritical ER networks was recently calculated using a topological expansion [E. Katzav, O. Biham and A.K. Hartmann, Phys. Rev. E 98, 012301 (2018)]. The DSPL, which accounts for the distance $\ell$ between any pair of nodes that reside on the same finite tree component, was found to follow a geometric distribution of the form $P(L=\ell |L<\infty )=(1-c)c^{\ell -1}$, where $0<c<1$ is the mean degree of the network. This result includes the contributions of trees of all possible sizes and topologies. Here we calculate the distribution of shortest path lengths $P(L=\ell |S=s)$ between random pairs of nodes that reside on the same tree component of a given size $s$. It is found that $P(L=\ell |S=s)=\frac{\ell +1}{s^{\ell }}\frac{(s-2)!}{(s-\ell -1)!}$. Surprisingly, this distribution does not depend on the mean degree $c$ of the network from which the tree components were extracted. This is due to the fact that the ensemble of tree components of a given size $s$ in subcritical ER networks is sampled uniformly from the set of labeled trees of size $s$ and thus does not depend on $c$. The moments of the DSPL are also calculated. It is found that the mean distance between random pairs of nodes on tree components of size $s$ satisfies $\mathbb{E}[L|S=s]\sim \sqrt{s}$, unlike small-world networks in which the mean distance scales logarithmically with $s$.

29 pages, 7 figures. arXiv admin note: text overlap with arXiv:1806.05743

References in corpus (9)

• Articulation Points in Complex Networks
• Component sizes in networks with arbitrary degree distributions
• Lagrange Inversion
• Distance distribution in random graphs and application to networks exploration
• On the number of circuits in random graphs
• The distribution of shortest path lengths in a class of node duplication network models
• Distribution of shortest cycle lengths in random networks
• Convergence towards an Erd{\H o}s-Rényi graph structure in network contraction processes
• Statistical analysis of edges and bredges in configuration model networks