The distribution of shortest path lengths in subcritical Erdős-Rényi networks

Abstract

Networks that are fragmented into small disconnected components are prevalent in a large variety of systems. These include the secure communication networks of commercial enterprises, government agencies and illicit organizations, as well as networks that suffered multiple failures, attacks or epidemics. The properties of such networks resemble those of subcritical random networks, which consist of finite components, whose sizes are non-extensive. Surprisingly, such networks do not exhibit the small-world property that is typical in supercritical random networks, where the mean distance between pairs of nodes scales logarithmically with the network size. Unlike supercritical networks whose structure has been studied extensively, subcritical networks have attracted little attention. A special feature of these networks is that the statistical and geometric properties vary between different components and depend on their sizes and topologies. The overall statistics of the network can be obtained by a summation over all the components with suitable weights. We use a topological expansion to perform a systematic analysis of the degree distribution and the distribution of shortest path lengths (DSPL) on components of given sizes and topologies in subcritical Erdos-Renyi (ER) networks. From this expansion we obtain an exact analytical expression for the DSPL of the entire subcritical network, in the asymptotic limit. The DSPL, which accounts for all the pairs of nodes that reside on the same finite component (FC), is found to follow a geometric distribution of the form $P_{\mathrm{FC}}(L=\ell |L<\infty )=(1-c)c^{\ell -1}$, where $c<1$ is the mean degree. We confirm the convergence to this asymptotic result using computer simulations. Using the duality relations between subcritical and supercritical ER networks, we obtain the DSPL on the non-giant components above the percolation transition.

arXiv comment57 pages, 11 figures, 7 tables

References in corpus (26)

• Epidemic processes in complex networks
• 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
• Thermodynamics and dynamics of systems with long-range interactions
• Percolation of localized attack on complex networks
• Structure of shells in complex networks
• First Passage Properties of the Erdos-Renyi Random Graph
• Sampling rare events: statistics of local sequence alignments
• Large-deviation properties of largest component for random graphs
• Distances in random graphs with finite variance degrees
• Metric structure of random networks
• On large deviation properties of Erdos-Renyi random graphs
• 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
• Analytical results for the distribution of shortest path lengths in random networks
• Distance distribution in configuration model networks
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• Distribution of shortest cycle lengths in random networks
• Bias in generation of random graphs
• The average number of distinct sites visited by a random walker on random graphs
• Broadband Macroscopic Cortical Oscillations Emerge from Intrinsic Neuronal Response Failures
• The distribution of first hitting times of random walks on Erdős-Rényi networks

Cited by in corpus (11)

• Big Bird: Transformers for Longer Sequences
• Statistical analysis of articulation points in configuration model networks
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• The birth of geometry in exponential random graphs
• Statistical analysis of edges and bredges in configuration model networks
• Phases of Small Worlds: A Mean Field Formulation
• Generating random networks that consist of a single connected component with a given degree distribution
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Resistance distance distribution in large sparse random graphs
• On the shape of Gaussian scale-free polymer networks
• Statistics of remote regions of networks