Skeleton and Fractal Scaling in Complex Networks

We find that the fractal scaling in a class of scale-free networks originates from the underlying tree structure called a skeleton, a special type of spanning tree based on the edge betweenness centrality. The fractal skeleton has the property of the critical branching tree. The original fractal networks are viewed as a fractal skeleton dressed with local shortcuts. An in silico model with both the fractal scaling and the scale-invariance properties is also constructed. The framework of fractal networks is useful in understanding the utility and the redundancy in networked systems.

Figure 1

(a)–(e) Box counting analysis of original networks (○, red) and their skeleton (▽, blue) and random spanning tree (△, orange). Shown are cases for (a) the World Wide Web, (b) the metabolic network of Escherichia coli, and (c) the protein interaction network of Homo sapiens, (d) the Internet at the autonomous systems level as of the year 2004, and (e) the static model network with $\gamma =2.3$ and $⟨k⟩=4$. In (a)–(c), we also show two guidelines for the fractal scaling of the original network (black) and its random spanning tree (gray). The slope of each guideline is (a) $-4.1$, (b) $-3.5$, and (c) $-2.3$. In (d)–(e), the black line is a fit to the exponential function and the gray one is to a power law. (a′)–(e′) Branching analysis. The mean branching number as a function of distance from the root for the skeleton (▽, blue) and the random spanning tree (△, orange) of the networks in (a)–(e). For (a′)–(c′), both the skeleton and the random spanning tree fulfill the criticality condition $⟨m⟩=1$ (horizontal line) as the distance from the root increases, while for (d′)–(e′), the mean branching number of the skeleton decays to zero with no plateau at $⟨m⟩=1$.

Figure 2

Fractal network model. (a) Uncorrelated scale-free tree with the degree exponent $\gamma =2.3$ and the number of vertices $N=164$. It is grown by the multiplicative branching rule [19], with the branching probability $b_m\sim m^{-\gamma }$. (b) Fractal model network created by adding local shortcuts (green) to the tree in (a). (c) A nonfractal model network created by adding random shortcuts (blue) allowing global connection. (d) The generic configuration of the network in (c) generated by Pajek, and the absence of inherent modular structure. In (b)–(d), the color of each vertex is that of the corresponding vertex in (a). (e) Schematic illustration of the growth rule of the fractal network model. The shaded region indicates the rest of the network generated so far. (f) The fractal scaling analysis of networks with larger size $N=311,043$, constructed in the same manner as those in (a)–(c). Squares (blue) correspond to the fractal network model in (b) with $p=0.5$, circles (black) to its skeleton, and the diamonds (red) to the nonfractal network model in (c) with $q=1$. The solid line is the guideline with slope $\approx -2.8$.