How clustering affects the bond percolation threshold in complex networks

The question of how clustering (nonzero density of triangles) in networks affects their bond percolation threshold has important applications in a variety of disciplines. Recent advances in modeling highly clustered networks are employed here to analytically study the bond percolation threshold. In comparison to the threshold in an unclustered network with the same degree distribution and correlation structure, the presence of triangles in these model networks is shown to lead to a larger bond percolation threshold (i.e. clustering increases the epidemic threshold or decreases resilience of the network to random edge deletion).

Figure 1

(Color online) (a) Bond percolation threshold in $z$-regular graphs with clustering $C$, generated using the algorithms of [2] ($p_{th}^{\left(\gamma \right)}$, black solid) [1], ($p_{th}^{\left(N\right)}$, magenta dash-dot), and [3] ($p_{th}^{\left(b\right)}$, blue symbols). For comparison, the threshold $p_{th}^{\left(1\right)}$ in an unclustered $z$-regular graph is shown by the red dashed line. Note $p_{th}^{\left(\gamma \right)}=p_{th}^{\left(N\right)}=p_{th}^{\left(b\right)}=p_{th}^{\left(1\right)}$ when $C=0$, but the clustered cases all have $p_{th}$ values exceeding $p_{th}^{\left(1\right)}$ when $C>0$. Values of $z$ are $z=3$ (top), $z=4$ (middle), and $z=6$ (bottom). (b) Sizes of GCC $S\left(p\right)$ in $z=4$ $\gamma$-theory regular graphs with clustering coefficients as shown.

Figure 2

(Color online) (a) Bond percolation threshold in $\gamma$-theory networks with Poisson degree distribution, $z=2$, and clustering $C$ (black solid). For comparison, also shown is the threshold $p_{th}^{\left(1\right)}$ in an unclustered network with same degree distribution (red dashed), and the threshold $p_{th}^{\left(2\right)}$ in an unclustered network with the same degree-degree correlations (blue dash-dot) as the $\gamma$ network. (b) Sizes of GCC $S\left(p\right)$ for the case $C=0.3$ in $\gamma$-theory networks (black solid), and in unclustered networks with the same degree distribution (red dashed), or same degree-degree correlations (blue dash-dot).

Figure 3

(Color online) Sizes of GCC $S\left(p\right)$ for the $\gamma$-theory networks defined by (7) (black solid) and in unclustered networks with the same degree distribution (red dashed), or same degree-degree correlations (blue dash-dot). The magenta dotted curve is for the colored-edge (unclustered) networks defined in Sec. 4. Parameters are $\alpha =0.9$, with (a) $\beta =0.1$, (b) $\beta =0.4$, and (c) $\beta =0.5$.

Figure 4

(Color online) Segment of a clustered network with clique edges colored red (thin lines) and external links colored green (thick lines). After breaking each edge to obtain colored stubs as in (b), a realization of a colored-edge network is created by randomly connecting pairs of stubs of the same color.