Connected components in networks with higher-order interactions
arXiv:2504.03060 · doi:10.1088/2632-072X/ae1431
Abstract
We address the problem of defining connected components in hypergraphs, which are models for systems with higher-order interactions. For graphs with dyadic interactions, connected components are defined in terms of paths connecting nodes along the graph. However, defining connected components in hypergraphs is a more involved problem, as one needs to consider the higher-order nature of the interactions associated with the hyperedge. Higher-order interactions can be taken into consideration through a logic associated with the hyperedges, two examples being OR-logic and AND-logic; these logical operations can be considered two limiting cases corresponding to non-cooperative and fully cooperative interactions, respectively. In this paper we show how connected components can be defined in hypergraphs with OR or AND logic. While OR-logic and AND-logic provide the same connected components for nondirected hypergraphs, for directed hypergraphs the strongly connected component of AND-logic is a subset of the OR-logic strongly connected component. Interestingly, higher-order interactions change the general topological properties of connected components in directed hypergraphs. Notably, while for directed graphs the strongly connected component is the intersection of its in- and out-component, in hypergraphs with AND-logic the intersection of in- and out-component does not equal the strongly connected component. We develop a theory for the fraction of nodes that are part of the largest connected component and through comparison with real-world data we show that degree-cardinality correlations play a significant role.
40 pages, 10 figures
References in corpus (18)
- Networks beyond pairwise interactions: structure and dynamics
- Simplicial Closure and higher-order link prediction
- Generating simple random graphs with prescribed degree distribution
- Component sizes in networks with arbitrary degree distributions
- The temporal dynamics of group interactions in higher-order social networks
- Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
- Mapping the Structure of Directed Networks: Beyond the "Bow-tie" Diagram
- The theory of percolation on hypergraphs
- The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
- Emergence of the giant weak-component in directed random graphs with arbitrary degree distributions
- How does bond percolation happen in coloured networks?
- Message passing methods on complex networks
- Exact sampling of graphs with prescribed degree correlations
- Linear stability analysis for large dynamical systems on directed random graphs
- On the complexity of strongly connected components in directed hypergraphs
- A Cavity Master Equation for the continuous time dynamics of discrete spins models
- Computational core and fixed-point organisation in Boolean networks
- Network resilience against intelligent attacks constrained by degree dependent node removal cost