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$.

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

References in corpus (29)

• Random graphs with arbitrary degree distributions and their applications
• Scale-Free Networks are Ultrasmall
• The phase transition in inhomogeneous random graphs
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Structure of shells in complex networks
• Articulation Points in Complex Networks
• Component sizes in networks with arbitrary degree distributions
• Lagrange Inversion
• Metric structure of random networks
• Distance distribution in random graphs and application to networks exploration
• Fractal Boundaries of Complex Networks
• Distribution of diameters for Erdös-Rényi random graphs
• On the number of circuits in random graphs
• Analytical results for the distribution of shortest path lengths in random networks
• Distance distribution in configuration model networks
• Circuits in random graphs: from local trees to global loops
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• The distribution of shortest path lengths in a class of node duplication network models
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Distribution of shortest cycle lengths in random networks
• Statistical analysis of articulation points in configuration model networks
• Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy
• Random matrices with row constraints and eigenvalue distributions of graph Laplacians
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication
• Convergence towards an Erd{\H o}s-Rényi graph structure in network contraction processes
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• Statistical analysis of edges and bredges in configuration model networks
• Phases of Small Worlds: A Mean Field Formulation

Cited by in corpus (1)

• On the shape of Gaussian scale-free polymer networks