Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter

Abstract

In this article, we present a novel box-covering algorithm for analyzing the fractal properties of complex networks. Unlike traditional algorithms that impose a predetermined box size, our approach assigns nodes to boxes identified by their nearest local hubs without enforcing rigid distance constraints. This flexibility leads to a key methodological shift: instead of fixing the box size in advance, we first determine the number of boxes and then compute their average size. We argue that this procedure is fully consistent with the recently proposed scaling theory of fractal complex networks and closely related to the concept of hidden metric spaces in which network nodes are embedded. We demonstrate that our approach not only significantly reduces computational complexity compared to existing methods, but also (despite relaxing constraints on box diameter) covers networks using boxes of more similar sizes than, for instance, the classical greedy coloring (GC) algorithm. To evaluate the effectiveness of our method, we analyze nine complex networks (three model-based and six real-world) representing a broad spectrum: from networks with confirmed fractality, through those with initially uncertain, but here confirmed, fractal properties (such as the Internet at the level of autonomous systems), to large-scale networks that have so far remained beyond the reach of existing algorithms due to their size.

14 pages, 8 figure

References in corpus (13)

• Benchmark graphs for testing community detection algorithms
• Hyperbolic Geometry of Complex Networks
• How to calculate the fractal dimension of a complex network: the box covering algorithm
• Self-similarity of complex networks and hidden metric spaces
• Avoiding catastrophic failure in correlated networks of networks
• Fractal and Transfractal Recursive Scale-Free Nets
• Fractality in complex networks: critical and supercritical skeletons
• Determination of multifractal dimensions of complex networks by means of the sandbox algorithm
• Scientific success from the perspective of the strength of weak ties
• Comparative Analysis of Box-Covering Algorithms for Fractal Networks
• Scaling theory of fractal complex networks
• Model-based reconstruction of real-world fractal complex networks
• Towards fractal origins of the community structure in complex networks: a model-based approach

Cited by in corpus (3)

• Model-based reconstruction of real-world fractal complex networks
• The Role of Fractal Dimension in Wireless Mesh Network Performance
• Universality classes in the time evolution of epidemic outbreaks on complex networks