How to calculate the fractal dimension of a complex network: the box covering algorithm

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).

arXiv comment16 pages, 14 figures

References in corpus (10)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Self-similarity of complex networks
• Origins of fractality in the growth of complex networks
• Optimal Paths in Disordered Complex Networks
• Spectral Scaling in Complex Networks
• Self-similar Scale-free Networks and Disassortativity
• Competitive cluster growth in complex networks
• Scaling Invariance in Spectra of Complex Networks: A Diffusion Factorial Moment Approach

Cited by in corpus (73)

• Critical phenomena in complex networks
• A small-world of weak ties provides optimal global integration of self-similar modules in functional brain networks
• Network Geometry
• Small world-Fractal Transition in Complex Networks: Renormalization Group Approach
• Self-similar scaling of density in complex real-world networks
• Correlation dimension of complex networks
• Power law and exponential ejecta size distributions from the dynamic fragmentation of shock-loaded Cu and Sn metals under melt conditions
• Scaling of degree correlations and the influence on diffusion in scale-free networks
• Complex networks renormalization: flows and fixed points
• Horizontal visibility graphs transformed from fractional Brownian motions: Topological properties versus Hurst index
• Determination of multifractal dimensions of complex networks by means of the sandbox algorithm
• A new information dimension of complex networks
• Multifractality of complex networks
• Identifying influential nodes based on fuzzy local dimension in complex networks
• The evolutionary dynamics of protein-protein interaction networks inferred from the reconstruction of ancient networks
• Fractal and multifractal properties of a family of fractal networks
• Multifractal analysis of complex networks
• Modularity map of the network of human cell differentiation
• Complex systems approach to natural language
• Close or connected? Distance and connectivity effects on transport in networks
• Fractal scale-free networks resistant to disease spread
• Topological properties and fractal analysis of recurrence network constructed from fractional Brownian motions
• Unveiling the Multi-fractal Structure of Complex Networks
• Fractal and complex network analyses of protein molecular dynamics
• Detecting the ultra low dimensionality of real networks
• Scaling of Energy Dissipation in Nonequilibrium Reaction Networks
• Tsallis information dimension of complex networks
• IMDB network revisited: unveiling fractal and modular properties from a typical small-world network
• Fractal and multifractal analysis of complex networks: Estonian network of payments
• Anomalous behavior of trapping on a fractal scale-free network
• Architecture of the Florida Power Grid as a Complex Network
• Renormalization flows in complex networks
• What is the dimension of citation space?
• Comparative Analysis of Box-Covering Algorithms for Fractal Networks
• Multifractality and Laplace spectrum of horizontal visibility graphs constructed from fractional Brownian motions
• Scaling theory of fractal complex networks
• Scale-free networks embedded in fractal space
• Characterization of graphs for protein structure modeling and recognition of solubility
• Fractality and degree correlations in scale-free networks
• Random elastic networks : strong disorder renormalization approach
• Self-affine Fractals Embedded in Spectra of Complex Networks
• Structure of percolating clusters in random clustered networks
• Random Sequential Renormalization of Networks I: Application to Critical Trees
• Metabolic networks are almost nonfractal: A comprehensive evaluation
• Multifractality in random networks with power-law decaying bond strengths
• A Fixed-Mass multifractal approach for unweighted complex networks
• 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
• Random Sequential Renormalization and Agglomerative Percolation in Networks: Application to Erd"os-R'enyi and Scale-free Graphs
• Routing Algorithm for Software Defined Network Based on Boxcovering Algorithm
• Transfinite fractal dimension of trees and hierarchical scale-free graphs
• Measuring the dimension of partially embedded networks
• 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
• Beyond traditional box-covering: Determining the fractal dimension of complex networks using a fixed number of boxes of flexible diameter
• Bifractality of fractal scale-free networks
• Model-based reconstruction of real-world fractal complex networks
• Optimal box-covering algorithm for fractal dimension of 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
• Simple model of fractal networks formed by self-organized critical dynamics
• Multi-fractal analysis of weighted networks
• Complex physical properties of an adaptive, self-organizing biological system
• The conundrum of functional brain networks: small-world efficiency or fractal modularity
• The Role of Fractal Dimension in Wireless Mesh Network Performance
• Renormalization and small-world model of fractal quantum repeater networks
• Fractality of Massive Graphs: Scalable Analysis with Sketch-Based Box-Covering Algorithm
• Modelling the Self-similarity in Complex Networks Based on Coulomb's Law
• An improved vulnerability index of complex networks based on fractal dimension
• A Fractal and Scale-free Model of Complex Networks with Hub Attraction Behaviors