Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915504025763840 |
|---|---|
| author | Lepek, Michal Makulski, Kordian Fronczak, Agata Fronczak, Piotr |
| author_facet | Lepek, Michal Makulski, Kordian Fronczak, Agata Fronczak, Piotr |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_16030 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter Lepek, Michal Makulski, Kordian Fronczak, Agata Fronczak, Piotr Disordered Systems and Neural Networks Computational Physics Data Analysis, Statistics and Probability 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. |
| title | Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter |
| topic | Disordered Systems and Neural Networks Computational Physics Data Analysis, Statistics and Probability |
| url | https://arxiv.org/abs/2501.16030 |