Evaluating similarity measures for emergent semantics of social tagging

ABSTRACT

Social bookmarking systems are becoming increasingly important data sources for bootstrapping and maintaining Semantic Web applications. Their emergent information structures have become known as folksonomies. A key question for harvesting semantics from these systems is how to extend and adapt traditional notions of similarity to folksonomies, and which measures are best suited for applications such as community detection, navigation support, semantic search, user profiling and ontology learning. Here we build an evaluation framework to compare various general folksonomy-based similarity measures, which are derived from several established information-theoretic, statistical, and practical measures. Our framework deals generally and symmetrically with users, tags, and resources. For evaluation purposes we focus on similarity between tags and between resources and consider different methods to aggregate annotations across users. After comparing the ability of several tag similarity measures to predict user-created tag relations, we provide an external grounding by user-validated semantic proxies based on WordNet and the Open Directory Project. We also investigate the issue of scalability. We find that mutual information with distributional micro-aggregation across users yields the highest accuracy, but is not scalable; per-user projection with collaborative aggregation provides the best scalable approach via incremental computations. The results are consistent across resource and tag similarity.

REFERENCES

• 1: M. Aurnhammer, P. Hanappe, and S. L. Integrating collaborative tagging and emergent semantics for image retrieval. In Proc. WWW Collaborative Web Tagging Workshop, 2006.
• 2: Shenghua Bao , Guirong Xue , Xiaoyuan Wu , Yong Yu , Ben Fei , Zhong Su, Optimizing web search using social annotations, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242640]
• 3: J. Bar-Ilan, S. Shoham, A. Idan, Y. Miller, and A. Shachak. Structured vs. unstructured tagging -- a case study. In Proc. WWW Collaborative Web Tagging Workshop, 2006.
• 4: G. Begelman, P. Keller, and F. Smadja. Automated tag clustering: Improving search and exploration in the tag space. In Proc. WWW Collaborative Web Tagging Workshop, 2006.
• 5: P. Boldi, M. Santini, and S. Vigna. Do your worst to make the best: Paradoxical effects in pagerank incremental computations. Internet Mathematics, 2(3):387--404, 2005.
• 6: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 7: Christopher H. Brooks , Nancy Montanez, Improved annotation of the blogosphere via autotagging and hierarchical clustering, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135869]
• 8: Alexander Budanitsky , Graeme Hirst, Evaluating WordNet-based Measures of Lexical Semantic Relatedness, Computational Linguistics, v.32 n.1, p.13-47, March 2006 [doi>10.1162/coli.2006.32.1.13]
• 9: C. Cattuto, A. Baldassarri, V. D. P. Servedio, and V. Loreto. Emergent community structure in social tagging systems. Advances in Complex Systems, 11:597--608, 2008.
• 10: Ciro Cattuto , Dominik Benz , Andreas Hotho , Gerd Stumme, Semantic Grounding of Tag Relatedness in Social Bookmarking Systems, Proceedings of the 7th International Conference on The Semantic Web, October 26-30, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-88564-1_39]
• 11: S. Christiaens. Metadata mechanisms: From ontology to folksonomy ... and back. In Proc. On the Move to Meaningful Internet Systems Workshop, LNCS. Springer, 2006.
• 12: J. Diederich and T. Iofciu. Finding communities of practice from user profiles based on folksonomies. Proc. 1st Intl. Workshop on Building Technology Enhanced Learning Solutions for Communities of Practice, 2006.
• 13: Justin J. Donaldson , Michael Conover , Benjamin Markines , Heather Roinestad , Filippo Menczer, Visualizing social links in exploratory search, Proceedings of the nineteenth ACM conference on Hypertext and hypermedia, June 19-21, 2008, Pittsburgh, PA, USA [doi>10.1145/1379092.1379132]
• 14: Prasanna Ganesan , Hector Garcia-Molina , Jennifer Widom, Exploiting hierarchical domain structure to compute similarity, ACM Transactions on Information Systems (TOIS), v.21 n.1, p.64-93, January 2003 [doi>10.1145/635484.635487]
• 15: Scott A. Golder , Bernardo A. Huberman, Usage patterns of collaborative tagging systems, Journal of Information Science, v.32 n.2, p.198-208, April 2006 [doi>10.1177/0165551506062337]
• 16: H. Halpin, V. Robu, and H. Shepard. The dynamics and semantics of collaborative tagging. In Proc. 1st Semantic Authoring and Annotation Workshop (SAAW), 2006.
• 17: T. Hammond, T. Hannay, B. Lund, and J. Scott. Social Bookmarking Tools (I): A General Review. D-Lib Magazine, 11(4), April 2005.
• 18: Y. Hassan-Montero and V. Herrero-Solana. Improving tag-clouds as visual information retrieval interfaces. In Proc. Intl. Conf. on Multidisciplinary Information Sciences and Technologies, 2006.
• 19: P. Heymann and H. Garcia-Molina. Collaborative creation of communal hierarchical taxonomies in social tagging systems. Technical Report 2006-10, Stanford InfoLab, April 2006.
• 20: Paul Heymann , Georgia Koutrika , Hector Garcia-Molina, Can social bookmarking improve web search?, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341558]
• 21: Paul Heymann , Daniel Ramage , Hector Garcia-Molina, Social tag prediction, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390425]
• 22: A. Hotho, R. Jaschke, C. Schmitz, and G. Stumme. BibSonomy: A social bookmark and publication sharing system. In Proc. Conceptual Structures Tool Interoperability Workshop at the 14th Intl. Conf. on Conceptual Structures, pages 87--102, 2006.
• 23: A. Hotho, R. Jäschke, C. Schmitz, and G. Stumme. Information retrieval in folksonomies: Search and ranking. In Y. Sure and J. Domingue, editors, The Semantic Web: Research and Applications, volume 4011 of LNAI, pages 411--426, Heidelberg, 2006. Springer.
• 24: Robert Jäschke , Leandro Marinho , Andreas Hotho , Lars Schmidt-Thieme , Gerd Stumme, Tag Recommendations in Folksonomies, Proceedings of the 11th European conference on Principles and Practice of Knowledge Discovery in Databases, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74976-9_52]
• 25: J. J. Jiang and D. W. Conrath. Semantic Similarity based on Corpus Statistics and Lexical Taxonomy. In Proc. Intl. Conf. on Research in Computational Linguistics (ROCLING), 1997.
• 26: Fritz Lehmann , Rudolf Wille, A Triadic Approach to Formal Concept Analysis, Proceedings of the Third International Conference on Conceptual Structures: Applications, Implementation and Theory, p.32-43, August 14-18, 1995
• 27: David Liben-Nowell , Jon Kleinberg, The link prediction problem for social networks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956972]
• 28: Dekang Lin, An Information-Theoretic Definition of Similarity, Proceedings of the Fifteenth International Conference on Machine Learning, p.296-304, July 24-27, 1998
• 29: B. Lund, T. Hammond, M. Flack, and T. Hannay. Social Bookmarking Tools (II): A Case Study -- Connotea. D-Lib Magazine, 11(4), April 2005.
• 30: Ana G. Maguitman , Filippo Menczer , Fulya Erdinc , Heather Roinestad , Alessandro Vespignani, Algorithmic Computation and Approximation of Semantic Similarity, World Wide Web, v.9 n.4, p.431-456, December 2006 [doi>10.1007/s11280-006-8562-2]
• 31: Ana G. Maguitman , Filippo Menczer , Heather Roinestad , Alessandro Vespignani, Algorithmic detection of semantic similarity, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060765]
• 32: Benjamin Markines , Heather Roinestad , Filippo Menczer, Efficient assembly of social semantic networks, Proceedings of the nineteenth ACM conference on Hypertext and hypermedia, June 19-21, 2008, Pittsburgh, PA, USA [doi>10.1145/1379092.1379122]
• 33: B. Markines, L. Stoilova, and F. Menczer. Social bookmarks for collaborative search and recommendation. In Proc. AAAI, 2006.
• 34: Cameron Marlow , Mor Naaman , Danah Boyd , Marc Davis, HT06, tagging paper, taxonomy, Flickr, academic article, to read, Proceedings of the seventeenth conference on Hypertext and hypermedia, August 22-25, 2006, Odense, Denmark [doi>10.1145/1149941.1149949]
• 35: P. Mika. Ontologies are us: A unified model of social networks and semantics. In Y. Gil, E. Motta, V. R. Benjamins, and M. A. Musen, editors, Proc. Intl. Semantic Web Conf., volume 3729 of LNCS, pages 522--536. Springer, 2005.
• 36: Gilad Mishne, AutoTag: a collaborative approach to automated tag assignment for weblog posts, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135961]
• 37: K. P. G. A. Mislove and P. Druschel. Exploiting social networks for internet search. In Proc. 5th Workshop on Hot Topics in Networks, Irvine, CA, 2006.
• 38: John C. Paolillo , Shashikant Penumarthy, The Social Structure of Tagging Internet Video on del.icio.us, Proceedings of the 40th Annual Hawaii International Conference on System Sciences, p.85, January 03-06, 2007 [doi>10.1109/HICSS.2007.555]
• 39: P. Resnik. Using Information Content to Evaluate Semantic Similarity in a Taxonomy. In Proc. IJCAI XI, pages 448--453, 1995.
• 40: Badrul Sarwar , George Karypis , Joseph Konstan , John Reidl, Item-based collaborative filtering recommendation algorithms, Proceedings of the 10th international conference on World Wide Web, p.285-295, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372071]
• 41: C. Schmitz, A. Hotho, R. Jaschke, and G. Stumme. Kollaboratives wissensmanagement. In T. Pellegrini and A. Blumauer, editors, Semantic Web -- Wege zur vernetzten Wissensgesellschaft, pages 273--290. Springer, 2006.
• 42: C. Schmitz, A. Hotho, R. Jaschke, and G. Stumme. Mining association rules in folksonomies. In Data Science and Classification: Proc. of the 10th IFCS Conf., pages 261--270, Berlin, Heidelberg, 2006. Springer.
• 43: P. Schmitz. Inducing ontology from Flickr tags. In WWW Collaborative Web Tagging Workshop, May 2006.
• 44: Börkur Sigurbjörnsson , Roelof van Zwol, Flickr tag recommendation based on collective knowledge, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367542]
• 45: Lubomira Stoilova , Todd Holloway , Ben Markines , Ana G. Maguitman , Filippo Menczer, GiveALink: mining a semantic network of bookmarks for web search and recommendation, Proceedings of the 3rd international workshop on Link discovery, p.66-73, August 21-25, 2005, Chicago, Illinois [doi>10.1145/1134271.1134281]
• 46: J. Voss. Tagging, folksonomy & co -- renaissance of manual indexing? Technical report, arXiv:cs/0701072, 2007.
• 47: Harris Wu , Mohammad Zubair , Kurt Maly, Harvesting social knowledge from folksonomies, Proceedings of the seventeenth conference on Hypertext and hypermedia, August 22-25, 2006, Odense, Denmark [doi>10.1145/1149941.1149962]
• 48: Z. Xu, Y. Fu, J. Mao, and D. Su. Towards the semantic web: Collaborative tag suggestions. In Proc. WWW Collaborative Web Tagging Workshop, 2006.
• 49: L. Zhang, X. Wu, and Y. Yu. Emergent semantics from folksonomies: A quantitative study. Journal on Data Semantics VI, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Information networks

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Design, Experimentation, Human Factors, Performance

Keywords:
ontology learning, semantic grounding, social similarity, web 2.0