PaperlayerView exact revision on arXiv

Source-linked AI summary

Percolation on complex networks: Theory and application

Ming Li, Run-Ran Liu, Linyuan Lü, Mao-Bin Hu, Shuqi Xu, Yi-Cheng Zhang

arXiv:2101.11761v1physics.soc-phcond-mat.stat-mech

TL;DR

Network percolation problems are easy to define but lack exact solutions for most systems. This paper reviews percolation models, theoretical methods, applications, and remaining challenges, emphasizing its quantitative use for network robustness and epidemic spreading.

  • Problem

    Network cluster-forming problems are easy to define, but exact percolation solutions are absent for most systems.

  • Method

    The paper reviews percolation on complex networks across models, analytical methods, and applications, including branching-process and Potts-model formulations.

  • Results

    Percolation theory provides quantitative network-science tools, using giant clusters and percolation thresholds to evaluate network functionality, robustness, and epidemic outbreaks.

  • Takeaways & Limitations

    Percolation theory connects network structure and dynamics while motivating further study of heterogeneous, higher-order, temporal, and interconnected networks.

  • Takeaways & Limitations

    Community-detection methods may fail to produce meaningful community structures in networks with only a few cliques.

Abstract

from arXiv · show

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.

1. Introduction

This review introduces percolation theory and synthesizes its use in complex-network structure and dynamics. It connects core concepts such as giant clusters, thresholds, and critical behavior with applications including robustness, epidemics, and emerging network models.

  • Network problems such as epidemic spread and attack tolerance can be framed as cluster-forming processes, but solving them is difficult.
  • Percolation theory provides concepts, analytical methods, and algorithms for studying networked systems when nodes or links are unavailable.
  • The review also covers extensions to heterogeneous, higher-order, and beyond-pairwise networks, while noting that complex mixtures of network properties remain open problems.
  • The review addresses a gap by systematically comparing and summarizing scattered developments and applications of percolation on complex networks.
  • Percolation analysis uses quantities such as the giant-cluster size, wrapping probability, mean cluster size, and characteristic length to describe transitions.

2. Classical percolation on networks

Classical percolation is extended from regular lattices to heterogeneous network systems, with emphasis on analytic methods, critical phenomena, and Monte Carlo algorithms.

  • The section reviews classical percolation on heterogeneous network systems rather than restricting analysis to regular lattices.
  • Its main topics are analytic methods for network percolation transitions.
  • It also considers critical phenomena and Monte Carlo algorithms.

2.1. Problem description

Network percolation models random node or link availability and connect the resulting clusters to network robustness and epidemic spreading. These mappings make the percolation threshold a measure of functional persistence or infectious ability.

  • Nodes or links are designated occupied with probability p and unoccupied with probability 1 − p, equivalently removing each with probability 1 − p.
  • Site percolation interprets unoccupied nodes as failures or removals, with a surviving giant cluster indicating a still-functional network.
  • A large percolation threshold pc indicates that a small amount of failed nodes can disconnect the network, implying poor robustness.
  • Scale-free networks are strongly robust to random failures but extremely fragile under intentional attacks.
  • Bond percolation maps occupied links to successful infections, while link occupation probability represents integrated disease-transmission probability.
  • The giant cluster corresponds to an epidemic outbreak, and a smaller pc indicates stronger infectious ability.

2.2. Analytic method based on branching process

A branching-process framework provides self-consistent calculations for giant and finite clusters on tree-like networks, where it can be exact. The review also discusses dilution, generating functions, critical criteria, and limitations caused by loops.

  • Because exact solutions are absent for most systems, a mean-field branching-process method is introduced for tree-like networks.
  • The branching equations determine the probability R that a link belongs to the giant cluster and the order parameter S for a randomly chosen node.
  • The excess-degree distribution qk and generating function G1 encode branching reached by following a link, requiring at least one excess link for continuation.
  • Percolation dilution is incorporated by replacing the original generating functions with those of the diluted network, whose links are preserved with probability p.
  • The same probability R can yield different giant clusters for bond and site percolation because their order-parameter definitions differ.
  • For tree-like networks, the mean-field equations can give an exact solution, as illustrated by simulations and theoretical predictions for ER and RR networks.
  • Loops invalidate the independent-branching equations because different links can reach the same nodes, while the Molloy–Reed criterion gives the transition condition in random graph theory.
  • Finite-cluster distributions are obtained through branching generating functions, with πs following the form πs ∝ s1−τ.

2.3. Potts model formulation

The Potts-model formulation represents percolation through Fortuin–Kasteleyn clusters and connects thermodynamic quantities to cluster observables. On tree-like networks, its recurrence relations recover the branching-process mean-field equations.

  • 2.3. Potts model formulation: The q → 1 limit of the q-state Potts model without external field corresponds to network percolation.
  • 2.3.1. Fortuin-Kasteleyn cluster representation: Expanding the Potts partition function over subnetworks replaces spin sums with sums over link-defined clusters, yielding the Fortuin–Kasteleyn representation.
  • 2.3.1. Fortuin-Kasteleyn cluster representation: The representation identifies each percolation configuration probability as p^l(G′)(1 − p)^(l(G)−l(G′)), thereby bridging the Potts and percolation models.
  • 2.3.1. Fortuin-Kasteleyn cluster representation: Percolation parameters, including the percolating-cluster size and mean cluster size, can be extracted from the Potts formulation.
  • 2.3.1. Fortuin-Kasteleyn cluster representation: A cluster-size generating function is obtained from the cluster counts ns and can be used to study cluster-size distributions.
  • 2.3.1. Fortuin-Kasteleyn cluster representation: Once a network Hamiltonian is known, the equations can provide percolation parameters, with applications to scale-free networks, correlated hypergraphs, and generalized random-network ensembles.
  • 2.3.2. Relation with the mean-field equations: For tree-like networks, recursive partition-function relations define branching states and exclude double counting that would arise from loops.
  • 2.3.2. Relation with the mean-field equations: After rescaling branching partition functions, the Potts formulation recovers the mean-field equations with x = 1 − pR, where tree-like structure remains required.

2.4. Message passing method

The message passing method estimates percolation on finite real networks where mean-field assumptions fail, using node-specific giant-cluster probabilities and a non-backtracking matrix. Its largest eigenvalue yields a lower bound for the site threshold and, with triangle effects, a tighter bond-threshold bound.

  • Finite real networks require message passing because their adjacency matrices, rather than degree distributions, characterize connectivity and invalidate the usual mean-field method.The method is commonly used to estimate the theoretical percolation threshold on finite networks.
  • Message passing assigns each node i its own probability s_i of belonging to the giant cluster and expresses the giant-cluster size from these probabilities.Link probabilities r_i→j describe whether neighboring links lead to the giant cluster.
  • The resulting matrix M is the Hashimoto, or non-backtracking, matrix: entries are nonzero only for head-to-tail links that exclude immediate backtracking.Its dimension is 2L × 2L for a network with L links.
  • At the critical point, expanding the message-passing equations as r_i approaches zero produces an eigenvalue equation for M.This linearization identifies the transition condition from the near-critical behavior of link probabilities.
  • pc = 1/λmax provides a lower bound for site percolation on infinite graphs, while triangle effects can yield a tighter lower bound for bond percolation on clustered networks.λmax is the largest eigenvalue of the non-backtracking matrix.
  • The same message-passing framework extends beyond thresholds to cluster-size distributions and bond percolation.Bond percolation follows by extending the site-percolation formulation.

2.5. Phase transition and critical phenomena

Percolation transitions on networks depend on network structure, with tree-like, Erdős–Rényi, and scale-free systems exhibiting distinct thresholds and critical behavior. Strong degree heterogeneity produces λ-dependent exponents, while regular mean-field behavior returns for sufficiently large λ.

  • 2.5.1. Percolation threshold: For tree-like networks, the threshold is determined by the non-trivial solution of the self-consistency equation, and site and bond percolation share the same critical point.The critical point occurs where the solution function becomes tangent to the R-axis at R_c = 0.
  • 2.5.1. Percolation threshold: For ER networks, the percolation threshold is pc = 1/⟨k⟩, reflecting the Poisson degree distribution.ER networks develop a giant cluster when ⟨k⟩ exceeds 1.
  • 2.5.1. Percolation threshold: For scale-free networks with 2 < λ < 3, the divergent second moment produces a vanished percolation threshold, pc = 0.Some other self-similar and hierarchical networks can also have zero threshold, without requiring tree-like structure.
  • 2.5.2. Scaling behaviors: Scale-free networks exhibit λ-dependent critical behavior despite lacking spatial constraints, unlike ER and regular random networks with mean-field exponents.The degree-distribution singularity generates the distinct scale-free behavior.
  • 2.5.2. Scaling behaviors: Regular mean-field exponents reappear when λ > λc = 4, where strong degree heterogeneity is sufficiently reduced.The crossover is associated with suppressing hubs in scale-free networks.
  • 2.5.2. Scaling behaviors: For 2 < λ < 3, site percolation has β = (4 − λ)/(3 − λ), distinguishing its critical exponent from bond percolation.This difference arises from the singular leading behavior of the generating-function equations.
  • 2.5.2. Scaling behaviors: The exponent τ remains theoretically unsettled for 2 < λ < 3, with competing results from the Potts-model formulation and tabulated treatments.One calculation evaluates τ at a small but fixed occupied probability because the threshold vanishes.

2.6. On clustered and correlated networks

Clustering, degree correlations, and small-world shortcuts modify how percolation proceeds beyond tree-like networks. Approximate, motif-based, and message-passing frameworks capture these effects within different structural limits.

  • Real networks commonly exhibit local clustering and degree correlations, so excess-degree branching alone cannot fully describe their percolation.Degree correlations require a joint degree-degree distribution for linked nodes.
  • Networks with low clustering: The low-clustering approximation revises excess degrees and the generating function, but it is not physically valid at C = 1.The approximation is designed for networks with low clustering.
  • For a fixed degree distribution, clustering raises the percolation threshold by reinforcing local cores while diluting global connections.Clustering nevertheless cannot restore a finite threshold in scale-free networks with 2 < λ < 3.
  • Networks with high clustering: Strong clustering can create distinct core and periphery transitions, making the low-clustering approximation inapplicable.High clustering also causes triangle-sharing overcounting that requires branching-process history beyond mean-field treatment.
  • Networks with high clustering: When motifs do not share links, each triangle or other motif can be treated as a special link or node, mapping the clustered network to a tree-like hyper-network.The approach requires distributions of all motifs attached to each node and becomes laborious for diverse structures.
  • Small-world networks: In small-world networks, finite clusters of the underlying lattice become effective nodes connected by sparse shortcuts, with shortcut loops nearly absent near or below threshold.The remaining loop structures are confined to clusters extracted from the underlying lattice.
  • Degree correlations: Assortative correlations make networks more robust, whereas disassortative correlations can make them fragile even when the degree second moment diverges.Random mixing in scale-free networks with 2 < λ < 3 can itself produce a vanished threshold.

2.7. On directed networks

Directed-network percolation distinguishes strongly, inward, outward, and weakly connected giant clusters. Self-consistent generating-function equations determine their emergence, while degree distributions and correlations shape thresholds and critical exponents.

  • Directed networks contain GSCC, GIC, GOC, and GWCC components distinguished by reachability and whether link directions are respected.Tubes and tendrils connect portions of the giant directed structure without belonging to the main strongly connected core.
  • The directed mean-field formulation uses separate probabilities R_I and R_O for links leading to and coming from the giant strongly connected cluster.Generating functions of in- and out-excess degrees define the self-consistent equations.
  • A GSCC exists when the self-consistent equations have a non-trivial solution rather than only R_I = R_O = 0.The GSCC size is then expressed from the two directional probabilities.
  • Directed-network thresholds can be obtained from the criterion for GSCC existence and from dilution through node or link removal.The threshold is represented by the corresponding directed-network transition equation.
  • For uncorrelated in- and out-degrees, the threshold reduces to pc = 1/⟨k⟩, and directed scale-free networks can retain a non-zero threshold when λ_I > 2 and λ_O > 2.λ_I and λ_O are the in-degree and out-degree distribution exponents.
  • GIC and GOC can have different β exponents, while GSCC follows the smaller of the two because it is their intersection.An effective λ* incorporates degree-distribution exponents and correlations.
  • With no degree correlations, bidirectional links favor GSCC emergence, and an infinitesimal fraction can be sufficient in scale-free networks.More generally, the threshold depends on the maximum eigenvalue of connectivity matrices.

2.8. Algorithm for network percolation

Network percolation algorithms either construct a percolation configuration before graph searching or update cluster information concurrently during occupation. The Newman-Ziff approach uses pointer-based trees to efficiently track clusters as links are occupied.

  • General algorithms: A universally applicable two-step algorithm first constructs the percolation configuration, then identifies clusters with breadth-first or depth-first searching.For a configuration with M links, graph searching takes O(M) time when neighbors can be scanned directly.
  • General algorithms: The two-step method has no specific requirement for percolation rules or network structures, but data structures such as adjacency matrices can increase its time complexity.Scanning an unknown structure is the minimal overhead only when network neighbors are directly accessible.
  • Newman-Ziff algorithm: The Newman-Ziff algorithm occupies nodes or links one by one while concurrently updating cluster-size information across a sequence of occupation probabilities.Its efficiency comes from blending configuration construction with cluster identification rather than treating them as standalone steps.
  • Newman-Ziff algorithm: Each cluster is represented as a pointer tree with one root, whose pointer can store the cluster size for efficient updates.Following pointer chains identifies roots, while path compression can improve efficiency.
  • Newman-Ziff algorithm: When an occupied link joins different clusters, the algorithm attaches the smaller tree to the larger root and updates the larger cluster size.If both endpoints already share a root, no further action is needed; equal-sized trees may be joined either way.

3. Network-specific percolation models

Network-specific percolation models extend classical occupation-based percolation by using diverse cluster-forming rules, often involving recursive or iterative processes. The review organizes these models by their rules and transition types.

  • Network-specific models: Network science commonly evaluates system performance through the emergence of a giant cluster as control parameters change.This framework applies across networked systems even when cluster formation is not simple probabilistic occupation.
  • Network-specific models: Network-specific cluster-forming rules are diverse and often include recursive or iterative processes rather than classical probabilistic occupation.The section distinguishes these rules from the occupation process used in classical percolation.
  • Network-specific models: A table lists the key rules and transition types for different network percolation models.The classification is organized around how clusters form and which transition behavior results.

3.1. k-core percolation

k-core percolation studies subnetworks whose nodes retain at least k neighbors after pruning or node removal. Its transitions depend strongly on k, threshold mixtures, network degree heterogeneity, directionality, and related activation or failure rules.

  • Model and phase transition characteristics: A k-core is the subnetwork in which every node has at least k links to other nodes in that subnetwork.k-core percolation studies the emergence of the giant k-core after occupying nodes with probability p, with k = 1 recovering classical percolation.
  • Model and phase transition characteristics: The k-core is obtained by iteratively removing nodes whose degrees are smaller than k.On finite tree-like networks, this pruning can remove the entire network for k ≥ 2, although infinite-network analysis remains possible.
  • Model and phase transition characteristics: For k = 1 and k = 2, the threshold equation reduces to the classical percolation equation, while k > 3 yields a distinguishable threshold.For k ≥ 3, a tangency point with nonzero R_k indicates a discontinuous transition.
  • Model and phase transition characteristics: The k-core transition combines a discontinuous jump with a critical singularity, giving it both first-order and second-order characteristics.For Bethe lattices, the reported order-parameter exponents are β = 1, 2, 1/2 for k = 1, 2, and k ≥ 3, respectively.
  • Model and phase transition characteristics: For scale-free networks, β_k=2/β_k=1 = λ −1 for 2 < λ < 3 and 2 for λ > 3.The review relates this to recovery of normal mean-field behavior for k-core percolation when λ > 3, compared with λ > 4 for classical percolation.
  • Model and phase transition characteristics: If the degree distribution has finite second moment, k-core percolation is hybrid; when it diverges for 2 < λ < 3, an infinite-order transition is observed.The review also notes that k-core critical behavior has been studied on clustered networks and other topologies.
  • Variants and related models: A binary heterogeneous k-core assigns thresholds k_a and k_b randomly with probabilities f and 1 − f, and its core size is a linear combination of the two threshold-specific sizes.The formulation uses the general heterogeneous k-core framework represented by the review’s equations.
  • Variants and related models: For k = (2, 3), continuous and hybrid transition lines meet at a tricritical point, whereas k = (1, 3) can exhibit two successive transitions.The k = (1, 3) case first shows a continuous transition and later a discontinuous hybrid transition for appropriate f; tricriticality is absent for k = (1, k).

3.2. Percolation on interdependent /multiplex networks

Interdependent or multiplex percolation iteratively combines connectivity pruning within layers with dependence-driven removals across layers, producing a mutual giant cluster whose transition can be abrupt and hybrid. The review also covers how coupling, spatial embedding, finite-size effects, and algorithms modify this behavior.

  • Model and phase transition characteristics: Interdependent percolation alternates layerwise pruning and dependence removals until only nodes reachable in every layer remain in the mutual giant cluster.Dependence links remove counterpart nodes across layers, while finite percolation clusters are pruned within each layer.
  • Model and phase transition characteristics: The mutual-giant-cluster transition is discontinuous and hybrid, with both abrupt change and critical exponents at the critical point.The number of cascading iterations diverges as p →pc and can identify the transition numerically.
  • Model and phase transition characteristics: Two interdependent ER networks have pc ≈2.4554/⟨k⟩, compared with pc = 1/⟨k⟩ for a single ER network.The corresponding minimum mean degree for observing a mutual giant cluster is ⟨k⟩≈2.4554.
  • Model and phase transition characteristics: Reducing coupled strength q can convert the discontinuous transition into a continuous one, whereas coupled lattices collapse abruptly for any finite q > 0.For spatial dependence links of typical length r, the transition is continuous for r < rmax ≈8 and discontinuous for larger r.
  • Model and phase transition characteristics: Spatial embedding changes the transition regime: for r < rmax, pc rises from 0.593 at r = 0 to 0.738 at r = rmax, then decreases to 0.683 at r = ∞.The review attributes this behavior to similar structures induced across spatially embedded layers, which break the usual cascading picture.
  • Algorithms and related models: Efficient algorithms address mutual-cluster detection in non-tree-like networks, including an O(N log N) approach and dynamic or wave-based procedures for tracking all mutual clusters.The review notes that tracing only the largest cluster can be too loose near criticality, where a smaller cluster may overtake it.

3.3. Explosive percolation

Explosive percolation modifies random link addition through competitive selection rules that suppress large-cluster growth. Although finite systems can display discontinuity-like signatures, the review reports that these transitions are continuous in the thermodynamic limit with unusual scaling properties.

  • Definition and construction: Achlioptas processes select among m potential links using a cluster-size rule, with positive correlation to s1 and s2 suppressing giant-cluster emergence.The best-of-m or min-cluster-m mechanism includes product and sum rules.
  • Definition and construction: For m = 1, the process reduces to ER percolation at ⟨k⟩= 1; for m ≥2, giant-cluster emergence is suppressed, producing explosive percolation.The product rule is f(s1, s2) = s1s2 and the sum rule is f(s1, s2) = s1 + s2.
  • Mechanism: In a complete network, the process can maintain maximum cluster size 2 for the first N/2 steps by linking isolated nodes before larger clusters form.Subsequent links merge clusters in progressively larger size stages.
  • Phase transition characteristics: A fixed number of randomly selected nodes yields a continuous transition, whereas m →∞ as N →∞ produces explosive percolation.Small m weakens suppression and blurs the largest-cluster jump.
  • Phase transition characteristics: Explosive percolation shows finite-system discontinuities, double-humped largest-cluster distributions, hysteresis, and non-analytic scaling, yet its transitions are continuous with unusual scaling properties.The order-parameter fluctuation does not disappear in the thermodynamic limit.

3.4. Percolation transition during the growth of networks

Growing-network models introduce nodes over time and can exhibit percolation transitions when new links are added probabilistically or according to attachment rules. Their growth mechanism changes threshold and critical behavior, including infinite-order transitions and rule-dependent reversions to second-order behavior.

  • Growing random network: The growing random network adds one node per step and connects two existing nodes with probability p, enabling a transition despite the network's changing size.Master equations track parameter increments and decrements during growth.
  • Growing random network: Its asymptotic degree distribution decreases with degree, while preferential attachment can produce a power-law degree distribution.The degree evolution is derived from rate equations and a stationary recursion.
  • Growing random network: The growing random network has pc = 1/8, lower than the configuration network with the same degree distribution.The review interprets this as evidence that growth facilitates giant-cluster formation in this model.
  • Phase transition characteristics: The growing-network transition can be infinite order, with S ∝ eα(p−pc)−β and β = 1/2 in the reported simulations.The giant-cluster size increases more slowly above threshold than in static networks because the core affects growth.
  • Variants and related models: In preferentially attached growing networks, power-law cluster sizes can persist throughout the phase without a giant cluster, indicating a critical state across that phase.The cited general model inserts links with probability proportional to (ki + a)(k_j + a).
  • Variants and related models: Achlioptas rules can restore a second-order transition in growing networks, although insufficient potential nodes or links allows growth to dominate the transition's nature.The scaling behavior depends on the specific competitive rule.

4. Applications to network structural analysis

Percolation-based structural analysis characterizes hierarchical organization, connectivity, and robustness across single, directed, spatial, and interdependent networks. It shows how degree heterogeneity, clustering, correlations, and attack strategies alter network resilience and phase transitions.

  • 4.1.1. Tree-like networks: Generating functions model shell branching and establish the giant-cluster existence condition in tree-like networks.G_0(x) describes sub-branchings from an arbitrary root, while G_1(x) represents branching after following outgoing links.
  • 4.1.1. Tree-like networks: Shell branching follows a power-law node-number distribution in a broad class of complex networks.The same branching process can construct configuration-model networks shell by shell.
  • 4.1.1. Tree-like networks: l ∝ln N in random networks, whereas scale-free networks can be ultrasmall or grow as ln ln N with system size.For some scale-free degree ranges, the shell count becomes size-independent; more generally, the diameter increases as ln ln N.
  • 4.2.1. Single networks: Percolation links degree structure and clustering to robustness: broader degree distributions strengthen ordinary networks, while clustering can create fragility or double transitions.Clustering raises the threshold for a fixed degree distribution, and strong clustering can induce a core-periphery structure with a double transition.
  • 4.2.1. Single networks: Targeted, localized, and directed attacks reveal vulnerabilities that random-removal analyses miss, including scale-free fragility and distinct directed giant components.For attacks weighted toward high-degree nodes, scale-free networks can become extremely fragile; directed networks may retain a GWCC without a GSCC.
  • 4.2.2. Multiplex networks: Interdependent networks reverse some single-network robustness patterns: broader degree distributions can increase pc, while dependent-node degree similarity improves robustness.Hub dependence on vulnerable low-degree nodes makes heterogeneous interdependent networks susceptible to cascades, whereas identical-degree partners strengthen them.

5. Applications to network dynamics

Percolation concepts connect network structure to epidemic spreading, cascading failures, traffic bottlenecks, and evolutionary-game transitions. Across these applications, cluster formation and percolation thresholds identify outbreak conditions, cascade regimes, functional bottlenecks, and transition universality.

  • Epidemic spreading: Epidemic spreading on networks is closely related to percolation: without a spanning cluster, infections remain confined to small areas.A spanning cluster supports large-scale transmission, whereas isolated susceptible clusters constrain outbreaks.
  • Epidemic spreading: Strong degree heterogeneity accelerates epidemic spreading because infections reaching hubs can trigger a cascade through decreasing degree classes.The outbreak time scale becomes smaller as κ increases, indicating faster spreading.
  • Epidemic spreading: For SF networks with 2 < λ < 3, the percolation threshold vanishes, so any non-zero infection rate can produce rapid epidemic spreading.This threshold behavior is reported for both SI and related epidemic analyses.
  • Cascading process on networks: Global cascades occur when vulnerable nodes percolate; depending on average degree and threshold, transitions can be continuous or discontinuous.At small thresholds, two phase transitions bound the structural regime supporting global cascades.
  • Urban traffic networks: Percolation identifies traffic bottleneck links whose congestion disintegrates giant functional clusters, while improving them can raise the traffic threshold more than improving other links.The bottlenecks vary across hours because traffic is dynamic and its critical threshold changes during the day.

6. Discussion and outlook

Percolation provides network science with concepts and quantitative tools for analyzing connectivity, resilience, and dynamics, while complex topologies extend percolation theory. The review synthesizes these developments and identifies unresolved questions involving mixed network structures, randomness, and higher-order organization.

  • Discussion: Percolation supplies a framework for studying complex networks because it describes connectivity patterns under random or semi-random mechanisms.Its applications extend from network structure to network dynamics.
  • Discussion: Strong heterogeneity, clustering, correlations, modularity, and hierarchy enrich percolation theory by producing new transition behaviors and mean-field characteristics.Examples include special transitions in scale-free and growing networks, explosive and hybrid transitions, and pruning-based structures.
  • Applications: The giant cluster offers a quantitative network-state criterion: its presence indicates functionality, whereas its absence indicates paralysis under the reviewed resilience interpretation.This makes percolation concepts directly useful for empirical network analysis.
  • Review scope: The review systematically traces network percolation from models and theoretical methods to applications, addressing a gap left by scattered discussions across network reviews.The scope spans developments and applications rather than a single network domain.
  • Open questions: Open questions concern whether mixtures of degree correlation, clustering, modularity, heterogeneity, small-world structure, and spatial constraints alter percolation transitions individually or collectively.Current theories often simplify these combined structures through approximate models.
  • Open questions: Percolation results vary across realizations, creating a tension with network identification methods that require deterministic conclusions.The review asks whether this fluctuation can instead provide additional structural information.
Loading 2101.11761v1…