Scalable Temporal Motif Densest Subnetwork Discovery

Finding dense subnetworks, with density based on edges or more complex structures, such as subgraphs or 𝑘-cliques, is a fundamental algorithmic problem with many applications. While the problem has been studied extensively in static networks, much remains to be explored for temporal networks.

In this work we introduce the novel problem of identifying the temporal motif densest subnetwork, i.e., the densest subnetwork with respect to temporal motifs, which are high-order patterns characterizing temporal networks. Identifying temporal motifs is an extremely challenging task, and thus, efficient methods are required. To address this challenge, we design two novel randomized approximation algorithms with rigorous probabilistic guarantees that provide high-quality solutions. We perform extensive experiments showing that our methods outperform baselines. Furthermore, our algorithms scale on networks with up to billions of temporal edges, while baselines cannot handle such large networks. We use our techniques to analyze a financial network and show that our formulation reveals important network structures, such as bursty temporal events and communities of users with similar interests.

• Theory of computation → Graph algorithms analysis; • Mathematics of computing → Probabilistic algorithms.