User:HungKChau/sandbox

FolkRank is a ranking algorithm for folksonomies on social bookmarking systems (for example, Flickr, del.icio.us, and bibsonomy). It adapted the PageRank algorithm to the folksonomies' structure. FolkRank was introduced by Andreas Hotho in 2006 . It is applied not only to determining an overall ranking and specific topic-related rankings, but also to a variety of applications, finding communities, structuring search results and trend detection within folksonomy, to name a few.

Introduction

It is simply easy for users to bookmark the resources on social resource sharing tools and use tags to describe or organize their bookmarks. The collection of all each user's assignment is called a personomy. Within folksonomies, the users are able to explore their own personomy as well as the personomies of other users. By clicking on resources or tags, they can see which tags others assign to the same resource with them, who use the same tags with them and which resources are connected to these tags. However, Over the past ten years, folksonomies have acquired a large number of users who have been creating a huge amount of information. This causes users more difficult to seek information by browsing within a folksonomy. Moreover, most of users are more familiar with search interfaces than browsing interfaces. Therefore, employing standard techniques for searching information in folksonomy-based systems help users ease the information seeking process.

The issue here is how to provide a suitable ranking list to a user query in order to meet their information need. Fortunately, the structure of folksonomy can be transformed into a graph structure. Hotho took advantages of the folksonomy structure and adapted PageRank algorithm to FolkRank algorithm in order to rank users, tags and resources in folksonomy based systems. The algorithm can be used for a topic-specific ranking. This ranking also can help to detect trends in these systems and recommend items (e.g., users, resources) to a specific user based on their preference.

Formal definitions of a folksonomy

The folksonomy structure of social bookmarking systems

Several studies have worked with folksonomy and defined a structure for it to use in their applications. All of them represent the folksonomy structure in some form that describes the connections among users, tags and resources. Hotho and colleagues give a formal definitions for a folksonomy as follows:

• Definition 1. a folksonomy is a tuple F := (U, T, R, Y), where:

• U is the finite set of all users
• T is the finite set of all tags
• R is the finite set of all resources
• Y ⊆ U × T × R, is a ternary relation between U, T and R, called tag assignments (TAS).

• Definition 2. a folksonomy for a specific user is called a personomy.

• The personomy $P_{u}\,$ of a given user u ∈ U is the restriction of F to u, i. e., $P_{u}:=(T_{u},R_{u},I_{u},re_{u})\,$ with I_u := {(t, r) ∈ T × R | (u, t, r) ∈ Y}, T_u := π₁ (I_u), R_u := π₂ (I_u) and re_u := {(t₁ ∈ T × T | (u, t₁, t₂) ∈ re}, where π_i denotes the projection on the ith dimension.

• Definition 3. a post represents a tag assignments of one user for one resource.

• The set P of all posts is defined as P := {(u, S, r) | u ∈ U, r ∈ R, S = tags(u, r), S ≠ ∅} where, for all u ∈ U and r ∈ R, tags(u, r) := {t ∈ T | (u, t, r) ∈ Y} denotes all tags the user u assigned to the resource r.

Although these definitions above focus on a folksonomy with users, tags and resources as three dimensions, it is possible to enhance the structure to include more dimensions . For example, Wu et al. consider the fourth element: timestamps which are assigned to tag-resource pairs in order to consider temporal aspects in their analysis.

Algorithm

Tripartite undirected hypergraph of a folksonomy structure

The FolkRank algorithm computes a topic-specific ranking in a folksonomy, it operates on an undirected, tripartite graph. The PageRank weight-spreading approach can not be directly applied to folksonomy because the structure of folksonomy is different with web graph. Therefore, a folksonomy structure F = (U, T, R, Y), firstly, is converted into a tripartite undirected hypergraph G = (V, E), which connects users, tags, and resources.

• V = U∪T∪R is the set of nodes of the graph consists of the disjoin union of all tags, users and resources
• E = {{u, t, r} | (u, t, r) ∈ Y } is the set of hyperedges of the graph. The set of edges E is the combination of all possible paths resulting from splitting tag assignments into three undirected edges: E = {{u, t}, {t, r}, {u, r} | (u, t, r) ∈ Y }

The PageRank formula can be iteratively applied to this hypergraph as follows:

$w_{t+1}=dA^{T}w_{t}+(1-d)p\,$

where:

• p : is used as preference vector used to determine the topic
• $d\in [0,1]\,$: damping factor controls the influence of the preference vector p, usually assigning d = 0.85
• A : the row-stochastic version of adjacency matrix of the graph G

Preference weights need to be specified for the preference vector p in order to compute a ranking of tags, resources and/or users tailored to the preferred item/topic. In web search, the tags which can be referred as search query terms receive a higher weight compared to the remaining items (i.e., remaining tags, all users and all resources) whose weight scores are equally distributed. With any distributions of weights, the equation ||w||₁ = ||p||₁. The algorithm is presented as follows.

Algorithm: FolkRank

Input: Undirected, tripartite graph G_F , a randomly chosen baseline vector w₀ and a randomly chosen FolkRank vector w₁.

1. Set preference vector p.

2. Compute baseline vector w₀ with p = 1 and $1=[1,...,1]^{T}$.

3. Compute topic specific vector w₁ specific preference vector p.

4. w := w₁ - w₀ is the final weight vector.

Output: FolkRank vector w.

Applications of FolkRank

• Trend detection. Folkrank is applied to explore trends in the folksonomy of social bookmarking systems . It measures the topic-specific rankings (i.e., the topic is described by defining the preference vector p) in order to determine which users, tags and resources have been gaining or losing their popularity at different points of time (e.g., who are the winners/losers?). Also, based on the rankings, the system is able to discover the absolute rankings (e.g., who is in the top ten of the topic "music" or what tags are in the top ten of the topic "politics").

• Item Recommendation. A social bookmarking system can apply FolkRank for its recommender system. A preference vector p could be defined using the user profile. Therefore, the system can compute the rankings on users, tags and resources. Based on this ranking list, it recommends items (e.g., users or resources) to the user. The three dimensions of social tagging systems allow to do multi-mode recommendations , for instance, finding resources, tags or users.

• Information Retrieval. FolkRank is also developed to support Google-like search in folksonomy-based systems. With the huge increase of numbers of items on the social booking systems, browsing becomes more difficult for users to seek for information. All the system, currently, provide users with searching. FolkRank can help to improve the result list against user queries in order to better users' information need. Moreover, traditional search engines also can transform their click data file into a folksonomy-like structure, called a logsonomy . Thus, search engines can apply FolkRank to support personalized search and a different ranking list.

See also

• PageRank
• SimRank
• SocialRank