Exact solution of bond percolation on small arbitrary graphs

Abstract

We introduce a set of iterative equations that exactly solves the size distribution of components on small arbitrary graphs after the random removal of edges. We also demonstrate how these equations can be used to predict the distribution of the node partitions (i.e., the constrained distribution of the size of each component) in undirected graphs. Besides opening the way to the theoretical prediction of percolation on arbitrary graphs of large but finite size, we show how our results find application in graph theory, epidemiology, percolation and fragmentation theory.

5 pages and 3 figures

References in corpus (5)

• Critical phenomena in complex networks
• Random graphs containing arbitrary distributions of subgraphs
• Bond percolation on a class of clustered random networks
• Critical surfaces for general bond percolation problems
• Zipf's law in Nuclear Multifragmentation and Percolation Theory

Cited by in corpus (5)

• Percolation on complex networks: Theory and application
• General and exact approach to percolation on random graphs
• Bond percolation on a class of correlated and clustered random graphs
• An exact formula for percolation on higher-order cycles
• Exact analytical solution of irreversible binary dynamics on networks