Towards identity anonymization on graphs

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 datasets and demonstrate their efficiency and practical utility.

REFERENCES

• 1: Charu C. Aggarwal , Philip S. Yu, Privacy-Preserving Data Mining: Models and Algorithms, Springer Publishing Company, Incorporated, 2008
• 2: 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]
• 3: Barabási, A.-L., and Albert, R. Emergence of scaling in random networks. Science 286, 5439 (October 1999), 509--512.
• 4: Roberto J. Bayardo , Rakesh Agrawal, Data Privacy through Optimal k-Anonymization, Proceedings of the 21st International Conference on Data Engineering, p.217-228, April 05-08, 2005 [doi>10.1109/ICDE.2005.42]
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: Erdös, P., and Gallai, T. Graphs with prescribed degrees of vertices. Mat. Lapok (1960).
• 7: 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]
• 8: Lise Getoor , Christopher P. Diehl, Link mining: a survey, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.3-12, December 2005 [doi>10.1145/1117454.1117456]
• 9: Hakimi, S. L. 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 (1962), 496--506.
• 10: Hay, M., Miklau, G., Jensen, D., Weis, P., and Srivastava, S. Anonymizing social networks. Technical report, University of Massachusetts Amherst, 2007.
• 11: Lee, Y.-S. Graphical demonstration of an optimality property of the median. The American Statistician 49, 4 (November 1995), 369--372.
• 12: 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]
• 13: Adam Meyerson , Ryan Williams, On the complexity of optimal K-anonymity, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055591]
• 14: Pei, J., and Zhou, B. Preserving privacy in social networks against neighborhood attacks. In Proceedings of the 24th International Conference on Data Engineering (ICDE'08) (Cancun, Mexico, April 2008).
• 15: 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]
• 16: Watts, D. J. Networks, dynamics, and the small-world phenomenon. American Journal of Sociology 105, 2 (September 1999), 493--527.
• 17: Watts, D. J., and Strogatz, S. H. Collective dynamics of small-world networks. Nature 393, 6684 (June 1998), 409--410.
• 18: Ying, X., and Wu, X. Randomizing social networks: a spectrum preserving approach. In Proceedings of SIAM International Conference on Data Mining (SDM'08) (Atlanta, GA, April 2008).
• 19: Zheleva, E., and Getoor, L. Preserving the privacy of sensitive relationships in graph data. In Proceedings of the International Workshop on Privacy, Security, and Trust in KDD (PinKDD'07) (San Jose, CA, August 2007).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation, Theory

Keywords:
anonymity, degree sequence, dynamic programming