Harry Halpin, <hhalpin -(a)- ibiblio.org>
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
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
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
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: 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
The collection of all tags and their frequencies ordered by rank frequency.
Over time, is this distribution dynamic? or chaotic?
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
Leads 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]
Preferential Attachment: "Rich get richer" model
[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
A tag applied to every relevant resource would retrieve every document, and so have an
of 0.
A tag that selects only the resource needed, would have an
informational value (
) 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.

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
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
Top 25 tags (all del.icio.us displays) from 500 heavily tagged sites (tags > 2000 times) on del.icio.us
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.

where
,
are the measured values of
and
corresponds to
the lowest value for which the power law behavior holds
See [Newman, 2005] for derivation of formula
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.
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.
For 500 randomly selected sites, the parameter for has α=-3.9 and SD of 4.63.
Popular sites better converge to a power law, the convergence is a function of number of tags and taggers and time
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
and
.
Formally, the
Kullback-Leibler divergence between
and
is defined as:
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
Results suggest that the power law may form relatively early on in the process for most sites and persist with remarkable consistency throughout.
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.
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.
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
Where we denote by
, respectively
, the number of
times each of the tags was used individually to tag all pages,
and by
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
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.
30 other edges (i.e. 45 edges in total for 15 tags) are considered
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.
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?
[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.