Differentially Private Online Community Detection for Censored Block Models: Algorithms and Fundamental Limits
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908578448670720 |
|---|---|
| author | Seif, Mohamed Xie, Liyan Goldsmith, Andrea J. Poor, H. Vincent |
| author_facet | Seif, Mohamed Xie, Liyan Goldsmith, Andrea J. Poor, H. Vincent |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_05724 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Differentially Private Online Community Detection for Censored Block Models: Algorithms and Fundamental Limits Seif, Mohamed Xie, Liyan Goldsmith, Andrea J. Poor, H. Vincent Social and Information Networks Cryptography and Security Information Theory 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. |
| title | Differentially Private Online Community Detection for Censored Block Models: Algorithms and Fundamental Limits |
| topic | Social and Information Networks Cryptography and Security Information Theory |
| url | https://arxiv.org/abs/2405.05724 |