Higher-order motif analysis in hypergraphs

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 (6)

• The physics of higher-order interactions in complex systems
• Random walks on hypergraphs
• Hypergraph reconstruction from network data
• Simplicial contagion in temporal higher-order networks
• Mapping flows on hypergraphs
• Local topological moves determine global diffusion properties of hyperbolic higher-order networks

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