Exact and sampling methods for mining higher-order motifs in large hypergraphs
arXiv:2209.10241 · doi:10.1007/s00607-023-01230-5
Abstract
Network motifs are recurrent, small-scale patterns of interactions observed frequently in a system. They shed light on the interplay between the topology and the dynamics of complex networks across various domains. In this work, we focus on the problem of counting occurrences of small sub-hypergraph patterns in very large hypergraphs, where higher-order interactions connect arbitrary numbers of system units. We show how directly exploiting higher-order structures speeds up the counting process compared to traditional data mining techniques for exact motif discovery. Moreover, with hyperedge sampling, performance is further improved at the cost of small errors in the estimation of motif frequency. We evaluate our method on several real-world datasets describing face-to-face interactions, co-authorship and human communication. We show that our approximated algorithm allows us to extract higher-order motifs faster and on a larger scale, beyond the computational limits of an exact approach.
arXiv commentIn press at Springer Computing. Computing (2023)
References in corpus (11)
- Networks beyond pairwise interactions: structure and dynamics
- Intensity and coherence of motifs in weighted complex networks
- The physics of higher-order interactions in complex systems
- Simplicial Closure and higher-order link prediction
- Motifs in Temporal Networks
- Temporal motifs in time-dependent networks
- Multilayer motif analysis of brain networks
- Higher-order motif analysis in hypergraphs
- Detecting early signs of the 2007-2008 crisis in the world trade
- Hypergraph Motifs: Concepts, Algorithms, and Discoveries
- FreSCo: Mining Frequent Patterns in Simplicial Complexes