Overlapping-box-covering method for the fractal dimension of complex networks

The fractality and self-similarity of complex networks have been widely investigated by evaluating the fractal dimension, the crux of which is how to locate the optimal solution or how to tile the network with the fewest boxes. The results yielded by the box-covering method with separated boxes possess great randomness or large errors. In this paper, we adopt the overlapping box to tile the entire network, called the overlapping-box-covering method. In such a case, for verifying its validity, we propose an overlapping-box-covering algorithm; we first apply it to three deterministic networks, then to four real-world fractal networks. It produces optimums or more accurate fractal dimension for the former; the quantities of boxes finally obtained for the latter are fewer and more deterministic, with the redundant box reaching up to 33.3%. The experimental results show that the overlapping-box-covering method is available and that the overlapping box outperforms the previous case, rendering the errors smaller. Moreover, we conclude that the overlapping box is an important determinant to acquire the fewest boxes for complex networks.

Figure 1

An example of covering a network $G$ with boxes at $l_B=2$. In the upper panel, shown in (a) and (b), are two possible solutions of the CBB algorithm with six, the minimum, and seven boxes, respectively. In the lower panel, two solutions corresponding to (a) and (b) are drawn in (a${}^{\prime }$) and (b${}^{\prime }$), respectively, when boxes are overlapping. There are six boxes (red ones) in (a${}^{\prime }$) same to that in (a). Meanwhile, it also has six boxes in (b${}^{\prime }$) when the RB, the middle one (green), is removed, whereas there is one more box in (b).

Figure 2

OBCA applied to $K_{m,t}$, $M_t$, and MII${}_t$. [(a)–(d)] The box counting of OBCA (red circle) in comparison with that of the CBB algorithm (green square). Shown are cases for (a) $K_{1,7}$, (b) $K_{2,6}$, (c) $M_{11}$, and (d) MII${}_5$. The difference (blue triangle) $\Delta N$ is the numbers of RBs among the boxes yielded by CBB algorithm, i.e., $\Delta N=N_{\mathrm{CBB}}-N_{\mathrm{OBCA}}$. Insets: The probability distribution of difference (blue triangle) $P\left(\Delta N\right)$ and the overlapping box (cyan diamond) $P\left(N_{\mathrm{olap}}\right)$. $P\left(\Delta N\right)=\Delta N/N_{\mathrm{CBB}},P\left(N_{\mathrm{olap}}\right)=N_{\mathrm{olap}}/N_B\left(l_B\right)$, where $N_{\mathrm{olap}}$ is the number of overlapping ones among the boxes produced by OBCA at a given $l_B$.

Figure 3

Probability distribution $P\left(N_B\right)$ of the number of boxes $N_B$ for the OBCA (red) and CBB algorithm (below, magenta), applied to $K_{1,6}$ for 5000 times. $P\left(N_B\right)$ is a straight line with its value 1 for the OBCA while it follows Gaussian distribution for the CBB algorithm.

Figure 4

OBCA applied to four fractal networks. [(a)–(d)] Their box-counting analyses of the OBCA (red circle) compared with that of the CBB algorithm (green square). Shown are cases for (a) A. fulgidus, (b) C. elegans, (c) E. coli, and (d) S. cerevisiae. The difference $\Delta N$ (blue triangle) is equal to $(N_{\mathrm{CBB}}-N_{\mathrm{OBCA}})$. Insets: The probability distribution of the difference (blue triangle) $P\left(\Delta N\right)$ and the overlapping box (magenta diamond) $P\left(N_{\mathrm{olap}}\right)$.

Figure 5

The comparisons between $P\left(N_B\right)$ of the OBCA (left, magenta) and that of the CBB algorithm (right, cyan), both applied to these four networks randomly $10000$ times. [(a)–(d)] The case of $l_B=2$. [(e)–(h)] The case of $l_B=3$ and 4. [(i)–(l)] The cases of $l_B=5$ and 6. They suggest that $P\left(N_B\right)$ of the OBCA follows the Gaussian distribution, similarly to that of the CBB algorithm. The black circles show the results yielded by the OBCA in the ascending execution sequence mentioned above.

Figure 6

The ratio of improvement $P(\Delta \langle N\rangle )$ between the means of $10000$ results produced by use of the OBCA and CBB algorithm, i.e., $\langle N_{\mathrm{OBCA}}\rangle$ and $\langle N_{\mathrm{CBB}}\rangle$. $\Delta \langle N\rangle =\langle N_{\mathrm{CBB}}\rangle -\langle N_{\mathrm{OBCA}}\rangle ,P\left(\Delta \langle N\rangle \right)=\Delta \langle N\rangle /\langle N_{\mathrm{CBB}}\rangle$. For (a) A. fulgidus, (b) C. elegans, (c) E. coli, and (d) S. cerevisiae $P(\Delta \langle N\rangle )$ at most reaches 24.5%, 21.3%, 33.3%, and 10.3%, respectively.

Figure 7

Koch network and the polygon network at $t=3$, i.e., $K_{1,3}$ and $M_3$.