The effect of constraints on information loss and risk for clustering and modification based graph anonymization methods
This work addresses privacy protection in social network data for researchers and practitioners, offering an incremental improvement over existing anonymization techniques.
The paper tackles the problem of anonymizing Online Social Network graphs by introducing constraints on node selection to reduce information loss while maintaining acceptable disclosure risk. Results show that methods with constraints outperform existing perturbation approaches across three real datasets, six information loss measures, and five adversary queries.
In this paper we present a novel approach for anonymizing Online Social Network graphs which can be used in conjunction with existing perturbation approaches such as clustering and modification. The main insight of this paper is that by imposing additional constraints on which nodes can be selected we can reduce the information loss with respect to key structural metrics, while maintaining an acceptable risk. We present and evaluate two constraints, 'local1' and 'local2' which select the most similar subgraphs within the same community while excluding some key structural nodes. To this end, we introduce a novel distance metric based on local subgraph characteristics and which is calibrated using an isomorphism matcher. Empirical testing is conducted with three real OSN datasets, six information loss measures, five adversary queries as risk measures, and different levels of k-anonymity. The results show that overall, the methods with constraints give the best results for information loss and risk of disclosure.