Tight lower bound for percolation threshold on a quasi-regular graph

Abstract

We construct an exact expression for the site percolation threshold p_c on a quasi-regular tree, and a related exact lower bound for a quasi-regular graph. Both are given by the inverse spectral radius of the appropriate Hashimoto matrix used to count non-backtracking walks. The obtained bound always exceeds the inverse spectral radius of the original graph, and it is also generally tighter than the existing bound in terms of the maximum degree.

5 pages, 2 figures

References in corpus (17)

• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Random graphs with arbitrary degree distributions and their applications
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Dynamical and correlation properties of the Internet
• Epidemics and percolation in small-world networks
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Random graphs with clustering
• Networks and the Epidemiology of Infectious Disease
• Percolation on sparse networks
• Percolation on correlated networks
• Fault-Tolerance of "Bad" Quantum Low-Density Parity Check Codes
• Percolation on dense graph sequences
• Weighted percolation on directed networks
• Quantitative modeling of degree-degree correlation in complex networks

Cited by in corpus (37)

• Epidemic processes in complex networks
• Random walks and diffusion on networks
• Robustness and resilience of complex networks
• Statistical physics of inference: Thresholds and algorithms
• Unification of theoretical approaches for epidemic spreading on complex networks
• Percolation on complex networks: Theory and application
• Percolation on sparse networks
• Percolation in real interdependent networks
• Explosive Percolation: Novel critical and supercritical phenomena
• Predicting percolation thresholds in networks
• Network science based quantification of resilience demonstrated on the Indian Railways Network
• Predicting the speed of epidemics spreading on networks
• Leveraging percolation theory to single out influential spreaders in networks
• Breaking of the site-bond percolation universality in networks
• Stability of a Giant Connected Component in a Complex Network
• Epidemic spreading and bond percolation in multilayer networks
• Beyond the locally tree-like approximation for percolation on real networks
• Message passing methods on complex networks
• Percolation in real multiplex networks
• Nonbacktracking expansion of finite graphs
• Assessing node risk and vulnerability in epidemics on networks
• Heterogeneous micro-structure of percolation in sparse networks
• Targeted influence maximization in complex networks
• Dynamic range maximization in excitable networks
• Node Immunization with Non-backtracking Eigenvalues
• Heterogeneous message passing for heterogeneous networks
• Spectral estimation of the percolation transition in clustered networks
• Explosive percolation in thresholded networks
• Assessing Percolation Threshold Based on High-Order Non-Backtracking Matrices
• Belief propagation on networks with cliques and chordless cycles
• Observability transition in real networks
• Scaling and universality for percolation in random networks: A unified view
• Analysis of the susceptible-infected-susceptible epidemic dynamics in networks via the non-backtracking matrix
• Backtracking activation impacts the criticality of excitable networks
• Numerical assessment of the percolation threshold using complement networks
• Combinatorial approach to spreading processes on networks
• Vaccination with partial transmission and social distancing on contact networks