Folks in Folksonomies: social link prediction from shared metadata

ABSTRACT

Web 2.0 applications have attracted a considerable amount of attention because their open-ended nature allows users to create lightweight semantic scaffolding to organize and share content. To date, the interplay of the social and semantic components of social media has been only partially explored. Here we focus on Flickr and Last.fm, two social media systems in which we can relate the tagging activity of the users with an explicit representation of their social network. We show that a substantial level of local lexical and topical alignment is observable among users who lie close to each other in the social network. We introduce a null model that preserves user activity while removing local correlations, allowing us to disentangle the actual local alignment between users from statistical effects due to the assortative mixing of user activity and centrality in the social network. This analysis suggests that users with similar topical interests are more likely to be friends, and therefore semantic similarity measures among users based solely on their annotation metadata should be predictive of social links. We test this hypothesis on the Last.fm data set, confirming that the social network constructed from semantic similarity captures actual friendship more accurately than Last.fm's suggestions based on listening patterns.

References

1. C. Cattuto, D. Benz, A. Hotho, and G. Stumme. Semantic grounding of tag relatedness in social bookmarking systems. In Proceedings of the 7th International Semantic Web Conference (ISWC08), volume 5318 of LNCS, pages 615--631. Springer-Verlag, 2008.
2. S. Golder and B.A. Huberman. The structure of collaborative tagging systems. Journal of Information Science, 32(2):198--208, April 2006.
3. T. Hammond, T. Hannay, B. Lund, and J. Scott. Social Bookmarking Tools (I): A General Review. D-Lib Magazine, 11(4), April 2005.
4. R. Kumar, J. Novak, and A. Tomkins. Structure and evolution of online social networks. In KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 611--617, New York, NY, USA, 2006. ACM Press.
5. K. Lerman and L. Jones. Social browsing on flickr. In Proceedings of International Conference on Weblogs and Social Media (ICWSM), March 2007. http://arxiv.org/abs/cs.HC/0612047.
6. J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins. Microscopic evolution of social networks. In KDD '08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 462--470, New York, NY, USA, 2008. ACM.
7. X. Li, L. Guo, and Y.E. Zhao. Tag-based social interest discovery. In Proceeding of the 17th Intl. Conf. on World Wide Web (WWW), pages 675--684, New York, NY, USA, 2008. ACM.
8. D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In Proc. 12th Intl. Conf. on Information and Knowledge Management (CIKM), pages 556--559, New York, NY, USA, 2003. ACM.
9. D. Lin. An information-theoretic definition of similarity. In J.W. Shavlik, editor, Proceedings of the Fifteenth International Conference on Machine Learning (ICML), pages 296--304. Morgan Kaufmann, 1998.
10. B. Markines, C. Cattuto, F. Menczer, D. Benz, A. Hotho, and G. Stumme. Evaluating similarity measures for emergent semantics of social tagging. In Proc. 18th Intl. World Wide Web Conference (WWW), 2009.
11. B. Markines and F. Menczer. A scalable, collaborative similarity measure for social annotation systems. In Proc. 20th ACM Conf. on Hypertext and Hypermedia (HT), 2009.
12. B. Markines, H. Roinestad, and F. Menczer. Efficient assembly of social semantic networks. In Proc. 19th ACM Conf. on Hypertext and Hypermedia (HT), pages 149--156, New York, NY, USA, 2008. ACM.
13. C. Marlow, M. Naaman, D. Boyd, and M. Davis. Ht06, tagging paper, taxonomy, flickr, academic article, to read. In Proc. 17th ACM Conference on Hypertext and hypermedia (HT), pages 31--40, New York, NY, USA, 2006. ACM Press.
14. A. Mathes. Folksonomies -- Cooperative Classification and Communication Through Shared Metadata, December 2004. http://www.adammathes.com/academic/computer-mediatedcommunication/folksonomies.html.
15. F. Menczer. Lexical and semantic clustering by Web links. Journal of the American Society for Information Science and Technology, 55(14):1261--1269, 2004.
16. P. Mika. Ontologies are us: A unified model of social networks and semantics. Web Semantics: Science, Services and Agents on the World Wide Web, 5(1):5--15, 2007.
17. A. Mislove, H.S. Koppula, K.P. Gummadi, P. Druschel, and B. Bhattacharjee. Growth of the flickr social network. In Proceedings of the 1st ACM SIGCOMM Workshop on Social Networks (WOSN'08), August 2008.
18. A. Mislove, M. Marcon, K.P. Gummadi, P. Druschel, and B. Bhattacharjee. Measurement and analysis of online social networks. In Proceedings of the 5th ACM/USENIX Internet Measurement Conference (IMC'07), October 2007.
19. M.E.J. Newman. Mixing patterns in networks. Phys. Rev. E, 67:026126, 2003.
20. R. Pastor-Satorras, A. Vázquez, and A. Vespignani. Dynamical and correlation properties of the Internet. Phys. Rev. Lett., 87:258701, 2001.
21. C. Prieur, D. Cardon, J.-S. Beuscart, N. Pissard, and P. Pons. The strength of weak cooperation: A case study on flickr. Technical Report arXiv:0802.2317v1, CoRR, 2008.
22. G. Salton. Automatic text processing: the transformation, analysis, and retrieval of information by computer. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1989.
23. E. Santos-Neto, D. Condon, N. Andrade, A. Iamnitchi, and M. Ripeanu. Individual and social behavior in tagging systems. In C. Cattuto, G. Ruffo, and F. Menczer, editors, Proceedings of the 20th ACM Conference on Hypertext and Hypermedia (HT), pages 183--192, New York, NY, USA, 2009. ACM.
24. S. Staab, S. Santini, F. Nack, L. Steels, and A. Maedche. Emergent semantics. Intelligent Systems, IEEE {see also IEEE Expert}, 17(1):78--86, 2002.
25. L. Steels. Semiotic dynamics for embodies agents. IEEE Intelligent Systems, 21, 2006.
26. R. van Zwol. Flickr: Who is looking? In WI '07: Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, pages 184--190, Washington, DC, USA, 2007. IEEE Computer Society.
27. A. Vázquez, R. Pastor-Satorras, and A. Vespignani. Large-scale topological and dynamical properties of the Internet. Phys. Rev. E, 65:066130, 2002.
28. T.V. Wal. Explaining and showing broad and narrow folksonomies, 2005. http://www.personalinfocloud.com/2005/02/explaining_and_.html.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Philosophical/theoretical foundations of artificial intelligence

      • Cognitive science

• Human-centered computing

  • Human computer interaction (HCI)

• Information systems

  • World Wide Web

    • Web applications

    • Web services