Percolation on complex networks: Theory and application

Abstract

In the last two decades, network science has blossomed and influenced various fields, such as statistical physics, computer science, biology and sociology, from the perspective of the heterogeneous interaction patterns of components composing the complex systems. As a paradigm for random and semi-random connectivity, percolation model plays a key role in the development of network science and its applications. On the one hand, the concepts and analytical methods, such as the emergence of the giant cluster, the finite-size scaling, and the mean-field method, which are intimately related to the percolation theory, are employed to quantify and solve some core problems of networks. On the other hand, the insights into the percolation theory also facilitate the understanding of networked systems, such as robustness, epidemic spreading, vital node identification, and community detection. Meanwhile, network science also brings some new issues to the percolation theory itself, such as percolation of strong heterogeneous systems, topological transition of networks beyond pairwise interactions, and emergence of a giant cluster with mutual connections. So far, the percolation theory has already percolated into the researches of structure analysis and dynamic modeling in network science. Understanding the percolation theory should help the study of many fields in network science, including the still opening questions in the frontiers of networks, such as networks beyond pairwise interactions, temporal networks, and network of networks. The intention of this paper is to offer an overview of these applications, as well as the basic theory of percolation transition on network systems.

88 pages,19 figures, 5 tables

References in corpus (345)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community detection in graphs
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Catastrophic cascade of failures in interdependent networks
• Statistical physics of social dynamics
• Epidemic processes in complex networks
• Random graphs with arbitrary degree distributions and their applications
• The spread of epidemic disease on networks
• Identification of influential spreaders in complex networks
• Multilayer Networks
• Evolution of networks
• Mixing patterns in networks
• The structure and dynamics of multilayer networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Network robustness and fragility: Percolation on random graphs
• Spatial Networks
• Resilience of the Internet to random breakdowns
• Mean-field theory for scale-free random networks
• Critical phenomena in complex networks
• Cascade-based attacks on complex networks
• Attack vulnerability of complex networks
• Critical Phenomena and Renormalization-Group Theory
• Networks beyond pairwise interactions: structure and dynamics
• Breakdown of the Internet under intentional attack
• Renormalization group analysis of the small-world network model
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Immunization of complex networks
• Influence maximization in complex networks through optimal percolation
• Universal Behavior of Load Distribution in Scale-free Networks
• Efficient Immunization Strategies for Computer Networks and Populations
• Vital nodes identification in complex networks
• Mitigation of Malicious Attacks on Networks
• Effective containment explains sub-exponential growth in confirmed cases of recent COVID-19 outbreak in Mainland China
• Organization of Growing Random Networks
• Scale-Free Networks are Ultrasmall
• Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• Epidemic outbreaks in complex heterogeneous networks
• Velocity and hierarchical spread of epidemic outbreaks in scale-free networks
• k-core organization of complex networks
• Robustness of a Network of Networks
• Control Principles of Complex Networks
• Spectral redemption: clustering sparse networks
• Clustering and Community Detection in Directed Networks: A Survey
• Universal behavior in a generalized model of contagion
• Clique percolation in random networks
• Absence of epidemic threshold in scale-free networks with connectivity correlations
• Pseudofractal Scale-free Web
• A fast Monte Carlo algorithm for site or bond percolation
• Robustness of interdependent networks under targeted attack
• Random graphs with clustering
• Efficient Monte Carlo algorithm and high-precision results for percolation
• Properties of highly clustered networks
• Class of correlated random networks with hidden variables
• Are randomly grown graphs really random?
• Cascade of failures in coupled network systems with multiple support-dependent relations
• Recent advances in percolation theory and its applications
• Mean-field solution of the small-world network model
• Avalanche Collapse of Interdependent Network
• Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
• Unification of theoretical approaches for epidemic spreading on complex networks
• Precise determination of the bond percolation thresholds and finite-size scaling corrections for the s.c., f.c.c., and b.c.c. lattices
• Cascade Dynamics of Multiplex Propagation
• Percolation Critical Exponents in Scale-Free Networks
• Stability and topology of scale-free networks under attack and defense strategies
• Inter-similarity between coupled networks
• The extreme vulnerability of interdependent spatially embedded networks
• Cut-offs and finite size effects in scale-free networks
• Percolation on sparse networks
• The critical effect of dependency groups on the function of networks
• Giant strongly connected component of directed networks
• "Explosive Percolation" Transition is Actually Continuous
• Random hypergraphs and their applications
• Resilience to damage of graphs with degree correlations
• Network robustness of multiplex networks with interlayer degree correlations
• Percolation Theory on Interdependent Networks Based on Epidemic Spreading
• Interdependent networks with correlated degrees of mutually dependent nodes
• Percolation in Multiplex Networks with Overlap
• A General Formalism for Inhomogeneous Random Graphs
• Dynamics of jamming transitions in complex networks
• Percolation in real interdependent networks
• Percolation in Directed Scale-Free Networks
• Assortativity Decreases the Robustness of Interdependent Networks
• Multiplexity-facilitated cascades in networks
• Bootstrap Percolation on Complex Networks
• 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
• Random graphs containing arbitrary distributions of subgraphs
• Epidemic threshold for the SIS model on networks
• Percolation and Epidemic Thresholds in Clustered Networks
• Spatially localized attacks on interdependent networks: the existence of a finite critical attack size
• If players are sparse social dilemmas are too: Importance of percolation for evolution of cooperation
• Exact solution of site and bond percolation on small-world networks
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Percolation of localized attack on complex networks
• Explosive Percolation is Continuous, but with Unusual Finite Size Behavior
• Infinite-Order Percolation and Giant Fluctuations in a Protein Interaction Network
• Multiple percolation transitions in a configuration model of network of networks
• Statistical ensemble of scale-free random graphs
• Bond and Site Percolation in Three Dimensions
• Efficient local strategies for vaccination and network attack
• Percolation of Interdependent Networks with Inter-similarity
• Explosive Percolation: Novel critical and supercritical phenomena
• Suppressing Epidemics with a Limited Amount of Immunization Units
• Towards real-world complexity: an introduction to multiplex networks
• Generalized percolation in random directed networks
• Small world-Fractal Transition in Complex Networks: Renormalization Group Approach
• Percolation of Partially Interdependent Scale-free Networks
• Percolation and epidemics in a two-dimensional small world
• Percolation in networks composed of connectivity and dependency links
• Accuracy of Mean-Field Theory for Dynamics on Real-World Networks
• Recent advances and open challenges in percolation
• Percolation on correlated networks
• Percolation of a general network of networks
• Percolation threshold determines the optimal population density for public cooperation
• Construction and Analysis of Random Networks with Explosive Percolation
• Tuning clustering in random networks with arbitrary degree distributions
• Finite-size scaling in complex networks
• Critical phenomena in networks
• Anomalous percolating properties of growing networks
• Percolation of partially interdependent networks under targeted attack
• Structure of shells in complex networks
• Geography in a Scale-Free Network Model
• Resilience of networks with community structure behaves as if under an external field
• Explosive percolation: a numerical analysis
• The robustness of interdependent clustered networks
• Clustering in complex networks. II. Percolation properties
• Two-Peak and Three-Peak Optimal Complex Networks
• Local cluster aggregation models of explosive percolation
• How clustering affects the bond percolation threshold in complex networks
• Avoiding a Spanning Cluster in Percolation Models
• Core percolation on complex networks
• Simultaneous analysis of three-dimensional percolation models
• Threshold model of cascades in temporal networks
• Core percolation in random graphs: a critical phenomena analysis
• Cascades on a class of clustered random networks
• Articulation Points in Complex Networks
• k-Core percolation on multiplex networks
• Predicting percolation thresholds in networks
• Triple Point in Correlated Interdependent Networks
• Robustness of onion-like correlated networks against targeted attacks
• Optimal percolation on multiplex networks
• Strongly discontinuous explosive percolation with multiple giant components
• Bursty communication patterns facilitate spreading in a threshold-based epidemic dynamics
• Local structure can identify and quantify influential global spreaders in large scale social networks
• Finding influential nodes for integration in brain networks using optimal percolation theory
• Cascading Dynamics in Modular Networks
• Potts model on complex networks
• Ordinary Percolation with Discontinuous Transitions
• Are Percolation Transitions always Sharpened by Making Networks Interdependent?
• Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks
• Component sizes in networks with arbitrary degree distributions
• Facilitated spin models on Bethe lattice: bootstrap percolation, mode-coupling transition and glassy dynamics
• Random Networks with Tunable Degree Distribution and Clustering
• Weak percolation on multiplex networks
• Uncorrelated Random Networks
• Evolution of robust network topologies: Emergence of central backbones
• Scale-free networks with an exponent less than two
• Robustness of partially interdependent network formed of clustered networks
• Tricritical point in explosive percolation
• Solving the Dynamic Correlation Problem of the Susceptible-Infected-Susceptible Model on Networks
• Recent advances of percolation theory in complex networks
• Epidemic Threshold of Susceptible-Infected-Susceptible Model on Complex Networks
• Structural Transitions in Dense Networks
• Metric structure of random networks
• Continuity of the Explosive Percolation Transition
• Evolution of scale-free random graphs: Potts model formulation
• Critical Percolation in High Dimensions
• Bicomponents and the robustness of networks to failure
• Inducing Effect on the Percolation Transition in Complex Networks
• Minimum spanning trees on random networks
• The influence of the broadness of the degree distribution on network's robustness: comparing localized attack and random attack
• Hybrid Phase Transition into an Absorbing State: Percolation and Avalanches
• Hybrid Percolation Transition in Cluster Merging Processes: Continuously Varying Exponents
• Group percolation in interdependent networks
• $k$-core percolation on complex networks: Comparing random, localized and targeted attacks
• Percolation transition in networks with degree-degree correlation
• Breaking of the site-bond percolation universality in networks
• Stability of a Giant Connected Component in a Complex Network
• Temporal percolation in activity driven networks
• Epidemic spreading and bond percolation in multilayer networks
• Measures of critical exponents in the four dimensional site percolation
• Effects of temporal correlations on cascades: Threshold models on temporal networks
• Exact bond percolation thresholds in two dimensions
• Tricritical point in heterogeneous k-core percolation
• Rare events and discontinuous percolation transitions
• Network Observability Transitions
• Weighted percolation on directed networks
• Tight lower bound for percolation threshold on a quasi-regular graph
• Analysis of a threshold model of social contagion on degree-correlated networks
• Beyond the locally tree-like approximation for percolation on real networks
• Percolation Threshold, Fisher Exponent, and Shortest Path Exponent for 4 and 5 Dimensions
• Topological Percolation on Hyperbolic Simplicial Complexes
• Analytic solution of a static scale-free network model
• Solution of the explosive percolation quest: Scaling functions and critical exponents
• A Hamiltonian approach for explosive percolation
• Micro-transition cascades to percolation
• Routes to thermodynamic limit on scale-free networks
• Width of percolation transition in complex networks
• Robustness of a Network Formed of Spatially Embedded Networks
• Densification and Structural Transitions in Networks that Grow by Node Copying
• Spreading of localized attacks in spatial multiplex networks
• Scale-free networks with exponent one
• Small-World Bonds and Patchy Percolation on the Hanoi Network
• The spectral dimension of simplicial complexes: a renormalization group theory
• Finite-size scaling theory for explosive percolation transitions
• Fractal Boundaries of Complex Networks
• Fluctuations in percolation of sparse complex networks
• Networking - A Statistical Physics Perspective
• Generalization of core percolation on complex networks
• Controlling the uncertain response of real multiplex networks to random damage
• Percolation in self-similar networks
• Biased Percolation on Scale-free Networks
• Explosive site percolation and finite size hysteresis
• Suppression effect on explosive percolations
• Dynamics on Modular Networks with Heterogeneous Correlations
• From discrete to continuous percolation in dimensions 3 to 7
• Bohman-Frieze-Wormald model on the lattice, yielding a discontinuous percolation transition
• Large-deviation properties of the largest biconnected component for random graphs
• Achlioptas processes are not always self-averaging
• Efficient algorithm to compute mutually connected components in interdependent networks
• Clique percolation in random graphs
• Interevent time distribution, burst, and hybrid percolation transition
• Two-dimensional SIR epidemics with long range infection
• Percolation Thresholds and Fisher Exponents in Hypercubic Lattices
• Limited path percolation in complex networks
• Percolation in real multiplex networks
• How does bond percolation happen in coloured networks?
• Exhaustive percolation on random networks
• Percolation properties in a traffic model
• Nonbacktracking expansion of finite graphs
• Exact equations for SIR epidemics on tree graphs
• Large deviation theory of percolation on multiplex networks
• The combined effect of connectivity and dependency links on percolation of networks
• Universal mechanism for hybrid percolation transitions
• Deriving an underlying mechanism for discontinuous percolation
• Asymmetry in interdependence makes a multilayer system more robust against cascading failures
• Solution of the explosive percolation quest. II. Infinite-order transition produced by the initial distributions of clusters
• Asymmetric percolation drives a double transition in sexual contact networks
• A Dynamic Model of Cascades on Random Networks with a Threshold Rule
• Dynamic facilitation picture of a higher-order glass singularity
• Diverse types of percolation transitions
• Cooperation percolation in spatial prisoner's dilemma game
• Bridges in Complex Networks
• Urban retail dynamics: insights from percolation theory and spatial interaction modelling
• Efficient algorithm to study interconnected networks
• Critical phenomena in heterogeneous k-core percolation
• Cascading failures in coupled networks with both inner-dependency and inter-dependency links
• Limited path entanglement percolation in quantum complex networks
• Universal condition for critical percolation thresholds of kagome-like lattices
• Discontinuous percolation transitions in real physical systems
• Critical behavior of $k$-core percolation: Numerical studies
• Universal Properties of Growing Networks
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• General and exact approach to percolation on random graphs
• Preferencial growth: exact solution of the time dependent distributions
• Asymptotic normality of the size of the giant component in a random hypergraph
• Spreading with immunization in high dimensions
• Percolation on branching simplicial and cell complexes and its relation to interdependent percolation
• Bond percolation on a class of correlated and clustered random graphs
• Unstable supercritical discontinuous percolation transitions
• Critical percolation clusters in seven dimensions and on a complete graph
• Smeared phase transitions in percolation on real complex networks
• General expression for the component size distribution in infinite configuration networks
• Numerical evaluation of the upper critical dimension of percolation in scale-free networks
• Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and SOS
• Percolation and cooperation with mobile agents: Geometric and strategy clusters
• Efficient space virtualisation for Hoshen--Kopelman algorithm
• Correlated percolation and tricriticality
• Cascades on clique-based graphs
• Scaling of percolation transitions on Erdös-Rényi networks under centrality-based attacks
• Interfaces and the edge percolation map of random directed networks
• Percolation on networks with weak and heterogeneous dependency
• Equitable random graphs
• Generating-function approach for bond percolations in hierarchical networks
• Renormalization group for evolving networks
• Asymmetric evolving random networks
• Correlations in complex networks under attack
• The fate of the bootstrap percolation hybrid critical point in finite dimension
• On the Tomography of Networks and Multicast Trees
• Precise bond percolation thresholds on several four-dimensional lattices
• $1/d$ Expansion for $k$-Core Percolation
• History-dependent percolation on multiplex networks
• Long-range epidemic spreading in a random environment
• Percolation on correlated random networks
• Critical exponents of the explosive percolation transition
• Maximum flow and topological structure of complex networks
• Renormalization group for link percolation on planar hyperbolic manifolds
• Reversible bootstrap percolation: Fake news and fact checking
• Finite connected components in infinite directed and multiplex networks with arbitrary degree distributions
• Clique percolation
• Insights into bootstrap percolation: Its equivalence with k-core percolation and the giant component
• On $k$-Core Percolation in Four Dimensions
• Effect of degree correlations above the first shell on the percolation transition
• Interdependent Lattice Networks in High Dimensions
• Color-avoiding percolation
• Multiple Hybrid Phase Transition: Bootstrap Percolation on Complex Networks with Communities
• Statistical analysis of articulation points in configuration model networks
• Hierarchical scale-free network is fragile against random failure
• Observability transitions in correlated networks
• Dynamics of k-core percolation in a random graph
• Robustness of Spatial Micronetworks
• Critical Phase of Bond Percolations on Growing Networks
• Statistical mechanics of random graphs
• Dynamics of k-core percolation
• Percolation transition in correlated hypergraphs
• Percolation properties of growing networks under an Achlioptas process
• Bond and site color-avoiding percolation in scale free networks
• Profile and scaling of the fractal exponent of percolations in complex networks
• The dynamical collision network in granular gases
• Disentangling Giant Component and Finite Cluster Contributions in Sparse Matrix Spectra
• Exotic phase transitions of k-cores in clustered networks
• Spectral estimation of the percolation transition in clustered networks
• Inverting the Achlioptas rule for explosive percolation
• Percolation transition and distribution of connected components in generalized random network ensembles
• Given enough choice, simple local rules percolate discontinuously
• Enhancing the robustness of a multiplex network leads to multiple discontinuous percolation transitions
• Graph Partitioning Induced Phase Transitions
• Phase transitions for scaling of structural correlations in directed networks
• Berezinskii-Kosterlitz-Thouless-like percolation transitions in the two-dimensional XY model
• Fundamental Structural Constraint of Random Scale-Free Networks
• Absence of the non-percolating phase for percolation on the non-planar Hanoi network
• Universality and scaling laws in the cascading failure model with healing
• Emergence of coexisting percolating clusters in networks
• Exact solution of bond percolation on small arbitrary graphs
• Duality with real-space renormalization and its application to bond percolation
• Coexistence of phases and the observability of random graphs
• History-dependent percolation in two dimensions
• Fragility and anomalous susceptibility of weakly interacting networks
• Giant component sizes in scale-free networks with power-law degrees and cutoffs
• Discontinuous percolation in diffusion-limited cluster aggregation
• Observability transition in real networks
• Hysteresis and criticality in hybrid percolation transitions
• Percolation on a maximally disassortative network
• Approaching the thermodynamic limit in equilibrated scale-free networks
• Scale-free random branching tree in supercritical phase
• Observability transition in multiplex networks
• Diversity and critical behavior in prisoner's dilemma game
• Disorder Induced Limited Path Percolation
• Degree-Ordered-Percolation on uncorrelated networks

Cited by in corpus (54)

• Robustness and resilience of complex networks
• Higher-order percolation processes on multiplex hypergraphs
• Structural Robustness of Complex Networks: A Survey of A Posteriori Measures
• From the origin of life to pandemics: Emergent phenomena in complex systems
• The dynamic nature of percolation on networks with triadic interactions
• Persistence in Complex Systems
• The theory of percolation on hypergraphs
• Unified Modeling and Experimental Realization of Electrical and Thermal Percolation in Polymer Composites
• Complex Network Modelling with Power-law Activating Patterns and Its Evolutionary Dynamics
• Identifying vital nodes by Achlioptas process
• A Comprehensive Taxonomy of Cellular Automata
• Strong Connectivity in Real Directed Networks
• Percolation thresholds on triangular lattice for neighbourhoods containing sites up-to the fifth coordination zone
• A general model of hierarchical fractal scale-free networks
• Shortest-path percolation on random networks
• Machine learning for percolation utilizing auxiliary Ising variables
• Directed Percolation in Random Temporal Network Models with Heterogeneities
• Global efficiency and network structure of urban traffic flows: A percolation-based empirical analysis
• Triadic percolation induces dynamical topological patterns in higher-order networks
• Extended-range percolation in complex networks
• Random site percolation on honeycomb lattices with complex neighborhoods
• Random node reinforcement and $K$-core structure of complex networks
• Network science Ising states of matter
• Higher-order triadic percolation on random hypergraphs
• General theory for extended-range percolation on simple and multiplex networks
• Effectiveness of Contact Tracing on Networks with Cliques
• Exact percolation probabilities for a square lattice: Site percolation on a plane, cylinder, and torus
• Effect of chemical short-range order and percolation on passivation in binary alloys
• Random site percolation thresholds on square lattice for complex neighborhoods containing sites up to the sixth coordination zone
• Infection-induced Cascading Failures -- Impact and Mitigation
• Emergence of biconnected clusters in explosive percolation
• Percolation in Networks of Liquid Diodes
• Scaling and universality for percolation in random networks: A unified view
• Universality of random-site percolation thresholds for two-dimensional complex non-compact neighborhoods
• Assessing the Robustness and Resilience of U.S. Strategic Highways: A Network Science Perspective
• Determinable and interpretable network representation for link prediction
• Triadic percolation on multilayer networks
• Cumulative Merging Percolation: A long-range percolation process in networks
• Finite-size scaling of percolation on scale-free networks
• $K$-selective percolation: A simple model leading to a rich repertoire of phase transitions
• Combinatorial Properties for a Class of Simplicial Complexes Extended from Pseudo-fractal Scale-free Web
• Universality of percolation at dynamic pseudocritical point
• Revisiting finite size effect of percolation in degree correlated networks
• Entanglement percolation in random quantum networks
• Color-avoiding percolation in edge-colored Erdős-Rényi graphs
• Superexponential growth of epidemics in networks with cliques
• Lower limit of percolation threshold on a square lattice with complex neighborhoods
• Modeling Multistability and Hysteresis in Urban Congestion Spreading
• Nonreciprocal random networks and their percolation properties
• A simple model of knowledge percolation
• Nonmonotonic percolation threshold in correlated networks and hypergraphs
• Structural Changes and Percolation Transition in Networks after Aging Processes
• Quantifying Influence and Information Transfer in a Modified Vicsek Model with Non-reciprocal Interactions
• Shortest-path percolation on scale-free networks