Finding Dense and Persistently Expansive Subgraphs

Petros Petsinis*, Charalampos E. Tsourakakis, Panagiotis Karras

*Corresponding author for this work

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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 languageEnglish
Title of host publicationWWW 2024 Companion - Companion Proceedings of the ACM Web Conference
Number of pages4
PublisherAssociation for Computing Machinery, Inc.
Publication date13 May 2024
Pages553-556
ISBN (Electronic)9798400701726
DOIs
Publication statusPublished - 13 May 2024
Event33rd ACM Web Conference, WWW 2024 - Singapore, Singapore
Duration: 13 May 202417 May 2024

Conference

Conference33rd ACM Web Conference, WWW 2024
Country/TerritorySingapore
CitySingapore
Period13/05/202417/05/2024

Keywords

  • dense subgraphs
  • expanders
  • spectral domination
  • temporal graphs

Fingerprint

Dive into the research topics of 'Finding Dense and Persistently Expansive Subgraphs'. Together they form a unique fingerprint.

Cite this