ABSTRACT
Social network data analysis raises concerns about the privacy of related entities or individuals. To address this issue, organizations can publish data after simply replacing the identities of individuals with pseudonyms, leaving the overall structure of the social network unchanged. However, it has been shown that attacks based on structural identification (e.g., a walk-based attack) enable an adversary to re-identify selected individuals in an anonymized network. In this paper we explore the capacity of techniques based on random edge perturbation to thwart such attacks. We theoretically establish that any kind of structural identification attack can effectively be prevented using random edge perturbation and show that, surprisingly, important properties of the whole network, as well as of subgraphs thereof, can be accurately calculated and hence data analysis tasks performed on the perturbed data, given that the legitimate data recipient knows the perturbation probability as well. Yet we also examine ways to enhance the walk-based attack, proposing a variant we call probabilistic attack. Nevertheless, we demonstrate that such probabilistic attacks can also be prevented under sufficient perturbation. Eventually, we conduct a thorough theoretical study of the probability of success of any}structural attack as a function of the perturbation probability. Our analysis provides a powerful tool for delineating the identification risk of perturbed social network data; our extensive experiments with synthetic and real datasets confirm our expectations.
- L. Backstrom, C. Dwork, and J. M. Kleinberg. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In WWW, 2007. Google ScholarDigital Library
- F. Bonchi, A. Gionis, and T. Tassa. Identity obfuscation in graphs through the information theoretic lens. In ICDE, 2011. Google ScholarDigital Library
- J. Cheng, A. W.-C. Fu, and J. Liu. k-isomorphism: privacy preserving network publication against structural attacks. In SIGMOD, 2010. Google ScholarDigital Library
- G. Cormode, D. Srivastava, T. Yu, and Q. Zhang. Anonymizing bipartite graph data using safe groupings. In VLDB, 2008. Google ScholarDigital Library
- L. da F. Costa, F. A. Rodrigues, G. Travieso, and P. R. V. Boas. Characterization of complex networks: A survey of measurements.Adv. Phys., 2007.Google ScholarCross Ref
- M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979. Google ScholarDigital Library
- M. Hay, G. Miklau, D. Jensen, D. Towsley, and P. Weis. Resisting structural re-identification in anonymized social networks. PVLDB, 1(1):102--114, 2008. Google ScholarDigital Library
- M. Hay, G. Miklau, D. Jesen, P. Weis, and S. Srivastava. Anonymizing social networks. Technical Report 07--19, 2007.Google Scholar
- K. Liu and E. Terzi. Towards identity anonymization on graphs. In SIGMOD, 2008. Google ScholarDigital Library
- X. Ying and X. Wu. Randomizing social networks: a spectrum preserving approach. In SIAM SDM, 2008.Google ScholarCross Ref
- B. Zhou and J. Pei. Preserving privacy in social networks against neighborhood attacks. In ICDE, 2008. Google ScholarDigital Library
- L. Zou, L. Chen, and M. T. Özsu. k-automorphism: A general framework for privacy preserving network publication. In VLDB, 2009. Google ScholarDigital Library
Index Terms
- Delineating social network data anonymization via random edge perturbation
Recommendations
An Efficient and Robust Social Network De-anonymization Attack
WPES '16: Proceedings of the 2016 ACM on Workshop on Privacy in the Electronic SocietyReleasing connection data from social networking services can pose a significant threat to user privacy. In our work, we consider structural social network de-anonymization attacks, which are used when a malicious party uses connections in a public or ...
Identities Anonymization in Dynamic Social Networks
ICDM '11: Proceedings of the 2011 IEEE 11th International Conference on Data MiningPrivacy in social network data publishing is always an important concern. Nowadays most prior privacy protection techniques focus on static social networks. However, there are additional privacy disclosures in dynamic social networks due to the ...
Preserving Structural Properties in Edge-Perturbing Anonymization Techniques for Social Networks
Social networks are attracting significant interest from researchers in different domains, especially with the advent of social networking systems which enable large-scale collection of network information. However, as much as analysis of such social ...
Comments