Temporal hypergraph patterns reveal local organization in complex networks
Motifs in temporal hypergraphs
Social and Information NetworksData Structures and Algorithms
Summary
Many complex systems involve groups interacting over time, not just pairs of nodes. This paper extends network motif analysis to capture these group interactions with timing, called temporal hypergraph motifs. The authors develop new algorithms that count such patterns efficiently and show these motifs help reveal unique local structures in data like emails, collaborations, and bitcoin transactions. Their work also includes tools to check which patterns are statistically significant.
What this means in practice
- •For network analysts: Extract temporal group interaction patterns to identify structural motifs unique to different real-world systems like social contacts or financial transactions.
- •For collaboration platform teams: Monitor persistent collaboration patterns over time to improve team coordination and detect emerging group dynamics.
Authors
Quintino Francesco Lotito, Lorenzo Betti, Federico Battiston, Giuseppe Francesco Italiano
Abstract
Network motifs, recurrent local patterns of interactions in graphs, provide fundamental insights on the interplay between structure and functionality in complex systems. Many real-world systems are not well represented by traditional static pairwise networks, as interactions may involve groups of nodes, occur over time, or encode directionality. In this paper, we introduce temporal motifs for hypergraphs and directed hypergraphs, extending motif analysis to timestamped many-body interactions. We formalize the corresponding mining problem, study the combinatorial structure of these motifs, and develop exact algorithms for their enumeration. In particular, we propose a dynamic programming algorithm that substantially reduces the computational cost of motif mining, achieving orders of magnitude speedups on empirical datasets. We also introduce a null model for temporal hypergraphs to assess the statistical over- and under-expression of motifs. Applying the proposed framework to real-world datasets from different domains, including face-to-face contacts, scientific collaborations, e-mail exchanges, and Bitcoin transactions, we show that temporal hypergraph motifs reveal distinct forms of local organization across systems. Finally, we demonstrate their use as an exploratory tool through focused case studies on persistent patterns in scientific collaborations and e-mail communications.