Link privacy in social networks

ABSTRACT

We consider a privacy threat to a social network in which the goal of an attacker is to obtain knowledge of a significant fraction of the links in the network. We formalize the typical social network interface and the information about links that it provides to its users in terms of lookahead. We consider a particular threat where an attacker subverts user accounts to get information about local neighborhoods in the network and pieces them together in order to get a global picture. We analyze, both experimentally and theoretically, the number of user accounts an attacker would need to subvert for a successful attack, as a function of his strategy for choosing users whose accounts to subvert and a function of lookahead provided by the network. We conclude that such an attack is feasible in practice, and thus any social network that wishes to protect the link privacy of its users should take great care in choosing the lookahead of its interface, limiting it to 1 or 2, whenever possible.

REFERENCES

• 1: Facebook Press Release. http://www.facebook.com/press/info.php?statistics, 2008.
• 2: TechCrunch. http://www.techcrunch.com/2008/05/17/facebooks-glass-jaw/, 2008.
• 3: Technology Review. http://www.technologyreview.com/Wire/20825/, 2008.
• 4: L. Adamic, R. Lukose, A. Puniyani, and B. Huberman. Search in power-law networks. Phys. Rev. E, 2001.
• 5: W. Aiello, F. Chung, and L. Liu. A random graph model for power law graphs. IEEE Symposium on Foundations of Computer Science, 2000.
• 6: 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]
• 7: A. Barabasi and R. Albert. Emergence of scaling in random networks. Science, (509), 1999.
• 8: Edward A. Bender , E. Rodney Canfield , Brendan D. McKay, The asymptotic number of labeled graphs with n vertices, q edges, and no isolated vertices, Journal of Combinatorial Theory Series A, v.80 n.1, p.124-150, Oct. 1997 [doi>10.1006/jcta.1997.2798]
• 9: Béla Bollobás , Christian Borgs , Jennifer Chayes , Oliver Riordan, Directed scale-free graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 10: Colin Cooper , Alan Frieze, A general model of web graphs, Random Structures & Algorithms, v.22 n.3, p.311-335, May 2003 [doi>10.1002/rsa.10084]
• 11: G. Csanyi and B. Szendroi. Structure of a large social network. Physical Review E 69, 2004.
• 12: Christos Gkantsidis , Milena Mihail , Amin Saberi, Conductance and congestion in power law graphs, ACM SIGMETRICS Performance Evaluation Review, v.31 n.1, June 2003
• 13: M. Hay, G. Miklau, D. Jensen, P. Weis, and S. Srivastava. Anonymizing social networks. University of Massachusetts, Amherst Technical Report, 2007.
• 14: M. Kelly. Facebook Security: Fighting the good fight. Facebook blog, http://blog.new.facebook.com/blog.php?post=25844207130, August 7, 2008.
• 15: J. Kleinberg. Navigation in a small world. Nature, (845), 2000.
• 16: B. Krebs. Account Hijackings Force LiveJournal Changes. Washington Post, January 20, 2006.
• 17: R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
• 18: J. Leskovec, D. Chakrabarti, J. M. Kleinberg, and C. Faloutsos. Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication. In PKDD, pages 133--145, 2005.
• 19: 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.
• 20: M. Mihail, A. Saberi, and P. Tetali. Random walks with lookahead in power law random graphs. Internet Mathematics.
• 21: R. Motwani and P. Raghavan. Cambridge University Press New York, NY, USA, 1995.
• 22: H. von Schelling. Coupon collecting for unequal probabilities. Am. Math. Monthly, 61:306--311, 1954.
• 23: S. Wasserman and K. Faust. Cambridge University Press, Cambridge, USA, 1994.
• 24: D. Watts and S. Strogatz. Collective dynamics of small-world networks. Nature 393 440--442, 1998.
• 25: 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, 2007.
• 26: B. Zhou and J. Pei. Preserving privacy in social networks against neighborhood attacks. In Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on, pages 506--515, 2008.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

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

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Design, Experimentation, Security, Theory

Keywords:
anonymization, link analysis, link privacy, privacy in data mining, social networks