Emergence and Size of the Giant Component in Clustered Random Graphs with a Given Degree Distribution

Standard techniques for analyzing network models usually break down in the presence of clustering. Here we introduce a new analytic tool, the “free-excess degree” distribution, which extends the generating function framework, making it applicable for clustered networks ($C>0$). The methodology is general and provides a new expression for the threshold point at which the giant component emerges and shows that it scales as $(1-C{)}^{-1}$. In addition, the size of the giant component may be predicted even for more complicated scenarios such as the removal of a fixed fraction of nodes at random.

Figure 1

Graphical illustration of the exposure procedure. Choose a node at random, say, $V_0$, and start diffusing from it and counting the nodes encountered on the way. (a) When $C=0$ and the network is treelike [9], after counting the new nodes ($a_1-a_4$) we pick one of them at random, say, $a_1$, and count its new neighboring nodes ($b_1-b_3$), which are distributed according to $\{q_i{\}}_{i=0}^{\infty }$. In the next step, we randomly choose one of the nodes ($a_2-a_4$, $b_1-b_3$) and continue until the entire component is exposed. (b) When $C>0$, two modifications are required to deal with cycles due to triangles (the dashed edges): we use $\{e_i{\}}_{i=0}^{\infty }$ and diffuse depthwise. After counting $a_1-a_4$, when we count the neighbors of $a_1$, we avoid overcounting $a_2$ because $\{e_i{\}}_{i=0}^{\infty }$ govern the distribution of the solid-black edges. In the next step if we go from $a_1$ to $b_3$ in order to count the neighbors of $b_3$, again we avoid overcounting $a_2$ (because it is connected to $a_1$). The depthwise exposure, which is a permissible scheme [10], is made use of to avoid dependencies.

Figure 2

The difference between the new criterion B and the conventional criterion A. (a) Consider the following example: a typical node has a neighborhood similar to $V_0$—3 nodes at a distance one at the first layer, $L_1$, and 2 nodes at a distance two at the second layer, $L_2$, but 4 edges to the second layer (from $L_1$ to $L_2$). Criterion A would not predict a GC, while criterion B would predict it. (b) The size of the largest component plotted vs $N$ for Poisson networks having mean degree $z_1=1.25$ and $C=0.2$ (i.e., at the critical point according to criterion B). Indeed the size at the critical point correctly scales as $\sim N^{2/3}$ as is known for the case $z_1=1$ $C=0$ (see reference in 2). Note that criterion A would wrongly predict this regime to be below the critical point (since $z_2\approx 1.19<z_1$), and would suggest that all components should scale as $O(\log N)$.

Figure 3

The critical mean degree $z_1^{*}$ for the formation of a GC, plotted as a function of $C$, for Poisson degree distribution. Predictions of criterion A (grey line; $z_2$ estimated as in [6]). Predictions of criterion B [black line; $z_1^{*}=(1-C{)}^{-1}$ (see text)]. Empirical estimates of $z_1^{*}$ (circles) were obtained through the following procedure in order to overcome finite size effects: First the value of the size of the largest component was found for networks with $C=0$ at the known threshold $z_1^{*}=1$ (inset; horizontal grey line). This value was used to identify the critical threshold in comparable networks with $C>0$.

Figure 4

The size of the GC, after a fraction $r$ of the nodes were removed randomly, as a function of the mean degree for $C=0.1$ and $C=0.2$. Black (grey) solid lines are predictions (simulations). The dashed line is the case $C=0$, $r=0.2$ given for comparison.