The union-split algorithm and cluster-based anonymization of social networks

ABSTRACT

Knowledge discovery on social network data can uncover latent social trends and produce valuable findings that benefit the welfare of the general public. A growing amount of research finds that social networks play a surprisingly powerful role in people's behaviors. Before the social network data can be released for research purposes, the data needs to be anonymized to prevent potential re-identification attacks. Most of the existing anonymization approaches were developed for relational data, and cannot be used to handle social network data directly.

In this paper, we model social networks as undirected graphs and formally define privacy models, attack models for the anonymization problem, in particular an i-hop degree-based anonymization problem, i.e., the adversary's prior knowledge includes the target's degree and the degrees of neighbors within i hops from the target. We present two new and efficient clustering methods for undirected graphs: bounded t-means clustering and union-split clustering algorithms that group similar graph nodes into clusters with a minimum size constraint. These clustering algorithms are contributions beyond the specific social network problems studied and can be used to cluster general data types besides graph vertices. We also develop a simple-yet-effective inter-cluster matching method for anonymizing social networks by strategically adding and removing edges based on nodes' social roles. We carry out a series of experiments to evaluate the graph utilities of the anonymized social networks produced by our algorithms.

REFERENCES

• 1: P. Bradley, K. Bennett, and A. Demiriz. Constrained k-means clustering. Technical Report MSR-TR-2000-65, Microsoft Research, 2000.
• 2: J.-W. Byun, A. Kamra, E. Bertino, and N. Li. Efficient k-anonymization using clustering techniques. In Proceedings of the 12th International Conference on Database Systems for Advanced Applications (DASFAA), volume 4443 of Lecture Notes in Computer Science, pages 188--200. Springer, 2007.
• 3: Cambridge English Dictionary. http://dictionary.cambridge.org/define.asp? key=68410&dict=CALD.
• 4: D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-MAT: A recursive model for graph mining. In M. W. Berry, U. Dayal, C. Kamath, and D. B. Skillicorn, editors, SDM. SIAM, 2004.
• 5: G. Cormode, D. Srivastava, T. Yu, and Q. Zhang. Anonymizing bipartite graph data using safe groupings. In Proceedings of the International Conference on Very Large Data Bases (VLDB), 2008.
• 6: Michael Hay , Gerome Miklau , David Jensen , Don Towsley , Philipp Weis, Resisting structural re-identification in anonymized social networks, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453873]
• 7: N. Li, T. Li, and S. Venkatasubramanian. t-closeness: Privacy beyond k-anonymity and l-diversity. In Proceedings of the 23rd International Conference on Data Engineering (ICDE), pages 106--115, 2007.
• 8: 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]
• 9: 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]
• 10: S. Milgram. The small world problem. Psychology Today, 1(1):60--67, May 1967.
• 11: Dan Pelleg , Andrew W. Moore, X-means: Extending K-means with Efficient Estimation of the Number of Clusters, Proceedings of the Seventeenth International Conference on Machine Learning, p.727-734, June 29-July 02, 2000
• 12: Arvind Narayanan , Vitaly Shmatikov, Robust De-anonymization of Large Sparse Datasets, Proceedings of the 2008 IEEE Symposium on Security and Privacy, p.111-125, May 18-21, 2008 [doi>10.1109/SP.2008.33]
• 13: M. Ercan Nergiz , Chris Clifton, Thoughts on k-anonymization, Data & Knowledge Engineering, v.63 n.3, p.622-645, December, 2007 [doi>10.1016/j.datak.2007.03.009]
• 14: M. E. Nergiz, C. Clifton, and A. E. Nergiz. Multirelational k-anonymity. In Proceedings of the 23rd International Conference on Data Engineering (ICDE), pages 1417--1421, 2007.
• 15: Netflix Prize. http://www.netflixprize.com.
• 16: 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]
• 17: R. Stein. Social networks' sway may be underestimated. Washington Post, May 26, 2008.
• 18: 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]
• 19: Raymond Chi-Wing Wong , Jiuyong Li , Ada Wai-Chee Fu , Ke Wang, (α, k)-anonymity: an enhanced k-anonymity model for privacy preserving data publishing, 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.1150499]
• 20: V. N. Zemlyachenko, N. M. Korneenko, and R. I. Tyshkevich. Graph isomorphism problem. Journal of Mathematical Sciences, 29(4):1426Ü1481, May 1985.
• 21: B. Zhou and J. Pei. Preserving privacy in social networks against neighborhood attacks. In Proceedings of the 24th International Conference on Data Engineering (ICDE), pages 506--515, 2008.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Data sharing

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures; Algorithms

General Terms:
Algorithms, Measurement, Performance, Security

Keywords:
clustering algorithms, graph anonymization, social networks, social role