Models of collaborative tagging

Descriptive models

Information theory models

For most tagging systems, the total number of objects being tagged far exceeds the total number of tags in the collective vocabulary. If a single tag in this system is specified, many documents would match, so that using single tags cannot effectively isolate any one document. However, some documents are more popular or important than others, which is reflected in the number of bookmarks per document. Thus, the focus should be on how well the mapping of tags to documents retains information about the distribution of the documents. Information theory provides a framework to understand the amount of shared information between two random variables. The conditional entropy measures the amount of entropy remaining in one random variable when the value of a second random variable is known.

A 2008 paper by Ed Chi and Todd Mytkowicz showed that the entropy of documents conditional on tags, H(D|T), is increasing rapidly. This suggests that, even after knowing completely the value of a tag, the entropy of the set of documents is increasing over time. Conditional entropy asks the question: "Given that a set of tags is known, how much uncertainty remains regarding the document set referenced by those tags?" This curve is strictly increasing, which suggests that the specificity of any given tag is decreasing. As a navigation aid, tags are becoming harder and harder to use, and a single tag will gradually reference too many documents to be considered useful.

Another approach is through mutual information, a measure of independence between two variables. Full independence is reached when I(D;T) = 0. Chi and Mytkowicz's research shows that as a measure of usefulness of tags and their encoding, there is a worsening trend in the ability of users to specify and find tags and documents when they are engaged in simple fact retrieval. This suggests that search and recommendation systems should be built to help users sift through resources in social tagging systems, especially when they are engaged in activities beyond fact retrieval, as characterized by information theory. Although the number of documents associated with any given tag is increasing, there are many ways contextual information can help users to look for relevant information. This is one of the major weakness of the simple information theory in explaining usefulness of tags – it ignores how humans can extract meanings from a set of tags assigned to a document. For example, a 2007 paper showed that while the number of tags is increasing, the general growth pattern is scale-free – the general distribution of tag-tag co-occurrences follows a power law.

The same paper also found that the characteristics of this scale-free distribution depend on the semantics of the tag – tags that are semantically general (e.g., blogs) tend to co-occur with many tags, while semantically narrow tags (e.g., Ajax) tend to co-occur with few tags across a wide set of documents in a social tagging system. This suggests that the assumption of the information theory approach is too simple – when taking into account the semantics of the set of tags assigned to documents, the predictive value of tags on contents of documents is relatively stable. This finding is important for development of recommender systems – discovering these higher-level semantic patterns is important in helping people find relevant information.

Tag convergence

Despite this potential vocabulary problem, research has found that at the aggregate level, tagging behavior seemed relatively stable, and that the tag choice proportions seemed to be converging rather than diverging. While these observations provided evidence against the proposed vocabulary problem, they also initiated research investigating how and why tag proportions tended to converge over time.

One explanation for the stability was that there was an inherent propensity for users to "imitate" word use of others as they create tags. This propensity may act as a form of social cohesion that fosters the coherence of tag-topic relations in the system, and leads to stability in the system. It was shown that the stochastic urn model created in 1923 was useful in explaining how simple imitation behavior at the individual level could explain the converging usage patterns of tags. Specifically, the convergence of tag choices was simulated by a process in which a colored ball was randomly selected from an urn, then replaced in the urn along with an additional ball of the same color, simulating the probabilistic nature of tag reuse. This simple model, however, does not explain why certain tags would be "imitated" more often than others, and therefore cannot provide a realistic mechanism for tag choices and how social tags could be used as navigational cues during exploratory search.

Complex systems dynamics and emergent vocabularies

Research based on data from the social bookmarking website Del.icio.us has shown that collaborative tagging systems exhibit a form of complex systems (or self-organizing) dynamics. Furthermore, although there is no central, controlled vocabulary to constrain the actions of individual users, the distributions of tags that describe different resources has been shown to converge over time to a stable, power-law distribution. Once such stable distributions form, the correlations between different tags can be used to construct simple folksonomy graphs, which can be partitioned to obtain a form of community or shared vocabularies. Such vocabularies can be seen as emerging from the decentralized actions of many users – a form of crowdsourcing.

Tag choice by stochastic process

The memory-based Yule-Simon (MBYS) model attempts to explain tag choices by a stochastic process. It was found that the temporal order of tag assignment influences users' tag choices. Similar to the stochastic urn model, the MBYS model assumes that at each step, a tag would be randomly sampled: with probability ${\displaystyle p}$ that the sampled tag was new, and with probability 1-${\displaystyle p}$ that the sampled tag was copied from existing tags. When copying, the probability of selecting a tag was assumed to decay with time, and this decay function was found to follow a power-law distribution. Thus, tags that were more recently used had a higher probability of being reused.

One major finding was that semantically general tags (e.g., "blog") generally co-occurred more frequently with other tags than semantically narrower tags (e.g., "Ajax"), and this difference could be captured by the decay function of tag reuse in their model. Specifically, it was found that a slower decay parameter (when the tag is reused more often) could explain the phenomenon that semantically general tags tended to co-occur with a larger set of tags. In other words, it was argued that the "semantic breadth" of a tag could be modeled by a memory decay function, which could lead to different emergent behavioral patterns in a tagging system.

Predictive models

Semantic imitation model

Descriptive models were based on analyses of word-word relations as revealed by the various statistical structures in the organization of tags (e.g., how likely one tag would co-occur with other tags or how likely each tag was reused over time). Thus, these models are descriptive models at the aggregate level, and have little to offer about predictions at the level of an individual's interface interactions and cognitive processes.

Rather than imitating other users at the word level, one possible explanation for this kind of social cohesion could be grounded on the natural tendency for people to process tags at the semantic level, and it was at this level of processing that most of the imitation occurred. This explanation was supported by research in the area of reading comprehension, which showed that during comprehension, people tended to be influenced by meanings of words rather than the words themselves. Assuming that people in the same culture tend to have shared structures – such as using similar vocabularies and their corresponding meanings to conform and communicate, users of the same social tagging system may also share similar semantic representations of words and concepts, even when the use of tags may vary across individuals at the word level. As such, part of the reason for the stability of social tagging systems can be attributed to the shared semantic representations among the users, such that users may have relatively stable and coherent interpretation of information contents and tags as they interact with the system. Based on this assumption, the semantic imitation model predicts how different semantic representations may lead to differences in individual tag choices and eventually different emergent properties at the aggregate behavioral level. The model also predicts that the folksonomies in the system reflect the shared semantic representations of the users.

Semantic imitation has important implications to the general vocabulary problem in information retrieval and human–computer interaction – the creation of a large number of diverse tags to describe the same set of information resources. Semantic imitation implies that the unit of communication among users is more likely at the semantic level rather than the word level. Thus, although there may not be strong coherence in the choice of words in describing a resource, at the semantic level, there seems to be a stronger coherence force that guides the convergence of descriptive indices. This is in sharp contrast to conclusions derived based on a purely information-theoretical approach, which assumes that humans search and evaluate information at the word level. Instead, the process of semantic imitation in social tagging implies that the information-theoretic approach is at most incomplete, as it does not take into account the basic unit of human information processing. Similar to the fact that human communication occurs at the semantic level, the fact that people may use different words or syntax does not affect the effectiveness of communication, so long as the underlying "common ground" between two people is the same.

In the social tagging case, as long as users share a similar understanding of the contents of the information resources, the fact that the information value of tag-document decreases (that humans have more words in their languages) does not imply that it will always be harder to find relevant information (similarly, the fact that there are an increasing number words in human languages does not mean that communication becomes less effective). However, it does point to the notion that one needs to effectively present these semantic structures in the information system so that people can effectively interpret the semantics of the tagged documents. Intelligent techniques based on statistical models of language, such as latent semantic analysis and the probabilistic topics model, could potentially overcome this vocabulary problem.