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.
arXiv commentpre-submission version, 10 pages and 5 figures + SI
References in corpus (33)
- The architecture of complex weighted networks
- Temporal Networks
- Networks beyond pairwise interactions: structure and dynamics
- Higher-order organization of complex networks
- Intensity and coherence of motifs in weighted complex networks
- The physics of higher-order interactions in complex systems
- Simplicial models of social contagion
- Structural measures for multiplex networks
- Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
- Evolutionary dynamics of higher-order interactions in social networks
- Simplicial Closure and higher-order link prediction
- Motifs in Temporal Networks
- Explosive higher-order Kuramoto dynamics on simplicial complexes
- Complex Networks as Hypergraphs
- Higher-order interactions in complex networks of phase oscillators promote abrupt synchronization switching
- Temporal motifs in time-dependent networks
- Can co-location be used as a proxy for face-to-face contacts?
- Random walks on hypergraphs
- Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
- Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
- Data on face-to-face contacts in an office building suggests a low-cost vaccination strategy based on community linkers
- Multilayer motif analysis of brain networks
- Multiorder Laplacian for synchronization in higher-order networks
- Chaos in generically coupled phase oscillator networks with nonpairwise interactions
- Higher-order clustering in networks
- Hypergraph reconstruction from network data
- Simplicial contagion in temporal higher-order networks
- Detecting early signs of the 2007-2008 crisis in the world trade
- Hypergraph Motifs: Concepts, Algorithms, and Discoveries
- Growing scale-free simplices
- Mapping flows on hypergraphs
- Opinion Dynamics with Multi-Body Interactions
- 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