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

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.