Recommendation systems which aim at providing relevant information to users are becoming more and more important and desirable due to the enormous amount of information available on the Web. Crucial to the performance of a recommendation system is the accuracy of the user pro¯les used to represent the interests of the users. In recent years, popular collaborative tagging systems such as del.icio.us have aggregated an abundant amount of user-contributed metadata which provides valuable information about the interests of the users. In this paper, we present our analysis on the personal data in folksonomies, and investigate how accurate user pro¯les can be generated from this data. We reveal that the majority of users possess multiple interests, and propose an algorithm to generate user pro¯les which can accurately represent these multiple interests. We also discuss how these user pro¯les can be used for recommending Web pages and organising personal data.
H.3.4 [Information Storage and Retrieval]: Systems and Software; H.3.5 [Information Storage and Retrieval]: Online Information Services; H.5 [Information Interfaces and Presentation (I.7)]:
The amount of resources on the Web nowadays is so
enormous that retrieval of relevant information is getting more
and more di±cult. While users are desperate to obtain
information that is relevant to their needs and to avoid
information that are irrelevant, publishers of resources are also
eager to deliver their information to their targeted readers.
This has resulted in the rise of recommendation systems [
Some research works attempt to construct user pro¯les based
on the browsing history of the users [
Recently, the rising popularity of collaborative tagging
systems [
Currently, only a few studies in the literature try to
construct user pro¯les from data in collaborative tagging
systems [
This paper is structured as follows. Section 2 introduces folksonomies and personomies. Section 3, presents the analysis of the data collected from del.icio.us which motivated this research. In Section 4, we describe in detail our proposed algorithm for user pro¯le construction. Evaluations, discussions and potential applications are presented in Section 5. We mentioned related works in Section 6. Finally, Section 7 concludes the paper and gives future research directions. 2.
Folksonomies [
De¯nition 1. A folksonomy F is a tuple F = (U; T; D; A), where U is a set of users, T is a set of tags, D is a set of Web documents, and A µ U £ T £ D is a set of annotations.
If we want to understand the interests of a single user, we
only need to concentrate on the tags and documents that
are associated with this particular user. Such set of data is
given the name personomy [
De¯nition 2. A personomy Pu of a user u is a restriction of a folksonomy F to u: i.e. Pu = (Tu; Du; Au), where Au is the set of annotations of the user: Au = f(t; d)j(u; t; d) 2 Ag, Tu is the user's set of tags: Tu = ftj(t; d) 2 Aug, and Du is the user's set of documents: Du = fdj(t; d) 2 Aug.
This de¯nition is identical to the one mentioned in [
To perform analysis on the personomy of a user, we ¯rst represent the personomy in the form of a network, with nodes representing tags and documents associated with the user. If folksonomy can be considered as a hypergraph with three disjoint sets of nodes (user, tags and documents), a personomy can be represented as a bipartite graph by extracting the part that is related to the user. The bipartite graph T Du of a personomy of a user u is de¯ned as follows.
T Du = hTu [ Du; Etdi; Etd = f(t; d)j(t; d) 2 Aug An edge exists between a tag and a document if the tag is assigned to the document. The graph can be represented in matrix form, which we denote as X = fxij g, xij = 1 if there is an edge connecting ti and dj , and xij = 0 otherwise.
To perform document clustering, we can fold the
bipartite graph into a one-mode network [
To facilitate the following discussions, we further de¯ne several notations here. Firstly, we denote the set of documents tagged by the tag t in the personomy of user u by Du;t:
Du;t = fdj(t; d) 2 Aug Also, we de¯ne Cou(t1; t2) which indicates whether two tags t1 and t2 have been used on the same document by a user: Cou(t1; t2) = ½ 1 if (t1; d) 2 Au, (t2; d) 2 Au for some d
0 otherwise 3In the blogosphere, the term personomy has also been used in a more general sense to represent the aggregated digit manifestation of a user on the Web. See http://personomies.com/what-are-personomies/.
Maximum Minimum Mean
To understand the characteristics of personomies in collaborative tagging systems, we perform analysis on data collected from del.icio.us. In particular, we want to gain insight into the general behaviour of Web users using these systems. We also want to understand if users are generally interested in a rather speci¯c domain, such as we might expect when studying the publications of a researcher, or if they are more likely to be interested in a wide range of topics.
In December 2007, we collected the bookmarking data of 9,431 users of del.icio.us, including their bookmarks and the tags they used, by crawling del.icio.us user names which appeared on the page showing the recently updated bookmarks.4 It is noted that among the 9,431 users whose data we have collected, 246 of them apply no tags to any of their stored bookmarks. These users are ¯ltered when performing the following analysis. We summarise the statistics of the data of the remaining 9,185 users in Table 1 and Figure 1. 3.1
From the summary of the data in Table 1 and Figure 1,
we can see that on average a user have used 285 unique
tags and have saved 602 unique bookmarks on del.icio.us.
Although some users have over 18,000 tags and over 34,000
bookmarks, only a very small number of users have more
than a thousand tags or bookmarks. This ¯nding agrees
with what Golder and Huberman [
In addition, we examine the correlation between the number of tags and the number of bookmarks of the users. Figure 2 shows a scatter plot of the data. It shows a moderate relationship between the number of tags and the number of bookmarks, with a correlation coe±cient of 0.55.
In fact, it is natural to suggest that when there are more bookmarks more tags are required to distinguish between di®erent bookmarks by putting them into more speci¯c categories. However the bookmarks and tags of the users in the system are also highly dependent on the interests of the users. If a user has a very speci¯c interest, a small number of tags will be enough for even a large number of bookmarks, as they will probably be about the same topic. On the other hand, if a user has diverse interests, more tags may be required to describe even a small number of bookmarks.
A further investigation of the data reveals that the
correlation between the two numbers is stronger for users with
fewer bookmarks than those with many bookmarks. For
users with fewer than 500 bookmarks, the correlation
coe±cient is 0.43. For users with more than 5,000 bookmarks, the
4http://del.icio.us/recent
(a) Tags
(b) Bookmarks
correlation coe±cient is only 0.14. A similar result can also
be found in [
With the average number of bookmarks signi¯cantly larger than the average number of tags being used, it is obvious that users are very likely to use a tag to describe more than one bookmark. However, the usage of tags also depends on the diversity of interests of the users. A user with only one or two speci¯c interests is likely to use fewer tags than another user who is interested in topics across several di®erent domains. To understand this aspect of users in collaborative tagging system, we propose two measures which re°ect the diversity of interests of the users. We will give examples based on the two ¯ctional users in Table 2, one with rather speci¯c interests in Semantic Web related topics, while another has more diverse interests such as cooking and sports.
Firstly, we study the relations between the tags and the bookmarks. If the tags used by a user are all assigned to most of the bookmarks, the user is likely to have a rather speci¯c interest, because this set of tags applies to most of the documents that the user is interested in. On the other hand, if most of the tags are only used on a small fraction of bookmarks, it is likely that the user has a broader range of interests. To quantify this characteristic, we propose a measure called tag utilisation which is de¯ned as follows.
De¯nition 3. Tag utilisation (TU) of a user u is the average of the fractions of bookmarks on which a tag is used: T agU til(u) = 1
X jDu;tj jTuj t2Tu jDuj (1)
In addition, the diversity of a user's interest can also be understood by examining tag co-occurrence. If for a user the tags are always used together with each other, it is likely that the tags are about similar topics, and so the user should have a rather speci¯c interest. If on the other hand the tags are mostly used separately, they are more likely to be about di®erent topics, and thus re°ect that the user should have multiple interests which are quite distinctive from each other. Such characteristic can be measure by average tag co-occurrence ratio, which is de¯ned as follows.
De¯nition 4. Average tag co-occurrence ratio (ATCR) of a user measures how likely two tags are used together on the same bookmark by a user:
Avg T ag Co(u) =
X
Co(ti; tj) ti;tj2Tu;ti6=tj 2 £ C2jTuj (2)
If we represent the co-occurrences between the tags as a
network (by constructing the adjacency matrix T), we can
see that the average tag co-occurrence ratio is actually
equivalent to the density of the network of tags: Co(ti; tj ) counts
the number of edges in the network, while CjTuj calculates
2
the number of possible edges based on the number of nodes.
This agrees with the formula of the density of a network:
where E is the set of edges and V is the set of nodes. Hence,
the average tag co-occurrence ratio actually re°ects the
cohesion [
As an illustrating example, we apply these two measures to the two users listed in Table 2. The tag utilisation of u1 is 0:60, while that of u2 is 0:33. The average tag cooccurrence ratio of u1 is 0:80, while that of u2 is 0:27. For both measures, u1 scores higher than u2, this agrees with the fact that the interests of u2 are more diverse as observed from this user's bookmark collection.
Next, we apply these two measures on the set of data that we have collected from del.icio.us. The results are summarised in Table 3 and Figure 3.
Although the two measures are designed to measure di®erent characteristics of personomies, the results do have very common features. Firstly, the mean values of tag utilisation and average tag co-occurrence ratio both very low, at 0.06 and 0.07 respectively, even though the values span across the whole range from 0 to 1. These values mean that on average a tag is only used on 6% of the bookmarks in a user's collection, and that a tag is only used together with 7% of other tags. We can see that there is a small group of points in both graphs in Figure 3 which attain a value of 1. These actually correspond to users who have only one bookmark in their collection. Other than these the values drop quickly, and the majority of personomies have values less than 0.2 (93% in both measures). Also, there is a strong correlation between tag utilisation and average tag co-occurrence ratio, with a correlation coe±cient of 0.71.
Given these ¯gures, we reveal that for most users many tags are used only on a small portion of their bookmarks, and that these tags are not always used together. This suggests that the bookmarks of the users have topics which are rather diverse such that tags do not apply to all of them. Also, a user's tags can be terms from di®erent domains which are not used together very often on the bookmarks. Hence, this indicates that users of del.icio.us have diverse interests instead of a single interest in a very speci¯c domains.
As the majority of users in del.icio.us are observed to be interested in a wide range of topics from di®erent domains, a user pro¯le in the form of a single set of tags is de¯nitely inadequate. Hence, user pro¯les which can accommodate the multiple interests of the users are very much desirable.
Identifying the di®erent interests can be a challenging task (a) Tag utilisation (b) Average tag co-occurrence ratio as tags are freely chosen by users and their actual meaning is usually not very clear. A solution to this problem is to exploit the associations between tags and documents in a folksonomy. As it is obvious that documents related to the same interest of a user would be tagged by similar tags, we can perform clustering algorithms on the documents tagged by a user to group documents of similar topics together, and extract the sets of tags assigned to these documents as indicators of the users' di®erent interests.
Based on this idea, we propose a method for constructing user pro¯les which involves constructing a network of documents out of a personomy, applying community-discovery algorithms to divide the nodes into clusters, and extracting sets of tags which act as signatures of the clusters to re°ect the interests of the users. 4.1
Clusters in a network are basically groups of nodes in
which nodes have more connections among each other than
with nodes in other clusters. The task of discovering clusters
of nodes in a network is usually referred to as the problem of
discovering community structures within networks [
To quantitatively measure the `goodness' of the clusters
discovered, the measure of modularity [
Although modularity provides a quantitative method to
determine how good a certain division of a network is, brute
force search of the optimal value of modularity is not
always possible due to the complexity of the networks and the
large number of possible divisions. Several heuristics have
been proposed for optimizing modularity, these include
simulated annealing [
Given a network of documents (which are bookmarks in our case), we can apply the community-discovery algorithms to obtain clusters of documents. As the di®erent clusters should contain documents which are related to similar topics, a cluster can be considered as corresponding to one of the many interests of the user. A common way to represent user interests is to construct a set of tags or a tag vector. Similarly, we can obtain a set of most frequently used tags from each of the document clusters to represent the corresponding interest. As a summary of our method, the following list describes the whole process of constructing a user pro¯le for user u.
1. Extract the personomy Pu of user u from the folksonomy F, and construct the bipartite graph T Du. 2. Construct a one-mode network of documents out of T Du, and perform modularity optimization over the network of documents using the fast greedy algorithm. 3. For each of the clusters (communities) ci obtained in the ¯nal division of the network, obtained a set Ki of tags which appear on more than f % of the documents in the cluster. The set of tags of a cluster is treated as a signature of that cluster. 4. Finally, return a user pro¯le Pu in the form of a set of
Ki0s: Pu = fKig.
For the signatures of the clusters, one can include all the tags which are used on the bookmarks in the cluster, or include only the tags which are common to the bookmarks in the cluster. However, the set of tags chosen for a cluster will a®ect how accurate the pro¯le is in modelling the user's interest. In general, for a large value of f only the most common tags in the cluster will be included in the signature, while a small value of f will include more tags in the signature. We will investigate the problem of choosing a K1 K2 K3 K4 K5 K1 K2 K3 K4
webdesign, web2.0, tutorial, blog, css linux, opensource, ubuntu, software webhosting, ¯lesharing grammar, english digg, sharing, music, mp3
webdesign, programming interesting, art, video, funny food, books, tobuy lort, debate
From our data set, we select at random 1,000 users who have over 100 bookmarks in their personomies. The requirement of having at least 100 bookmarks is to ensure that there are enough bookmarks for clustering so that clearer results can be obtained. We apply our proposed method of generating user pro¯les on these personomies, and obtain a set of clusters of bookmarks and their signatures. We discover that there are a substantial number of clusters with only one bookmark. The bookmarks in these clusters are mostly not assigned any tags. Hence, we exclude these single-bookmark clusters in the following analysis. Figure 4 graphs the number of clusters discovered for each of the personomies. On average 15 clusters are discovered in each personomy.
We believe that the use of multiple sets of tags in user pro¯les should give a more accurate representation of the interests of the users. Therefore we try to evaluate our proposed method by asking the following question: are the sets of tags accurate descriptions of the clusters of bookmarks from which they are extracted? If this is the case, then the user pro¯les should accurately represent the interests of the users. In the following we present the evaluations which
Our question concerns with the issue of whether the sets of
tags in the user pro¯le are accurate descriptions of the
bookmarks in the clusters. An appropriate method of evaluation
is to approach this question from an information retrieval
perspective. Given the signature of a cluster as a query,
can we retrieve all the bookmarks within that cluster and
avoid obtaining bookmarks in other clusters which are
irrelevant? In addition, how many tags should be included in
the signature in order to accurately described a cluster? To
answer such questions, we will employ the measures of
precision and recall [
Precision and recall are two widely used measures for evaluating performance of information retrieval. Precision measures the fraction of documents in the retrieved set which are relevant to the query, while recall measures the fraction of relevant documents that the system is able to retrieve.
To employ the precision-recall measures, we treat the signatures of the clusters as queries, and use them to retrieve bookmarks by comparing the tags assigned to them to those in the queries. As for the representation of tags, we employ a vector space model of information retrieval. In other words, for each personomy, we construct a term vector ~e = (e1; e2; :::; en) for each bookmark, with ei = 1 if the bookmark is assigned the ith tag, and ei = 0 otherwise. Similarly, the signature of a cluster is converted into a query in the form of a term vector q~. The retrieval process is carried out by calculating the cosine similarity between the query vector and the bookmark vectors:
Sim(q~; ~e) =
q~ ¢ ~e
jq~jj~ej
Those with similarity higher than a certain threshold t will
be retrieved (0 · t · 1). For a cluster c, let the set of
bookmarks in the cluster be Dc, and the set of bookmarks
retrieved by the signature of the cluster be Dx. The
precision and recall of the system on c are de¯ned as follows.
In addition, we also consider the F1 measure [
P recision(c) =
Recall(c) =
F1(c) = jDx \ Dcj
jDxj jDx \ Dcj
jDcj 2 £ P recision(c) £ Recall(c)
P recision(c) + Recall(c)
We calculated the three measures for the user pro¯les generated from the 1,000 selected personomies. We control two parameters in our evaluation, one is the value of f , the percentage of bookmarks above which a tag is assigned to in a cluster for it to be included in the signature, and the value of t, the threshold of cosine similarity. The results are presented in Figure 5.
Figure 5(a) shows that for most values of similarity threshold precision attains maximum for f in the range from 0:1 to 0:4, and thereafter it continues to decrease as f increases. The result suggests that if only the most common tags are included in the signatures, they will become less representative as summaries of the clusters. This is probably due to the fact that the most common tags are usually too general (4) (5) (6) (7) (a) Precision
(b) Recall (c) F1 measure and a query constructed from these tags will tend to retrieve bookmarks from other clusters as well which are related to a di®erent sub-topic under the common tags. On the other hand, when one includes all the tags which appear in a cluster (with f = 0%), the signature will include too many tags such that it will not be similar to any of the signatures of the bookmarks, leading again to a low precision.
As for recall, we observe some di®erences for di®erent values of similarity threshold. For small values of t (from 0.0 to 0.3), recall continues to decrease as f increases. However, for larger values of t (from 0.4 to 1.0), recall ¯rst increases and then decreases as t increases. This is probably due to the reason that when the similarity threshold is low, the number of tags in the cluster signature is less important as most of the bookmarks will be retrieved even if their similarity with the query is small. As f increases, fewer tags are included in the signature and therefore it becomes more di±cult to retrieve relevant bookmarks. On the other hand, when t becomes higher, signatures which include all the tags in a cluster or include only the most common tags are very dissimilar to any of the bookmarks in the cluster, therefore recall attains maximum somewhere between the two extremes.
For common values of similarity threshold between t = 0:3 to t = 0:5, precision and recall attain maximum for values of f between 0:1 and 0:2, with precision over 0:8 and recalls over 0:7. F1 measures also attain maximum around these values of t and f . This suggests that it is better to include more tags in a cluster signature so as to make it speci¯c enough for representing the topic of the cluster (and thus the interest of the user represented by the cluster). Given these results, we conclude that by choosing a suitable value of f the tags extracted do constitute good descriptions of the bookmarks within the clusters. 5.2
Our proposed algorithm provides a new way for constructing better user pro¯les based on the data available from collaborative tagging. There are a number of areas in which such algorithms can be applied to. We brie°y discuss two of them in this section.
Firstly, as the user pro¯les provide a summary of the different interests of the users, it can be readily used to facilitate the management and organization of personal Web resources. For example, the sets of tags representing the clusters of bookmarks can be used to facilitate navigation and retrieval of a user's own bookmarks in del.icio.us. This would be much more e±cient than navigating through the bookmarks by a single tag.
In addition, the user pro¯les can also be used to support Web page recommendation systems. Currently, del.icio.us provides various methods which allow users to keep track of new bookmarks which they may ¯nd interesting, such as subscribing to the RSS feed of a tag, or adding a user of similar interests to one's network. However, there have been no mechanisms which directly recommend interesting bookmarks to the users. With the user pro¯les constructed by our proposed method, recommendation systems will have a better understanding of the interests of the users, and be able to recommend more speci¯c bookmarks to users by targeting a particular interest of the users.
User pro¯le representation and construction has been a
key research area in the context of personal information
agents and recommendation systems. The representation
of user pro¯les concerns with how user interests and
preferences are modelled in a structured way. Probably the
simplest form of user pro¯le is a term vector indicating which
terms are interested by the user. The weights in the
vector is usually determined by the tf-idf weighting scheme as
terms are extracted from documents interested by the user or
obtained by observing user behaviour [
On the other hand, since the rise in popularity of
collaborative tagging systems, some studies have also focused on
generating user pro¯les from folksonomies. For example, in
[
The emergence of collaborative tagging systems provide valuable sources of information for understanding user interests and constructing better user pro¯les. In this paper, we investigated the characteristics of personomies extracted from folksonomies, and observed that the majority of users possess a wide range of interests, which cannot be modelled by simple methods such as a single set of tags. A novel method for constructing user pro¯les which take into account the diversity of interests of the users is proposed. We also evaluated the user pro¯les by looking at whether they provide a good summary of the bookmarks of the users.
This research work provides insight into how user pro¯les of multiple interests can be constructed based on the data collected from a folksonomy. From this point, we plan to carry out further research work in two main directions. Firstly, we will further investigate how the proposed method can be improved. In our study, a user pro¯les constructed treats every cluster of bookmarks and its signature as corresponding to a distinctive interest of the user. However, it may be true that two interests are related and are only subtopics of a more general area. We will investigate if the introduction of a hierarchical structure is desirable. Secondly, we will attempt to evaluate our proposed method by applying the user pro¯les on applications such as Web page recommendation or personal resource management. We hope this research will ultimately deliver useful algorithms and applications which utilise the power of user-contributed metadata in collaborative tagging systems.