Status report for 11/08/2007 to 11/14/2007

I've been reading a paper about ranking in folksonomy, called FolkRank, proposed in Trend detection in folksonomies, Information Retrieval in Folksonomies: Search and Ranking.

FolkRank is based on well-known PageRank algorithm used in Google (The Anatomy of a Large-Scale Hypertextual Web Search Engine and The PageRank Citation Ranking: Bringing Order to the Web).

In a nut shell, the basic idea of PageRank is that a page is important if there are many pages linking to it. This can be formulated by the following matrix equation:

R(u) = c \sum R(v)/N or R(u) = c \sum R(v)/N + cE(u)

where

u is a web page and v is a page referring u,

R(u) and R(v) are PageRank of u and v repectively,

N is a number of all links in page u, and

E(u) is called a source of rank.

 

Folksonomy can also be represented as a graph by using the similar concept of PageRank but a few exceptions:

• Folksonomy graph is undirected, while web graph in PageRank is directed.
• Nodes are heterogeneous and the graph is triadic, while in PageRank the nodes are homogeneous.

I think it's a good start to begin with applying PageRank algorithm to folksonomy recommendation system. For this purpose, I'm planing to dig into more details on the PageRank algorithm and find some sample code for better understand.

Status report for 11/01/2007 to 11/07/2007

1. I made a reading list about folksonomy at my CGL blog or del.icio.us. I will update the list frequently by adding related articles.

2. Characteristics of Folksonomy Network

The folksonomy networks show the following characteristics:

a. Small-world Network

Almost similar with a random network but having much larger clustering co-efficient factor. I.e., Small shortest path but a larger clustering coefficient.

b. Scale-free Network

A scale-free network is a network in which any two nodes can be connected no matter what the system size is. This is because there is a node called "hub"which is a highly connected node than any others. In folksonomies, popular keywords can act like this hub and thus the network shows scale-free network properties.

A scale-free network shows the following rules:

(1) Power law : Degree distribution follows the Yule-Simon distribution, which is called a power law: P(k) ~ k^(-r), where k is a degree of connectivity of a node and P(k) is it's probability

(2) Preferential Attachment : A way to build a scale-free network. The idea is to make a connection with a more connected node.

3. Next step

a. Build a simple graph by using CITEAM tag data

b. Find some algorithms about recommendation

Reading list about folksonomy analysis

(Also available at http://del.icio.us/yyalli/folksonomy)

Formal Model, Graph

• The Complex Dynamics of Collaborative Tagging, HT 07
• Network Properties of Folksonomies, WWW 07
• Mining Association Rules in Folksonomies, Data Science and Classification
• Ontologies are us: A unified model of social networks and semantics, Web Semant. 5, 1 (Mar. 2007)
• Folksonomy as a Complex Network
• Trend detection in folksonomies, LNCS, 2006
• A Social Networking Model of a Web Community,

Semantic Web

• Bridging the Gap Between Folksonomies and the Semantic Web: An Experience Report, ESWC 07

Pattern, Structure

• Towards Better Understanding of Folksonomic Patterns, HT 07
• HT06, tagging paper, taxonomy, Flickr, academic article, to read, HT 06

Recommendation, Ranking, Trend

• Tag Recommendations in Folksonomies, LNCS, 2007
• Trend detection in folksonomies
• Recommending Smart Tags in a Social Bookmarking System
• Information Retrieval in Folksonomies: Search and Ranking
• Harvesting social knowledge from folksonomies, HT 06

Tag Generation

• P-TAG: large scale automatic generation of personalized annotation tags for the web, WWW 07

PageRank

• The Anatomy of a Large-Scale Hypertextual Web Search Engine, Sergey Brin and Lawrence Page, 1998
• The PageRank Citation Ranking: Bringing Order to the Web, 1998

Clustering (referred from Filippo Menczer's class material)

• Web Page Recommender System based on Folksonomy Mining for ITNG ’06 Submissions, ITNG '06, 2006
• Finding related pages in the World Wide Web, Computer Networks, 1999
• Self-Organization and Identification of Web Communities, IEEE Computer, 2002
• Finding replicated Web collections, ACM SIGMOD '00, 2000
• Community structure in social and biological networks, PNAS, 2002
• Defining and identifying communities in networks, PNAS, 2004

Learning and Classification (referred from Filippo Menczer's class material)

• Text Categorization with Support Vector Machines: Learning with Many Relevant Features, 1997
• Support Vector Machines, 1998
• A Tutorial on Support Vector Machines for Pattern Recognition, 1998
• A re-examination of text categorization methods, ACM SIGIR, 1999