The nature of hypergraph $k$-core percolation problems

Abstract

Hypergraphs are higher-order networks that capture the interactions between two or more nodes. Hypergraphs can always be represented by factor graphs, i.e. bipartite networks between nodes and factor nodes (representing groups of nodes). Despite this universal representation, here we reveal that $k$-core percolation on hypergraphs can be significantly distinct from $k$-core percolation on factor graphs. We formulate the theory of hypergraph $k$-core percolation based on the assumption that a hyperedge can only be intact if all its nodes are intact. This scenario applies for instance to supply chains where the production of a product requires all raw materials and all processing steps; in biology it applies to protein-interaction networks where protein complexes can only function if all the proteins are present, and it applies as well to chemical reaction networks where a chemical reaction can take place only when all the reactants are present. Formulating a message-passing theory for hypergraph $k$-core percolation, and combining it with the theory of critical phenomena on networks we demonstrate sharp differences with previously studied factor graph $k$-core percolation processes where it is allowed for hyperedges to have one or more damaged nodes and still be intact. To solve the dichotomy between $k$-core percolation on hypergraphs and on factor graphs, we define a set of pruning processes that act either exclusively on nodes or exclusively on hyperedges and depend of their second-neighborhood connectivity. We show that the resulting second-neighbor $k$-core percolation problems are significantly distinct from each other. Moreover we reveal that although these processes remain distinct from factor graphs $k$-core processes, when the pruning process acts exclusively on hyperedges the phase diagram is reduced to the one of factor graph $k$-cores.

arXiv comment(18 pages, 8 figures)

References in corpus (37)

• Identification of influential spreaders in complex networks
• 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
• Simplicial models of social contagion
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• k-core organization of complex networks
• Dynamics on higher-order networks: A review
• Random graphs with clustering
• Explosive higher-order Kuramoto dynamics on simplicial complexes
• Social contagion models on hypergraphs
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Simplicial complexes and complex systems
• Redundant interdependencies boost the robustness of multilayer networks
• Distinct types of eigenvector localization in networks
• Higher-order percolation processes on multiplex hypergraphs
• Message passing theory for percolation models on multiplex networks with link overlap
• Universal nonlinear infection kernel from heterogeneous exposure on higher-order networks
• The dynamic nature of percolation on networks with triadic interactions
• Covering Problems and Core Percolations on Hypergraphs
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Message passing for vertex covers
• Topological Percolation on Hyperbolic Simplicial Complexes
• Belief propagation for networks with loops
• The theory of percolation on hypergraphs
• Hyper-cores promote localization and efficient seeding in higher-order processes
• 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
• Superspreading k-cores at the center of COVID-19 pandemic persistence
• $(k,q)$-core decomposition of hypergraphs
• Heterogeneous message passing for heterogeneous networks
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Weighted projected networks: mapping hypergraphs to networks

Cited by in corpus (6)

• The theory of percolation on hypergraphs
• Global topological synchronization of weighted simplicial complexes
• The structural evolution of temporal hypergraphs through the lens of hyper-cores
• Analysis of the inference of ratings and rankings in complex networks using discrete exterior calculus on higher--order networks
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Superexponential growth of epidemics in networks with cliques