Method To Calculate The Fractal Dimension Of Complex Networks

The fractality and self-similarity of complex networks have been widely investigated by using the box-covering method to evaluate the fractal dimension, the crux of which is how to locate the optimal solution or how to tile the network with the fewest boxes. In the cases of separated box and the ignorance of network’s own structure, the results yielded by the box-covering method possess great randomness or large errors. In this paper, we research on the crux from two aspects, i.e., overlapping box as well as the hierarchy from exterior to interior, with the purpose to obtain the fewer numbers of boxes as much as possible.First, 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 (OBCA); 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 to33.3%. The experimental results show that the overlapping-box-covering method is available and that the overlapping box outperforms the previous case, rendering the randomness dropped and the errors smaller.Next, we check whether the node sequences from exterior to interior could help the box-covering method to yield fewer boxes. At first, we define two kinds of hierarchies from exterior to interior, that is, distance hierarchy and degree hierarchy. Then, OBCA and CBB algorithm are employed to deterministic networks and real-world fractal networks mentioned above, respectively, with their node sequences in these two hierarchies. In any random sequences of distance hierarchy, both obtain the optimums for the former. For the latter, in these two hierarchies, CBB algorithm can produce fewer boxes while the numbers of boxes yielded by OBCA vary a little. The experimental results show that these two hierarchies from exterior to interior play effective roles, and are beneficial for the box-covering method to obtain fewer boxes, especially CBB algorithm.In the end, we think the overlapping box and the hierarchy from exterior to interior are two determinants for rendering the fractal dimension of complex networks more accurate.