PlumX Metrics
Embed PlumX Metrics

Scalable Temporal Motif Densest Subnetwork Discovery

Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ISSN: 2154-817X, Page: 2536-2547
2024
  • 1
    Citations
  • 0
    Usage
  • 2
    Captures
  • 0
    Mentions
  • 0
    Social Media
Metric Options:   Counts1 Year3 Year

Metrics Details

  • Citations
    1
    • Citation Indexes
      1
      • CrossRef
        1
  • Captures
    2

Conference Paper Description

Finding dense subnetworks, with density based on edges or more complex structures, such as subgraphs or k-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.

Bibliographic Details

Provide Feedback

Have ideas for a new metric? Would you like to see something else here?Let us know