The theory of percolation on hypergraphs

Abstract

Hypergraphs capture the higher-order interactions in complex systems and always admit a factor graph representation, consisting of a bipartite network of nodes and hyperedges. As hypegraphs are ubiquitous, investigating hypergraph robustness is a problem of major research interest. In the literature the robustness of hypergraphs as been so far only treated adopting factor-graph percolation which describe well higher-order interactions which remain functional even after the removal of one of more of their nodes. This approach, however, fall short to describe situations in which higher-order interactions fail when anyone of their nodes is removed, this latter scenario applying for instance to supply chains, catalytic networks, protein-interaction networks, networks of chemical reactions, etc. Here we show that in these cases the correct process to investigate is hypergraph percolation with is distinct from factor graph percolation. We build a message-passing theory of hypergraph percolation and we investigate its critical behavior using generating function formalism supported by Monte Carlo simulations on random graph and real data. Notably, we show that the node percolation threshold on hypergraphs exceeds node percolation threshold on factor graphs. Furthermore we show that differently from what happens in ordinary graphs, on hypergraphs the node percolation threshold and hyperedge percolation threshold do not coincide, with the node percolation threshold exceeding the hyperedge percolation threshold. These results demonstrate that any fat-tailed cardinality distribution of hyperedges cannot lead to the hyper-resilience phenomenon in hypergraphs in contrast to their factor graphs, where the divergent second moment of a cardinality distribution guarantees zero percolation threshold.

arXiv comment(12 pages, 4 figures)

References in corpus (35)

• Random graphs with arbitrary degree distributions and their applications
• Critical phenomena in complex networks
• Networks beyond pairwise interactions: structure and dynamics
• Higher-order organization of complex networks
• The physics of higher-order interactions in complex systems
• Dynamics on higher-order networks: A review
• Random graphs with clustering
• A message passing approach for general epidemic models
• Percolation on complex networks: Theory and application
• Percolation Transitions in Scale-Free Networks under Achlioptas Process
• Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes
• Redundant interdependencies boost the robustness of multilayer networks
• Message passing on networks with loops
• Higher-order percolation processes on multiplex hypergraphs
• Message passing theory for percolation models on multiplex networks with link overlap
• Recent advances of percolation theory in complex networks
• The dynamic nature of percolation on networks with triadic interactions
• Percolation on interacting, antagonistic networks
• Covering Problems and Core Percolations on Hypergraphs
• Rare events and discontinuous percolation transitions
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Message passing for vertex covers
• Cavity-based robustness analysis of interdependent networks: Influences of intranetwork and internetwork degree-degree correlations
• Hyper-cores promote localization and efficient seeding in higher-order processes
• A message-passing approach to epidemic tracing and mitigation with apps
• The phase transition in random catalytic sets
• Schumpeterian economic dynamics as a quantifiable minimum model of evolution
• Message passing methods on complex networks
• A class of models for random hypergraphs
• The nature of hypergraph $k$-core percolation problems
• $(k,q)$-core decomposition of hypergraphs
• Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
• Heterogeneous message passing for heterogeneous networks
• Random Recursive Hypergraphs
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes

Cited by in corpus (8)

• The nature of hypergraph $k$-core percolation problems
• Global topological synchronization of weighted simplicial complexes
• Higher-order triadic percolation on random hypergraphs
• General theory for extended-range percolation on simple and multiplex networks
• Triadic percolation on multilayer networks
• Analysis of the inference of ratings and rankings in complex networks using discrete exterior calculus on higher--order networks
• Connected components in networks with higher-order interactions
• Nonmonotonic percolation threshold in correlated networks and hypergraphs