Logsonomy - social information retrieval with logdata

ABSTRACT

Social bookmarking systems constitute an established part of the Web 2.0. In such systems users describe bookmarks by keywords called tags. The structure behind these social systems, called folksonomies, can be viewed as a tripartite hypergraph of user, tag and resource nodes. This underlying network shows specific structural properties that explain its growth and the possibility of serendipitous exploration.

Today's search engines represent the gateway to retrieve information from the World Wide Web. Short queries typically consisting of two to three words describe a user's information need. In response to the displayed results of the search engine, users click on the links of the result page as they expect the answer to be of relevance.

This clickdata can be represented as a folksonomy in which queries are descriptions of clicked URLs. The resulting network structure, which we will term logsonomy is very similar to the one of folksonomies. In order to find out about its properties, we analyze the topological characteristics of the tripartite hypergraph of queries, users and bookmarks on a large snapshot of del.icio.us and on query logs of two large search engines. All of the three datasets show small world properties. The tagging behavior of users, which is explained by preferential attachment of the tags in social bookmark systems, is reflected in the distribution of single query words in search engines. We can conclude that the clicking behaviour of search engine users based on the displayed search results and the tagging behaviour of social bookmarking users is driven by similar dynamics.

REFERENCES

• 1: E. Adar. User 4xxxxx9: Anonymizing query logs. In Query Logs Workshop at WWW2006, 2007.
• 2: Y.-Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong. Analysis of topological characteristics of huge online social networking services. In WWW '07: Proceedings of the 16th International Conference on the World Wide Web, pages 835-844, New York, NY, USA, 2007. ACM.
• 3: R. Baeza-Yates and A. Tiberi. Extracting semantic relations from query logs. In KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 76--85, New York, NY, USA, 2007. ACM.
• 4: D. Beeferman and A. Berger. Agglomerative clustering of a search engine query log. In KDD '00: Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 407--416, New York, NY, USA, 2000. ACM.
• 5: C. Cattuto, A. Baldassarri, V. D. P. Servedio, and V. Loreto. Vocabulary growth in collaborative tagging systems, 2007. http://www.citebase.org/abstract?id=oai:arXiv.org:0704.3316.
• 6: C. Cattuto, C. Schmitz, A. Baldassarri, V. D. P. Servedio, V. Loreto, A. Hotho, M. Grahl, and G. Stumme. Network properties of folksonomies. AI Communications Special Issue on Network Analysis in Natural Sciences and Engineering (to appear), 2007.
• 7: S. Dorogovtsev and J. Mendes. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, Oxford, January 2003.
• 8: H. Halpin, V. Robu, and H. Shepard. The dynamics and semantics of collaborative tagging. In Proceedings of the 1st Semantic Authoring and Annotation Workshop (SAAW'06), 2006.
• 9: 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 Lecture Notes in Computer Science, pages 411--426, Heidelberg, June 2006. Springer.
• 10: P. Kolari, T. Finin, Y. Yesha, Y. Yesha, K. Lyons, S. Perelgut, and J. Hawkins. On the Structure, Properties and Utility of Internal Corporate Blogs. In Proceedings of the International Conference on Weblogs and Social Media (ICWSM 2007), March 2007.
• 11: C. Marlow, M. Naaman, D. Boyd, and M. Davis. Position Paper, Tagging, Taxonomy, Flickr, Article, ToRead. In Collaborative Web Tagging Workshop at WWW2006, May 2006.
• 12: P. Mika. Ontologies are us: A unified model of social networks and semantics. In Proceedings of the Fourth International Semantic Web Conference (ISWC 2005), LNCS, pages 522--536. Springer, 2005.
• 13: M. E. J. Newman. Assortative mixing in networks. Phys. Rev. Lett., 89:208701, 2002.
• 14: M. E. J. Newman. Random graphs as models of networks, pages 35--68. Wiley, first edition, 2003.
• 15: G. Pass, A. Chowdhury, and C. Torgeson. A picture of search. In Proc. 1st Intl. Conf. on Scalable Information Systems. ACM Press New York, NY, USA, 2006.
• 16: J. Röttgers. Am Ende der Flegeljahre - Das Web 2.0 wird erwachsen. c't 25/2007, page 148, 2007.
• 17: X. Shi. Social network analysis of web search engine query logs. Technical report, University of Michigan, School of Information, University of Michigan, 2007.
• 18: G. Smith. Search tagging, 2005. http://atomiq.org/archives/2005/05/search tagging.html.
• 19: D. J. Watts and S. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, June 1998.
• 20: G.-R. Xue, H.-J. Zeng, Z. Chen, Y. Yu, W.-Y. Ma, W. Xi, and W. Fan. Optimizing web search using web click-through data. In CIKM '04: Proceedings of the thirteenth ACM international conference on Information and knowledge management, pages 118--126, New York, NY, USA, 2004. ACM.
• 21: D. Zhang and Y. Dong. A novel web usage mining approach for search engines. Computer Networks, 39(3):303--310, June 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

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

General Terms:
Experimentation, Measurement

Keywords:
folksonomy, logsonomy, query log analysis, search engine