Higher-order motif analysis in hypergraphs
arXiv:2108.03192 · doi:10.1038/s42005-022-00858-7
Abstract
A deluge of new data on social, technological and biological networked systems suggests that a large number of interactions among system units are not limited to pairs, but rather involve a higher number of nodes. To properly encode such higher-order interactions, richer mathematical frameworks such as hypergraphs are needed, where hyperlinks describe connections among an arbitrary number of nodes. Here we introduce the concept of higher-order motifs, small connected subgraphs where vertices may be linked by interactions of any order. We provide lower and upper bounds on the number of higher-order motifs as a function of the motif size, and propose an efficient algorithm to extract complete higher-order motif profiles from empirical data. We identify different families of hypergraphs, characterized by distinct higher-order connectivity patterns at the local scale. We also capture evidences of structural reinforcement, a mechanism that associates higher strengths of higher-order interactions for the nodes that interact more at the pairwise level. Our work highlights the informative power of higher-order motifs, providing a first way to extract higher-order fingerprints in hypergraphs at the network microscale.
pre-submission version, 10 pages and 5 figures + SI
References in corpus (4)
Cited by in corpus (22)
- Higher-order interactions shape collective dynamics differently in hypergraphs and simplicial complexes
- Inference of hyperedges and overlapping communities in hypergraphs
- The temporal dynamics of group interactions in higher-order social networks
- Community Detection in Large Hypergraphs
- Higher-Order Components Dictate Higher-Order Contagion Dynamics in Hypergraphs
- Hypergraphx: a library for higher-order network analysis
- Contagion dynamics on hypergraphs with nested hyperedges
- Exact and sampling methods for mining higher-order motifs in large hypergraphs
- Hyperlink communities in higher-order networks
- A framework to generate hypergraphs with community structure
- Hypercore Decomposition for Non-Fragile Hyperedges: Concepts, Algorithms, Observations, and Applications
- Multiplex measures for higher-order networks
- How Transitive Are Real-World Group Interactions? -- Measurement and Reproduction
- Filtering higher-order datasets
- Simplicial temporal networks from Wi-Fi data in a University Campus: the effects of restrictions on epidemic spreading
- Compression-based inference of network motif sets
- Higher-order shortest paths in hypergraphs
- Community detection in hypergraphs through hyperedge percolation
- Clustering Coefficient Reflecting Pairwise Relationships within Hyperedges
- HIF: The hypergraph interchange format for higher-order networks
- Beyond Trivial Edges: A Fractional Approach to Cohesive Subgraph Detection in Hypergraphs
- Identifying maximal sets of significantly interacting nodes in higher-order networks