Abstract
The proliferation of network data in various application domains has raised privacy concerns for the individuals involved. Recent studies show that simply removing the identities of the nodes before publishing the graph/social network data does not guarantee privacy. The structure of the graph itself, and in its basic form the degree of the nodes, can be revealing the identities of individuals. To address this issue, we study a specific graph-anonymization problem. We call a graph k-degree anonymous if for every node v, there exist at least k-1 other nodes in the graph with the same degree as v. This definition of anonymity prevents the re-identification of individuals by adversaries with a priori knowledge of the degree of certain nodes. We formally define the graph-anonymization problem that, given a graph G, asks for the k-degree anonymous graph that stems from G with the minimum number of graph-modification operations. We devise simple and efficient algorithms for solving this problem. Our algorithms are based on principles related to the realizability of degree sequences. We apply our methods to a large spectrum of synthetic and real data sets and demonstrate their efficiency and practical utility.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This work was done when the authors Kun Liu and Evimaria Terzi were at IBM Almaden Research Center.
References
C. C. Aggarwal, and P. S. Yu. Privacy-Preserving Data Mining: Models and Algorithms, vol. 34 of Advances in Database Systems. Springer, 233 Spring Street, New York, NY 10013, USA, 2008.
L. Backstrom, C. Dwork, and J. M. Kleinberg. Wherefore art thou R3579X?: Anonymized social networks, hidden patterns, and structural steganography. In Proceedings of the 16th International Conference on World Wide Web (WWW’07) (Alberta, Canada, May 2007), pp. 181–190.
A.-L. Barabási, and R. Albert. Emergence of scaling in random networks. Science 286, 5439 (October 1999), 509–512.
R. J. Bayardo, and R. Agrawal. Data privacy through optimal k-anonymization. In Proceedings of the 21st International Conference on Data Engineering (ICDE’05), pages 217–228 Tokyo, Japan, April 2005.
S. Boyd, and L. Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, 2004.
T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990.
I. Diakonikolas, and M. Yannakakis. Succinct approximate convex pareto curves. In SODA, pages 74–83 2008.
P. Erdös, and T. Gallai. Graphs with prescribed degrees of vertices. Mat. Lapok, 11:264–274, 1960.
L. Getoor, and C. P. Diehl. Link mining: a survey. ACM SIGKDD Explorations Newsletter, 7, (2): 3–12, 2005.
S. L. Hakimi. On realizability of a set of integers as degrees of the vertices of a linear graph. Journal of the Society for Industrial and Applied Mathematics, 10(3): 496–506, 1962.
M. Hay, G. Miklau, D. Jensen, D. Towsely, and P. Weis. Resisting structural re-identification in anonymized social networks. In Proceedings of the VLDB Endowment. Volume 1, Issue 1, pages 102–114, Publisher VLDB Endowment, August 2008.
M. Hay, G. Miklau, D. Jensen, P. Weis, and S. Srivastava. Anonymizing social networks. Technical report, University of Massachusetts Amherst, 2007.
A. Korolova, R. Motwani, S. U. Nabar, and 0002, Y. X. Link privacy in social networks. In CIKM, pages 289–298, 2008.
Y.-S. Lee. Graphical demonstration of an optimality property of the median. The American Statistician 49(4): 369–372, November 1995.
K. Liu, and E. Terzi. Towards identity anonymization on graphs. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD’08), pages 93–106, Vancouver, Canada, June 2008.
A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-diversity: Privacy beyond k-anonymity. In Proceedings of the 22nd International Conference on Data Engineering (ICDE’06), pages 24, Atlanta, GA, April 2006, 2006.
A. Meyerson, and R. Williams. On the complexity of optimal k-anonymity. In Proceedings of the Twenty-third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS’04), pages 223–228, Paris, France, 2004, 2004.
J. Pei, and B. Zhou. Preserving privacy in social networks against neighborhood attacks. In Proceedings of the 24th International Conference on Data Engineering (ICDE’08), Cancun, Mexico, April 2008.
P. Samarati, and L. Sweeney. Generalizing data to provide anonymity when disclosing information. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS’98) page 188 Seattle, WA, 1998.
D. J. Watts. Networks, dynamics, and the small-world phenomenon. American Journal of Sociology, 105(2): 493–527, September 1999.
D. J. Watts, and S. H. Strogatz. Collective dynamics of small-world networks. Nature 393 (6684): 409–410, June 1998.
X. Ying, and X. Wu. Randomizing social networks: a spectrum preserving approach. In Proceedings of SIAM International Conference on Data Mining (SDM’08), pages 739–750, Atlanta, GA, April 2008.
E. Zheleva, and L. Getoor. Preserving the privacy of sensitive relationships in graph data. In Proceedings of the International Workshop on Privacy, Security, and Trust in KDD (PinKDD’07), pages 153–171, San Jose, CA, August 2007.
B. Zhou, J. Pei, and W.-S. Luk. A brief survey on anonymization techniques for privacy preserving publishing of social network data. ACM SIGKDD Explorations 10(2): 12–22, December, 2008.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Clarkson, K.L., Liu, K., Terzi, E. (2010). Toward Identity Anonymization in Social Networks. In: Yu, P., Han, J., Faloutsos, C. (eds) Link Mining: Models, Algorithms, and Applications. Springer, New York, NY. https://doi.org/10.1007/978-1-4419-6515-8_14
Download citation
DOI: https://doi.org/10.1007/978-1-4419-6515-8_14
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4419-6514-1
Online ISBN: 978-1-4419-6515-8
eBook Packages: Biomedical and Life SciencesBiomedical and Life Sciences (R0)