Comparative Analysis of Box-Covering Algorithms for Fractal Networks

Abstract

Research on fractal networks is a dynamically growing field of network science. A central issue is to analyze fractality with the so-called box-covering method. As this problem is known to be NP-hard, a plethora of approximating algorithms have been proposed throughout the years. This study aims to establish a unified framework for comparing approximating box-covering algorithms by collecting, implementing, and evaluating these methods in various aspects including running time and approximation ability. This work might also serve as a reference for both researchers and practitioners, allowing fast selection from a rich collection of box-covering algorithms with a publicly available codebase.

arXiv commentThe paper has been published in Applied Network Science: https://appliednetsci.springeropen.com/articles/10.1007/s41109-021-00410-6

References in corpus (11)

• Power-law distributions in empirical data
• Self-similarity of complex networks
• Origins of fractality in the growth of complex networks
• How to calculate the fractal dimension of a complex network: the box covering algorithm
• Scaling theory of transport in complex networks
• Fractal and Transfractal Recursive Scale-Free Nets
• A box-covering algorithm for fractal scaling in scale-free networks
• Betweenness Centrality of Fractal and Non-Fractal Scale-Free Model Networks and Tests on Real Networks
• Determination of multifractal dimensions of complex networks by means of the sandbox algorithm
• Exploring self-similarity of complex cellular networks: The edge-covering method with simulated annealing and log-periodic sampling
• Transfinite fractal dimension of trees and hierarchical scale-free graphs

Cited by in corpus (7)

• Scaling theory of fractal complex networks
• Routing Algorithm for Software Defined Network Based on Boxcovering Algorithm
• Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter
• Eigenvalue Preferential Attachment Networks A Dandelion Structure
• Model-based reconstruction of real-world fractal complex networks
• Hub-collision avoidance and leaf-node options algorithm for fractal dimension and renormalization of complex networks
• The Role of Fractal Dimension in Wireless Mesh Network Performance