Markus Strohmaier
Denis Helic
Dominik Benz
Skip Abstract Section
Abstract
Algorithms for constructing hierarchical structures from user-generated metadata have caught the interest of the academic community in recent years. In social tagging systems, the output of these algorithms is usually referred to as folksonomies (from folk-generated taxonomies). Evaluation of folksonomies and folksonomy induction algorithms is a challenging issue complicated by the lack of golden standards, lack of comprehensive methods and tools as well as a lack of research and empirical/simulation studies applying these methods. In this article, we report results from a broad comparative study of state-of-the-art folksonomy induction algorithms that we have applied and evaluated in the context of five social tagging systems. In addition to adopting semantic evaluation techniques, we present and adopt a new technique that can be used to evaluate the usefulness of folksonomies for navigation. Our work sheds new light on the properties and characteristics of state-of-the-art folksonomy induction algorithms and introduces a new pragmatic approach to folksonomy evaluation, while at the same time identifying some important limitations and challenges of folksonomy evaluation. Our results show that folksonomy induction algorithms specifically developed to capture intuitions of social tagging systems outperform traditional hierarchical clustering techniques. To the best of our knowledge, this work represents the largest and most comprehensive evaluation study of state-of-the-art folksonomy induction algorithms to date.
- Adamic, L. and Adar, E. 2005. How to search a social network. Social Netw. 27, 3, 187--203.Google Scholar
Cross Ref
- Adamic, L. A., Lukose, R. M., Puniyani, A. R., and Huberman, B. A. 2001. Search in power-law networks. Phys. Rev. E 64, 4, 046135 1--8.Google ScholarCross Ref
- Angeletou, S. 2010. Semantic enrichment of folksonomy tagspaces. In Proceedings of the International Semantic Web Conference (ISWC’08). Springer, 889--894.Google Scholar
- Au Yeung, C., Gibbins, N., and Shadbolt, N. 2009. Contextualising tags in collaborative tagging systems. In Proceedings of the 20th ACM Conference on Hypertext and Hypermedia. ACM, 251--260. Google ScholarDigital Library
- Benz, D., Hotho, A., and Stumme, G. 2010. Semantics made by you and me: Self-emerging ontologies can capture the diversity of shared knowledge. In Proceedings of the 2nd Web Science Conference (WebSci’10). Web Science Trust, Raleigh, NC.Google Scholar
- Boguñá, M., Krioukov, D., and Claffy, K. C. 2009. Navigability of complex networks. Nature Phys. 5, 74--80.Google ScholarCross Ref
- Boguñá, M., Papadopoulos, F., and Krioukov, D. 2010. Sustaining the Internet with hyperbolic mapping. Nature Comm. 1, 62.Google ScholarCross Ref
- Brank, J., Madenic, D., and Groblenik, M. 2006. Gold standard based ontology evaluation using instance assignment. In Proceedings of the 4th Workshop on Evaluating Ontologies for the Web (EON’06).Google Scholar
- Cattuto, C., Schmitz, C., Baldassarri, A., Servedio, V. D. P., Loreto, V., Hotho, A., Grahl, M., and Stumme, G. 2007. Network properties of folksonomies. AI Comm. 20, 4, 245--262. Google ScholarDigital Library
- Cattuto, C., Benz, D., Hotho, A., and Stumme, G. 2008. Semantic grounding of tag relatedness in social bookmarking systems. In Proceedings of International Semantic Web Conference. A. P. Sheth, S. Staab, M. Dean, M. Paolucci, D. Maynard, T. W. Finin, and K. Thirunarayan Eds., Lecture Notes in Artificial Intelligence, vol. 5318, Springer, 615--631. Google ScholarDigital Library
- Dellschaft, K. 2005. Measuring the similarity of concept hierarchies and its inuence on the evaluation of learning procedures. M.S. thesis, Institute for Computer Science, University of Koblenz-Landau, Germany.Google Scholar
- Dellschaft, K. and Staab, S. 2006. On how to perform a gold standard based evaluation of ontology learning. In Proceedings of the International Semantic Web Conference. Springer. Google ScholarDigital Library
- Dhillon, I., Fan, J., and Guan, Y. 2001. Efficient clustering of very large document collections. In Data Mining for Scientific and Engineering Applications, R. Grossman, C. Kamath, and R. Naburu Eds., Kluwer.Google Scholar
- Frey, B. J. J. and Dueck, D. 2007. Clustering by passing messages between data points. Science 315, 5814, 972--976.Google Scholar
- Helic, D. and Strohmaier, M. 2011. Building directories for social tagging systems. In Proceedings of the 20th ACM Conference on Information and Knowledge Management. Google ScholarDigital Library
- Helic, D., Trattner, C., Strohmaier, M., and Andrews, K. 2010. On the navigability of social tagging systems. In Proceedings of the IEEE International Conference on Social Computing. IEEE, 161--168. Google ScholarDigital Library
- Helic, D., Strohmaier, M., Trattner, C., Muhr, M., and Lerman, K. 2011. Pragmatic evaluation of folksonomies. In Proceedings of the 20th International World Wide Web Conference. ACM. Google ScholarDigital Library
- Heymann, P. and Garcia-Molina, H. 2006. Collaborative creation of communal hierarchical taxonomies in social tagging systems. Tech. rep. 2006-10, Stanford InfoLab.Google Scholar
- Hotho, A., Jäschke, R., Schmitz, C., and Stumme, G. 2006a. Bibsonomy: A social bookmark and publication sharing system. In Proceedings of the Conceptual Structures Tool Interoperability Workshop at the 14th International Conference on Conceptual Structures. A. de Moor, S. Polovina, and H. Delugach Eds., Aalborg University Press, Aalborg, Denmark, 87--102.Google Scholar
- Hotho, A., Jaeschke, R., Schmitz, C., and Stumme, G. 2006b. Folkrank: A ranking algorithm for folksonomies. In Proceedings of the Special Interest Group on Information Retrieval. Gesellschaft Für Informatik, Bonn, Germany, 111--114.Google Scholar
- Kleinberg, J. 2000a. The small-world phenomenon: An algorithm perspective. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC’00). ACM, 163--170. Google ScholarDigital Library
- Kleinberg, J. M. 2000b. Navigation in a small world. Nature 406, 6798, 845.Google ScholarCross Ref
- Kleinberg, J. M. 2001. Small-world phenomena and the dynamics of information. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS). MIT Press, Cambridge, MA.Google Scholar
- Kleinberg, J. 2006. Complex networks and decentralized search algorithms. In Proceedings of the International Congress of Mathematicians. European Mathematical Society Publishing House, Zürich, Switzerland, 1019--1044.Google Scholar
- Koerner, C., Benz, D., Strohmaier, M., Hotho, A., and Stumme, G. 2010. Stop thinking, start tagging---tag semantics emerge from collaborative verbosity. In Proceedings of the 19th International World Wide Web Conference (WWW’10). ACM. Google ScholarDigital Library
- Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., and Boguñá, M. 2010. Hyperbolic geometry of complex networks. Phys. Rev. E 82, 3, 036106.Google ScholarCross Ref
- Leicht, E. A., Holme, P., and Newman, M. E. J. 2006. Vertex similarity in networks. Phys. Rev. E 73, 2, 026120.Google ScholarCross Ref
- Li, R., Bao, S., Yu, Y., Fei, B., and Su, Z. 2007. Towards effective browsing of large scale social annotations. In Proceedings of the 16th International Conference on World Wide Web (WWW’07). ACM, 952. Google ScholarDigital Library
- Maedche, A. 2002. Ontology Learning for the Semantic Web. Kluwer, Boston. Google ScholarDigital Library
- Menczer, F. 2002. Growing and navigating the small world web by local content. Proc. Natl. Acad. Sci. USA 99, 22, 14014--14019.Google ScholarCross Ref
- Mika, P. 2007. 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. Google ScholarDigital Library
- Milgram, S. 1967. The small world problem. Psych. Today 1, 60--67.Google Scholar
- Miller, G. A. 1995. Wordnet: A lexical database for English. Comm. ACM 38, 1, 39--41. Google ScholarDigital Library
- Plangprasopchok, A., Lerman, K., and Getoor, L. 2010a. From saplings to a tree: Integrating structured metadata via relational affinity propagation. In Proceedings of the AAAI Workshop on Statistical Relational AI. AAAI, Menlo Park, CA.Google Scholar
- Plangprasopchok, A., Lerman, K., and Getoor, L. 2010b. Growing a tree in the forest: Constructing folksonomies by integrating structured metadata. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 949--958. Google ScholarDigital Library
- Ponzetto, S. P. and Strube, M. 2007. Deriving a large-scale taxonomy from wikipedia. In Proceedings of the 22nd Conference on the Advancement of Artificial Intelligence. AAAI Press, Menlo Park, CA, 440--1445. Google ScholarDigital Library
- Ramezani, M., Sandvig, J., Schimoler, T., Gemmell, J., Mobasher, B., and Burke, R. 2009. Evaluating the impact of attacks in collaborative tagging environments. In Proceedings of the International Conference on Computational Science and Engineering. Vol. 4, IEEE, 136--143. Google ScholarDigital Library
- Schifanella, R., Barrat, A., Cattuto, C., Markines, B., and Menczer, F. 2010. Folks in folksonomies: Social link prediction from shared metadata. In Proceedings of the 3rd ACM International Conference on Web Search and Data Mining. ACM, New York, NY, 271--280. Google ScholarDigital Library
- Schmitz, C., Hotho, A., Jöschke, R., and Stumme, G. 2006. Mining association rules in folksonomies. In Proceedings of the 10th IFCS Conference on Studies in Classification, Data Analysis, and Knowledge Organization. Springer, 261--270.Google Scholar
- Serrano, M. A., Krioukov, D., and Boguñá, M. 2008. Self-similarity of complex networks and hidden metric spaces. Phys. Rev. Lett. 100, 7, 078701.Google Scholar
- Strohmaier, M., Koerner, C., and Kern, R. 2010. Why do users tag? Detecting users’ motivation for tagging in social tagging systems. In Proceedings of the International AAAI Conference on Weblogs and Social Media (ICWSM’10). AAAI, Menlo Park, CA, USA.Google Scholar
- Suchanek, F. M., Kasneci, G., and Weikum, G. 2007. Yago: A core of semantic knowledge. In Proceedings of the 16th International World Wide Web Conference (WWW’07). ACM. Google ScholarDigital Library
- Vander Wal, T. 2007. Folksonomy coinage and definition. http://vanderwal.net/folksonomy.html.Google Scholar
- Watts, D. J. and Strogatz, S. H. 1998. Collective dynamics of small-world networks. Nature 393, 6684, 440--442.Google Scholar
- Watts, D. J., Dodds, P. S., and Newman, M. E. J. 2002. Identity and search in social networks. Science 296, 1302--1305.Google ScholarCross Ref
- Yeung, C., Gibbins, N., and Shadbolt, N. 2008. A k-nearest-neighbour method for classifying web search results with data in folksonomies. In Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WIIAT’08). Vol. 1, IEEE, 70--76. Google ScholarDigital Library
- Zhong, S. 2005. Efficient online spherical k-means clustering. In Proceedings of the IEEE International Joint Conference on Neural Networks. Vol. 5, 3180--3185.Google Scholar
Index Terms
- Evaluation of Folksonomy Induction Algorithms
Recommendations
Pragmatic evaluation of folksonomies
WWW '11: Proceedings of the 20th international conference on World wide webRecently, a number of algorithms have been proposed to obtain hierarchical structures - so-called folksonomies - from social tagging data. Work on these algorithms is in part driven by a belief that folksonomies are useful for tasks such as: (a) ...
Leveraging Semantic Similarity for Folksonomy-Based Recommendation
To recommend interesting resources such as webpages or pictures that are available through social tagging sites, recommender systems must be able to assess such resources' similarity to user profiles. Here, the authors analyze the role semantic ...
The benefit of additional semantics in folksonomy systems
PIKM '08: Proceedings of the 2nd PhD workshop on Information and knowledge managementWith the advent of Web 2.0 folksonomy systems like Flickr, del.icio.us, etc. have become very popular. They enable users to annotate resources (images, websites, etc.) with freely chosen keywords, so-called tags. The evolving set of such tag assignments,...
Comments