The Complex Dynamics of Collaborative Tagging

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

Valentin Robu, <robu -(a)- cwi.nl>

Hana Shepard, <hshepher -(a)- princeton.edu>

Distribution

WWW2007, Banff, Canada, May 12th 2007

What about Folksonomies?

Folksonomy is a neologism for a practice of collaborative categorization using freely chosen keywords. More colloquially, this refers to a group of people cooperating spontaneously to organize information into categories. In contrast to formal classification methods, this phenomenon typically only arises in non-hierarchical communities, such as public websites

For an example, see my del.icio.us bookmarks

Our search for me on flickr

Classification vs. Categorization

[Jacob, 2004]:

Ontology vs. Folksonomy

The Semantic Web versus Collaborative Tagging

Tagging is considered a categorization process

Expert-created Semantic Web ontologies are a pre-optimized classification process

[Shirky, 2005]: A lot of users tagging things foobar are also tagging them frobnitz. I'll tell the user foobar and frobnitz are related." It's up to the user to decide whether or not that recommendation is useful -- del.icio.us has no idea what the tags mean. The tag overlap is in the system, but the tag semantics are in the users. This is not a way to inject linguistic meaning into the machine.

[Butterfield, 2005]:Free typing loose associations is just a lot easier than making a decision about the degree of match to a pre-defined category (especially hierarchical ones). It's like 90\% of the value of a proper taxonomy but 10 times simpler

From taxonomy...

hierarchy

Picture from [Shirky, 2005]

...to...

hierarchy with links

Picture from [Shirky, 2005]

...folksonomy

hierarchy with lots of links

Picture from [Shirky, 2005]

Drawbacks and Advantages: Tagging

Problem: Ambiguity in the meaning of tags, the use of synonyms which creates informational redundancy, and the possibility of idiosyncratic naming conventions where individuals string together many words or label items according to their personal utility, no facets or data-typing like dates

Advantage: [Mathes,2004] Groups of users do not have to agree on a hierarchy of tags or detailed taxonomy, they only need to agree, in a general sense, on the `meaning' of a tag enough to label similar material with terms for there to be cooperation and shared value

Drawbacks and Advantages: Ontologies

Problem:[Shirky, 2005]If you've got a large, ill-defined corpus, if you've got naive users, if your cataloguers aren't expert, if there's no one to say authoritatively what's going on, then ontology is going to be a bad strategy. (Shirky)

Advantage:People can share data in discrete units that are categorized with complex relationships to other units, including hierarchical ones, without resorting to vague or redundant tags. Ontologies are more expressive in many cases and can deal easily with facets and data-typing.

Hypothesis

Hypothesis: How to determine when the collective tags of users converge to some coherent and socially navigable way of organizing metadata?

Null Hypothesis: Without a centralized controlled vocabulary,no coherent categorization scheme can emerge at all

Test using empirical data from del.icio.us

Tag Distributions

The collection of all tags and their frequencies ordered by rank frequency.

A typical del.icio.us user

Over time, is this distribution dynamic? or chaotic?

Tripartite Structure of Tagging

Overview
  1. The users of the system (people who actually do the tagging)
  2. The tags themselves
  3. The resources (websites) being tagged.

Tagging as Information Retrieval

Tagging is a methodology for information retrieval

Relies on human knowledge, as opposed to an algorithm, to connect terms to documents before a search begins

Tagging as Information Retrieval PictureLeads to a feedback cycle if other tags of other users are displayed pre-tagging, as in del.icio.us' recommended tags.

Imitation and shared knowledge [Golder and Huberman, 2006]

A Generative Model for Tagging

Preferential Attachment: "Rich get richer" model

Shuffling

[Diaconis et. al., 1995]for details

Preferential Attachment would not explain how one search term can become more popular than another except through pure chance. The oldest tags for a resource are not always the most popular tag

Information Value

Informational Value

A tag applied to every relevant resource would retrieve every document, and so have an $I$ of 0.

A tag that selects only the resource needed, would have an informational value ($I$) of 1.

Users presumably want the optimal tag to return some cognitively appropriate number of resources

Tag combinations may have different informational values that are not additive.

In our work we empirically estimate the informational value of a tag by retrieving the number of web-pages a del.icio.us search with a tag returns and converting it into a probability.

Generative Model

Generative Equation

Probability of a tag being used on a given resource given by a linear interpolation (λ) of information value of that tag and (1-&lambda) preferential attachment, where P(o) is the chance of a tagging action

Complex Systems

Online tagging systems are complex systems: a large number of users, a lack of central coordination, non-linear dynamics

Known to produce a power-law distributions.

These networks are scale-free, such that regardless of how larger the system grows, the shape of the distribution remains the same, and thus stable [Shen and Wu].

In Math:

y = cxα

If you apply logarithms to both sides of the equation:

log y = α log(x) + log(c)

The Long Tail and the Giant Component

Empirical Data from Del.icio.us

Top 25 tags (all del.icio.us displays) from 500 heavily tagged sites (tags > 2000 times) on del.icio.us

Individual Distribution

Discovering the Powerlaw

log y = α log(x) + log(c): When plotted in log-log space, power laws are straight lines

Can't average power-laws, it's a non-normal distribution, so Central Limit Theorem doesn't hold.

Newman Equation

where $x_i$, $i=1..n$ are the measured values of $x$ and $x_{min}$ corresponds to the lowest value for which the power law behavior holds

See [Newman, 2005] for derivation of formula

The Power-Law Revealed

The parameter for the slop of the power law, using Newman's Equation, has α=-1.28. For the individual sites (not shown graphically, for the sake of clarity of the picture), the slopes were in a similar range, an average α =-1.22, with SD of 0.03.

Log Distribution

Tags in positions 7 to 10 have a considerably sharper drop in frequency than the general trend line would predict - likely a result of "cognitively appropriate usage of tags" and artifact of recommended tags by del.icio.us.

Power Law in Randomly Selected Sites

For 500 randomly selected sites, the parameter for has α=-3.9 and SD of 4.63.

Distribution for Randomly Selected Sites

Popular sites better converge to a power law, the convergence is a function of number of tags and taggers and time

When Do Tags Stabilize?

How does the shape of these distributions forms in time from the tagging action of the individual users?

We tell if a particular tag distribution has stabilized using Kullback-Leibler Divergence (also known ``relative entropy" or ``information divergence") represents a natural distance measure between two probability distributions $P$ and $Q$.

Formally, the Kullback-Leibler divergence between $P$ and $Q$ is defined as:

Log Distribution

Tags Convergence over Time

Take the KL Divergence between every two consecutive points in time of the distribution, where each point in time represents some change in the distribution

Stabilization is when distribution goes to zero

KL over time

Results suggest that the power law may form relatively early on in the process for most sites and persist with remarkable consistency throughout.

Convergence Again..

Or take the KL Divergence of the tag distribution for each time step with respect to the final tag distribution or an ideal tag distribution for that site.

Assumes final or ideal distribution is stable.

KL over steps

We use final "power-law" distribution

There is a substantial amount of variation in the initial values of the Kullback-Leibler distance prior to the convergence.

Information Value and Inter-tag Correlation

Now that we have stable distributions, what do we do with them?

Visualize how the stable tags in the distribution influence each other, to discover which ones have the highest information value, using Cosine Distance

KL over steps

Where we denote by $N(T_i)$, respectively $N(T_j)$, the number of times each of the tags was used individually to tag all pages, and by $N(T_i, T_j)$ the number of times two tags are used to tag the same page (summed up over all pages).

Construct a tag-tag correlation graph, where the nodes represent the tags themselves (weighed by their absolute frequencies, represented by size), while the edges are weighed with the cosine distance measure, interpreted as similarity

High information value tags have a large node size and have highest information value in combination with distant related tags

Graphing a Single Tag

Only the dependencies between the tag ``complexity" and all other tags in the subset are taken into account when building the graph

A visualization of this weighed tag-tag correlation, by using a ``spring-embedder" type of algorithm - the Kawada-Kawai algorithm.

tag graph

Graphing a Group of Tags

30 other edges (i.e. 45 edges in total for 15 tags) are considered

tag graph

Human Language Evolution and Zipf's Law

Inter-word correlation graphs of human language, far from having the structure predicted by random graph theory for such large networks, have, in fact a ``small world" structure [Sole,2005]

Speakers prefer to use ambiguous, general words which have minimum entropy (and minimize their effort for choosing the word), while hearers prefer words with high entropy, and thus high information content.

Tagging Analogy: resources = real-world objects, taggers = speakers, retrievers=hearers

Taggers want to use tags that minimize ambiguity but can be shared amongst other users for each other's maximal benefit in information retrieval.

Conclusions

Future Work

Use data to estimate the parameters values for our model?

Can we see if after tagging stabilizes, taxonomies can be formed in an unsupervised manner?

Can we repair taxonomies with the use of tagging via supervised learning?

See if tagging stabilization varies over various domains like current news events, scientific areas, and so on?

Are some terms: Convergent? Divergent? Chaotic?

References

[1] P. Diaconis, M. McGrath, and J. Pitman. Riffle shuffles, cycles and descents. Combinatorica, 15:11-29, 1995.

[2] S. Golder and B. Huberman. The structure of collaborative tagging systems, 2006. HP Labs Technical Report. http://www.hpl.hp.com/research/idl/papers/tags.

[3] E. Jacob. Classification and categorization: A difference that makes a difference. Library Trends, 52(3):515-540, 2004.

[4] A. Mathes. Folksonomies: Cooperative classification and communication through shared metadata, 2004.

[5] P. Mika. Ontologies are us: A unified model of social networks and semantics. In Proc. of the 4th Int. Semantic Web Conference (ISWC'05). Springer LNCS vol. 3729, 2005.

[6] M. Newman. Power laws, pareto distributions and zipf's law. Contemporary Physics, 46:323-351, 2005.

[7] K. Shen and L. Wu. Folksonomy as a complex network, 2005. http://arxiv.org/abs/cs.IR/0509072.

[8] C. Shirky. Ontology is over-rated, 2005. http://www.shirky.com/writings/ontology-overrated.html.

[9] R. V. Sole. Syntax for free? Nature, 434:289, 2005.

[10] G. Zipf. Human Behaviour and the Principle of Least Effort. Addison-Wesley, Cambridge, Massachusets, 1949.