Finding Dense and Persistently Expansive Subgraphs

Petros Petsinis; Charalampos E. Tsourakakis; Panagiotis Karras

doi:10.1145/3589335.3651507

Finding Dense and Persistently Expansive Subgraphs

Petros Petsinis^*, Charalampos E. Tsourakakis, Panagiotis Karras

^*Corresponding author af dette arbejde

Institut for Datalogi

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer 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.

Originalsprog	Engelsk
Titel	WWW 2024 Companion - Companion Proceedings of the ACM Web Conference
Antal sider	4
Forlag	Association for Computing Machinery, Inc.
Publikationsdato	13 maj 2024
Sider	553-556
ISBN (Elektronisk)	9798400701726
DOI	https://doi.org/10.1145/3589335.3651507
Status	Udgivet - 13 maj 2024
Begivenhed	33rd ACM Web Conference, WWW 2024 - Singapore, Singapore Varighed: 13 maj 2024 → 17 maj 2024

Konference

Konference	33rd ACM Web Conference, WWW 2024
Land/Område	Singapore
By	Singapore
Periode	13/05/2024 → 17/05/2024

Adgang til dokumentet

10.1145/3589335.3651507

Andre filer og links

Link to publication in Scopus

Citationsformater

@inproceedings{de7ee9af2a81453d9157918f5094f920,

title = "Finding Dense and Persistently Expansive Subgraphs",

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.",

keywords = "dense subgraphs, expanders, spectral domination, temporal graphs",

author = "Petros Petsinis and Tsourakakis, {Charalampos E.} and Panagiotis Karras",

note = "Publisher Copyright: {\textcopyright} 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.; 33rd ACM Web Conference, WWW 2024 ; Conference date: 13-05-2024 Through 17-05-2024",

year = "2024",

month = may,

day = "13",

doi = "10.1145/3589335.3651507",

language = "English",

pages = "553--556",

booktitle = "WWW 2024 Companion - Companion Proceedings of the ACM Web Conference",

publisher = "Association for Computing Machinery, Inc.",

}

Finding Dense and Persistently Expansive Subgraphs. / Petsinis, Petros; Tsourakakis, Charalampos E.; Karras, Panagiotis.
WWW 2024 Companion - Companion Proceedings of the ACM Web Conference. Association for Computing Machinery, Inc., 2024. s. 553-556.

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Finding Dense and Persistently Expansive Subgraphs

AU - Petsinis, Petros

AU - Tsourakakis, Charalampos E.

AU - Karras, Panagiotis

PY - 2024/5/13

Y1 - 2024/5/13

N2 - 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.

AB - 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.

KW - dense subgraphs

KW - expanders

KW - spectral domination

KW - temporal graphs

UR - http://www.scopus.com/inward/record.url?scp=85194502410&partnerID=8YFLogxK

U2 - 10.1145/3589335.3651507

DO - 10.1145/3589335.3651507

M3 - Article in proceedings

AN - SCOPUS:85194502410

SP - 553

EP - 556

BT - WWW 2024 Companion - Companion Proceedings of the ACM Web Conference

PB - Association for Computing Machinery, Inc.

T2 - 33rd ACM Web Conference, WWW 2024

Y2 - 13 May 2024 through 17 May 2024

ER -

Finding Dense and Persistently Expansive Subgraphs

Abstract

Konference

Adgang til dokumentet

Andre filer og links

Fingeraftryk

Citationsformater