Error and attack tolerance of complex networks
2000/07/27 by Réka Albert, Reka Albert, Hawoong Jeong +2 · 1 voice · 7,290 citations
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Complex network #Complex system #Degree (music) #Error detection and correction #Fault tolerance #Opportunistic and Delay-Tolerant Networks #Origins and Evolution of Life #Robustness (evolution) #Vulnerability (computing) #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.1038/35019019
published in Nature 406(6794), 378-382 (Nature Portfolio) · 14 pages, 4 figures, Latex
openalex publication_date 2000/07/27 · arxiv created 2000/08/03 · arxiv updated 2009/11/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/06
Abstract
Many complex systems, such as communication networks, display a surprising degree of robustness: while key components regularly malfunction, local failures rarely lead to the loss of the global information-carrying ability of the network. The stability of these complex systems is often attributed to the redundant wiring of the functional web defined by the systems' components. In this paper we demonstrate that error tolerance is not shared by all redundant systems, but it is displayed only by a class of inhomogeneously wired networks, called scale-free networks. We find that scale-free networks, describing a number of systems, such as the World Wide Web, Internet, social networks or a cell, display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected by even unrealistically high failure rates. However, error tolerance comes at a high price: these networks are extremely vulnerable to attacks, i.e. to the selection and removal of a few nodes that play the most important role in assuring the network's connectivity.
Cited by
- Identification of influential spreaders in complex networks
- A resource- and computationally-efficient protocol for multipartite entanglement distribution in Bell-pair networks
- Robustness of 'small' networks
- Detecting bias in algorithms used to disseminate information in social networks and mitigating it using multiobjective optimization
- A Probabilistic View of Forbidden Links: Their Prevalence and Their Consequences for the Robustness of Plant–Hummingbird Communities
- Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
- HWL-HIN: A Hypergraph-Level Hypergraph Isomorphism Network as Powerful as the Hypergraph Weisfeiler-Lehman Test with Application to Higher-Order Network Robustness
- Spectral Dynamics of Semantic Drift in Clinical Multi-Agent Language Model Networks
- A Mathematical Framework for Misinformation Propagation in Complex Networks: Topology-Dependent Distortion and Control
- Who Connects Global Aid? The Hidden Geometry of 10 Million Transactions
- Local-Scale Damming Impact on the Planktonic Bacterial and Eukaryotic Assemblages in the upper Yangtze River
- Evaluation of Risk and Resilience of the MBTA Green Rapid Transit System
- A unified framework for identifying influential nodes in hypergraphs
- PINE: Pipeline for Important Node Exploration in Attributed Networks
- AgentShield: Make MAS more secure and efficient
- Trade-Off Between Multiplicity and Specificity in the Inter-layer Connectivity of non-identical Multilayer Networks
- Assessing Automated Fact-Checking for Medical LLM Responses with Knowledge Graphs
- Linking the minimum spanning tree and edge betweenness to understand arterial corridors in an ecological network
- Structural asymmetry as a fraud signature: detecting collusion with Heron's Information Coefficient
- When one protocol fits none: Self-organized network routing through evolutionary game dynamics
- Enhancing complex-network synchronization
- Efficient local strategies for vaccination and network attack
- Edge vulnerability in neural and metabolic networks
- Multiple weak hits confuse complex systems: A transcriptional regulatory network as an example
- Novel insights through the integration of structural and functional genomics data with protein networks
- Decoding Microbial Community Assembly: Insights on Vectors of Infectious Diseases
- A Novel Discrete-time Model of Information Diffusion on Social Networks Considering Users Behavior
- Metabolomics – the link between genotypes and phenotypes
- Crossover behavior in a communication network
- The local Gaussian correlation networks among return tails in the Chinese stock market
- A fast Monte Carlo algorithm for site or bond percolation
- Scale-free networks are rare
- Rich-Club Organization of the Human Connectome
- When Your AI Agent Succumbs to Peer-Pressure: Studying Opinion-Change Dynamics of LLMs
- Diversity, connectivity and negative interactions define robust microbiome networks across land, stream, and sea
- Large scale statistically validated comorbidity networks
- Perron-Frobenius theorem for dual tensors and its applications
- The evolving landscape of neuroscience
- Temporal dynamics of interactions in European Administrative Networks: The case of SOLVIT
- Understanding How Network Geometry Influences Diffusion Processes in Complex Networks: A Focus on Cryptocurrency Blockchains and Critical Infrastructure Networks
- Network entropy as a key to the past: A quantitative approach to complex social networks
- Evolution of the social network of scientific collaborations
- Graph theory—Recent developments of its application in geomorphology
- Robustness and resilience of complex networks
- Supply network stress-testing of food security on the establishment-level
- Renaissance minds in 21st century science
- Emergent scale-free networks
- Brain network communication: concepts, models and applications
- Foundations of Gerophysics
- Limited Improvement of Connectivity in Scale-Free Networks by Increasing the Power-Law Exponent
- Stability Optimization and Analysis of Energy Flow Networks versus Different Centrality Measurement
- Shortest-path percolation on scale-free networks
- Breaking trade-offs: Development of fast, high-resolution, wide-field two-photon microscopes to reveal the computational principles of the brain
- Economics of information security investment in the case of concurrent heterogeneous attacks with budget constraints
- Network synchronization, diffusion, and the paradox of heterogeneity
- Reduced microbial stability in the active layer is associated with carbon loss under alpine permafrost degradation
- Universal vulnerability in strong modular networks with various degree distributions between inequality and equality
- The Small-World Beneath LEO Satellite Coverage: Ground Hubs in Multi-Shell Constellations
- HDBMS: A Context-Aware Hybrid Graph Traversal Algorithm for Efficient Information Discovery in Social Networks
- Directed Cycles as Higher-Order Units of Information Processing in Complex Networks
- Cascade Control and Defense in Complex Networks
- Localized risk perception triggers early behavioral adaptations in epidemics on networks
- The origins of large-scale structure in family networks
- A complex network perspective on brain disease
- Parcellation‐dependent small‐world brain functional networks: A resting‐state fMRI study
- Networking the seceder model: Group formation in social and economic systems
- Is criticality a unified setpoint of brain function?
- Identifying large robust network clusters via new compact formulations of maximum k-club problems
- Technology Network Structure Conditions the Economic Resilience of Regions
- Dynamics of information diffusion and its applications on complex networks
- Identification of Authoritative Nodes and Dismantling of Illicit Networks Using a Novel Metric for Measuring Strength of a Graph
- False News On Social Media
- Growth-induced percolation on complex networks
- Statistical physics of crime: A review
- Efficient Immunization Strategies for Computer Networks and Populations
- Synchronization transition in scale-free networks: Clusters of synchrony
- Informal lending networks in rural Ethiopia
- Challenging the dogma: the hidden layer of non‐protein‐coding RNAs in complex organisms
- Sandpile on Scale-Free Networks
- Statistical mechanical load balancer for the web
- Path finding strategies in scale-free networks
- The effects of spatial constraints on the evolution of weighted complex networks
- Patterns of pan‐genome occupancy and gene coexpression under water‐deficit in Brachypodium distachyon
- Transportation security and the role of resilience: A foundation for operational metrics
- Social physics
- An α-triangle eigenvector centrality of graphs
- Approach to network failure due to intrinsic fluctuations
- Sandpile avalanche dynamics on scale-free networks
- Probabilistic Prediction in Scale-Free Networks: Diameter Changes
- The Large‐Scale Structure of Semantic Networks: Statistical Analyses and a Model of Semantic Growth
- A preliminary theory of dark network resilience
- Reinforcement learning approach for robustness analysis of complex networks with incomplete information
- Epidemic dynamics in physical-information-social multilayer networks
- Critical and Nonpercolating Phases in Bond Percolation on the Song-Havlin-Makse Network
- Sequential Elimination and Union Shapley Value for Group Assessment in Coalitional Games
- Identifying and ranking influential spreaders in complex networks by neighborhood coreness
- Semantic Networks as Clues: A Theoretical Foundation and Process Optimization for Semantic Network Construction
- Why Are There Six Degrees of Separation in a Social Network?
- The bipartite structure of treatment-trial networks reveals the flow of information in network meta-analysis
- The effect of preferential node deletion on the structure of networks that evolve via preferential attachment
- A structured overview of 50 years of small-world research
- Measuring the impact of spammers on e-mail and Twitter networks
- Robustness and stability of enterprise intranet social networks: The impact of moderators
- Power law of path multiplicity in complex networks
- Containing misinformation: Modeling spatial games of fake news
- Community detection in graphs
- Cluster Vertex Deletion Problems on Cubic Graphs
- Locally Optimal Percolation for Network Resilience Dismantling via Fiedler Vector Gradient Iterative Attack
- The large-scale organization of metabolic networks
- Statistical mechanics of complex networks
- Dissemination strategy for immunizing scale-free networks
- Resource allocation pattern in infrastructure networks
- Degree and component size distributions in the generalized uniform recursive tree
- Power grids vulnerability: a complex network approach
- Bose-Einstein Condensation in Complex Networks
- Brain architecture: a design for natural computation
- Coevolution of dynamical states and interactions in dynamic networks
- Robustness of networks against propagating attacks under vaccination strategies
- The effect of recombination on the neutral evolution of genetic robustness
- Food-web structure and network theory: The role of connectance and size
- Percolation theory applied to measures of fragmentation in social networks
- Percolation transition and distribution of connected components in generalized random network ensembles
- Multi-state epidemic processes on complex networks
- Extreme fluctuations in noisy task-completion landscapes on scale-free networks
- Resilience of complex networks to random breakdown
- Analysis of a large-scale weighted network of one-to-one human communication
- Dynamics ofk-core percolation
- Exactly solvable scale-free network model
- Characterization of subgraph relationships and distribution in complex networks
- Distributed Retrieval-Augmented Generation
- Stochastic opinion formation in scale-free networks
- Designer nets from local strategies
- Emergence of a Small World from Local Interactions: Modeling Acquaintance Networks
- Model for cascading failures in complex networks
- The simultaneous evolution of author and paper networks
- The spread of low-credibility content by social bots
- On Automorphism Groups of Networks
- Temporal correlations of local network losses
- Protecting infrastructure networks from cost-based attacks
- Identifying structural design principles shaping the computational abilities of recurrent neural networks
- Spectra and eigenvectors of scale-free networks
- Thermodynamic stability and structural transitions in virus-host networks
- Explosive Percolation in Scale-Free Networks
- Random walks in local dynamics of network losses
- Entropy optimization of scale-free networks’ robustness to random failures
- Declines in research funding and science ecosystem fragility
- Universal fractal scaling of self-organized networks
- Scaling Properties of Human Brain Functional Networks
- The Rich-Club Phenomenon in the Internet Topology
- The effects of degree correlations on network topologies and robustness
- Log-periodic oscillations due to discrete effects in complex networks
- Investigation of a protein complex network
- Ferromagnetic phase transition in Barabási–Albert networks
- Resilience to damage of graphs with degree correlations
- Topology and correlations in structured scale-free networks
- Preferential attachment with information filtering—node degree probability distribution properties
- Laplacian spectra as a diagnostic tool for network structure and dynamics
- Maximal planar networks with large clustering coefficient and power-law degree distribution
- Dynamical and Correlation Properties of the Internet
- Radial structure of the Internet
- Anomalous percolation properties of growing networks
- Multifractal properties of growing networks
- Complex networks theory for analyzing metabolic networks
- Fastest learning in small-world neural networks
- Mixing patterns in networks
- Critical load and congestion instabilities in scale-free networks
- Network analysis in the legal domain: a complex model for European Union legal sources
- Deterministic small-world networks
- Immunization of complex networks
- Assortative Mixing in Networks
- Self-assembly of information in networks
- The architecture of complex weighted networks
- Hierarchical organization in complex networks
- Inferring General Relations between Network Characteristics from Specific Network Ensembles
- Some asymptotic properties of duplication graphs
- Limited Path Percolation in Complex Networks
- Metabolomics in Systems Biology
- Modeling spatio-temporal dynamics of network damage and network recovery
- Protecting free expression online with Freenet
- Freenet: A Distributed Anonymous Information Storage and Retrieval System
- Dynamics and processing in finite self-similar networks
- Evolution of cooperation on scale-free networks subject to error and attack
- Global Civil Unrest: Contagion, Self-Organization, and Prediction
- Degree-ordered percolation on a hierarchical scale-free network
- Brain reward circuitry beyond the mesolimbic dopamine system: A neurobiological theory
- Graph neural network explanations reveal a topological signature of disease-associated hubs in biological networks
- Efficiency and robustness in ant networks ofgalleries
- On the distribution of links in the interbank network: evidence from the e-MID overnight money market
- Dimensions of superspreading
- Non‐coding RNAs: the architects of eukaryotic complexity
- The Evolution of Controlled Multitasked Gene Networks: The Role of Introns and Other Noncoding RNAs in the Development of Complex Organisms
- Regime shifts occur disproportionately faster in larger ecosystems
- Infection dynamics on scale-free networks
- Error and attack tolerance of collective problem solving: The DARPA Shredder Challenge
- Non-random coextinctions in phylogenetically structured mutualistic networks
- The structure of gallery networks in the nests of termite Cubitermes spp. revealed by X-ray tomography
- Gene expression dynamics in the macrophage exhibit criticality
- The “robust yet fragile” nature of the Internet
- Controlling edge dynamics in complex networks
- Percolation transition in networks with degree-degree correlation
- Percolation on complex networks: Theory and application
- Characterizing and predicting the robustness of power-law networks
- Bicomponents and the Robustness of Networks to Failure
- Robustness of interdependent networks under targeted attack
- Effect of node deleting on network structure
- Bilinear effect in complex systems
- Social Structure of a Semi-Free Ranging Group of Mandrills (Mandrillus sphinx): A Social Network Analysis
- Hamiltonian approach for explosive percolation
- Resilience of public transport networks against attacks
- Assessing interaction networks with applications to catastrophe dynamics and disaster management
- Robustness of a partially interdependent network formed of clustered networks
- Prediction of lethal and synthetically lethal knock-outs in regulatory networks
- k-Core Organization of Complex Networks
- A simple model of global cascades on random networks
- Synthetic connectivity, emergence, and self-regeneration in the network of prebiotic chemistry
- Collective communication and behaviour in response to uncertain ‘Danger’ in network experiments
- Modern temporal network theory: a colloquium
- Efficient generation of networks with minimal average shortest-path distance
- Spin-glass model for the C-dismantling problem
- Node-weighted measures for complex networks with spatially embedded, sampled, or differently sized nodes
- Hysteretic Percolation from Locally Optimal Individual Decisions
- Laplacian spectra of, and random walks on, complex networks: Are scale-free architectures really important?
- Maximum Shortest Path Interdiction Problem by Upgrading Nodes on Trees under Unit Cost
- Generating Robust and Efficient Networks Under Targeted Attacks
- Analyzing host-viral interactome of SARS-CoV-2 for identifying vulnerable host proteins during COVID-19 pathogenesis
- Optimal shattering of complex networks
- Signatures of small-world and scale-free properties in large computer programs
- Integrating fluctuations into distribution of resources in transportation networks
- A study on the effects of diffusion of information on epidemic spread
- Changing motif distributions in complex networks by manipulating rich-club connections
- Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices
- Multiple tipping points and optimal repairing in interacting networks
- The network structure of mathematical knowledge according to the Wikipedia, MathWorld, and DLMF online libraries
- Cascading collapse of online social networks
- The Neural Pruning Law Hypothesis
- Predicting percolation thresholds in networks
- A new design principle of robust onion-like networks self-organized in growth
- Immunization strategies in networks with missing data
- Degree-ordered-percolation on uncorrelated networks
- Spectral Entropies as Information-Theoretic Tools for Complex Network Comparison
- Critical line in undirected Kauffman Boolean networks — the role of percolation
- Percolation of networks with directed dependency links
- Towards designing robust coupled networks
- Dynamical Patterns of Cattle Trade Movements
- Modeling resource consumption in the US air transportation system via minimum-cost percolation
- Thermodynamic forces, flows, and Onsager coefficients in complex networks
- MULTIDIMENSIONAL CONSENSUS MODEL ON A BARABÁSI–ALBERT NETWORK
- Analytical results for bond percolation andk-core sizes on clustered networks
- How to Make a Fragile Network Robust and Vice Versa
- Dynamical robustness of network of oscillators
- Statistical analysis of articulation points in configuration model networks
- Tuning degree distributions: Departing from scale-free networks
- Structural and spectral properties of a family of deterministic recursive trees: rigorous solutions
- Breakdown of the Internet under Intentional Attack
- The percolation transition in correlated hypergraphs
- How breadth of degree distribution influences network robustness: Comparing localized and random attacks
- Efficient Behavior of Small-World Networks
- An optimal network for passenger traffic
- The globalization of socio-ecological systems: An agenda for scientific research
- Rate equation approach for correlations in growing network models
- Small-world networks and the conformation space of a short lattice polymer chain
- Finding missing edges and communities in incomplete networks
- Effect of edge removal on topological and functional robustness of complex networks
- Sustaining the Internet with hyperbolic mapping
- Random Walks on Simplicial Complexes and the Normalized Hodge 1-Laplacian
- Optimal cost for strengthening or destroying a given network
- Network resilience of FitzHugh-Nagumo neurons in the presence of nonequilibrium dynamics
- Ranking Vertices or Edges of a Network by Loops: A New Approach
- Biology helps to construct weighted scale-free networks
- Peeling the yeast protein network
- Random networks with tunable degree distribution and clustering
- Scaling in small-world resistor networks
- Scale effects on spatially embedded contact networks
- Site- and bond-percolation thresholds inKn,n-based lattices: Vulnerability of quantum annealers to random qubit and coupler failures on chimera topologies
- Measuring network resilience through connection patterns
- Robustness of planar random graphs to targeted attacks
- Award for Distinguished Scientific Contributions: Irving I. Gottesman.
- Optimizing disorder with machine learning to harness synchronization
- An automated method for finding molecular complexes in large protein interaction networks
- Optimization of network structure to random failures
- Robustness of network measures to link errors
- The effect of digital platform adoption on the resilience of innovation ecosystems: An empirical analysis using social media data
- Utility-aware Social Network Anonymization using Genetic Algorithms
- Réka Albert [wikipedia]
Discussions
Related