k-symmetry model for identity anonymization in social networks
Authors:
Open Access
- 22 March 2010
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 111-122
Abstract
With more and more social network data being released, protecting the sensitive information within social networks from leakage has become an important concern of publishers. Adversaries with some background structural knowledge about a target individual can easily re-identify him from the network, even if the identifiers have been replaced by randomized integers(i.e., the network is naively-anonymized). Since there exists numerous topological information that can be used to attack a victim's privacy, to resist such structural re-identification becomes a great challenge. Previous works only investigated a minority of such structural attacks, without considering protecting against re-identification under any potential structural knowledge about a target. To achieve this objective, in this paper we propose k-symmetry model, which modifies a naively-anonymized network so that for any vertex in the network, there exist at least k -- 1 structurally equivalent counterparts. We also propose sampling methods to extract approximate versions of the original network from the anonymized network so that statistical properties of the original network could be evaluated. Extensive experiments show that we can successfully recover a variety of such properties of the original network through aggregations on quite a small number of sample graphs.Keywords
Funding Information
- Ministry of Science and Technology of the People's Republic of China (2005CB321905)
- Shanghai Leading Academic Discipline Project (B114)
- Research Grants Council, University Grants Committee, Hong Kong (2.01E+11)
- National Natural Science Foundation of China (6.07E+15)
This publication has 14 references indexed in Scilit:
- k-automorphismProceedings of the VLDB Endowment, 2009
- Symmetry in complex networksDiscrete Applied Mathematics, 2008
- Network quotients: Structural skeletons of complex systemsPhysical Review E, 2008
- Resisting structural re-identification in anonymized social networksProceedings of the VLDB Endowment, 2008
- Emergence of symmetry in complex networksPhysical Review E, 2008
- Towards identity anonymization on graphs2008
- k-ANONYMITY: A MODEL FOR PROTECTING PRIVACYInternational Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002
- Protecting respondents identities in microdata releaseIEEE Transactions on Knowledge and Data Engineering, 2001
- Error and attack tolerance of complex networksNature, 2000
- A note on the graph isomorphism counting problemInformation Processing Letters, 1979