Fractality in complex networks: Critical and supercritical skeletons

Fractal scaling—a power-law behavior of the number of boxes needed to tile a given network with respect to the lateral size of the box—is studied. We introduce a box-covering algorithm that is a modified version of the original algorithm introduced by Song et al. [Nature (London) 433, 392 (2005)]; this algorithm enables easy implementation. Fractal networks are viewed as comprising a skeleton and shortcuts. The skeleton, embedded underneath the original network, is a special type of spanning tree based on the edge betweenness centrality; it provides a scaffold for the fractality of the network. When the skeleton is regarded as a branching tree, it exhibits a plateau in the mean branching number as a function of the distance from a root. For nonfractal networks, on the other hand, the mean branching number decays to zero without forming a plateau. Based on these observations, we construct a fractal network model by combining a random branching tree and local shortcuts. The scaffold branching tree can be either critical or supercritical, depending on the small worldness of a given network. For the network constructed from the critical (supercritical) branching tree, the average number of vertices within a given box grows with the lateral size of the box according to a power-law (an exponential) form in the cluster-growing method. The critical and supercritical skeletons are observed in protein interaction networks and the World Wide Web, respectively. The distribution of box masses, i.e., the number of vertices within each box, follows a power law $P_m\left(M\right)\sim M^{-\eta }$. The exponent $\eta$ depends on the box lateral size ${\ell }_B$. For small values of ${\ell }_B$, $\eta$ is equal to the degree exponent $\gamma$ of a given scale-free network, whereas $\eta$ approaches the exponent $\tau =\gamma ∕(\gamma -1)$ as ${\ell }_B$ increases, which is the exponent of the cluster-size distribution of the random branching tree. Finally, we study the perimeter $H_{\alpha }$ of a given box $\alpha$, i.e., the number of edges connected to different boxes from a given box $\alpha$ as a function of the box mass $M_{B,\alpha }$. It is obtained that the average perimeter over the boxes with box mass $M_B$ is likely to scale as $⟨H\left(M_B\right)⟩\sim M_B$, irrespective of the box size ${\ell }_B$.

Figure 1

(Color online) Schematic illustration of the box-covering algorithm introduced in this work. Vertices are selected randomly, for example, from vertex 1 to 4 successively. Vertices within distance ${\ell }_B=1$ from vertex 1 are assigned to a box represented by a solid (red) circle. Vertices from vertex 2, not yet assigned to their respective box, are represented by a dashed-dotted-dotted (black) closed curve, vertices from vertex 3 are represented by a dashed-dotted (green) circle, and vertices from vertex 4 are represented by dashed (blue) ellipse.

Figure 2

(Color online) Comparison of the box-covering methods introduced by Song et al. [1] $(◻)$ and in this paper $(엯)$ for the WWW. The results obtained from the two box-covering methods applied to the WWW are plotted here. The two methods yield the same fractal dimension $d_B\approx 4.1$.

Figure 3

(Color online) Fractal scaling analysis (left-hand column) and mean branching number (right-hand column) of real-world networks including fractal (a)–(d) and nonfractal (e)–(i) networks. For each network, the original network $(엯)$, the skeleton $(▿)$, and a random spanning tree $(▵)$ are studied. In (a)–(d), the straight lines, drawn for guidance, have slopes of $-4.10$, $-3.53$, $-2.28$, and $-2.01$, respectively, for the original networks. Those for the random spanning trees have slopes of $-3.76$, $-3.94$, $-2.24$, and $-1.84$. In (e)–(h), the fits to the exponential function for the original network and to a power-law function for the random spanning tree are shown. In the right-hand panels $\left({\mathrm{a}}^{\prime }\right)$–$\left({\mathrm{i}}^{\prime }\right)$, the horizontal line at 1 is drawn for reference.

Figure 4

(Color online) Fractal scaling analysis (a)–(e) and mean branching number $\left({\mathrm{a}}^{\prime }\right)$–$\left({\mathrm{e}}^{\prime }\right)$ of the SF network models. The symbols used are similar to those in Fig. 3 except in (d). The different symbols in (d) represent different parameters in the model. Red circle, blue square, and green diamond symbols represent generations $m=1$, 2, and 3 of the model, respectively. In (a) and (c), the exponential fit for the original network and a power-law fit for the random spanning tree are shown. For (b) and (d), which are tree networks, the exponential fit is shown. In (e), the exponential fit for the original network is shown. Note that in (e), the box numbers for the original network, the skeleton, and the random spanning tree all overlap. In panels $\left({\mathrm{a}}^{\prime }\right)$–$\left({\mathrm{e}}^{\prime }\right)$, a horizontal line at 1 is drawn for reference.

Figure 5

(Color online) Length distribution of shortcuts. The length of a shortcut is defined as the shortest distance along the skeleton between the two vertices connected by the shortcut. The arrows indicate the diameter of the skeleton of each network. Here, $n_s\left(d\right)$ and $n_T$ are the number of shortcuts with length $d$ and the total number of shortcuts, respectively.

Figure 6

(Color) Snapshots of the fractal network models. (a) A critical branching tree with $\gamma =2.3$ and $N=164$ created in step (i). (b) A network created by adding local shortcuts (blue) following the rule (ii) to the branching tree in (a). Parameter $p=0.5$ is used. This network is still fractal. (c) A network created by adding global shortcuts (red) following the rule (iii) to the network in (b). Parameter $q=0.02$ is used. This network is no longer fractal, but small world. (d) A supercritical branching tree with mean branching number $⟨n⟩=2$, which is fractal as well as small world. (e) A dressed network to network (d) by local shortcuts (blue) generated with $p=0.5$. The network is fractal as well as small world. (f) A network created by adding global shortcuts (red) to the network in (e). $q=0.02$ is used. In (a)–(f), the colors of each vertex represent distinct generations from the root.

Figure 7

(Color online) Fractal scaling analysis (a) and mean branching number (b) for the fractal models based on the critical branching tree with only local shortcuts with $p=0.5$ and $q=0$ $(◻)$, and with 1% of global shortcuts with $p=0.5$ and $q=0.01$ $(▵)$. The bare critical branching tree is represented by $(엯)$. The solid line in (a) is guideline with a slope of –3.2. The measured degree exponent is $\gamma \approx 2.4$ and system size is $N=3\times {10}^5$.

Figure 8

(Color online) Fractal scaling analysis (a) and (c), and mean branching number (b) and (d) for the fractal models generated from a supercritical branching tree with $⟨n⟩=2$, dressed by shortcuts. The data are for the bare supercritical tree $(엯)$ and dressed networks with $p=0.5$ and $q=0$ $(◻)$, $p=0.5$ and $q=0.01$ $(▵)$, and $p=0$ and $q=0.05$ $(◇)$. The solid lines in (a) and (c) are guidelines with slopes of –4.2 each. The degree exponent is $\gamma =2.3$ and system size is $N=1\times {10}^5$.

Figure 9

(Color online) Average box mass $⟨M_C\left({\ell }_C\right)⟩$ in the cluster-growing method divided by the total number of vertices $N$, as a function of the distance ${\ell }_C$. Plots of (a) and (b) are drawn on a semilogarithmic scale and those of (c) and (d) on a double-logarithmic scale, respectively. Filled and open symbols represent the original network and the skeleton of each network, respectively. The solid lines for reference in (c) and (d) have slopes of 1.9 and 2.3, respectively.

Figure 10

(Color online) Average box mass $⟨M_B\left({\ell }_B\right)⟩$ divided by the total number of vertices $N$, as a function of box size ${\ell }_B$ in the box-covering method. Filled and open symbols represent the original network and the skeleton of each network, respectively. The solid lines (drawn for reference) have slopes of 4.10, 3.53, 2.24, and 2.03 for (a), (b), (c), and (d), respectively.

Figure 11

(Color online) Cumulative fraction $F_c\left(f\right)$ of the vertices counted $f$ times in the cluster-growing algorithm. $F_c\left(f\right)$ follows a power law in the small $f$ region, where the slope depends on box size ${\ell }_C$. However, for large values of $f$, the data largely deviate from the value extrapolated from the power-law behavior. Data are presented for ${\ell }_C=2$ $(●)$, ${\ell }_C=3$ $(∎)$, and ${\ell }_C=5$ $(▴)$.

Figure 12

(Color online) Box mass distribution in the cluster-growing method (a) and box-covering method (b) for the WWW. Data in (a) are for ${\ell }_C=2$ and those in (b) are for ${\ell }_B=2$ $(●)$ and ${\ell }_B=5$ $(∎)$. The solid lines are guidelines with slopes of $-2.2$ and $-1.8$, respectively.

Figure 13

(Color online) Average box mass versus box lateral size in the cluster-growing method (a) and the box-covering method (b) for the fractal network model constructed from a critical branching tree, dressed by shortcuts with $p=0.5$ and $q=0$ $(●)$ and $p=0.5$ and $q=0.01$ $(∎)$. Degree exponent is $\gamma =2.3$ and system size is $N=3\times {10}^5$. Solid lines in (a) have slopes of 3.3 and 2.4, respectively, and the solid line in (b) has a slope of 3.3.

Figure 14

(Color online) Average box mass as a function of box size in the cluster-growing method (a) and the box-covering method (b) for the model network constructed from a supercritical branching tree, dressed by shortcuts with $p=0.5$ and $q=0$ $(●)$ and $p=0.5$ and $q=0.01$ $(∎)$. Degree exponent is $\gamma =2.3$, and system size $N=1\times {10}^5$. The solid line in (b) has a slope of 4.0, which is drawn for guidance.

Figure 15

(Color online) Box mass distribution in the cluster-growing method (a) and box-covering method (b) for the fractal model network grown from a critical branching tree with $\gamma =2.3$ and dressed by shortcuts generated with $p=0.5$ and $q=0.001$. The data in (b) are for ${\ell }_B=2$ $(●)$ and ${\ell }_B=5$ $(∎)$. Their slopes are –2.3 and –1.8, respectively. The system size is $N\approx 3\times {10}^5$.

Figure 16

(Color online) (a) Average box mass versus box size in the cluster-growing $(\times )$ and box-covering $(∎)$ methods for a bare critical branching tree with $\gamma =2.6$. Solid lines, drawn for guidance, have slopes of 2.3 $(\times )$ and 2.6 $(∎)$, respectively. (b) Box mass distribution for the bare tree of (a). Solid guidelines have slopes of –2.8 for ${\ell }_B=2$ $(●)$, –2.6 for ${\ell }_B=5$ $(∎)$, and –1.6 for ${\ell }_B=32$ $(▴)$.

Figure 17

(Color online) Box mass distribution in the cluster-growing method (a) and box-covering method (b) for the fractal model network grown from a supercritical branching tree with $⟨n⟩=2$ and $\gamma =2.3$, which is dressed by shortcuts with the parameters $p=0.5$ and $q=0$. The box size in (b) is ${\ell }_M=2$ $(●)$ and ${\ell }_M=5$ $(∎)$. Solid lines in (b) have slopes –2.3 and –1.8, drawn for guidance. The system size is $N\approx 1\times {10}^5$.

Figure 18

(Color online) Plot of the average perimeter $⟨H\left(M_B\right)⟩$ versus box mass $M_B$ for the WWW (a) and the model network with the parameters of $\gamma =2.3$, $p=0.5$, and $q=0.0$ (b). Data are for box sizes ${\ell }_B=2$ $(●)$, ${\ell }_B=3$ $(∎)$, ${\ell }_B=5$ $(▴)$. The solid line (drawn as reference) has a slope of 1.0 for both (a) and (b).