Aleksandra Korolova
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.
- Facebook Press Release. http://www.facebook.com/press/info.php?statistics, 2008.Google Scholar
- TechCrunch. http://www.techcrunch.com/2008/05/17/facebooks-glass-jaw/, 2008.Google Scholar
- Technology Review. http://www.technologyreview.com/Wire/20825/, 2008.Google Scholar
- L. Adamic, R. Lukose, A. Puniyani, and B. Huberman. Search in power-law networks. Phys. Rev. E, 2001.Google ScholarCross Ref
- W. Aiello, F. Chung, and L. Liu. A random graph model for power law graphs. IEEE Symposium on Foundations of Computer Science, 2000.Google Scholar
- L. Backstrom, C. Dwork, and J. Kleinberg. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In WWW '07: Proceedings of the 16th international conference on World Wide Web, pages 181--190, New York, NY, USA, 2007. ACM Press. Google ScholarDigital Library
- A. Barabasi and R. Albert. Emergence of scaling in random networks. Science, (509), 1999.Google Scholar
- E. A. Bender and E. R. Canfield. The asymptotic number of labeled graphs with given degree sequences. Journal of Combinatorial Theory, Series A 24, pp. 296--307, 1978. Google ScholarDigital Library
- B. Bollobas, C. Borgs, T. Chayes, and O. Riordan. Directed scale-free graphs. ACM-SIAM Sypmosium on Discrete Algorithms, 2003. Google ScholarDigital Library
- C. Cooper and A. Frieze. A general model of web graphs. Random Structures and Algorithms, 22(3), pp.311--335, 2003. Google ScholarDigital Library
- G. Csanyi and B. Szendroi. Structure of a large social network. Physical Review E 69, 2004.Google Scholar
- C. Gkantsidis, M. Mihail, and A. Saberi. Conductance and congestion in power law graphs. Sigmetrics, 2003. Google ScholarDigital Library
- M. Hay, G. Miklau, D. Jensen, P. Weis, and S. Srivastava. Anonymizing social networks. University of Massachusetts, Amherst Technical Report, 2007.Google Scholar
- M. Kelly. Facebook Security: Fighting the good fight. Facebook blog, http://blog.new.facebook.com/blog.php?post=25844207130, August 7, 2008.Google Scholar
- J. Kleinberg. Navigation in a small world. Nature, (845), 2000.Google Scholar
- B. Krebs. Account Hijackings Force LiveJournal Changes. Washington Post, January 20, 2006.Google Scholar
- R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic models for the web graph. IEEE Symposium on Foundations of Computer Science, 2000. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- M. Mihail, A. Saberi, and P. Tetali. Random walks with lookahead in power law random graphs. Internet Mathematics.Google Scholar
- R. Motwani and P. Raghavan. Cambridge University Press New York, NY, USA, 1995.Google Scholar
- H. von Schelling. Coupon collecting for unequal probabilities. Am. Math. Monthly, 61:306--311, 1954.Google ScholarCross Ref
- S. Wasserman and K. Faust. Cambridge University Press, Cambridge, USA, 1994.Google Scholar
- D. Watts and S. Strogatz. Collective dynamics of small-world networks. Nature 393 440--442, 1998.Google ScholarCross Ref
- 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.Google Scholar
- 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. Google ScholarDigital Library
Index Terms
- Link privacy in social networks
Recommendations
Preservation of Centrality Measures in Anonymized Social Networks
SOCIALCOM '13: Proceedings of the 2013 International Conference on Social ComputingSocial media sites became a pervasive presence in the nowadays society. We can learn a lot of useful information about human behavior and interaction by paying attention to the information and relations of social media users. This information can be ...
Revisiting link privacy in social networks
CODASPY '12: Proceedings of the second ACM conference on Data and Application Security and PrivacyIn this paper, we revisit the problem of the link privacy attack in online social networks. In the link privacy attack, it turns out that by bribing or compromising a small number of nodes (users) in the social network graph, it is possible to obtain ...
Privacy preservation for social networks sequential publishing
AbstractThe proliferation of social networks allowed creating a big quantity of data about users and their relationships. Such data contain much private information. Therefore, anonymization is required before publishing the data for data ...
Comments