TY - JOUR
T1 - Exact and sampling methods for mining higher-order motifs in large hypergraphs
AU - Lotito, Quintino Francesco
AU - Musciotto, Federico
AU - Battiston, Federico
AU - Montresor, Alberto
N1 - Publisher Copyright:
© 2023, The Author(s).
PY - 2023/10/20
Y1 - 2023/10/20
N2 - 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.
AB - 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.
KW - Complex networks
KW - Higher-order networks
KW - Hypergraph algorithms
KW - Network motifs
UR - http://www.scopus.com/inward/record.url?scp=85174567805&partnerID=8YFLogxK
U2 - 10.1007/s00607-023-01230-5
DO - 10.1007/s00607-023-01230-5
M3 - Article
AN - SCOPUS:85174567805
SN - 0010-485X
VL - 106
SP - 475
EP - 494
JO - Computing
JF - Computing
IS - 2
ER -