Abstract
How can we detect a group of individuals whose connectivity persists and even strengthens over time? Despite extensive research on temporal networks, this practically pertinent question has been scantily investigated. In this paper, we formulate the problem of selecting a subset of nodes whose induced subgraph maximizes the overall edge count while abiding by time-aware spectral connectivity constraints. We solve the problem via a semidefinite programming (SDP) relaxation. Our experiments on a broad array of synthetic and real-world data establish the effectiveness of our method and deliver key insights on real-world temporal graphs.
Original language | English |
---|---|
Title of host publication | WWW 2024 Companion - Companion Proceedings of the ACM Web Conference |
Number of pages | 4 |
Publisher | Association for Computing Machinery, Inc. |
Publication date | 13 May 2024 |
Pages | 553-556 |
ISBN (Electronic) | 9798400701726 |
DOIs | |
Publication status | Published - 13 May 2024 |
Event | 33rd ACM Web Conference, WWW 2024 - Singapore, Singapore Duration: 13 May 2024 → 17 May 2024 |
Conference
Conference | 33rd ACM Web Conference, WWW 2024 |
---|---|
Country/Territory | Singapore |
City | Singapore |
Period | 13/05/2024 → 17/05/2024 |
Keywords
- dense subgraphs
- expanders
- spectral domination
- temporal graphs