On the Simultaneous Preservation of Privacy and Community Structure in Anonymized Networks
This work addresses privacy concerns in network analysis for researchers and practitioners, but it is incremental as it builds on existing models and methods.
The paper tackles the problem of performing community detection on networks while preserving privacy against adversaries with auxiliary correlated networks, deriving information-theoretic bounds for perfect deanonymization using the Stochastic Block Model and edge sub-sampling, and shows that percolation-based algorithms fail under these conditions.
We consider the problem of performing community detection on a network, while maintaining privacy, assuming that the adversary has access to an auxiliary correlated network. We ask the question "Does there exist a regime where the network cannot be deanonymized perfectly, yet the community structure could be learned?." To answer this question, we derive information theoretic converses for the perfect deanonymization problem using the Stochastic Block Model and edge sub-sampling. We also provide an almost tight achievability result for perfect deanonymization. We also evaluate the performance of percolation based deanonymization algorithm on Stochastic Block Model data-sets that satisfy the conditions of our converse. Although our converse applies to exact deanonymization, the algorithm fails drastically when the conditions of the converse are met. Additionally, we study the effect of edge sub-sampling on the community structure of a real world dataset. Results show that the dataset falls under the purview of the idea of this paper. There results suggest that it may be possible to prove stronger partial deanonymizability converses, which would enable better privacy guarantees.