Physical Review Letters · 2014 · 62 citations · 41 references
Natural SciencesComputer ScienceMathematicsCombinatoricsDiscrete MathematicsTopologyGraph AlgorithmsGraph TheoryNetwork TheoryPercolation TheoryRandom WalksEigenvalue BoundsNetwork Percolation ThresholdsPercolationPercolation On NetworksPercolation ThresholdsRandom Walks On GraphsSite PercolationSpectral Radius
We construct a tight lower bound for the site percolation threshold on an infinite graph, which becomes exact for an infinite tree. The bound is given by the inverse of the maximal eigenvalue of the Hashimoto matrix used to count nonbacktracking walks on the original graph. Our bound always exceeds the inverse spectral radius of the graph's adjacency matrix, and it is also generally tighter than the existing bound in terms of the maximum degree. We give a constructive proof for existence of such an eigenvalue in the case of a connected infinite quasitransitive graph, a graph-theoretic analog of a translationally invariant system.
41
Statistical mechanics of complex networks
Réka Albert, Albert-Ĺaszló Barabási · Reviews of Modern Physics · 2002 · 20.6K citations · Full text
Error and attack tolerance of complex networks
Error and attack tolerance of complex networks
2000 · 6.5K citations
Scott Kirkpatrick · Reviews of Modern Physics · 1973 · 5.2K citations