A brief survey on anonymization techniques for privacy preserving publishing of social network data

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A brief survey on anonymization techniques for privacy preserving publishing of social network data

Full text

Pdf (261 KB)

Source

ACM SIGKDD Explorations Newsletter archive
Volume 10 , Issue 2 (December 2008) table of contents

SESSION: Contributed articles table of contents

Pages 12-22

Year of Publication: 2008

ISSN:1931-0145

Authors

Bin Zhou	Simon Fraser University, Canada
Jian Pei	Simon Fraser University, Canada
WoShun Luk	Simon Fraser University, Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 83, Downloads (12 Months): 239, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1540276.1540279 What is a DOI?

ABSTRACT

Nowadays, partly driven by many Web 2.0 applications, more and more social network data has been made publicly available and analyzed in one way or another. Privacy preserving publishing of social network data becomes a more and more important concern. In this paper, we present a brief yet systematic review of the existing anonymization techniques for privacy preserving publishing of social network data. We identify the new challenges in privacy preserving publishing of social network data comparing to the extensively studied relational case, and examine the possible problem formulation in three important dimensions: privacy, background knowledge, and data utility. We survey the existing anonymization methods for privacy preservation in two categories: clustering-based approaches and graph modification approaches.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Rakesh Agrawal , Ramakrishnan Srikant , Dilys Thomas, Privacy preserving OLAP, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066187]
	2	N. Alon and J. Spencer. The Probabilistic Method. John Wiley, 1992.
	3	Lars Backstrom , Cynthia Dwork , Jon Kleinberg, Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242598]
	4	A. Campan and T.M. Truta. A clustering approach for data and structural anonymity in social networks. In Proceedings of the 2nd ACM SIGKDD International Workshop on Privacy, Security, and Trust in KDD (PinKDD'08), in Conjunction with KDD'08, Las Vegas, Nevada, USA, 2008.
	5	G. Cormode, D. Srivastava, T. Yu, and Q. Zhang. Anonymizing bipartite graph data using safe groupings. In Proceedings of the 34th International Conference on Very Large Databases (VLDB'08). ACM, 2008.
	6	R. Diestel. Graph Theory (3rd Edition), volume 173. Springer-Verlag, Heidelberg, 2005.
	7	Alexandre Evfimievski , Johannes Gehrke , Ramakrishnan Srikant, Limiting privacy breaches in privacy preserving data mining, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.211-222, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773174]
	8	L.C. Freeman, D.R. White, and A.K. Romney. Research Methods in Social Network Analysis. George Mason University Press, Fairfax, VA, 1989.
	9	Keith B. Frikken , Philippe Golle, Private social network analysis: how to assemble pieces of a graph privately, Proceedings of the 5th ACM workshop on Privacy in electronic society, October 30-30, 2006, Alexandria, Virginia, USA [doi>10.1145/1179601.1179619]
	10	Benjamin C. M. Fung , Ke Wang , Philip S. Yu, Anonymizing Classification Data for Privacy Preservation, IEEE Transactions on Knowledge and Data Engineering, v.19 n.5, p.711-725, May 2007 [doi>10.1109/TKDE.2007.1015]
	11	Jonathan Gross , Jay Yellen, Graph theory and its applications, CRC Press, Inc., Boca Raton, FL, 1999
	12	M. Hay, G. Miklau, D. Jensen, and D. Towsley. Resisting structural identification in anonymized social networks. In Proceedings of the 34th International Conference on Very Large Databases (VLDB'08). ACM, 2008.
	13	M. Hay, G. Miklau, D. Jensen, P. Weis, and S. Srivastava. Anonymizing social networks. Technical Report 07-19, University of Massachusetts Amherst, 2007.
	14	Jon M. Kleinberg, Challenges in mining social network data: processes, privacy, and paradoxes, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, p.4-5, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281195]
	15	Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Mondrian Multidimensional K-Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.25, April 03-07, 2006 [doi>10.1109/ICDE.2006.101]
	16	Jure Leskovec , Christos Faloutsos, Scalable modeling of real graphs using Kronecker multiplication, Proceedings of the 24th international conference on Machine learning, p.497-504, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273559]
	17	K. Liu, K. Das, T. Grandison, and H. Kargupta. Privacy-preserving data analysis on graphs and social networks. In H. Kargupta, J. Han, P. Yu, R. Motwani, and V. Kumar, editors, Next Generation Data Mining. CRC Press, 2008.
	18	Kun Liu , Evimaria Terzi, Towards identity anonymization on graphs, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376629]
	19	L. Liu, J. Wang, J. Liu, and J. Zhang. Privacy preserving in social networks against sensitive edge disclosure. Technical Report Technical Report CMIDA-HiPSCCS 006-08, Department of Computer Science, University of Kentucky, KY, 2008.
	20	Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
	21	Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	22	Stuart J. Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson Education, 2003
	23	Pierangela Samarati , Latanya Sweeney, Generalizing data to provide anonymity when disclosing information (abstract), Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.188, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275508]
	24	J. Scott. Social Network Analysis Handbook. Sage Publications Inc., 2000.
	25	J. Srivastava, M.A. Ahmad, N. Pathak, and D.K.-W. Hsu. Data mining based social network analysis from online behavior. Tutorial at the 8th SIAM International Conference on Data Mining (SDM'08), 2008.
	26	Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
	27	Y. Tao, X. Xiao, J. Li, and D. Zhang. On anti-corruption privacy preserving publication. In Proceedings of the 24th International Conference on Data Engineering (ICDE'08), pages 725--734, 2008.
	28	D.-W. Wang, C.-J. Liau, and T. sheng Hsu. Privacy protection in social network data disclosure based on granular computing. In Proceedings of the 2006 IEEE International Conference on Fuzzy Systems, pages 997--1003, Vancouver, BC, Canada, July 16-21, 2006.
	29	S. Wasserman and K. Faust. Social network analysis: Methods and applications. Cambridge University Press, 1994.
	30	D.J. Watts and S.H. Strogatz. Collective dynamics of "small-world" networks. Nature, 393(6684):440--442, June 1998.
	31	Barry Wellman, For a social network analysis of computer networks: a sociological perspective on collaborative work and virtual community, Proceedings of the 1996 ACM SIGCPR/SIGMIS conference on Computer personnel research, p.1-11, April 11-13, 1996, Denver, Colorado, United States [doi>10.1145/238857.238860]
	32	Xiaokui Xiao , Yufei Tao, Anatomy: simple and effective privacy preservation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	33	Xiaokui Xiao , Yufei Tao, Personalized privacy preservation, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142500]
	34	Jian Xu , Wei Wang , Jian Pei , Xiaoyuan Wang , Baile Shi , Ada Wai-Chee Fu, Utility-based anonymization using local recoding, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150504]
	35	Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining, p.721, December 09-12, 2002
	36	X. Ying and X. Wu. Randomizing social networks: a spectrum preserving approach. In Proceedings of the 2008 SIAM International Conference on Data Mining (SDM'08), pages 739--750. SIAM, 2008.
	37	E. Zheleva and L. Getoor. Preserving the privacy of sensitive relationships in graph data. In Proceedings of the 1st ACM SIGKDD Workshop on Privacy, Security, and Trust in KDD (PinKDD'07), 2007.
	38	B. Zhou and J. Pei. The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks. Submitted for publication.
	39	B. Zhou and J. Pei. Preserving privacy in social networks against neighborhood attacks. In Proceedings of the 24th IEEE International Conference on Data Engineering (ICDE'08), pages 506--515, Cancun, Mexico, 2008. IEEE Computer Society.