Fractal Analysis of Overlapping Box Covering Algorithm for Complex Networks

Abstract

Due to extensive research on complex networks, fractal analysis with scale invariance is applied to measure the topological structure and self-similarity of complex networks. Fractal dimension can be used to quantify the fractal properties of the complex networks. However, in the existing box covering algorithms, accurately calculating the fractal dimension of complex networks is still an NP-hard problem. Therefore, in this paper, an improved overlapping box covering algorithm is proposed to explore a more accurate and effective method to calculate the fractal dimension of complex networks. Moreover, in order to verify the effectiveness of the algorithm, the improved algorithm is applied to six complex networks, and compared with other algorithms. Finally, the experimental results demonstrate that the improved overlapping box covering algorithm can cover the whole networks with fewer boxes. In addition, the improved overlapping box covering algorithm is a high accuracy and low time complexity method for calculating the fractal dimension of complex networks.

Keywords

• Overlapping box covering algorithm
• fractal dimension
• complex networks