Exploring self-similarity of complex cellular networks: The edge-covering method with simulated annealing and log-periodic sampling

Abstract

Song, Havlin and Makse (2005) have recently used a version of the box-counting method, called the node-covering method, to quantify the self-similar properties of 43 cellular networks: the minimal number $N_V$ of boxes of size $\ell$ needed to cover all the nodes of a cellular network was found to scale as the power law $N_V\sim (\ell +1{)}^{-D_V}$ with a fractal dimension $D_V=3.53\pm 0.26$. We propose a new box-counting method based on edge-covering, which outperforms the node-covering approach when applied to strictly self-similar model networks, such as the Sierpinski network. The minimal number $N_E$ of boxes of size $\ell$ in the edge-covering method is obtained with the simulated annealing algorithm. We take into account the possible discrete scale symmetry of networks (artifactual and/or real), which is visualized in terms of log-periodic oscillations in the dependence of the logarithm of $N_E$ as a function of the logarithm of $\ell$. In this way, we are able to remove the bias of the estimator of the fractal dimension, existing for finite networks. With this new methodology, we find that $N_E$ scales with respect to $\ell$ as a power law $N_E\sim {\ell }^{-D_E}$ with $D_E=2.67\pm 0.15$ for the 43 cellular networks previously analyzed by Song, Havlin and Makse (2005). Bootstrap tests suggest that the analyzed cellular networks may have a significant log-periodicity qualifying a discrete hierarchy with a scaling ratio close to 2. In sum, we propose that our method of edge-covering with simulated annealing and log-periodic sampling minimizes the significant bias in the determination of fractal dimensions in log-log regressions.

19 elsart pages including 9 eps figures

References in corpus (17)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• The large-scale organization of metabolic networks
• Self-similarity of complex networks
• Origins of fractality in the growth of complex networks
• Discrete scale invariance and complex dimensions
• Skeleton and fractal scaling in complex networks
• Fractality in complex networks: critical and supercritical skeletons
• Self-similar Scale-free Networks and Disassortativity
• Artifactual log-periodicity in finite size data: Relevance for earthquake aftershocks
• Geographical Coarsegraining of Complex Networks
• Statistical Significance of Periodicity and Log-Periodicity with Heavy-Tailed Correlated Noise
• Evidence of Intermittent Cascades from Discrete Hierarchical Dissipation in Turbulence
• Punctuated vortex coalescence and discrete scale invariance in two-dimensional turbulence
• Log-periodic oscillations in degree distributions of hierarchical scale-free networks
• Discrete Scale Invariance in Scale Free Graphs

Cited by in corpus (19)

• Multifractal detrended cross-correlation analysis for two nonstationary signals
• Bubble Diagnosis and Prediction of the 2005-2007 and 2008-2009 Chinese stock market bubbles
• Statistical properties of visibility graph of energy dissipation rates in three-dimensional fully developed turbulence
• Self-similar scaling of density in complex real-world networks
• 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
• Multifractal analysis of complex networks
• Topological properties and fractal analysis of recurrence network constructed from fractional Brownian motions
• Fractal and complex network analyses of protein molecular dynamics
• Fractal and multifractal analysis of complex networks: Estonian network of payments
• Statistical significance of rich-club phenomena in complex networks
• Comparative Analysis of Box-Covering Algorithms for Fractal Networks
• A Fixed-Mass multifractal approach for unweighted complex networks
• Bifractality of fractal scale-free networks
• Discrete Scale Invariance in Scale Free Graphs
• Optimal box-covering algorithm for fractal dimension of complex networks
• Upper Bound of Relative Error of Random Ball Coverage for Calculating Fractal Network Dimension
• A Fractal and Scale-free Model of Complex Networks with Hub Attraction Behaviors
• Modelling the Self-similarity in Complex Networks Based on Coulomb's Law