2011 PrivacyPreservingSocialNetworkP

• (Tai et al., 2011) ⇒ Chih-Hua Tai, Philip S. Yu, De-Nian Yang, and Ming-Syan Chen. (2011). “Privacy-preserving Social Network Publication Against Friendship Attacks.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020599

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Privacy-preserving+Social+Network+Publication+Against+Friendship+Attacks
• http://dl.acm.org/citation.cfm?id=2020408.2020599&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; anonymization; data mining; privacy; social network

Abstract

Due to the rich information in graph data, the technique for privacy protection in published social networks is still in its infancy, as compared to the protection in relational databases. In this paper we identify a new type of attack called a friendship attack. In a friendship attack, an adversary utilizes the degrees of two vertices connected by an edge to re-identify related victims in a published social network data set. To protect against such attacks, we introduce the concept of k2-degree anonymity, which limits the probability of a vertex being re-identified to 1/k. For the k2-degree anonymization problem, we propose an Integer Programming formulation to find optimal solutions in small-scale networks. We also present an efficient heuristic approach for anonymizing large-scale social networks against friendship attacks. The experimental results demonstrate that the proposed approaches can preserve much of the characteristics of social networks.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 PrivacyPreservingSocialNetworkP	Philip S. Yu Chih-Hua Tai Ming-Syan Chen De-Nian Yang			Privacy-preserving Social Network Publication Against Friendship Attacks				10.1145/2020408.2020599		2011