Self-similarity of complex networks
arXiv:cond-mat/0503078 · doi:10.1038/nature03248
Abstract
Complex networks have been studied extensively due to their relevance to many real systems as diverse as the World-Wide-Web (WWW), the Internet, energy landscapes, biological and social networks \cite{ab-review,mendes,vespignani,newman,amaral}. A large number of real networks are called ``scale-free'' because they show a power-law distribution of the number of links per node \cite{ab-review,barabasi1999,faloutsos}. However, it is widely believed that complex networks are not {\it length-scale} invariant or self-similar. This conclusion originates from the ``small-world'' property of these networks, which implies that the number of nodes increases exponentially with the ``diameter'' of the network \cite{erdos,bollobas,milgram,watts}, rather than the power-law relation expected for a self-similar structure. Nevertheless, here we present a novel approach to the analysis of such networks, revealing that their structure is indeed self-similar. This result is achieved by the application of a renormalization procedure which coarse-grains the system into boxes containing nodes within a given "size". Concurrently, we identify a power-law relation between the number of boxes needed to cover the network and the size of the box defining a finite self-similar exponent. These fundamental properties, which are shown for the WWW, social, cellular and protein-protein interaction networks, help to understand the emergence of the scale-free property in complex networks. They suggest a common self-organization dynamics of diverse networks at different scales into a critical state and in turn bring together previously unrelated fields: the statistical physics of complex networks with renormalization group, fractals and critical phenomena.
28 pages, 12 figures, more informations at http://www.jamlab.org
References in corpus (4)
Cited by in corpus (336)
- Fast unfolding of communities in large networks
- Understanding individual human mobility patterns
- Uncovering the overlapping community structure of complex networks in nature and society
- Catastrophic cascade of failures in interdependent networks
- Spatial Networks
- Characterization of complex networks: A survey of measurements
- Critical phenomena in complex networks
- From time series to complex networks: the visibility graph
- Vital nodes identification in complex networks
- Extracting the multiscale backbone of complex weighted networks
- Scale-free networks are rare
- Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
- New Model of Internet Topology Using k-shell Decomposition
- MEDUSA - New Model of Internet Topology Using k-shell Decomposition
- Network Physiology reveals relations between network topology and physiological function
- Robustness of a Network of Networks
- Random walks and diffusion on networks
- First-passage times in complex scale-invariant media
- Origins of fractality in the growth of complex networks
- Statistical properties of sampled networks
- A small-world of weak ties provides optimal global integration of self-similar modules in functional brain networks
- Unification of theoretical approaches for epidemic spreading on complex networks
- How to calculate the fractal dimension of a complex network: the box covering algorithm
- Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
- Self-similarity of complex networks and hidden metric spaces
- Analysis of community structure in networks of correlated data
- Spreading dynamics in complex networks
- Statistically validated networks in bipartite complex systems
- Weighted network modules
- Application of Random Matrix Theory to Biological Networks
- Skeleton and fractal scaling in complex networks
- Robustness of a Tree-like Network of Interdependent Networks
- Network resilience
- Network Geometry
- Fractal and Transfractal Recursive Scale-Free Nets
- Social tipping processes for sustainability: An analytical framework
- Impact of Single Links in Competitive Percolation -- How complex networks grow under competition
- Self-organized adaptation of a simple neural circuit enables complex robot behaviour
- Percolation in Interdependent and Interconnected Networks: Abrupt Change from Second to First Order Transition
- Global mean first-passage times of random walks on complex networks
- Statistical physics approaches to the complex Earth system
- Spectral entropies as information-theoretic tools for complex network comparison
- Small world-Fractal Transition in Complex Networks: Renormalization Group Approach
- Percolation of Partially Interdependent Scale-free Networks
- Communities, Knowledge Creation, and Information Diffusion
- Griffiths phases on complex networks
- Identify influential spreaders in complex networks, the role of neighborhood
- Google matrix analysis of directed networks
- Statistical properties of visibility graph of energy dissipation rates in three-dimensional fully developed turbulence
- Percolation of a general network of networks
- Fractality in complex networks: critical and supercritical skeletons
- Spectral coarse-graining of complex networks
- Complex Networks from Classical to Quantum
- Percolation of partially interdependent networks under targeted attack
- Structure of shells in complex networks
- Spectral Scaling in Complex Networks
- Exact solution for mean first-passage time on a pseudofractal scale-free web
- Community structure and ethnic preferences in school friendship networks
- Multiscale unfolding of real networks by geometric renormalization
- Feigenbaum graphs: a complex network perspective of chaos
- Directed network modules
- Google in a Quantum Network
- Resolving structural variability in network models and the brain
- Self-similar scaling of density in complex real-world networks
- Correlation dimension of complex networks
- Information filtering in complex weighted networks
- Reconstruction methods for networks: the case of economic and financial systems
- Geometric renormalization unravels self-similarity of the multiscale human connectome
- Quantum Google in a Complex Network
- A box-covering algorithm for fractal scaling in scale-free networks
- True scale-free networks hidden by finite size effects
- Multifractal Network Generator
- Betweenness Centrality of Fractal and Non-Fractal Scale-Free Model Networks and Tests on Real Networks
- Robustness of partially interdependent network formed of clustered networks
- Identification of clusters of investors from their real trading activity in a financial market
- Chaperones as integrators of cellular networks: Changes of cellular integrity in stress and diseases
- Self-similar Scale-free Networks and Disassortativity
- Scaling of degree correlations and the influence on diffusion in scale-free networks
- Complex networks renormalization: flows and fixed points
- Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
- The influence of the broadness of the degree distribution on network's robustness: comparing localized attack and random attack
- Horizontal visibility graphs transformed from fractional Brownian motions: Topological properties versus Hurst index
- Persistent Homology in Sparse Regression and its Application to Brain Morphometry
- Determination of multifractal dimensions of complex networks by means of the sandbox algorithm
- -core percolation on complex networks: Comparing random, localized and targeted attacks
- Laplacian Renormalization Group for heterogeneous networks
- Analytical properties of horizontal visibility graphs in the Feigenbaum scenario
- The structural role of weak and strong links in a financial market network
- Weighted Fractal Networks
- Aging cellular networks: chaperones as major participants
- Competitive cluster growth in complex networks
- Exploring self-similarity of complex cellular networks: The edge-covering method with simulated annealing and log-periodic sampling
- Spectral dimensions of hierarchical scale-free networks with shortcuts
- A new information dimension of complex networks
- Topological and geometric measurements of force chain structure
- Complete trails of co-authorship network evolution
- Multifractality of complex networks
- Symmetry based Structure Entropy of Complex Networks
- Critical dynamics of the k-core pruning process
- The evolutionary dynamics of protein-protein interaction networks inferred from the reconstruction of ancient networks
- Analyses of Some Structural Properties on a Class of Hierarchical Scale-free Networks
- Community characterization of heterogeneous complex systems
- Drug-therapy networks and the predictions of novel drug targets
- Emergence of Symmetry in Complex Networks
- Fractal and multifractal properties of a family of fractal networks
- Centrality measure based on continuous-time quantum walks and experimental realization
- Networking - A Statistical Physics Perspective
- Fractal Boundaries of Complex Networks
- Complex Networks and Symmetry I: A Review
- Network Quotients: Structural Skeletons of Complex Systems
- Multifractal analysis of complex networks
- Modularity map of the network of human cell differentiation
- The interplay of microscopic and mesoscopic structure in complex networks
- Synchronization Patterns: From Network Motifs to Hierarchical Networks
- Mean first-passage time for random walks on the T-graph
- Distinct scalings for mean first-passage time of random walks on scale-free networks with the same degree sequence
- Network structure of subway passenger flows
- Multifractal analysis of weighted networks by a modified sandbox algorithm
- Percolation theory applied to measures of fragmentation in social networks
- Complex systems approach to natural language
- Griffiths singularities and algebraic order in the exact solution of an Ising model on a fractal modular network
- International trade network: fractal properties and globalization puzzle
- Topological properties and fractal analysis of recurrence network constructed from fractional Brownian motions
- Localizations on Complex Networks
- Scaling theory of continuum dislocation dynamics in three dimensions: Self-organized fractal pattern formation
- Fractal scale-free networks resistant to disease spread
- Counting spanning trees in self-similar networks by evaluating determinants
- Structural preferential attachment: Network organization beyond the link
- Unveiling the Multi-fractal Structure of Complex Networks
- Detecting the ultra low dimensionality of real networks
- Fractal and complex network analyses of protein molecular dynamics
- Scaling of Energy Dissipation in Nonequilibrium Reaction Networks
- Process Flow Diagram of an Ammonia Plant as a Complex Network
- Tsallis information dimension of complex networks
- Classification of Complex Networks Based on Topological Properties
- Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks
- IMDB network revisited: unveiling fractal and modular properties from a typical small-world network
- Role of fractal dimension in random walks on scale-free networks
- Fractal and multifractal analysis of complex networks: Estonian network of payments
- Mean first-passage time for random walks in general graphs with a deep trap
- How higher goals are constructed and collapse under stress: a hierarchical Bayesian control systems perspective
- Enhancing the robustness of scale-free networks
- The Network of Scientific Collaborations within the European Framework Programme
- Edwards thermodynamics of the jamming transition for frictionless packings: ergodicity test and role of angoricity and compactivity
- Anomalous behavior of trapping on a fractal scale-free network
- Scaling Invariance in Spectra of Complex Networks: A Diffusion Factorial Moment Approach
- Scaling laws for diffusion on (trans)fractal scale-free networks
- Statistical significance of rich-club phenomena in complex networks
- Fluids mobilization in Arabia Terra, Mars: depth of pressurized reservoir from mounds self-similar clustering
- Renormalization flows in complex networks
- Swimming path statistics of an active Brownian particle with time-dependent self-propulsion
- Exponential random graph models for networks with community structure
- Multifractal Characterization of Protein Contact Networks
- The nature and nurture of network evolution
- Deterministic hierarchical networks
- Meta-validation of bipartite network projections
- The robustness of interdependent networks under the interplay between cascading failures and virus propagation
- Empirical study on clique-degree distribution of networks
- Dynamics and Processing in Finite Self-Similar Networks
- Comparative Analysis of Box-Covering Algorithms for Fractal Networks
- Prokaryotic regulatory systems biology: Common principles governing the functional architectures of Bacillus subtilis and Escherichia coli unveiled by the natural decomposition approach
- The Fractional Preferential Attachment Scale-Free Network Model
- Predicting link directions via a recursive subgraph-based ranking
- Multifractality and Laplace spectrum of horizontal visibility graphs constructed from fractional Brownian motions
- Diffusion geometry of multiplex and interdependent systems
- Transition from fractal to non-fractal scalings in growing scale-free networks
- Power-law Scaling to Assist with Key Challenges in Artificial Intelligence
- Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
- A geometric growth model interpolating between regular and small-world networks
- Quantifying long-range correlations in complex networks beyond nearest neighbors
- Mesoscopic analysis of networks: applications to exploratory analysis and data clustering
- Statistics of cycles in large networks
- Scale-free networks embedded in fractal space
- Dense networks with scale-free feature
- A simple model clarifies the complicated relationships of complex networks
- Scaling theory of fractal complex networks
- Quantum centrality testing on directed graphs via PT-symmetric quantum walks
- Analysis of diffusion and trapping efficiency for random walks on non-fractal scale-free trees
- Percolation and the effective structure of complex networks
- Optimal high-level descriptions of dynamical systems
- Anomalous biased diffusion in networks
- Statistically consistent coarse-grained simulations for critical phenomena in complex networks
- Morphological complex networks: Can individual morphology determine the general connectivity and dynamics of networks?
- Planar unclustered scale-free graphs as models for technological and biological networks
- A unified data representation theory for network visualization, ordering and coarse-graining
- Characterization of graphs for protein structure modeling and recognition of solubility
- Driven synchronization in random networks of oscillators
- Internet Topology over Time
- Tracing the Evolution of Physics on the Backbone of Citation Networks
- Fractality and degree correlations in scale-free networks
- Scale-Free Networks beyond Power-Law Degree Distribution
- A general model of hierarchical fractal scale-free networks
- Self-affine Fractals Embedded in Spectra of Complex Networks
- Random elastic networks : strong disorder renormalization approach
- Effects of reciprocity on random walks in weighted networks
- Analysis of heat kernel highlights the strongly modular and heat-preserving structure of proteins
- Topological fractal networks introduced by mixed degree distribution
- Self-similar non-equilibrium dynamics of a many-body system with power-law interactions
- Fractal Weyl law for Linux Kernel Architecture
- Structure of percolating clusters in random clustered networks
- Structural preferential attachment: Stochastic process for the growth of scale-free, modular and self-similar systems
- Metabolic networks are almost nonfractal: A comprehensive evaluation
- Irreversible Aggregation and Network Renormalization
- Agglomerative Percolation on Bipartite Networks: A Novel Type of Spontaneous Symmetry Breaking
- Random Sequential Renormalization of Networks I: Application to Critical Trees
- Exact eigenvalue spectrum of a class of fractal scale-free networks
- The bounds of heavy-tailed return distributions in evolving complex networks
- Networks with many structural scales: a Renormalization Group perspective
- Multiscale network renormalization: scale-invariance without geometry
- Network Renormalization
- A Fixed-Mass multifractal approach for unweighted complex networks
- Phase-Space Networks of Geometrical Frustrated Systems
- Centrality properties of directed module members in social networks
- Multifractality in random networks with power-law decaying bond strengths
- Partition of Networks into Basins of Attraction
- Overlapping modularity at the critical point of k-clique percolation
- Spectral coarse graining for random walk in bipartite networks
- Finite-size scaling of geometric renormalization flows in complex networks
- Chimera states in neural networks and power systems
- Complex networks as an emerging property of hierarchical preferential attachment
- A computationally-efficient sandbox algorithm for multifractal analysis of large-scale complex networks with tens of millions of nodes
- Anomalous electrical and frictionless flow conductance in complex networks
- Nested Subgraphs of Complex Networks
- Unsupervised clustering analysis: a multiscale complex networks approach
- Maximum matchings in scale-free networks with identical degree distribution
- Analytical estimation of the correlation dimension of integer lattices
- Random Sequential Renormalization and Agglomerative Percolation in Networks: Application to Erd"os-R'enyi and Scale-free Graphs
- Asymptotic scaling behavior of self-avoiding walks on critical percolation clusters
- Growing homophilic networks are natural navigable small worlds
- The rigorous solution for the average distance of a Sierpinski network
- Scaling of disordered recursive networks
- The interplay of university and industry through the FP5 network
- Financial Markets and the Phase Transition between Water and Steam
- Scaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk
- Subgraphs and motifs in a dynamic airline network
- Dismantling Efficiency and Network Fractality
- Modeling Network Evolution Using Graph Motifs
- Degree correlations in graphs with clique clustering
- Fast Reversible Learning based on Neurons functioning as Anisotropic Multiplex Hubs
- Mapping dynamical systems onto complex networks
- Spectra, hitting times, and resistance distances of -subdivision graphs
- Effects of node position on diffusion and trapping efficiency for random walks on fractal scale-free trees
- The fractal time growth of COVID-19 pandemic: an accurate self-similar model, and urgent conclusions
- Emergent information dynamics in many-body interconnected systems
- Scaling properties of scale-free networks in degree-thresholding renormalization flows
- Emergence of Long-Range Correlations in Random Networks
- Self-Avoiding Walk on Fractal Complex Networks: Exactly Solvable Cases
- Transfinite fractal dimension of trees and hierarchical scale-free graphs
- Network analysis of chaotic dynamics in fixed-precision digital domain
- Edge Balance Ratio: Power Law from Vertices to Edges in Directed Complex Network
- Laplacian Renormalization Group: An introduction to heterogeneous coarse-graining
- Investigating the Origins of Fractality Based on Two Novel Fractal Network Models
- Topological Convergence of Urban Infrastructure Networks
- Segregation in the annihilation of two-species reaction-diffusion processes on fractal scale-free networks
- Strange Attractors in Complex Networks
- Obtaining Communities with a Fitness Growth Process
- Universal features of mountain ridge networks on Earth
- Output-input coupling in thermally fluctuating biomolecular machines
- Spectral Renormalization Group for the Gaussian model and theory on non-spatial networks
- Exactly solvable tight-binding models on two scale-free networks with identical degree distribution
- A measure for characterizing heavy-tailed networks
- Towards a generalization of information theory for hierarchical partitions
- Average trapping time on a type of horizontally segmented 3 dimensional Sierpinski gasket network with two types of locally self-similar structures
- Multifractality of complex networks is also due to geometry. The Geometric SandBox algorithm
- Vital Spreaders Identification in Complex Networks with Multi-Local Dimension
- Diversity and critical behavior in prisoner's dilemma game
- Response to targeted perturbations for random walks on networks
- Using complex networks to model 2-D and 3-D soil porous architecture
- Coarse-grained Monte Carlo simulations of the phase transition of Potts model on weighted networks
- Social Connection Induces Cultural Contraction: Evidence from Hyperbolic Embeddings of Social and Semantic Networks
- Complexity in linearly coupled dynamical networks: Some unusual phenomena in energy accumulation
- An internet reviews topic hierarchy mining method based on modified continuous renormalization procedure
- A large-scale study of the World Wide Web: network correlation functions with scale-invariant boundaries
- Hierarchy, Fractality, Small-World and Resilience of Haversian Bone Structure: A Complex Network Study
- Disassortativity of random critical branching trees
- Inhomogeneous substructures hidden in random networks
- 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
- Fractals in the Nervous System: conceptual Implications for Theoretical Neuroscience
- Tsallis mapping in growing complex networks with fitness
- Maximizing Entropy Yields Spatial Scaling in Social Networks
- Unraveling linguistic patterns in dog behaviour
- On the Capacity of Fractal D2D Social Networks with Hierarchical Communications
- Optimal box-covering algorithm for fractal dimension of complex networks
- Hub-collision avoidance and leaf-node options algorithm for fractal dimension and renormalization of complex networks
- Degree and connectivity of the Internet's scale-free topology
- Self-similar planar graphs as models for complex networks
- Model-based reconstruction of real-world fractal complex networks
- Tracing the Attention of Moving Citizens
- Around Average Behavior: 3-lambda Network Model
- Nonextensive analysis on the local structure entropy of complex networks
- Measure the similarity of nodes in the complex networks
- Kaleidoscopic reorganization of network communities across different scales
- Multi-fractal analysis of weighted networks
- Degree-layer theory of network topology
- Global decomposition of networks into multiple cores formed by local hubs
- Symmetry-driven embedding of networks in hyperbolic space
- Complex physical properties of an adaptive, self-organizing biological system
- Flux of information in scale-free networks
- A Method for Geodesic Distance on Subdivision of Trees with Arbitrary Orders and Their Applications
- Markov-Binary Visibility Graph: a new method for analyzing Complex Systems
- Interpretation of percolation in terms of infinity computations
- From Logistic Growth to Exponential Growth in a Population Dynamical Model
- The conundrum of functional brain networks: small-world efficiency or fractal modularity
- Random walks on bifractal networks
- Generalisation of the fractal Einstein law relating conduction and diffusion on networks
- An improved vulnerability index of complex networks based on fractal dimension
- Universal scaling hypothesis of quantum spatial search in complex networks
- Modelling the Self-similarity in Complex Networks Based on Coulomb's Law
- Fractional stochastic model of citation dynamics with memory and volatility
- The Role of Fractal Dimension in Wireless Mesh Network Performance
- Asymptotic formula on average path length of fractal networks modelled on Sierpinski Gasket
- Conan: a platform for complex network analysis
- Latent geometry emerging from network-driven processes
- Chaotic renormalization group flow and entropy gradients over Haros graphs
- Fractality of Massive Graphs: Scalable Analysis with Sketch-Based Box-Covering Algorithm
- From Spatial to Spectral: Network Renormalization via Dynamical Correlations
- Enhancing speed of pinning synchronizability: low-degree nodes with high feedback gains
- Impact of Dynamic Interactions on Multi-Scale Analysis of Community Structure in Networks
- The Truth about Power Laws: Theory and Reality
- General Connectivity Distribution Functions for Growing Networks with Preferential Attachment of Fractional Power
- A hybrid multiscale coarse-grained method for dynamics on complex networks
- Edge Domination Number and the Number of Minimum Edge Dominating Sets in Pseudofractal Scale-Free Web and Sierpiński Gasket
- Exact mean first-passage time on generalized Vicsek fractal
- Phase-space networks and connectivity of the kagome antiferromagnet
- A Fractal and Scale-free Model of Complex Networks with Hub Attraction Behaviors
- Tsallis entropy of complex networks
- Universality classes in the time evolution of epidemic outbreaks on complex networks
- Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket
- Renormalization and small-world model of fractal quantum repeater networks
- The Impact of Network Flows on Community Formation in Models of Opinion Dynamics
- Propagation Time in Stochastic Communication Networks
- Some Combinatorial Problems in Power-law Graphs
- Quantum Google Algorithm: Construction and Application to Complex Networks
- Graph Theory in Brain Networks
- Time series of Internet AS-level topology graphs: four patterns and one model