Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter
arXiv:2501.16030 · doi:10.1016/j.chaos.2025.116908
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.
arXiv comment14 pages, 8 figure
References in corpus (20)
- From Louvain to Leiden: guaranteeing well-connected communities
- Benchmark graphs for testing community detection algorithms
- Self-similarity of complex networks
- Hyperbolic Geometry of Complex Networks
- Origins of fractality in the growth of complex networks
- A small-world of weak ties provides optimal global integration of self-similar modules in functional brain 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
- Network Geometry
- Fractal and Transfractal Recursive Scale-Free Nets
- Fractality in complex networks: critical and supercritical skeletons
- Self-similar Scale-free Networks and Disassortativity
- Determination of multifractal dimensions of complex networks by means of the sandbox algorithm
- Scientific success from the perspective of the strength of weak ties
- Exponential random graph models for networks with community structure
- 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