Abstract
Efficient and adaptive network topology design is fundamental in communication systems. A key problem is to construct low-cost structures like minimum spanning trees (MSTs) from uncertain and stochastic link measurements. However, topology and link data often reveal sensitive attributes, including location and traffic patterns, posing privacy risks. We propose Differentially Private Matroid Bandits, an online learning framework for consecutive MST construction with formal privacy guarantees. Modeling the problem as stochastic optimization over a matroid, we develop algorithms that balance exploration and exploitation while ensuring differential privacy in both central and local models. We establish regret upper bounds capturing the trade-offs among privacy, accuracy, and structural complexity. Experiments on real network data show our approach achieves near-optimal performance with strong privacy protection.
| Original language | English |
|---|---|
| Title of host publication | Differentially Private Matroid Bandits for Online Network Topology Optimization |
| Publisher | ACM |
| Pages | 19-24 |
| Number of pages | 6 |
| ISBN (Electronic) | 9798400719745 |
| DOIs | |
| Publication status | Published - 13 Nov 2025 |
Fingerprint
Dive into the research topics of 'Differentially Private Matroid Bandits for Online Network Topology Optimization'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver