Connected components in networks with higher-order interactions

We address the problem of defining connected components in hypergraphs, which are models for systems with higher-order interactions. For graphs with binary 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. In this Paper we show that higher-order interactions can be taken into consideration through a logic associated with the hyperedges, and we give two examples of such logical operations, namely, OR-logic and AND-logic; these logical operations can be considered two limiting cases corresponding with non-cooperative and fully cooperative interactions, respectively. 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, within 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.