Statistical analysis of edges and bredges in configuration model networks

A bredge (bridge-edge) in a network is an edge whose deletion would split the network component on which it resides into two separate components. Bredges are vulnerable links that play an important role in network collapse processes, which may result from node or link failures, attacks, or epidemics. Therefore, the abundance and properties of bredges affect the resilience of the network to these collapse scenarios. We present analytical results for the statistical properties of bredges in configuration model networks. Using a generating function approach based on the cavity method, we calculate the probability $\widehat{P}(e\in \mathrm{B})$ that a random edge $e$ in a configuration model network with degree distribution $P\left(k\right)$ is a bredge (B). We also calculate the joint degree distribution $\widehat{P}(k,k^{\prime }|\mathrm{B})$ of the end-nodes $i$ and $i^{\prime }$ of a random bredge. We examine the distinct properties of bredges on the giant component (GC) and on the finite tree components (FC) of the network. On the finite components all the edges are bredges and there are no degree-degree correlations. We calculate the probability $\widehat{P}(e\in \mathrm{B}|\mathrm{GC})$ that a random edge on the giant component is a bredge. We also calculate the joint degree distribution $\widehat{P}(k,k^{\prime }|\mathrm{B},\mathrm{GC})$ of the end-nodes of bredges and the joint degree distribution $\widehat{P}(k,k^{\prime }|\mathrm{NB},\mathrm{GC})$ of the end-nodes of nonbredge edges on the giant component. Surprisingly, it is found that the degrees $k$ and $k^{\prime }$ of the end-nodes of bredges are correlated, while the degrees of the end-nodes of nonbredge edges are uncorrelated. We thus conclude that all the degree-degree correlations on the giant component are concentrated on the bredges. We calculate the covariance $\mathrm{\Gamma }(\mathrm{B},\mathrm{GC})$ of the joint degree distribution of end-nodes of bredges and show it is negative, namely bredges tend to connect high degree nodes to low degree nodes. We apply this analysis to ensembles of configuration model networks with degree distributions that follow a Poisson distribution (Erdős-Rényi networks), an exponential distribution and a power-law distribution (scale-free networks). The implications of these results are discussed in the context of common attack scenarios and network dismantling processes.

Figure 1

Schematic illustration of bredges and their surrounding network components: (a) A bredge $e$ (marked by a thick line) in a finite tree component. Deletion of the bredge $e$ would split the tree component into two separate tree components. The end-node $i$ will reside on one of the tree components and the end-node $i^{\prime }$ will reside on the other tree component; (b) a bredge $e$ (thick line) where one of its end nodes, $i^{\prime }$, resides on a cycle. Deletion of the bredge would split the network into two separate components; (c) here the edge $e$, marked by a thick line, is not a bredge because the end nodes of this edge are connected by another path. As a result, on deletion of the marked edge its two end nodes remain on the same network component.

Figure 2

(a) A random node $i$ (empty circle) of degree $k$ in a configuration model network (left). The probability that $i$ does not reside on the giant component is equal to the probability that none of its $k$ neighbors (full circles) resides on the giant component of the reduced network (right) from which $i$ is removed, together with its links (dashed lines). (b) A node $i$ (empty circle) of degree $k$ sampled via a random edge (left), which is marked as a dashed line. We are interested in the probability that $i$ does not reside on the giant component of the reduced network from which the sampled edge (dashed line) is removed. This probability is equal to the probability that none of its $k-1$ remaining neighbors of $i$ resides on the giant component of the further reduced network (right) from which the node $i$ is removed together with its links (dashed lines). (c) A random edge $e$ with end-nodes $i$ and $i^{\prime }$ of degrees $k$ and $k^{\prime }$, respectively (left). The probability that $e$ does not reside on the giant component is equal to the probability that none of its two end-nodes resides on the giant component of the reduced network from which $e$ is removed. This probability is equal to the probability that none of the $k-1$ remaining neighbors of $i$ and none of the $k^{\prime }-1$ remaining neighbors of $i^{\prime }$ resides on the giant component of the further reduced network (right) from which $i$ and $i^{\prime }$ are removed together with their links (dashed lines).

Figure 3

Illustration of the four categories of nodes considered in this paper, presented in the form of a two by two matrix diagram. The horizontal axis accounts for the two sampling procedures, namely random node sampling and node sampling via random edges. The vertical axis accounts for the location of a node in the network, which can be either on the giant component or on one of the finite tree components. Each one of the four categories of nodes exhibits different statistical properties.

Figure 4

Illustration of the four categories of edges considered in this paper, presented in the form of a two by two matrix diagram. The horizontal axis accounts for the two sampling procedures, namely random sampling from all the edges in the network or random sampling restricted to those edges which are bredges. The vertical axis accounts for the location of an edge in the network, which can be either on the giant component or in one of the finite tree components. Each one of the four categories of edges exhibits different statistical properties.

Figure 5

(a) The probability $\widehat{P}(e\in \mathrm{GC})$ (dashed line), that a randomly sampled edge in an ER network resides on the giant component, as a function of the mean degree $c=\langle K\rangle$, obtained from Eq. (35); The complementary probability $\widehat{P}(e\in \mathrm{FC})$ (dotted line) that a randomly sampled edge resides on one of the finite components is also shown. (b) The probability $\widehat{P}(e\in \mathrm{B})$ (solid line) that a randomly sampled edge in an ER network is a bredge, as a function of the mean degree $c$, obtained from Eq. (73); The probability $\widehat{P}(e\in \mathrm{B})$ is equal to the sum of two components: the probability $\widehat{P}(e\in \mathrm{B},\mathrm{GC})$ (dashed line) that a randomly sampled edge is a bredge that resides on the giant component, and the probability $\widehat{P}(e\in \mathrm{B},\mathrm{FC})$ (dotted line) that a randomly sampled edge is a bredge that resides on one of the finite components. The analytical results are in excellent agreement with the results of computer simulations (circles), performed for an ensemble of ER networks of $N={10}^4$ nodes.

Figure 6

Analytical results for the marginal degree distribution $\tilde{P}\left(k\right|\mathrm{GC})$ (solid line) of end-nodes of randomly sampled edges, the marginal degree distribution $\tilde{P}\left(k\right|\mathrm{B},\mathrm{GC})$ (dotted line) of end-nodes of randomly sampled bredges and the marginal degree distribution $\tilde{P}\left(k\right|\mathrm{NB},\mathrm{GC})$ (dashed line) of randomly sampled nonbredge edges on the giant component of an ER network with mean degree $c=2$. The analytical results are in excellent agreement with the results obtained from computer simulations (circles).

Figure 7

Analytical results for the correlation coefficient $R\left(\mathrm{GC}\right)$ (solid line) between the degrees $k$ and $k^{\prime }$ of end-nodes of randomly sampled edges and the correlation coefficient $R(\mathrm{B},\mathrm{GC})$ (dotted line) between the end-nodes of randomly sampled bredges that reside on the giant component of an ER network, as a function of the mean degree $c$. The analytical results are in excellent agreement with the results obtained from computer simulations (circles). The correlations, which are concentrated on the bredges, are negative and become stronger as $c$ is increased. Since the fraction of bredges on the giant component is a decreasing function of $c$, the correlation coefficient over all the edges on the giant component decreases (in absolute value) as $c$ is increased.

Figure 8

(a) Analytical results for the probability $\widehat{P}(e\in \mathrm{GC})$ (dashed line) that a randomly sampled edge in a configuration model network with an exponential degree distribution resides on the giant component, as a function of the mean degree $c$; The complementary probability $\widehat{P}(e\in \mathrm{FC})$ (dotted line) that a randomly sampled edge resides on one of the finite tree components is also shown. (b) Analytical results for the probability $\widehat{P}(e\in \mathrm{B})$ (solid line) that a randomly sampled edge is a bredge, as a function of the mean degree $c$, obtained from Eq. (73); The probability $\widehat{P}(e\in \mathrm{B})$ is equal to the sum of two components: the probability $\widehat{P}(e\in \mathrm{B},\mathrm{GC})$ (dashed line), that a randomly sampled edge is a bredge that resides on the giant component and the probability $\widehat{P}(e\in \mathrm{B},\mathrm{FC})$ that a randomly sampled edge is a bredge that resides on one of the finite components. The analytical results are in excellent agreement with the results of computer simulations (circles), performed for an ensemble of configuration model networks of $N={10}^4$ nodes.

Figure 9

Analytical results for the marginal degree distribution $\tilde{P}\left(k\right|\mathrm{GC})$ (solid line) of end-nodes of randomly sampled edges, the marginal degree distribution $\tilde{P}\left(k\right|\mathrm{B},\mathrm{GC})$ (dotted line) of end-nodes of randomly sampled bredges, and the marginal degree distribution $\tilde{P}\left(k\right|\mathrm{NB},\mathrm{GC})$ (dashed line) of randomly sampled nonbredge edges, on the giant component of a configuration model network with an exponential degree distribution and mean degree $c=2.5$. The analytical results are in excellent agreement with the results obtained from computer simulations (circles).

Figure 10

Analytical results for the correlation coefficient $R\left(\mathrm{GC}\right)$ (solid line) between the degrees $k$ and $k^{\prime }$ of end-nodes of edges and the correlation coefficient $R(\mathrm{B},\mathrm{GC})$ (dotted line) between the end-nodes of bredges that reside on the giant component of a configuration model network with an exponential degree distribution, as a function of the mean degree $c$. The analytical results are in excellent agreement with the results obtained from computer simulations (circles).

Figure 11

(a) Analytical results for the probability $\widehat{P}(e\in \mathrm{GC})$ (dashed line) that a randomly sampled edge in a configuration model network with a power-law degree distribution resides on the giant component, as a function of the mean degree $c$. The complementary probability $\widehat{P}(e\in \mathrm{FC})$ (dotted line) that a randomly sampled edge resides on one of the finite tree components is also shown; (b) analytical results for the probability $\widehat{P}(e\in \mathrm{B})$ (solid line) that a random edge is a bredge, as a function of the mean degree $c$. The probability $\widehat{P}(e\in \mathrm{B})$ is equal to the sum of two components: the probability $\widehat{P}(e\in \mathrm{B},\mathrm{GC})$ (dashed line) that a randomly sampled edge is a bredge that resides on the giant component and the probability $\widehat{P}(e\in \mathrm{B},\mathrm{FC})$ (dotted line) that a randomly sampled edge is a bredge that resides on one of the finite components. The analytical results are in excellent agreement with the results of computer simulations (circles), performed for networks of $N={10}^4$ nodes and $k_{\max }=100$.

Figure 12

Analytical results for the marginal degree distribution $\tilde{P}\left(k\right|\mathrm{GC})$ of end-nodes of randomly selected edges (solid line), the marginal degree distribution $\tilde{P}\left(k\right|\mathrm{B},\mathrm{GC})$ of end-nodes of bredges (dotted line) and the marginal degree distribution $\tilde{P}\left(k\right|\mathrm{NB},\mathrm{GC})$ of end-nodes of nonbredge edges (dashed line) on the giant component of a configuration model network with a power-law degree distribution with an exponent $\gamma =2.5$, mean degree $c=1.54$, and $k_{\max }=100$. The analytical results are in excellent agreement with the results obtained from computer simulations (circles).

Figure 13

Analytical results for the correlation coefficient $R\left(\mathrm{GC}\right)$, between the degrees $k$ and $k^{\prime }$ of end-nodes of edges (solid line) and the correlation coefficient $R(\mathrm{B},\mathrm{GC})$ between the end-nodes of bredges (dotted line) that reside on the giant component of a configuration model network with a power-law degree distribution, as a function of the mean degree $c$ with $k_{\max }=100$. The analytical results are in excellent agreement with the results obtained from computer simulations (circles), except for the dilute network regime just above the percolation transition. In this regime the giant component is small and its size fluctuates between different network instances. The data points in this regime were averaged over 100 network instances, while all the other data points were averaged over 20 network instances.

Figure 14

Erdős-Rényi networks of $N=100$ nodes with mean degree $c=1.1$ (a) and $c=1.7$ (b), which exhibit a coexistence between a giant component and finite tree components. The nonbredge edges (solid lines) connect pairs of nodes that reside on the 2-core of the giant component. In the more dilute case (a) the 2-core consists of a single cycle, while in the denser case (b) it exhibits a complex web of cycles. The root bredges (dashed lines) connect the tree branches on the giant component to the 2-core. All the other bredges (dotted lines) connect pairs of nodes on that reside on the tree branches of the giant component and pairs of nodes on the finite tree components.