How to calculate the fractal dimension of a complex network: the box covering algorithm
arXiv:cond-mat/0701216 · doi:10.1088/1742-5468/2007/03/P03006
Abstract
Covering a network with the minimum possible number of boxes can reveal interesting features for the network structure, especially in terms of self-similar or fractal characteristics. Considerable attention has been recently devoted to this problem, with the finding that many real networks are self-similar fractals. Here we present, compare and study in detail a number of algorithms that we have used in previous papers towards this goal. We show that this problem can be mapped to the well-known graph coloring problem and then we simply can apply well-established algorithms. This seems to be the most efficient method, but we also present two other algorithms based on burning which provide a number of other benefits. We argue that the presented algorithms provide a solution close to optimal and that another algorithm that can significantly improve this result in an efficient way does not exist. We offer to anyone that finds such a method to cover his/her expenses for a 1-week trip to our lab in New York (details in http://jamlab.org).
16 pages, 14 figures
References in corpus (3)
Cited by in corpus (43)
- Critical phenomena in complex networks
- Network Geometry
- Scaling of degree correlations and the influence on diffusion in scale-free networks
- Complex networks renormalization: flows and fixed points
- Determination of multifractal dimensions of complex networks by means of the sandbox algorithm
- Identifying influential nodes based on fuzzy local dimension in complex networks
- Complex systems approach to natural language
- Fractal scale-free networks resistant to disease spread
- Topological properties and fractal analysis of recurrence network constructed from fractional Brownian motions
- Detecting the ultra low dimensionality of real networks
- Fractal and complex network analyses of protein molecular dynamics
- Tsallis information dimension of complex networks
- Scaling of Energy Dissipation in Nonequilibrium Reaction Networks
- Fractal and multifractal analysis of complex networks: Estonian network of payments
- Anomalous behavior of trapping on a fractal scale-free network
- Renormalization flows in complex networks
- Comparative Analysis of Box-Covering Algorithms for Fractal Networks
- Scaling theory of fractal complex networks
- Random elastic networks : strong disorder renormalization approach
- Self-affine Fractals Embedded in Spectra of Complex Networks
- Metabolic networks are almost nonfractal: A comprehensive evaluation
- Random Sequential Renormalization of Networks I: Application to Critical Trees
- A Fixed-Mass multifractal approach for unweighted complex networks
- Multifractality in random networks with power-law decaying bond strengths
- Finite-size scaling of geometric renormalization flows in complex networks
- Maximum matchings in scale-free networks with identical degree distribution
- Analytical estimation of the correlation dimension of integer lattices
- Propinquity drives the emergence of network structure and density
- Routing Algorithm for Software Defined Network Based on Boxcovering Algorithm
- Multifractality of complex networks is also due to geometry. The Geometric SandBox algorithm
- Vital Spreaders Identification in Complex Networks with Multi-Local Dimension
- An internet reviews topic hierarchy mining method based on modified continuous renormalization procedure
- Bifractality of fractal scale-free networks
- Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter
- Model-based reconstruction of real-world fractal complex networks
- On the Capacity of Fractal D2D Social Networks with Hierarchical Communications
- Hub-collision avoidance and leaf-node options algorithm for fractal dimension and renormalization of complex networks
- Complex physical properties of an adaptive, self-organizing biological system
- Modelling the Self-similarity in Complex Networks Based on Coulomb's Law
- An improved vulnerability index of complex networks based on fractal dimension
- The Role of Fractal Dimension in Wireless Mesh Network Performance
- Fractality of Massive Graphs: Scalable Analysis with Sketch-Based Box-Covering Algorithm
- The conundrum of functional brain networks: small-world efficiency or fractal modularity