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

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 structural and statistical properties of such networks resemble those of subcritical random networks, which consist of finite components, whose sizes are nonextensive. 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 relatively 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 Erdős-Rényi (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. Using computer simulations we calculate the DSPL in subcritical ER networks of increasing sizes and confirm the convergence to this asymptotic result. We also obtain exact asymptotic results for the mean distance, ${\langle L\rangle }_{\mathrm{FC}}$, and for the standard deviation of the DSPL, ${\sigma }_{L,\mathrm{FC}}$, and show that the simulation results converge to these asymptotic results. Using the duality relations between subcritical and supercritical ER networks, we obtain the DSPL on the nongiant components of ER networks above the percolation transition.

Figure 1

Illustration of the structure of one instance of a subcritical ER network of $N=100$ nodes and $c=0.9$. It consists of 33 isolated nodes, 9 dimers, two chains of three nodes, two chains of four nodes, one tree with a single hub and four branches, one tree with two hubs, and two larger trees of 10 and 14 nodes.

Figure 2

A list of all the possible backbone tree topologies that consist of up to six hubs ($h=1,2,\cdots ,6$). The linear chain topology appears for all values of $h$. For $h\le 3$ it is the only topology, while for $h\ge 4$ more complex topologies appear and their number quickly increases.

Figure 3

Illustration of the range of possible values of $b$ (the number of branches) in a tree of $h$ hubs, which consists of $s$ nodes. This range is bounded from below by $b=h+2$, due to a topological constraint, regardless of $s$ (ascending straight line). For a network that consists of $s$ nodes, it is bounded from above by $b=s-h$ (descending straight line). The two lines intersect at $(h,2h+2)$. Combinations of $(h,b)$ that are possible in a tree of $s=12$ nodes are marked by full circles, while combination that exist only in larger trees are marked by empty circles. Each backbone tree can be represented by its adjacency matrix $A$, which is an $h\times h$ matrix. The topology of a complete tree is denoted by $\tau =(h,A,\vec{b})$, where $\vec{b}=(b_1,\cdots ,b_h)$ accounts for a specific division of the $b$ branches between the $h$ hubs.

Figure 4

Analytical results for the mean degree, $\mathbb{E}\left[K\right|2\le S\le s]$, over all tree topologies of sizes smaller or equal to $s$, as a function of $c$, for $s=2,3,\cdots ,10$ (solid lines), from bottom to top, respectively, obtained from Eq. (67). The thick solid line shows the asymptotic result, ${\langle K\rangle }_{\mathrm{FC}}$.

Figure 5

The mean degree $\mathbb{E}\left[K\right|2\le S\le s]$ over all trees of size smaller than or equal to $s$, as a function of $s$ for $c=1$. The analytical results (circles), obtained from Eq. (70), are in excellent agreement with the exact results of the asymptotic expansion (solid line). The results of the asymptotic expansion to order $1/\sqrt{s}$ ($\times$), obtained from the first two terms of Eq. (71), exhibit large deviations from the exact results, particularly for small values of $s$. However, an expansion to order $1/s$ obtained by including the third term in Eq. (71) greatly improves the results ($+$).

Figure 6

Illustration of the collapse process that is used in order to obtain the combinatorial factors for the DSPL on a finite component. In this case, the number of pairs of nodes that are at a distance of $\ell =3$ from each other on a linear chain of size $s=9$ (top chain) is equal to the number of possible locations of the marked node (large empty circle) on the reduced chain of $s-\ell =6$ nodes (bottom chain).

Figure 7

The DSPLs of subcritical ER network ensembles with $N={10}^4$ and $c=0.2,0.4,0.6$, and 0.8. The theoretical results for the corresponding asymptotic networks (solid lines), obtained from Eq. (95), are in very good agreement with the numerical simulations (symbols). The deviations in the tail are due to the finite size of the sampled networks.

Figure 8

The probability $P_{\mathrm{FC}}(L=\ell |L<\infty )$ given by Eq. (95) is shown as a function of the mean degree, $c$, for $\ell =1,2,5$, and 10. The probability $P_{\mathrm{FC}}(L=1|L<\infty )$ is a monotonically decreasing function of $c$. For $\ell \ge 2$, the probability $P_{\mathrm{FC}}(L=\ell |L<\infty )$ exhibits a peak at $c=1-1/\ell$, which is the value of $c$ at which the probability of two random nodes being at a distance $\ell$ from each other is maximal.

Figure 9

Numerical results for the DSPL on the finite components of an $\mathrm{ER}[N,c/(N-1\left)\right]$ network with $N={10}^4$ and $c=1.547$, above percolation (circles), and on its dual network, $\mathrm{ER}[N^{\prime },c^{\prime }/(N^{\prime }-1)]$ where $N^{\prime }=3882$ [obtained from Eq. (104)] and $c^{\prime }=0.6$ [obtained from Eq. (105)], below percolation ($\times$), which are essentially identical and in excellent agreement with the theoretical results (solid line), obtained from Eq. (95).

Figure 10

The mean distance $\mathbb{E}\left[L\right|S\le s]$, over all tree topologies of sizes smaller or equal to $s$, as a function of $c$, for $s=2,3,\cdots ,10$ (solid lines), from bottom to top, respectively. The thick solid line shows the asymptotic result, ${\langle L\rangle }_{\mathrm{FC}}$.

Figure 11

The mean, ${\langle L\rangle }_{\mathrm{FC}}$ (a), and the standard deviation, ${\sigma }_{L,\mathrm{FC}}$ (b), of the DSPL of a subcritical ER network vs the mean degree, $c$. The numerical results (symbols) for $N={10}^2$, ${10}^3$, and ${10}^4$ clearly converge towards the analytical results (solid lines).