Differentially Private Online Community Detection for Censored Block Models: Algorithms and Fundamental Limits

Mohamed Seifx; Liyan Xie; Andrea J. Goldsmith; H. Vincent Poor

doi:10.1109/TIFS.2025.3592556

Differentially Private Online Community Detection for Censored Block Models: Algorithms and Fundamental Limits

Mohamed Seifx, Liyan Xie, Andrea J. Goldsmith, H. Vincent Poor

Research output: Contribution to journal › Article › peer-review

Abstract

We study the private online change detection problem for dynamic communities, using a censored block model (CBM). We consider edge differential privacy (DP) in both local and central settings, and propose joint change detection and community estimation procedures for both scenarios. We seek to understand the fundamental tradeoffs between the privacy budget, detection delay, and exact community recovery of community labels. Further, we provide theoretical guarantees for the effectiveness of our proposed method by showing necessary and sufficient conditions for change detection and exact recovery under edge DP. Simulation and real data examples are provided to validate the proposed methods.

Original language	English (US)
Pages (from-to)	8312-8326
Number of pages	15
Journal	IEEE Transactions on Information Forensics and Security
Volume	20
DOIs	https://doi.org/10.1109/TIFS.2025.3592556
State	Published - 2025

All Science Journal Classification (ASJC) codes

Safety, Risk, Reliability and Quality
Computer Networks and Communications

Keywords

community detection
Differential privacy
graphs
online change point detection

Access to Document

10.1109/TIFS.2025.3592556

Cite this

@article{aa7861c618d443a98533ae3a2a3eab88,

title = "Differentially Private Online Community Detection for Censored Block Models: Algorithms and Fundamental Limits",

abstract = "We study the private online change detection problem for dynamic communities, using a censored block model (CBM). We consider edge differential privacy (DP) in both local and central settings, and propose joint change detection and community estimation procedures for both scenarios. We seek to understand the fundamental tradeoffs between the privacy budget, detection delay, and exact community recovery of community labels. Further, we provide theoretical guarantees for the effectiveness of our proposed method by showing necessary and sufficient conditions for change detection and exact recovery under edge DP. Simulation and real data examples are provided to validate the proposed methods.",

keywords = "community detection, Differential privacy, graphs, online change point detection",

author = "Mohamed Seifx and Liyan Xie and Goldsmith, \{Andrea J.\} and Poor, \{H. Vincent\}",

note = "Publisher Copyright: {\textcopyright} 2005-2012 IEEE.",

year = "2025",

doi = "10.1109/TIFS.2025.3592556",

language = "English (US)",

volume = "20",

pages = "8312--8326",

journal = "IEEE Transactions on Information Forensics and Security",

issn = "1556-6013",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Differentially Private Online Community Detection for Censored Block Models

T2 - Algorithms and Fundamental Limits

AU - Seifx, Mohamed

AU - Xie, Liyan

AU - Goldsmith, Andrea J.

AU - Poor, H. Vincent

PY - 2025

Y1 - 2025

N2 - We study the private online change detection problem for dynamic communities, using a censored block model (CBM). We consider edge differential privacy (DP) in both local and central settings, and propose joint change detection and community estimation procedures for both scenarios. We seek to understand the fundamental tradeoffs between the privacy budget, detection delay, and exact community recovery of community labels. Further, we provide theoretical guarantees for the effectiveness of our proposed method by showing necessary and sufficient conditions for change detection and exact recovery under edge DP. Simulation and real data examples are provided to validate the proposed methods.

AB - We study the private online change detection problem for dynamic communities, using a censored block model (CBM). We consider edge differential privacy (DP) in both local and central settings, and propose joint change detection and community estimation procedures for both scenarios. We seek to understand the fundamental tradeoffs between the privacy budget, detection delay, and exact community recovery of community labels. Further, we provide theoretical guarantees for the effectiveness of our proposed method by showing necessary and sufficient conditions for change detection and exact recovery under edge DP. Simulation and real data examples are provided to validate the proposed methods.

KW - community detection

KW - Differential privacy

KW - graphs

KW - online change point detection

UR - https://www.scopus.com/pages/publications/105012031360

UR - https://www.scopus.com/inward/citedby.url?scp=105012031360&partnerID=8YFLogxK

U2 - 10.1109/TIFS.2025.3592556

DO - 10.1109/TIFS.2025.3592556

M3 - Article

AN - SCOPUS:105012031360

SN - 1556-6013

VL - 20

SP - 8312

EP - 8326

JO - IEEE Transactions on Information Forensics and Security

JF - IEEE Transactions on Information Forensics and Security

ER -

Differentially Private Online Community Detection for Censored Block Models: Algorithms and Fundamental Limits

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this