Resisting structural re-identification in anonymized social networks

ABSTRACT

We identify privacy risks associated with releasing network data sets and provide an algorithm that mitigates those risks. A network consists of entities connected by links representing relations such as friendship, communication, or shared activity. Maintaining privacy when publishing networked data is uniquely challenging because an individual's network context can be used to identify them even if other identifying information is removed. In this paper, we quantify the privacy risks associated with three classes of attacks on the privacy of individuals in networks, based on the knowledge used by the adversary. We show that the risks of these attacks vary greatly based on network structure and size. We propose a novel approach to anonymizing network data that models aggregate network structure and then allows samples to be drawn from that model. The approach guarantees anonymity for network entities while preserving the ability to estimate a wide variety of network measures with relatively little bias.

REFERENCES

• 1: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
• 2: R. Albert, H. Jeong, and A.-L. Barabasi. Error and attack tolerance of complex networks. Nature, 406:378, 2000.
• 3: Laszlo Babai , Ludik Kucera, Canonical labelling of graphs in linear average time, Proceedings of the 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), p.39-46, October 29-31, 1979
• 4: 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]
• 5: A. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286, 1999.
• 6: G. Bianconi and M. Marsili. Emergence of large cliques in random scale-free networks. Europhysics Letters, 74(4):740--746, 2006.
• 7: W. W. Cohen. Enron email dataset, 2005.
• 8: D. G. Corneil , C. C. Gotlieb, An Efficient Algorithm for Graph Isomorphism, Journal of the ACM (JACM), v.17 n.1, p.51-64, Jan. 1970 [doi>10.1145/321556.321562]
• 9: C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, 2006.
• 10: P. Erdős and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5:17--61, 1960.
• 11: N. Friedkin. Horizons of observability and limits of informal control in organizations. Social Forces, 62(1):54--77, 1983.
• 12: 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]
• 13: J. Grochow and M. Kellis. Network motif discovery using subgraph enumeration and symmetry-breaking. In RECOMB, 2007.
• 14: M. Hay, G. Miklau, D. Jensen, P. Weis, and S. Srivastava. Anonymizing social networks. Technical Report 07--19, UMass Amherst, 2007.
• 15: N. Immerman and E. Lander. Describing graphs: A first-order approach to graph canonization. In Complexity Theory Retrospective. Springer-Verlag, 1990.
• 16: A. Korolova, R. Motwani, S. Nabar, and Y. Xu. Link privacy in social networks. In ICDE, 2008.
• 17: 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]
• 18: 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]
• 19: D. Martin, D. Kifer, A. Machanavajjhala, J. Gehrke, and J. Halpern. Worst-case background knowledge. ICDE, 2007.
• 20: M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45(2):167--256, 2003.
• 21: J. J. Potterat, L. Phillips-Plummer, S. Q. Muth, R. B. Rothenberg, D. E. Woodhouse, T. S. Maldonado-Long, H. P. Zimmerman, and J. B. Muth. Risk network structure in the early epidemic phase of HIV transmission in Colorado Springs. Sexually Trans. Infections, 2002.
• 22: Vibhor Rastogi , Dan Suciu , Sungho Hong, The boundary between privacy and utility in data publishing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 23: S. Russell and P. Norvig. AI: A Modern Approach. 2003.
• 24: Lisa Singh , Justin Zhan, Measuring Topological Anonymity in Social Networks, Proceedings of the 2007 IEEE International Conference on Granular Computing, p.770, November 02-04, 2007 [doi>10.1109/GRC.2007.95]
• 25: 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]
• 26: D.-W. Wang, C.-J. Liau, and T.-S. Hsu. Privacy protection in social network data disclosure based on granular computing. In International Conference on Fuzzy Systems, 2006.
• 27: D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, 1998.
• 28: D. B. West. Introduction to Graph Theory. August 2000.
• 29: X. Ying and X. Wu. Randomizing social networks: a spectrum preserving approach. In SIAM Conf. on Data Mining, 2007.
• 30: E. Zheleva and L. Getoor. Preserving the privacy of sensitive relationships in graph data. In PinKDD Workshop, 2007.
• 31: B. Zhou and J. Pei. Preserving privacy in social networks against neighborhood attacks. In ICDE, 2008.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Design, Management, Security