Information-Theoretic Models of Tagging

Harry Halpin, University of Edinburgh <hhalpin -(a)- ibiblio.org>

Distribution

Dagstuhl Seminar, Germany, Sept. 21st 2008

Introduction: Power-Law Emergence

In Halpin, Robu, and Shepard, we showed using Kulback-Leibler (KL) divergence that not only do tags form a power law distribution, but that the distribution forms very quickly. Take the KL Divergence between every two consecutive points in time of the distribution, stabilization is when distribution goes to zero.

Log Distribution KL over time

Et tu Feedback?

feedback graph

Originally hypothesized that the "bump" in the data could be caused by a preferential attachment mechanism. However, in an experiment that tested both feedback and no-feedback conditions over tagging (300 subjects) shows that the power-law distribution arises regardless of any feedback effect (Bollen and Halpin, in preparation).

Tags and Information Theory

Would an information-theoretic analysis of tags that leads to a power-law without feedback? Perhaps just an idealized information retrieval paradigm, with each group of tags having an entropy assigned to it?

Informational Value

A tag applied to every relevant resource would retrieve every document, and so have an $I$ of 0 while a tag that selects a single relevant resource would have an information ($I$) of 1. If users selected an ideal encoding with every choice, a power-law could result.

Applications of similar models to social networks, with aim of surveying, discovering, and finding patterns in social networks?

Harry Halpin, School of Informatics, University of Edinburgh: Interests in Web architecture, analytic and continental philosophy, collective intelligence, natural language processing, and the Semantic Web. W3C (World Wide Web Consortium) Fellowship (MIT/INRIA) starting in January 2009, to launch Social Web W3C Incubator Group