Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In order to address privacy concerns, many social media websites allow users to hide their personal profiles from the public. In this work, we show how an adversary can exploit an online social network with a mixture of public and private user profiles to predict the private attributes of users. We map this problem to a relational classification problem and we propose practical models that use friendship and group membership information (which is often not hidden) to infer sensitive attributes. The key novel idea is that in addition to friendship links, groups can be carriers of significant information. We show that on several well-known social media sites, we can easily and accurately recover the information of private-profile users. To the best of our knowledge, this is the first work that uses link-based and group-based classification to study privacy implications in social networks with mixed public and private user profiles.

REFERENCES

• 1: G. Aggarwal, T. Feder, K. Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, and A. Zhu. Approximation algorithms for k--anonimity. JPT, Nov. 2005.
• 2: Edoardo M. Airoldi , David M. Blei , Stephen E. Fienberg , Eric P. Xing, Mixed Membership Stochastic Blockmodels, The Journal of Machine Learning Research, 9, p.1981-2014, 6/1/2008
• 3: 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]
• 4: D. Baldassarri and A. Gelman. Partisans without constraint: Political polarization and trends in american public opinion. American Journal of Sociology, 114(2):408--446, September 2008.
• 5: 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]
• 6: C. Dwork. Differential privacy. In ICALP, 2006. L. Getoor and B. Taskar, editors. Introduction to statistical relational learning. MIT Press, 2007.
• 7: 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]
• 8: J. He, W. Chu, and Z. Liu. Inferring privacy information from social networks. In ISI, 2006.
• 9: K. Lewis, J. Kaufman, M. Gonzalez, A. Wimmer, and N. Christakis. Tastes, ties, and time. hd l:1902.1/11827.
• 10: N. Li, T. Li, and S. Venkatasubramanian. t-closeness: Privacy beyond k-anon. and l-diversity. In ICDE, 2007.
• 11: D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic routing in social networks. PNAS, 102(33):11623--11628, August 2005.
• 12: Jack Lindamood , Raymond Heatherly , Murat Kantarcioglu , Bhavani Thuraisingham, Inferring private information using social network data, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain [doi>10.1145/1526709.1526899]
• 13: Huan Liu , Lei Yu, Toward Integrating Feature Selection Algorithms for Classification and Clustering, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.491-502, April 2005 [doi>10.1109/TKDE.2005.66]
• 14: 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]
• 15: A. Machanava jjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-diversity: Privacy beyond k-anonymity. In ICDE, 2006.
• 16: Sofus A. Macskassy , Foster Provost, Classification in Networked Data: A Toolkit and a Univariate Case Study, The Journal of Machine Learning Research, 8, p.935-983, 5/1/2007
• 17: 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]
• 18: M. E. Nergiz and C. Clifton. Multirelational k-anonymity. In ICDE, April 2007.
• 19: Jennifer Neville , David Jensen, Leveraging Relational Autocorrelation with Latent Group Models, Proceedings of the Fifth IEEE International Conference on Data Mining, p.322-329, November 27-30, 2005 [doi>10.1109/ICDM.2005.89]
• 20: P. Sen, G. M. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi--Rad. Collective classification in network data. Technical Report CS-TR-4905, Univ. of Maryland, 2008.
• 21: Latanya Sweeney, Achieving k-anonymity privacy protection using generalization and suppression, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.571-588, October 2002 [doi>10.1142/S021848850200165X]
• 22: Ioannis Tsochantaridis , Thomas Hofmann , Thorsten Joachims , Yasemin Altun, Support vector machine learning for interdependent and structured output spaces, Proceedings of the twenty-first international conference on Machine learning, p.104, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015341]
• 23: Y. Wang and G. Wong. Stochastic blockmodels for directed graphs. JASA, 1987.
• 24: E. Zheleva and L. Getoor. Preserving the privacy of sensitive relationships in graph data. PinKDD, 2007.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
attribute inference, groups, privacy, social networks