Belief propagation on networks with cliques and chordless cycles
arXiv:2301.07959 · doi:10.1103/PhysRevE.107.054303
Abstract
It is well known that tree-based theories can describe the properties of undirected clustered networks with extremely accurate results [S. Melnik, \textit{et al}. Phys. Rev. E 83, 036112 (2011)]. It is reasonable to suggest that a motif based theory would be superior to a tree one; since additional neighbour correlations are encapsulated in the motif structure. In this paper we examine bond percolation on random and real world networks using belief propagation in conjunction with edge-disjoint motif covers. We derive exact message passing expressions for cliques and chordless cycles of finite size. Our theoretical model gives good agreement with Monte Carlo simulation and offers a simple, yet substantial improvement on traditional message passing showing that this approach is suitable to study the properties of random and empirical networks.
14 pages, 7 figures
References in corpus (14)
- Community detection in networks: A user guide
- Random graphs with clustering
- A message passing approach for general epidemic models
- Percolation on sparse networks
- Random graphs containing arbitrary distributions of subgraphs
- Hopping on the Bethe lattice: Exact results for densities of states and dynamical mean-field theory
- Tight lower bound for percolation threshold on a quasi-regular graph
- Network clique cover approximation to analyze complex contagions through group interactions
- Belief propagation for networks with loops
- Spectra of random networks with arbitrary degrees
- Cavity analysis on the robustness of random networks against targeted attacks: Influences of degree-degree correlations
- Minimum Long-Loop Feedback Vertex Set and Network Dismantling
- Degree correlations in graphs with clique clustering
- An exact formula for percolation on higher-order cycles