Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter
Michał Łepek, Kordian Makulski, Agata Fronczak, Piotr Fronczak · 2025
Read Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter by Michał Łepek, Kordian Makulski, Agata Fronczak, Piotr Fronczak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-16030.txt.
Introduction
Michał Łepek, Kordian Makulski, Agata Fronczak, and Piotr Fronczak wrote this paper in two thousand twenty-five. It gives a new box-covering method to gauge the fractal dimension of complex networks, with a twist on the old recipe.
Classic methods fix a box size first, then count the boxes. Here nodes join the box of their nearest hub, with no hard span rule. The count of boxes is set first, and their mean size is read off after. The authors tie this to fresh scaling theory and to hidden metric spaces. On nine networks the method runs cheaper than rivals and packs boxes of more even size. It confirms fractal traits in networks once too big to test.
Catalog record
| CREATOR | Michał Łepek, Kordian Makulski, Agata Fronczak, Piotr Fronczak |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-16030
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter Michał Łepek, Kordian Makulski, Agata Fronczak, Piotr Fronczak 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. Journal: Chaos, Solitons & Fractals 1 Introduction In this paper, we propose a new method for estimating the box-counting dimension of fractal complex networks [ 1 , 2 , 3 ] and compare it with the currently most widely used technique based on greedy coloring (GC) [ 4 , 5 , 6 ] . Just as the well-known method for computing the fractal dimension of classical fractals embedded in Euclidean space operationalizes the concept of geometric self-similarity, our approach is grounded in the generalized notion of geometric self-similarity—an idea introduced and supported in the recent paper on scaling theory of fractal complex networks [ 7 ] . To rationalize and justify our approach, we begin by recalling the fundamental properties of classical fractals [ 8 , 9 ] and explaining how these differ from the structural properties of fractal complex networks [ 10 ] . We first introduce the concept of geometric self-similarity and the standard procedures for estimating fractal dimension in classical systems [ 11 , 12 ] . We then discuss the generalized notion of geometric self-similarity in fractal networks, which led to a consistent scaling theory [ 7 ] . Among the several scaling relations derived within that theory, we highlight those which—together with other well-established concepts such as hub repulsion [ 2 , 13 ] and hidden metric spaces [ 14 , 15 , 16 ] —served as theoretical guidelines in the development of our box-covering algorithm, which is the central result of this paper. In later sections, we demonstrate that our algorithm not only significantly outperforms the GC method in terms of computational complexity, but also yields objectively more efficient coverings. The core idea behind our algorithm is based on the so-called graph Voronoi diagrams, a geometric partitioning technique introduced in [ 17 ] and already adopted for community detection in complex networks [ 18 ] . Given the conceptual link between Voronoi tessellations and underlying metric spaces, the strong performance of our algorithm further supports the hypothesis that fractality in networks may emerge from latent geometric structure [ 19 ] . This connection opens up several promising directions for future research, which we discuss in the final section of the paper. The remainder of this paper is organized as follows. In Section 2 , we briefly discuss the theoretical background behind the classical box-covering method and highlight the motivation for inverting its logic by fixing the number of boxes (FNB) instead of their diameter in fractal complex networks. Readers primarily interested in the algorithm itself, its implementation, and its performance can skip this section without loss of continuity. In Section 3 , we describe the core implementation of the FNB algorithm step by step. Section 4 provides a detailed overview of the fractal complex networks, both model-based and real-world, used for testing the algorithm. In Section 5 , we present the results of applying the algorithm to estimate the box dimension of fractal networks and assess the quality of the obtained coverings. In Section 6 , we explore several possible extensions of the algorithm and introduce measures for evaluating its efficiency. Section 7 is devoted to comparing the FNB approach with the classical GC algorithm. Finally, Section 8 summarizes our main findings and discusses potential directions for further development and applications of the FNB methodology. The article also includes Supplementary Materials (SM) with additional charts and analyses referenced throughout the paper. 2 Conceptual and theoretical foundations of the algorithm 2.1 Geometric self-similarity of classical fractals A defining property of classical fractals—such as the Sierpinski gasket or critical percolation cluster—is geometric self-similarity [ 11 ] , meaning that their structure appears similar across different scales. This notion can be formalized by considering how a measurable property of the object, such as mass, length, or area, denoted m(L) changes with the observation scale L . Specifically, if the object of size L is rescaled by a factor \lambda>0 , so that the new observation scale becomes L^{\prime} , the quantity m(L) transforms according to the scale-invariant law [ 12 ] : m(L^{\prime})=\lambda^{d}\,m(L),\quad\text{where}\quad L^{\prime}=\lambda L, (1) and d is the fractal (similarity) dimension . This implies a power-law dependence of the observable: m(L)\sim L^{d}, (2) indicating that the measured quantity increases with the scale of observation. Observing the object at a larger scale (for \lambda>1 ) yields a coarser resolution and a proportionally larger total measure, as encoded by m(\lambda L) . In contrast, observing the object at finer resolution (for \lambda<1 reveals additional structural detail. As smaller features become accessible, the effective complexity increases—reflected in the growing number of smaller-scale components needed to represent the object. This increasing complexity at finer scales provides the foundation for various methods of quantifying fractality, including the cluster-growing and box-counting approaches, which operationalize the scaling principle described above. In particular, the cluster-growing method, which is typically used for classical fractals embedded in Euclidean space, involves measuring the average mass \langle m(\ell_{B})\rangle contained within a distance \ell_{B} from a designated seed element. If this mass scales as a power law with distance, i.e., \langle m(\ell_{B})\rangle\sim\ell_{B}^{\,d_{f}}, (3) then the above, empirically obtained scaling relation yields a direct estimate of the so-called spreading or growth fractal dimension d_{f} , which, for such systems, coincides with the fractal dimension of the object: d_{f}=d . A complementary and widely used method is box-counting. In this approach, the object is covered by a minimal number N_{B}(\ell_{B}) of non-overlapping boxes of side length \ell_{B} . Assuming that the content measured within a single box scales as m(\ell_{B})\sim\ell_{B}^{d} , cf. Eq. ( 2 ), it follows that the total number of boxes required to cover the object scales as N_{B}(\ell_{B})\sim\ell_{B}^{-d_{B}}, (4) where d_{B}=d is the box-counting dimension. This relation reflects the assumption that the total size (or mass) of the object remains constant across