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.