《电子商务 E-business》阅读文献：Categorising social tags to improve folksonomy-based recommendations

Web Semantics: Science, Services and Agents on the world wide web 9(2011)1-15 Contents lists available at Science Direct Web Semantics: Science, Services and agents on the world wide web ELSEVIER journalhomepagewww.elsevier.com/locate/websem Categorising social tags to improve folksonomy-based recommendations Ivan Cantadora, C, *, ioannis Konstas D, Joemon M. Jose adria, Calle francisco Tomas y valiente. 11. 28049 Madrid, Spain b School of Informatics, University of Edinburgh, EH8 9AB Edinburgh, United Ki Department of Computing Science, University of Glasgow, G12 8QQ Glasgow, United Kingdom ARTICLE INFO A BSTRACT In social tagging systems, users have different purposes when they annotate items. Tags not only depict the content of the annotated items. for example by listing the objects that appear in a photo, or express eceived in revised form 11 October 2010 ccepted 11 October 2010 ontextual information about the items, for example by providing the location or the time in which a Available online 20 october 2010 photo was taken, but also describe subjective qualities and opinions about the items, or can be related to rganisational aspects, such as self-references and personal tasks Current folksonomy-based search and recommendation models exploit the social as a whole to retrieve those items relevant to a tag-based query or user profile, and do not take i aeration the purposes of tags. We hypothesise that a significant percentage of tags are noisy for trieval and believe that the distinction of the personal intentions underlying the tags may be the accuracy of search and recommendation processes. W3C Linking Open Data We present a mechanism to automatically filter and classify raw tags in a set of purpose-oriented cat egories. Our approach finds the underlying meanings( ts ) of the tags, mapping them to semantic entities belonging to external knowledge bases, namely WordNet and wikipedia, through the exploita tion of ontologies created within the w3C Linking Open Data initiative. The obtained concepts are then transformed into semantic classes that can be uniquely assigned to content- and context-based cate- gories. The identification of subjective and organisational tags is based on natural language processing heuristics a. We collected a representative dataset from Flickr social tagging system, and conducted an empirical study to categorise real tagging data, and eval her the resultant tags categories really ben- efit a recommendation model using the rand with Restarts method. The results show that content-and context-based tags are considered to subjective and organisational tags, achieving equivalent performance to using the whole tag d wu eror o O 2010 Elsevier B V. All rights reserved Flickr, 'audio tracks in Last. m, video clips in YouTube, and Web documents in Delicious, 4 among others. a user can usually create (upload) items, and annotate them with tags he considers appro- priate. In some folksonomies, the user can also tag items he did not During the last few years, we have been witnessing an unex- create pected success and increasing popularisation of social tagging The main advantage of folksonomies is that users are not systems. In these systems, users create or upload content(items), requested to rely on a priori agreed knowledge structure or shared annotate it with freely chosen words(tags), and share it with other vocabulary and thus are not imposed any constraint in the tag Isers. The whole set of tags constitutes an unstructured knowl- ging process and information management. Nevertheless, this issue edge classification scheme that is commonly known as folksonomy implies a number of limitations on the content retrieval mecha- [32]. This implicit classification is then used to search and recom- nisms. Social tags may explicitly describe the content of an item, e. g mend items. The nature of tagged items is manifold: photos in by listing physical objects that are shown in a photo or a video, or Flickr-photosharinghttp://www.flickr.com. Tel:+34914972358;fax:+34914972235. E-mail address: ivan. cantador@uames(l. Cantador) 4Delicious-socialbookmarkinghttp://delicious.com. J-8268S-see front matter o 2010 Elsevier B V. All rights reserved

Web Semantics: Science, Services and Agents on the World Wide Web 9 (2011) 1–15 Contents lists available at ScienceDirect Web Semantics: Science, Services and Agents on the World Wide Web journal homepage: www.elsevier.com/locate/websem Categorising social tags to improve folksonomy-based recommendations Iván Cantador a,c,∗, Ioannis Konstas b,c, Joemon M. Josec a Departamento de Ingeniería Informática, Universidad Autónoma de Madrid, Calle Francisco Tomás y Valiente, 11, 28049 Madrid, Spain b School of Informatics, University of Edinburgh, EH8 9AB Edinburgh, United Kingdom c Department of Computing Science, University of Glasgow, G12 8QQ Glasgow, United Kingdom article info Article history: Received 27 July 2010 Received in revised form 11 October 2010 Accepted 11 October 2010 Available online 20 October 2010 Keywords: Social tagging Recommender systems Ontologies Semantic Web W3C Linking Open Data abstract In social tagging systems, users have different purposes when they annotate items. Tags not only depict the content of the annotated items, for example by listing the objects that appear in a photo, or express contextual information about the items, for example by providing the location or the time in which a photo was taken, but also describe subjective qualities and opinions about the items, or can be related to organisational aspects, such as self-references and personal tasks. Current folksonomy-based search and recommendation models exploit the social tag space as a whole to retrieve those items relevant to a tag-based query or user profile, and do not take into consideration the purposes of tags. We hypothesise that a significant percentage of tags are noisy for content retrieval, and believe that the distinction of the personal intentions underlying the tags may be beneficial to improve the accuracy of search and recommendation processes. We present a mechanism to automatically filter and classify raw tags in a set of purpose-oriented cat￾egories. Our approach finds the underlying meanings (concepts) of the tags, mapping them to semantic entities belonging to external knowledge bases, namely WordNet and Wikipedia, through the exploita￾tion of ontologies created within the W3C Linking Open Data initiative. The obtained concepts are then transformed into semantic classes that can be uniquely assigned to content- and context-based cate￾gories. The identification of subjective and organisational tags is based on natural language processing heuristics. We collected a representative dataset from Flickr social tagging system, and conducted an empirical study to categorise real tagging data, and evaluate whether the resultant tags categories really ben￾efit a recommendation model using the Random Walk with Restarts method. The results show that content- and context-based tags are considered superior to subjective and organisational tags, achieving equivalent performance to using the whole tag space. © 2010 Elsevier B.V. All rights reserved. 1. Introduction 1.1. Motivation During the last few years, we have been witnessing an unex￾pected success and increasing popularisation of social tagging systems. In these systems, users create or upload content (items), annotate it with freely chosen words (tags), and share it with other users. The whole set of tags constitutes an unstructured knowl￾edge classification scheme that is commonly known as folksonomy [32]. This implicit classification is then used to search and recom￾mend items. The nature of tagged items is manifold: photos in ∗ Corresponding author at: Departamento de Ingeniería Informática, Universidad Autónoma de Madrid, Calle Francisco Tomás y Valiente, 11, 28049 Madrid, Spain. Tel.: +34 91 497 2358; fax: +34 91 497 2235. E-mail address: ivan.cantador@uam.es (I. Cantador). Flickr,1 audio tracks in Last.fm,2 video clips in YouTube,3 and Web documents in Delicious,4 among others. A user can usually create (upload) items, and annotate them with tags he considers appro￾priate. In some folksonomies, the user can also tag items he did not create. The main advantage of folksonomies is that users are not requested to rely on a priori agreed knowledge structure or shared vocabulary, and thus are not imposed any constraint in the tag￾ging process and information management. Nevertheless, this issue implies a number of limitations on the content retrieval mecha￾nisms. Social tags may explicitly describe the content of an item, e.g. by listing physical objects that are shown in a photo or a video, or 1 Flickr – Photo sharing, http://www.flickr.com. 2 Last.fm – Personal online radio, http://www.last.fm. 3 YouTube – Video sharing, http://www.youtube.com. 4 Delicious – Social bookmarking, http://delicious.com. 1570-8268/$ – see front matter © 2010 Elsevier B.V. All rights reserved. doi:10.1016/j.websem.2010.10.001

L Contador et al /Web Semantics: Science, Services and Agents on the World Wide Web 9(2011)1-15 by giving keywords that appear in a Web document or a song lyric. multi-domain tagging system where photos are freely annotated They may also provide contextual information about the annotated by their owners. the results show there are certain tag cate- item, e.g. by identifying the place a photo was taken, or the date gories that are superior to others in terms of recommendat a video was recorded Furthermore, they may express subjective performance, and even equivalent to that obtained when using opinions and qualities(nice picture, rock music, dark movie the whole tag space. scene, incomprehensible text), or self-references and personal We have collected a dataset from Flickr system, which we have tasks(my wife, to read, work). This suggests that users have dif- made available to the research community ferent intentions when tagging, and not all the tags available in a folksonomy are related with the content of the annotated items 3]. 1.3. Structure of the engines do not take into account the above distinction of tags, and run their content retrieval algorithms in the entire tag space. The The rest of the paper is organised as follows. Section 2 describes problem is that although useful subjective and organisational tags related works that have motivated our research. Section 3 presents e for the purposes (intentions)of an individual, still they m. an overview of our approach to automatically categorise social fail to be of benefit when recommending items to other users. As a tags based on their purpose. Section 4 explains in more detail result, mixing these with the rest content- and context-based tag the approach, describing how the semantic concepts underlying social tags are identified, and how they are mapped to a set of mendations. We hypothesise that distinguishing and considering predefined purpose-oriented categories. Section 5 describes the purpose-oriented categories of tags could be extremely valuable to folksonomy-based recommendation model with which we have improve the accuracy of recommendation approaches. Hence, the evaluated our tag categorisation proposal. Section 6 presents the corroboration of this assumption represents the main challenge to conducted experiments, and Section 7 provides a discussion of the address in the work presented herein. obtained results. Finally, Section 8 contains conclusions and future In order to achieve such tag categorisation, we first have to research lines understand the meaning of each social tag. For example, to deter- mine that kilt can be categorised as a"content-based"tag, it has to be identified that a kilt is a Scottish piece of cloth, i.e. a"phys- 2. Related work ical entity". Similarly, to categorise glasgow as a"context-based tag, it has to be identified that glasgow is a city in Scotland, ie a 2.1. Categorisation of social tags location It is our objective to study the role of various tag categori a prior goal in many social tagging systems is to meet the for item recommendation. However, categorising a set of general needs of individual users, e.g. by allowing personal organisation purpose tags is not trivial In this context, we have identified the of items and their subsequent retrieval. Nonetheless, social tags following research questions should help other people to browse and find items. Furthermore, being a mechanism of community-based item description, they RQ1: Is it possible to find out the underlying meanings of social should also facilitate information sharing and discovery(recom tags in a general way? mendation). Marlow et al. [22], and Ames and Naaman [3 discuss We should (1)identify the meanings of social tags indepen- an exhaustive list of incentives expressing the range of potential dently of the domains covered by the folksonomies they belong motivations that influence tagging. Among them, content man- to: and (2) be aware of contemporary terminology that continu- agement and retrieval are shown as two of the most important usly appears in our daily lives(web 2.0, podcast, diy). incentives to tag resources. Our work is based on this observation RQ2: Is it possible to automatically categorise social tags based and aims to identify which social tags are more useful for content on their intention? retrieval and recommendation The transformation of semantic concepts into purpose- To provide such functionalities, it is not obvious how social tags oriented categories could be done by exploiting external can be best exploited Suchanek et al. [35 ] show that user-generated knowledge bases such as thesauri, taxonomies and ontologies. tags present significant semantic noise more than terms extracted RQ3: Is a purpose-oriented categorisation of social tags useful from Web page contents or search queries. When tagging, peo- for folksonomy-based recommendation strategies? ple not only introduce misspellings(barcelona, barclona), and To validate the utility of the purpose-oriented categories, these use different synonyms(car, automobile), acronyms(nyc, new should be evaluated in a real folksonomy-based recommender york city)and logic derivations(blog, blogs, blogging system. for a given concept [36], but also include tags that express per sonal assessments(funny, to print), or even are unintelligible to 1. 2. Contribution another person(####a)35]. We deal with these issues making us of a tag processing and filtering approaches presented in a previous In this work, we address the research questions listed above, works [36,37), and mapping the resultant tags to semantic concepts nd make the following contributions described in external knowledge bases(KB). similarly to 9]. where social tags are linked to ontology classes and instances We have developed a mechanism that automatically processes The purposes of tagging and consequently the types of social structured knowledge bases identify which are the social tags relevant for knowle e siming to and maps social tags to semantic concepts depicted in external tags are manifold. Recent works have analysed this fact, aiming to Exploiting the semantic relations provided by the above ment and information retrieval. Apart from describing the nowledge structures, we have designed a novel strategy to auto- of the items, social tags may represent contextual inform m matically infer the semantic classes of a given concept that allow subjective opinions and qualities [15, 30], or self-presentation and determining the intension of the corresponding social tag. organisation aspects 41]. We consider these purpose-oriented tag We have conducted an empirical study to evaluate the effect categories, and propose a more fine-grained categorisation within of various tag categories in photo recommendation. The experi- them, in order to study which types of tags are useful for content ments have been performed with a dataset obtained from Flickr, a retrieval tasks

2 I. Cantador et al. / Web Semantics: Science, Services and Agents on the World Wide Web 9 (2011) 1–15 by giving keywords that appear in a Web document or a song lyric. They may also provide contextual information about the annotated item, e.g. by identifying the place a photo was taken, or the date a video was recorded. Furthermore, they may express subjective opinions and qualities (nice picture, rock music, dark movie scene, incomprehensible text), or self-references and personal tasks (my wife, to read, work). This suggests that users have dif￾ferent intentions when tagging, and not all the tags available in a folksonomy are related with the content of the annotated items [3]. Current folksonomy-based search and recommendation engines do not take into account the above distinction of tags, and run their content retrieval algorithms in the entire tag space. The problem is that although useful subjective and organisational tags are for the purposes (intentions) of an individual, still they may fail to be of benefit when recommending items to other users. As a result, mixing these with the rest content- and context-based tags may not add or even deteriorate the overall quality of the recom￾mendations. We hypothesise that distinguishing and considering purpose-oriented categories of tags could be extremely valuable to improve the accuracy of recommendation approaches. Hence, the corroboration of this assumption represents the main challenge to address in the work presented herein. In order to achieve such tag categorisation, we first have to understand the meaning of each social tag. For example, to deter￾mine that kilt can be categorised as a “content-based” tag, it has to be identified that a kilt is a Scottish piece of cloth, i.e. a “phys￾ical entity”. Similarly, to categorise glasgow as a “context-based” tag, it has to be identified that Glasgow is a city in Scotland, i.e. a “location”. It is our objective to study the role of various tag categories for item recommendation. However, categorising a set of general purpose tags is not trivial. In this context, we have identified the following research questions: • RQ1: Is it possible to find out the underlyingmeanings of social tags in a general way? We should (1) identify the meanings of social tags indepen￾dently of the domains covered by the folksonomies they belong to; and (2) be aware of contemporary terminology that continu￾ously appears in our daily lives (web 2.0, podcast, diy). • RQ2: Is it possible to automatically categorise social tags based on their intention? The transformation of semantic concepts into purpose￾oriented categories could be done by exploiting external knowledge bases such as thesauri, taxonomies and ontologies. • RQ3: Is a purpose-oriented categorisation of social tags useful for folksonomy-based recommendation strategies? To validate the utility of the purpose-oriented categories, these should be evaluated in a real folksonomy-based recommender system. 1.2. Contributions In this work, we address the research questions listed above, and make the following contributions: • We have developed a mechanism that automatically processes and maps social tags to semantic concepts depicted in external structured knowledge bases. • Exploiting the semantic relations provided by the above knowledge structures, we have designed a novel strategy to auto￾matically infer the semantic classes of a given concept that allow determining the intension of the corresponding social tag. • We have conducted an empirical study to evaluate the effect of various tag categories in photo recommendation. The experi￾ments have been performed with a dataset obtained from Flickr, a multi-domain tagging system where photos are freely annotated by their owners. The results show there are certain tag cate￾gories that are superior to others in terms of recommendation performance, and even equivalent to that obtained when using the whole tag space. • We have collected a dataset from Flickr system, which we have made available to the research community. 1.3. Structure of the paper The rest of the paper is organised as follows. Section 2 describes related works that have motivated our research. Section 3 presents an overview of our approach to automatically categorise social tags based on their purpose. Section 4 explains in more detail the approach, describing how the semantic concepts underlying social tags are identified, and how they are mapped to a set of predefined purpose-oriented categories. Section 5 describes the folksonomy-based recommendation model with which we have evaluated our tag categorisation proposal. Section 6 presents the conducted experiments, and Section 7 provides a discussion of the obtained results. Finally, Section 8 contains conclusions and future research lines. 2. Related work 2.1. Categorisation of social tags A prior goal in many social tagging systems is to meet the needs of individual users, e.g. by allowing personal organisation of items and their subsequent retrieval. Nonetheless, social tags should help other people to browse and find items. Furthermore, being a mechanism of community-based item description, they should also facilitate information sharing and discovery (recom￾mendation). Marlow et al. [22], and Ames and Naaman [3] discuss an exhaustive list of incentives expressing the range of potential motivations that influence tagging. Among them, content man￾agement and retrieval are shown as two of the most important incentives to tag resources. Our work is based on this observation, and aims to identify which social tags are more useful for content retrieval and recommendation. To provide such functionalities, it is not obvious how social tags can be best exploited. Suchanek et al.[35] show that user-generated tags present significant semantic noise more than terms extracted from Web page contents or search queries. When tagging, peo￾ple not only introduce misspellings (barcelona, barclona), and use different synonyms (car, automobile), acronyms (nyc, new york city) and morphologic derivations (blog, blogs, blogging) for a given concept [36], but also include tags that express per￾sonal assessments (funny, to print), or even are unintelligible to another person (#####) [35]. We deal with these issues making use of a tag processing and filtering approaches presented in a previous works [36,37], and mapping the resultant tags to semantic concepts described in external knowledge bases (KB), similarly to [9], where social tags are linked to ontology classes and instances. The purposes of tagging and consequently the types of social tags are manifold. Recent works have analysed this fact, aiming to identify which are the social tags relevant for knowledge manage￾ment and information retrieval. Apart from describing the content of the items, social tags may represent contextual information [3], subjective opinions and qualities [15,30], or self-presentation and organisation aspects [41]. We consider these purpose-oriented tag categories, and propose a more fine-grained categorisation within them, in order to study which types of tags are useful for content retrieval tasks

L Contador et al/Web Semantics: Science, Services and Agents on the World wide Web 9(2011)1-15 Motivated by the previous works, Bischoff et al. [7] manually Au Yeung et al. [6] describe a strategy that clusters the items lassify a number of tag collections obtained from different social tagged by the users. In the item-tag space, given a network of tagging systems( Flickr, Delicious, Last. fm)in several tag types, and items, a graph-based clustering algorithm to obtain sets of related study the distributions of tags assigned to each type, analysing items is applied. As the different clusters should contain items their usage implications on search tasks. The obtained results pro- that are related to similar topics, a cluster can be considered as vide insight into the use of different kinds of tags for improving corresponding to one of the interests of the user. Moreover, the search. Here we go a step beyond attempting to categorise the tags experiments presented in the paper show that the obtained groups utomatically. In this case, the evaluation of the tag categorise- of tags and items seem to correspond to the different meanings tion is assessed with a recommendation model [17] which does of ambiguous tags. In this work, we also use a graph-based algo- not depend on a specific domain. In this paper, we have conducted rithm on the item-tag space In our case, using a Random Walk s with a dataset obtained from flickr. w gy we aim to identify related tags and items relevant for the freely tagged by the owners in a multi-domain scenario. To achieve such tag categorisation, the meanings of social tags Similarly, Gemmell et al. explore in several works [14,31 ave to be found beforehand. We propose to map them to semantic strategies that cluster the entire space of tags to obtain sets of ncepts described in external KBs, such as thesauri and ontologies. (semantically)related tags. These clusters may represent coherent Halpin et al. [16] show that tagging distributions tend to stabili topic areas. By associating a user's interest to a particular cluster. into power law distributions, which is an essential aspect of what the user's interests in the topic are surmised. As discussed in the light be user consensus around the categorisation of information last section of the paper this type of clustering techniques could be riven by tagging. The authors state that it is quite plausible that incorporated into our approach in order to enhance the automatic folksonomies and ontologies are fundamentally compatible. We categorisation of ambiguous social tags, according to the context of follow this principle, and attempt to integrate social tags into YAGo the user profile in which a given tag appears. [34]. a large ontology that covers WordNet [24 and a significant Instead of implicit clusters, other personalisation and recom part of Wikipedia.5 mendation approaches aim to exploit explicit, and more structured Constructing and linking folksonomies with structured seman- representations of folksonomies. Quintarelli et al. [ 29] propose KBs is indeed a problem that has attracted much attention a personal multi-facet categorisation of tags, which allows the recently [28]. Mika [23 is recognised as one of the first authors to exploitation of taxonomic relations to enhance content retrieval tend the traditional bipartite resource-concept model of ontolo- In a series of previous works [8,9, 36] we have investigated rec- es with the social dimension. He presents a graph based approach ommendation approaches that make use of ontology-based user to construct a network of related tags, projected from either a profiles. Social tags are automatically transformed into ontology Iser-tag or resource-tag association graph. Applying clustering concepts(classes and instances)using semantic knowledge bases tags, and using their co-occurrence statistics, he like WordNet and Wikipedia. Arbitrary ontology relations between produces conceptual hierarchies. Specia and Motta[33] present a these concepts are exploited to expand the user profiles, and pe combination of pre-processing strategies and statistical techniques sonalise search and recom tion results. In this work, we together with knowledge provided by ontologies available on the attempt to map social tags to semantic concepts. As explained in Semantic Web to generate clusters of highly related tags that co subsequent sections, in this case, we propose to use YAGO onto respond to ontology concepts. As explained in subsequent sections, ogy, aiming to join and contribute to the w3C Linking Open Data we shall also make use of tag processing and filtering techniques, initiative similar to those presented in 33. Angeletou [4]proposes a seman- Recent works have focused on exploiting folksonomies tic enrichment of folksonomies by exploiting online ontologies, as sources of semantic information, integrating them with nesauri and other knowledge sources to make explicit the seman- content-based and collaborative filtering(CF)recommendation tic relations between social tags Instead of inferring such semantic approaches. relations between tags, we use those explicitly defined in YAGO De Gemmis et al. [11 present a hybrid strategy that learns the This is enough for our approach since our goal is to categorise the rofile of the user from both static content and tags associated with tags, and we only have to exploit hierarchical relations between items rated by him, instead of relying on tags only the authors pro- pose to include in the user profile not only his personal tags, but also the tags adopted by other users who rated the same items as him. Since the main problem lies in the fact that tags are freely 2. 2. Folksonomy-based recommender systems chosen by users, and their actual meaning is usually not very clear they suggest to semantically interpreting tags by means of Word- Collaborative tagging systems allow a user to search for the Net. Our tag categorisation also follows this idea, but extends the content that he has tagged using a personal vocabulary As users use of wordNet to wikipedia, allowing the consideration of social with similar interests tend to have a shared vocabulary tags cre- tags related to proper nouns and contemporary terms not available ted by one user may be useful to others, particularly those with in a dictionary such as WordNet. similar interests this is in Tso-Sutter et al. 38 describe a generic method that allows tags tems. In these systems, a user does not usually declare explicitly to be incorporated into standard heuristic-based CF algorithms his information needs(e.g, by means of a keyword-based query). such as user-and item-based CF, by reducing the three-dimensional In contrast, he is presented with items that may be interested for (user, item, tag) correlations to three two-dimensional correla him according to his profile(content-based approaches), or to the tions, and then applying a fusion method to re-associate these profiles of"similar"people(collaborative filtering approaches ) The correlations. The integration of folksonomy information into CF ader is referenced to [1 for an overview of the state of the art in is also studied by Zhen et al. [44 In this case, the authors pro- recommender systems. In the following, we focus our attention on pose to use the model-based CF algorithm based on probabilistic recommendation approaches that exploit folksonomy information. matrix factorization. Differently to these approaches, as explained in the paper, our tag-based recommendation model follows the CF paradigm by means of applying Random Walk algorithm on the global graph formed by users, items, tags and their explicit

I. Cantador et al. / Web Semantics: Science, Services and Agents on the World Wide Web 9 (2011) 1–15 3 Motivated by the previous works, Bischoff et al. [7] manually classify a number of tag collections obtained from different social tagging systems (Flickr, Delicious, Last.fm) in several tag types, and study the distributions of tags assigned to each type, analysing their usage implications on search tasks. The obtained results pro￾vide insight into the use of different kinds of tags for improving search. Here we go a step beyond attempting to categorise the tags automatically. In this case, the evaluation of the tag categorisa￾tion is assessed with a recommendation model [17], which does not depend on a specific domain. In this paper, we have conducted experiments with a dataset obtained from Flickr, where photos are freely tagged by the owners in a multi-domain scenario. To achieve such tag categorisation, the meanings of social tags have to be found beforehand. We propose to map them to semantic concepts described in external KBs, such as thesauri and ontologies. Halpin et al. [16] show that tagging distributions tend to stabilise into power law distributions, which is an essential aspect of what might be user consensus around the categorisation of information driven by tagging. The authors state that it is quite plausible that folksonomies and ontologies are fundamentally compatible. We follow this principle, and attempt to integrate social tags into YAGO [34], a large ontology that covers WordNet [24] and a significant part of Wikipedia.5 Constructing and linking folksonomies with structured seman￾tic KBs is indeed a problem that has attracted much attention recently [28]. Mika [23] is recognised as one of the first authors to extend the traditional bipartite resource-concept model of ontolo￾gies with the social dimension. He presents a graph based approach to construct a network of related tags, projected from either a user-tag or resource-tag association graph. Applying clustering techniques to tags, and using their co-occurrence statistics, he produces conceptual hierarchies. Specia and Motta [33] present a combination of pre-processing strategies and statistical techniques together with knowledge provided by ontologies available on the Semantic Web to generate clusters of highly related tags that cor￾respond to ontology concepts. As explained in subsequent sections, we shall also make use of tag processing and filtering techniques, similar to those presented in [33]. Angeletou [4] proposes a seman￾tic enrichment of folksonomies by exploiting online ontologies, thesauri and other knowledge sources to make explicit the seman￾tic relations between social tags. Instead of inferring such semantic relations between tags, we use those explicitly defined in YAGO. This is enough for our approach since our goal is to categorise the tags, and we only have to exploit hierarchical relations between them. 2.2. Folksonomy-based recommender systems Collaborative tagging systems allow a user to search for the content that he has tagged using a personal vocabulary. As users with similar interests tend to have a shared vocabulary, tags cre￾ated by one user may be useful to others, particularly those with similar interests. This is in fact the essence of recommender sys￾tems. In these systems, a user does not usually declare explicitly his information needs (e.g., by means of a keyword-based query). In contrast, he is presented with items that may be interested for him according to his profile (content-based approaches), or to the profiles of “similar” people (collaborative filtering approaches). The reader is referenced to [1] for an overview of the state of the art in recommender systems. In the following, we focus our attention on recommendation approaches that exploit folksonomy information. 5 Wikipedia encyclopaedia, http://wikipedia.org. Au Yeung et al. [6] describe a strategy that clusters the items tagged by the users. In the item-tag space, given a network of items, a graph-based clustering algorithm to obtain sets of related items is applied. As the different clusters should contain items that are related to similar topics, a cluster can be considered as corresponding to one of the interests of the user. Moreover, the experiments presented in the paper show that the obtained groups of tags and items seem to correspond to the different meanings of ambiguous tags. In this work, we also use a graph-based algo￾rithm on the item-tag space. In our case, using a Random Walk strategy we aim to identify related tags and items relevant for the user. Similarly, Gemmell et al. explore in several works [14,31] strategies that cluster the entire space of tags to obtain sets of (semantically) related tags. These clusters may represent coherent topic areas. By associating a user’s interest to a particular cluster, the user’s interests in the topic are surmised. As discussed in the last section of the paper, this type of clustering techniques could be incorporated into our approach in order to enhance the automatic categorisation of ambiguous social tags, according to the context of the user profile in which a given tag appears. Instead of implicit clusters, other personalisation and recom￾mendation approaches aim to exploit explicit, and more structured representations of folksonomies. Quintarelli et al. [29] propose a personal multi-facet categorisation of tags, which allows the exploitation of taxonomic relations to enhance content retrieval. In a series of previous works [8,9,36], we have investigated rec￾ommendation approaches that make use of ontology-based user profiles. Social tags are automatically transformed into ontology concepts (classes and instances) using semantic knowledge bases like WordNet and Wikipedia. Arbitrary ontology relations between these concepts are exploited to expand the user profiles, and per￾sonalise search and recommendation results. In this work, we also attempt to map social tags to semantic concepts. As explained in subsequent sections, in this case, we propose to use YAGO ontol￾ogy, aiming to join and contribute to the W3C Linking Open Data initiative. Recent works have focused on exploiting folksonomies as sources of semantic information, integrating them with content-based and collaborative filtering (CF) recommendation approaches. De Gemmis et al. [11] present a hybrid strategy that learns the profile of the user from both static content and tags associated with items rated by him, instead of relying on tags only. The authors pro￾pose to include in the user profile not only his personal tags, but also the tags adopted by other users who rated the same items as him. Since the main problem lies in the fact that tags are freely chosen by users, and their actual meaning is usually not very clear, they suggest to semantically interpreting tags by means of Word￾Net. Our tag categorisation also follows this idea, but extends the use of WordNet to Wikipedia, allowing the consideration of social tags related to proper nouns and contemporary terms not available in a dictionary such as WordNet. Tso-Sutter et al. [38] describe a generic method that allows tags to be incorporated into standard heuristic-based CF algorithms, such as user- and item-based CF, by reducing the three-dimensional (user, item, tag) correlations to three two-dimensional correla￾tions, and then applying a fusion method to re-associate these correlations. The integration of folksonomy information into CF is also studied by Zhen et al. [44]. In this case, the authors pro￾pose to use the model-based CF algorithm based on probabilistic matrix factorization. Differently to these approaches, as explained in the paper, our tag-based recommendation model follows the CF paradigm by means of applying Random Walk algorithm on the global graph formed by users, items, tags and their explicit relations

L Cantador et al Web Semantics: Science, Services and Agents on the world Wide Web 9(2011)1-15 Table 1 omparison of purpose-based categorisation of social tags Our categories Xu et al. [411 Sen et al. [301 Golder a d Huberman[15 Bischoff et al. [7 Attribute Factual Who ows Contextbased Context-based Refining other categories live Personal Self reference Self reference Adapted from [7]- y content-based m1()则如? category natural cc口 part-of-speech Fig. 1. Purpose-oriented categorisation of social tags 3. Overview of the approach 2a and 3a in the figure). In this case, we assume a semantic concept corresponds to a physical or non-physical entity related to con Our goal is to automatically categorise social tags based on their tent or contextual information of an item: objects, living entities. tention, considering the following four main categories locations, time references, etc On the other hand if the tag is not found in the available KBs, we employ Natural Language Process- Content-based Social tags that describe the content of the items, ing(NLP)techniques and categorisation heuristics to determine such as the objects and living things(animals, plants)that appear whether the tag can be assigned to subjective or organisational in a photo or video, or are mentioned in a text document or a categories(stages 1b, 2b and 3b in the figure). In the following. song lyric. Some examples of tags belonging to this category e briefly describe the above cases. More details are given in vehicle, dog and t Section 4 Context-based Social tags that provide contextual information about the items, such as the place where a photo was taken, ti date or period of time when a video was recorded, etc. Examples 3. 1. Content-based and contex of this kind of tags are madrid, mountain, summer and holidays Subjective Social tags that express opinions and qualities of the In principle, social tags belonging to content-and context-based items. Some examples of these tags are happy, sunny and con- categories are nouns denoting physical and non-physical entities whose definition can be found in dictionaries, encyclopaedias or Organisational Social tags that define personal usages and tasks, thesauri. Thus, the first step is to process and map an input tag to a or indicate self-references Examples within this category are look at, scan from print, myself and our best friend. input tag is nyc, which is the acronym for the city of New York, USA. Looking for this term in KBs, we could obtain references to seman- These tag categories are similar to those identified in the liter- tic entities related to that concept. For example, in Wikipedia. New ature.bischoffetal.[7compareseveralcategorisationschemasYorkcityisidentifiedbytheUrlshttpen.wikipedia.org/wiki/nyc Table 1 summarises this comparison, and includes our categorise tion, which fits with previous schemas. et us say the identified concept for nyc is [NewYorkcityl In contrast to previous studies, we attempt to automatically Once we have established the semantic concept underlying determine the most suitable category for a given social tag. Fig. 1 a social tag, and assuming the existence of taxonomic rela of the input tag, we distinguish two different cases. If the tag can relations expanding the concept towards its taxonomic ances- be mapped to a semantic concept of an external KB, then it will be assigned to either content-or context-based categories(stages la, which allows us to later categorise the concept as a content or a context-based tag. In Section 4, we present and justify the considered"reference"concepts. Here, continuing with the 6 In Section 4.2, we explain in detail how a tag is mapped to a semant example, we just mention that the concept [New-York-city] an external KB. At this point, the reader is asked to assume the existence of an al is an instance of the class USA__cities, and that expanding matic mechanism that links a tag with"names"of taxonomy categories, ontology USA- cities we might find out that [NewYorkcity] also belongs lasses or instances etc. available in the KB to the classes New-york_ state_ citites. Cities and locations

4 I. Cantador et al. / Web Semantics: Science, Services and Agents on the World Wide Web 9 (2011) 1–15 Table 1 Comparison of purpose-based categorisation of social tags. Our categories Xu et al. [41] Sen et al. [30] Golder and Huberman [15] Bischoff et al. [7] Content-based Factual What or who is about Topic Content-based Attribute What it is Type Who owns it Author/owner Context-based Context-based Refining other categories Time Location Subjective Subjective Subjective Qualities/characteristics Opinions/qualities Organisational Organisational Personal Task organisation Usage context Self reference Self reference Adapted from [7]. Fig. 1. Purpose-oriented categorisation of social tags. 3. Overview of the approach Our goal is to automatically categorise social tags based on their intention, considering the following four main categories: • Content-based. Social tags that describe the content of the items, such as the objects and living things (animals, plants) that appear in a photo or video, or are mentioned in a text document or a song lyric. Some examples of tags belonging to this category are vehicle, dog and tree. • Context-based. Social tags that provide contextual information about the items, such as the place where a photo was taken, the date or period of time when a video was recorded, etc. Examples of this kind of tags are madrid, mountain, summer and holidays. • Subjective. Social tags that express opinions and qualities of the items. Some examples of these tags are happy, sunny and con￾temporary art. • Organisational. Social tags that define personal usages and tasks, or indicate self-references. Examples within this category are to look at, scan from print, myself and our best friend. These tag categories are similar to those identified in the liter￾ature. Bischoff et al. [7] compare several categorisation schemas. Table 1 summarises this comparison, and includes our categorisa￾tion, which fits with previous schemas. In contrast to previous studies, we attempt to automatically determine the most suitable category for a given social tag. Fig. 1 depicts the whole categorisation process. Depending on the nature of the input tag, we distinguish two different cases. If the tag can be mapped6 to a semantic concept of an external KB, then it will be assigned to either content- or context-based categories (stages 1a, 6 In Section 4.2, we explain in detail how a tag is mapped to a semantic concept of an external KB. At this point, the reader is asked to assume the existence of an auto￾matic mechanism that links a tag with “names” of taxonomy categories, ontology classes or instances, etc. available in the KB. 2a and 3a in the figure). In this case, we assume a semantic concept corresponds to a physical or non-physical entity related to con￾tent or contextual information of an item: objects, living entities, locations, time references, etc. On the other hand, if the tag is not found in the available KBs, we employ Natural Language Process￾ing (NLP) techniques and categorisation heuristics to determine whether the tag can be assigned to subjective or organisational categories (stages 1b, 2b and 3b in the figure). In the following, we briefly describe the above cases. More details are given in Section 4. 3.1. Content-based and context-based categories In principle, social tags belonging to content- and context-based categories are nouns denoting physical and non-physical entities whose definition can be found in dictionaries, encyclopaedias or thesauri. Thus, the first step is to process and map an input tag to a concept existing in a KB (stage 1a in Fig. 1). Let us suppose that the input tag is nyc, which is the acronym for the city of New York, USA. Looking for this term in KBs, we could obtain references to seman￾tic entities related to that concept. For example, in Wikipedia, New York city is identified by the URLshttp://en.wikipedia.org/wiki/NYC and http://en.wikipedia.org/wiki/New York City, among others. Let us say the identified concept for nyc is [New York city]. Once we have established the semantic concept underlying a social tag, and assuming the existence of taxonomic rela￾tions among concepts in the KB, we propose to exploit such relations expanding the concept towards its taxonomic ances￾tors until reaching a “reference” ancestor (stage 2a in Fig. 1), which allows us to later categorise the concept as a content￾or a context-based tag. In Section 4, we present and justify the considered “reference” concepts. Here, continuing with the example, we just mention that the concept [New York city] is an instance of the class USA cities, and that expanding USA cities we might find out that [New York city] also belongs to the classes New York state citites, Cities and Locations

L Contador et al/Web Semantics: Science, Services and Agents on the World wide Web 9(2011)1-15 Table 2 Proposed purpose-oriented categories and semantic subcategories, with examples of real Flickr tags Category Subcategory Flickr tag examples Physical entin food, glue, heart, ice react comb, finger, helicopter, table Living entity cell, clone, life,mushroom L-Animal caterpillar, frog, pigeon, pet Content-based -Person boy,daniel,friend, sister - Plant cactus, cereal flower, tree Non-physical entity cloud, feminism, noise, tennis Organisation bmw, ibm, religion, rolling stones Location california, rome, spain, wedding Context-based Time halloween, march, sixties, winter oh damn, so cute, unto Subjective golden picture, geometric elegance Self-reference i love you, her, missing you Organisational Task time for change, do not want to know Action avoid, hiking, explore page, sit In Wikipedia, this kind of classification is given by its"Wiki 4. Categorisation of social tags categories”:7 In the example, the semantic expansion is stopped at Locations 4.1. Tag categories class. This is a reference concept since it is uniquely associated te he context-based category(stage 3a in Fig. 1). For each of the four purpose-based categories proposed in this entities that can be assigned to those categories. Table 2 shows 3. 2. Subjective and organisational categorie these subcategories and examples of Flickr social tags automatically categorised by our approach a number of categorisation heuristics to determine whether it can ical entities, we do have artefacts and living entities. Living entities The first step is to tokenise the tags, and determine the part of can be split into animals and plants. Persons are considered as ani- be categorised as a subjective or an organisational tag. mals, and similarly, organisations are non-physical entities Related peech( PoS), i.e. noun, verb, adjective, adverb, preposition, etc of to the context of an item, we find location and time entities within each of the obtained tokens(stage 1b in Fig. 1). For example, let the subjective category. we distinguish between personal opinions us suppose that the input tag is to-read. This is tokenised as(to, and qualities. Finally, organisational entities are divided into self- read), and transformed into the tuple (to ). Instead of directly assigning a social tag to a purpose-based cat- Next, we analyse the PoS tuple in order to find a subset of tokens egory, we firstly identify the most suitable subcategory, and then that satisfies one of a set of patterns predefined for each category obtain the corresponding main category We detail this process in In the example, the pattern [+ ] may rep- Sections 4.2 and 4.3 esent a task(stage 2b in Fig. 1) Finally, through a heuristic approach, we assign the found pat- tern to a category(stage 3b in Fig. 1). Continuing with the example, 4.2. Categorising content- and context-based social tags task is assigned to the organisational category. In the next section, we will describe our tag categorisation approach in more mn, he categorisation of content-and context-based tags is based their mapping to semantic concepts described in an external KB. A major requirement imposed on the KB is that it has to pro- vide a classification hierarchy (taxonomy among its concepts. As described in Section 3, given a social tag. we should not only be . wikipedia. org/wiki/ Special/ Categories. able to map it to a semantic concept, but also to determine one of

I. Cantador et al. / Web Semantics: Science, Services and Agents on the World Wide Web 9 (2011) 1–15 5 Table 2 Proposed purpose-oriented categories and semantic subcategories, with examples of real Flickr tags categorisations. Category Subcategory Flickr tag examples Content-based Physical entity food, glue, heart, ice Artefact comb, finger, helicopter, table Living entity cell, clone, life, mushroom Animal caterpillar, frog, pigeon, pet Person boy, daniel, friend, sister Plant cactus, cereal flower, tree Non-physical entity cloud, feminism, noise, tennis Organisation bmw, ibm, religion, rolling stones Context-based Location california, rome, spain, wedding Time halloween, march, sixties, winter Subjective Opinion oh damn, so cute, unforgettable Quality golden picture, geometric elegance Organisational Self-reference i love you, her, missing you Task time for change, do not want to know Action avoid, hiking, explore page, sit In Wikipedia, this kind of classification is given by its “Wiki categories”.7 In the example, the semantic expansion is stopped at Locations class. This is a reference concept since it is uniquely associated to the context-based category (stage 3a in Fig. 1). 3.2. Subjective and organisational categories When a social tag is not a noun, we apply NLP techniques and a number of categorisation heuristics to determine whether it can be categorised as a subjective or an organisational tag. The first step is to tokenise the tags, and determine the part of speech (PoS), i.e. noun, verb, adjective, adverb, preposition, etc., of each of the obtained tokens (stage 1b in Fig. 1). For example, let us suppose that the input tag is to read. This is tokenised as (to, read), and transformed into the tuple (to , read ). Next, we analyse the PoS tuple in order to find a subset of tokens that satisfies one of a set of patterns predefined for each category. In the example, the pattern [ + ] may rep￾resent a task (stage 2b in Fig. 1). Finally, through a heuristic approach, we assign the found pat￾tern to a category (stage 3b in Fig. 1). Continuing with the example, a task is assigned to the organisational category. In the next section, we will describe our tag categorisation approach in more detail. 7 Wikipedia categories, http://en.wikipedia.org/wiki/Special/Categories. 4. Categorisation of social tags 4.1. Tag categories For each of the four purpose-based categories proposed in this work, we define a set of subcategories encompassing the types of entities that can be assigned to those categories. Table 2 shows these subcategories and examples of Flickr social tags automatically categorised by our approach. In contents, we find physical and non-physical entities. As phys￾ical entities, we do have artefacts and living entities. Living entities can be split into animals and plants. Persons are considered as ani￾mals, and similarly, organisations are non-physical entities. Related to the context of an item, we find location and time entities. Within the subjective category, we distinguish between personal opinions and qualities. Finally, organisational entities are divided into self￾references, tasks and actions. Instead of directly assigning a social tag to a purpose-based cat￾egory, we firstly identify the most suitable subcategory, and then obtain the corresponding main category. We detail this process in Sections 4.2 and 4.3. 4.2. Categorising content- and context-based social tags The categorisation of content- and context-based tags is based on their mapping to semantic concepts described in an external KB. A major requirement imposed on the KB is that it has to pro￾vide a classification hierarchy (taxonomy) among its concepts. As described in Section 3, given a social tag, we should not only be able to map it to a semantic concept, but also to determine one of

L Cantador et al Web Semantics: Science, Services and Agents on the world Wide Web 9(2011)1-15 Music UniTer PROSITE Un Prot Gere OMIM Data sets published and interlinked by The w3C Linking Open Data project duly 2009). Coloured data sets represent the main semantic data sources exploited by our tag categorisation proposal. For interpretation of the references to color in this figure legend, the reader is referred to the web version of the article. its taxonomic ancestors that would allow us to assign the tag to The lod project aims to extend the web with a data commons by either the content-based category or the context-based category. publishing open data sets as RDF on the Web and by setting RDF The tag nyc(New York city )is not just a city, but also a locatie links between data items from different data sources. These rdf links can be for example followed by crawlers and Semantic Web In this context, WordNet [24, being a lexical database for the search engines to provide sophisticated search and query capabili- English language commonly exploited to support automatic text ties over crawled data. Fig. 2 shows that YAGO ontology forms part analysis and artificial intelligence applications, could be a good of the LOD repository and directly links to wordNet and DBpe candidate for our categorisation goals. However, we are also inter- dia [ 5, a huge knowledge base containing structured information ested in a repository flexible and capable of incorporating new extracted from wikipedia. concepts appearing in our daily lives(e.g, web 2. 0, podcast, diy We propose to use YAGO in our social tag categorisation Wikipedia, which is an online encyclopaedia updated collabora- approach, as a way of bridging the gap between folksonomies tively by the community, represents one of our best alternatives (understood as non-interlinked social tag sets)and the Seman- YAGo [34 is an ontological KB- supported by the w3C Linking tic Web(under the perspective of the lod project). Fig 3 shows Open Data(LOD)initiative -which contains information har- a portion of YAGo taxonomy The coloured classes are reference vested from WordNet and wikipedia. As of September 2009, YAGo concepts linked to content-and context-based (sub)categories, knows over 2 million entities such as people, organisations, cities, explained in the following etc, and about 20 million facts about these entities. Among other To categorise a social tag, the first step is to map it to a YAGO class semantic relations, it provides a multi-domain knowledge classi-(stage la in Fig. 1). In many cases, a direct mapping between the fication where the upper-level classes are the concepts existing in tag and the names of an ontology class is not possible. People add WordNet, and the lower-level classes correspond to wikipedia cat- tags in singular and plural forms indistinctively, use morphological gories YAGO thus can be understood as a taxonomy divided into derivations(e.g, acronyms), make misspellings, and include com- two parts: one invariant part which covers generic concepts that und nouns with different separation characters(e.g, NewYork, can be found in a dictionary, and other open part that extends the New York, New-York). For this reason, we perform a number of ormer with more specific classes about concepts not existing in a morphological transformations of the tags obtaining a set of equiv dictionary, but in an updated modern encyclopaedia. alent terms to be matched with YAGo class names. First, we apply stemming and stop word removal techniques to the tags. We also 8 Linking Open Data http:/lesw.w3.org/topic/sweolgtaskforces

6 I. Cantador et al. / Web Semantics: Science, Services and Agents on the World Wide Web 9 (2011) 1–15 Fig. 2. Data sets published and interlinked by The W3C Linking Open Data project (July 2009). Coloured data sets represent the main semantic data sources exploited by our social tag categorisation proposal. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of the article.) its taxonomic ancestors that would allow us to assign the tag to either the content-based category or the context-based category. The tag nyc (New York city) is not just a city, but also a location, which is a contextual entity. In this context, WordNet [24], being a lexical database for the English language commonly exploited to support automatic text analysis and artificial intelligence applications, could be a good candidate for our categorisation goals. However, we are also inter￾ested in a repository flexible and capable of incorporating new concepts appearing in our daily lives (e.g., web 2.0, podcast, diy). Wikipedia, which is an online encyclopaedia updated collabora￾tively by the community, represents one of our best alternatives. YAGO [34] is an ontological KB – supported by the W3C Linking Open Data (LOD) initiative8 – which contains information har￾vested from WordNet and Wikipedia. As of September 2009, YAGO knows over 2 million entities such as people, organisations, cities, etc., and about 20 million facts about these entities. Among other semantic relations, it provides a multi-domain knowledge classi- fication where the upper-level classes are the concepts existing in WordNet, and the lower-level classes correspond to Wikipedia cat￾egories. YAGO thus can be understood as a taxonomy divided into two parts: one invariant part which covers generic concepts that can be found in a dictionary, and other open part that extends the former with more specific classes about concepts not existing in a dictionary, but in an updated modern encyclopaedia. 8 Linking Open Data project, http://esw.w3.org/topic/SweoIG/TaskForces/ CommunityProjects/LinkingOpenData. The LOD project aims to extend theWeb with a data commons by publishing open data sets as RDF9 on the Web, and by setting RDF links between data items from different data sources. These RDF links can be for example followed by crawlers and Semantic Web search engines to provide sophisticated search and query capabili￾ties over crawled data. Fig. 2 shows that YAGO ontology forms part of the LOD repository, and directly links to WordNet and DBpe￾dia [5], a huge knowledge base containing structured information extracted from Wikipedia. We propose to use YAGO in our social tag categorisation approach, as a way of bridging the gap between folksonomies (understood as non-interlinked social tag sets) and the Seman￾tic Web (under the perspective of the LOD project). Fig. 3 shows a portion of YAGO taxonomy. The coloured classes are reference concepts linked to content- and context-based (sub) categories, as explained in the following. To categorise a social tag, the first step is tomap it to a YAGO class (stage 1a in Fig. 1). In many cases, a direct mapping between the tag and the names of an ontology class is not possible. People add tags in singular and plural forms indistinctively, use morphological derivations (e.g., acronyms), make misspellings, and include com￾pound nouns with different separation characters (e.g., NewYork, New York, New York). For this reason, we perform a number of morphological transformations of the tags obtaining a set of equiv￾alent terms to be matched with YAGO class names. First, we apply stemming and stop word removal techniques to the tags. We also 9 Resource Description Framework (RDF), http://www.w3.org/RDF

L Contador et al/Web Semantics: Science, Services and Agents on the World wide Web 9(2011)1-15 Table 3 Category YAGO reference classes Phvsical entity physical_entity Artefact artifact Living entity living_thing, life_form, live_body L-animal animal -Person person,human_body,kin Plant plant,plant_part -physical entity abstraction zation Location ocation, land, geological formation, social group Time time, time_interval, time period, time_unit to the wikipedia part of YAGO. Then, we extend that concept physical_ entity through its ancestors, and obtain concepts such as larid, coastal diving bird, seabird.. bird,., animal. Finally, the linking between a semantic subcategory(reference organising YAGO class)and a purpose-oriented category is direct(stage 3a in mlcroorgar1sn-“ Fig 1). The social tag Seagulls is an animal, and therefore has to be categorised as a content-based tag. It is important to note that there is no overlap between reference classes, i. e the hierarchy branches of content-and context-based animal F vertebrate vertebrate hebian reptile Java(chicken) fkicategory_Chicken_ breeds abstraction tetrapod Subcategory: location Java, Georgia Fig 3. A part of YAGO taxonomy. Coloured classes are reference concepts mapped bikicategory cities, towns amd villages in georgia to our purpose-oriented categories. For interpretation of the references to color in Dakota this figure legend, the reader is referred to the web version of the article. wikicategory_ Towns_m_ South_ dakota use an efficient algorithm that makes use of Google did you Java, New York mean"functionality to split compound nouns with no spaces, and wtkicategory_ Towns in New_ York correct misspellings. All these tag processing and filtering tech- niques are presented in previous works 36, 37]. Without going into details, we just give a couple of example transformations. The social wikicategory_ Islands of_ indonesia tag newyork is transformed into the terms newyork, Newyork, NEWYORK, new-york, New-york, NEW-YORK, New.York. The social tag Subcategory: non-physical barclona is transformed into barclona, barcelona, Barcelona, Java〔band) BARCELONA. The generated tag derivations are then searched as wikicategory_French_hip_ hop_groups names of the yago classes (see an example in Fig 4) If a mapping is found we proceed with the search of a reference Java〔 board_aame YAGo class that uniquely identifies a content- or context-based wikicategory Economic simulation board games subcategory(stage 2a in Fig. 1). To do this, we recursively obtain the ancestor classes of the mapped concept, stopping when reach- ing a predefined reference class (one of those shown in Table 3). For example, let Seagulls be the social tag to categorise. After Subcategory: person forming it into different morphologic derivations, let us that we find a matching with the concept seagull, which wikicategory Film actors Fig 4. Semantic subcategories, concepts and yago classes associated to the social 10goOglewebsearchenginehttp://www.google.com. tag java

I. Cantador et al. / Web Semantics: Science, Services and Agents on the World Wide Web 9 (2011) 1–15 7 Table 3 YAGO reference classes associated to the considered content- and context-based subcategories. Category Subcategory YAGO reference classes Content-based Physical entity physical_entity Artefact artifact Living entity living_thing, life_form, live_body Animal animal Person person, human_body, kin Plant plant, plant_part Non-physical entity abstraction Organisation organization Context-based Location location, land, geological_formation, social_group Time time, time_interval, time_period, time_unit Fig. 3. A part of YAGO taxonomy. Coloured classes are reference concepts mapped to our purpose-oriented categories. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of the article.) use an efficient algorithm that makes use of Google10 “did you mean” functionality to split compound nouns with no spaces, and correct misspellings. All these tag processing and filtering tech￾niques are presented in previous works [36,37]. Without going into details, we just give a couple of example transformations. The social tag newyork is transformed into the terms {newyork, Newyork, NEWYORK, new york, New york, NEW YORK, New York}. The social tag barclona is transformed into {barclona, barcelona, Barcelona, BARCELONA}. The generated tag derivations are then searched as names of the YAGO classes (see an example in Fig. 4). If a mapping is found, we proceed with the search of a reference YAGO class that uniquely identifies a content- or context-based subcategory (stage 2a in Fig. 1). To do this, we recursively obtain the ancestor classes of the mapped concept, stopping when reach￾ing a predefined reference class (one of those shown in Table 3). For example, let Seagulls be the social tag to categorise. After trans￾forming it into different morphologic derivations, let us assume that we find a matching with the concept seagull, which belongs 10 Google web search engine, http://www.google.com. to the Wikipedia part of YAGO. Then, we extend that concept through its ancestors, and obtain concepts such as larid, coastal diving bird, seabird, ..., bird, ..., animal. Finally, the linking between a semantic subcategory (reference YAGO class) and a purpose-oriented category is direct (stage 3a in Fig. 1). The social tag Seagulls is an animal, and therefore has to be categorised as a content-based tag. It is important to note that there is no overlap between reference classes, i.e. the hierarchy branches of content- and context-based Fig. 4. Semantic subcategories, concepts and YAGO classes associated to the social tag java

L Cantador et al Web Semantics: Science, Services and Agents on the world Wide Web 9(2011)1-15 are disjoint. Moreover, although the hierarchy branches of content- denotes similarity measures between items. They evaluate their based subcategories intersect (e.g. a person is an animal, an system using movie rating data from MovieLens. Liu and Yang 19 animal is a living entity, and a living entity is a physi- propose a collaborative filtering approach that models user pref cal entity), our algorithm takes into account the level in which erences derived from the ratings by measuring the correlation a mapping occurs. The lower-level reference classes are preferred between their rankings of the items rather than the rating values. to the upper-level ones(e.g, Brad pitt is categorised as person, using a Random Walk model. They evaluate their method on Each- and not as animal, living entity or physical entity). Movie and NetFlix data Konstas et al. [17 perform RWR on a social 22. Of course, there are ambiguity problems when a tag-concept graph using friendships and social tagging information, captured mapping is done, as shown in Fig 4 for the tag j from the social network Last. fm. In these studies Random walk Terms have different meanings, and only one should be chosen models are used based on their superiority to other collaborative for the corresponding social tag. Here, we obtain and categorise filtering methods. As a result, we also opted to perfor m evaluation all the possible concepts mapped to a tag, and do not perform using an equivalent random walk model ny disambiguation technique. We plan to do it in future work, as discussed in section 8 5.1. Random walk with restarts 4.3. Categorising subjective and organisational social tags A graph is a natural representation of data with some inherent When no mapping between a social tag and a YAGO concept is be represented as nodes and weighted edges respectively, where found, we analyse whether the tag can be categorised as subjective weights denote the strength of the relationships This abstraction or organisation We identify PoS of each term forming the tag using NLP tech- allows us to integrate heterogeneous sources of data in a principled manner iques [2]. After removing some stop-words(e.g, conjunctions). Measuring the relatedness of two nodes in the graph can be we consider the tag as a tuple of pos [poS1,., PoSk, and col achieved using the Random Walks with Restarts(RWR)theory [20]. defined for the subcategories, which have to be interpreted as reg- there is a probability a to restart at x Let pelly bs ly follow- are it with a set of PoS-tuple patterns defined for the subjective Starting from a node x, a rWr is performed by randomly follow- and organisational subcategories. Below, we list the Pos patterns ing a link to another node at each step additiona ular expressions. An asterisk(")means any element, and the OR where p(o) denotes the probability that the random walk at step t operator is used when a subcategory is defined by several PoS pat- is at node i. g is a column vector of zeros with the element corre- sponding to the starting node set to 1, i.e. gx=1. Also let s be the column normalised adjacency matrix of the graph. In other words [] OR [] OR [***] probability ofj being the urrent state is l · Qualities:【**] The stationary, or steady-state, probabilities for each node can b Self-references: [pronoun] OR [***] oR obtained by recursively applying(1) ['**] · Tasks:【** p+1)=(1-a)sp)+aq (1) · Actions: where ae[O, 1. If there is a match between the tag PoS-tuple and a subcate- The stationary probabilities give us the long term visit rate of ry PoS-pattern, then we ca se the tag with that subcategory. each node given a bias towards a particular starting node. Therefore, Otherwise, we do not categorise the tag, and discard it. state after converg can be considered as a Some refinements may be done in these categorisation heuris- measure of relatedness between nodes x and i considered as content-based if we discard the adjectives: the tag 5.2. Social graph big house could be transformed to the tag house Moreover, there may exist incorrect tag assignments within Random Walks with Restarts has recently attracted the interest the subjective subcategories. For example, the tag bad hotel is of researchers in many different areas within Information Retrieval, categorised by our approach as a quality tag as it satisfies the starting from link analysis [25]to image annotation and retrieval [**] regulare ion. whereas it should be 26.39, text classification 42]. click-through data analysis 10 and categorised as an opinion tag. collaborative recommendations [13 These issues have to be carefully studied in the future. In this study we aim to evaluate the effect of tag categorisation in the context of folksonomy-based item recommendation using 5. Recommendation algorithm data crawled from the multi-topic social networking system of Flickr RWR allows us to directly predict the preference of users to In general, recommender systems aim to provide person- particular photos(to which we shall refer to as items from now on) ed on their prev ro collection acquired, by taking behaviour as well as on other information gathered by item descrip- their personal profiles in terms of item preferences (Un) but also tions and user profiles. In particular, given the success of item their tagging behaviour, social network as well as similarly tagged ecommendation in commercial websites such as amazon. com items d Netflix. com, it is considered worthwhile to exploit and evaluate Specifically, we create our social graph by representing users, our tag categorisation technique via the recommendation problem, items and tags as nodes. User relationships (Uu) are encoded graph-based algorithm, namely Random Walk with Restarts using either uni-or bi-directional edges between the correspond (RWR)[20 ing nodes. Similarly, we add edges between items and tags(ITg) Yildirim and Krishnamoorthy [43] propose a novel recommen- as well as users and tags(UTg). More details are given in a later ation algorithm which performs Random Walks on a graph that section

8 I. Cantador et al. / Web Semantics: Science, Services and Agents on the World Wide Web 9 (2011) 1–15 are disjoint. Moreover, although the hierarchy branches of content￾based subcategories intersect (e.g., a person is an animal, an animal is a living entity, and a living entity is a physi￾cal entity), our algorithm takes into account the level in which a mapping occurs. The lower-level reference classes are preferred to the upper-level ones (e.g., Brad Pitt is categorised as person, and not as animal, living entity or physical entity). Of course, there are ambiguity problems when a tag-concept mapping is done, as shown in Fig. 4 for the tag java. Terms have different meanings, and only one should be chosen for the corresponding social tag. Here, we obtain and categorise all the possible concepts mapped to a tag, and do not perform any disambiguation technique. We plan to do it in future work, as discussed in Section 8. 4.3. Categorising subjective and organisational social tags When no mapping between a social tag and a YAGO concept is found, we analyse whether the tag can be categorised as subjective or organisational. We identify PoS of each term forming the tag using NLP tech￾niques [2]. After removing some stop-words (e.g., conjunctions), we consider the tag as a tuple of PoS [PoS1, ..., PoSk], and com￾pare it with a set of PoS-tuple patterns defined for the subjective and organisational subcategories. Below, we list the PoS patterns defined for the subcategories, which have to be interpreted as reg￾ular expressions. An asterisk (*) means any element, and the ‘OR’ operator is used when a subcategory is defined by several PoS pat￾terns. • Opinions: [] OR [] OR [***] • Qualities: [**] • Self-references: [pronoun] OR [***] OR [***] • Tasks: [**] • Actions: [] If there is a match between the tag PoS-tuple and a subcate￾gory PoS-pattern, then we categorise the tag with that subcategory. Otherwise, we do not categorise the tag, and discard it. Some refinements may be done in these categorisation heuris￾tics. For example, some tags categorised as qualities may be considered as content-based if we discard the adjectives: the tag big house could be transformed to the tag house. Moreover, there may exist incorrect tag assignments within the subjective subcategories. For example, the tag bad hotel is categorised by our approach as a quality tag as it satisfies the [**] regular expression, whereas it should be categorised as an opinion tag. These issues have to be carefully studied in the future. 5. Recommendation algorithm In general, recommender systems aim to provide person￾alised recommendations of items to users based on their previous behaviour as well as on other information gathered by item descrip￾tions and user profiles. In particular, given the success of item recommendation in commercial websites, such as Amazon.com and Netflix.com, it is considered worthwhile to exploit and evaluate our tag categorisation technique via the recommendation problem, using a graph-based algorithm, namely RandomWalk with Restarts (RWR) [20]. Yildirim and Krishnamoorthy [43] propose a novel recommen￾dation algorithm which performs Random Walks on a graph that denotes similarity measures between items. They evaluate their system using movie rating data from MovieLens. Liu and Yang [19] propose a collaborative filtering approach that models user pref￾erences derived from the ratings, by measuring the correlation between their rankings of the items rather than the rating values, using a Random Walk model. They evaluate their method on Each￾Movie and NetFlix data. Konstas et al. [17] perform RWR on a social graph using friendships and social tagging information, captured from the social network Last.fm. In these studies, Random Walk models are used based on their superiority to other collaborative filtering methods. As a result, we also opted to perform evaluation using an equivalent Random Walk model. 5.1. Random walk with restarts A graph is a natural representation of data with some inherent relational structure. In a graph, objects and their relationships can be represented as nodes and weighted edges respectively, where weights denote the strength of the relationships. This abstraction allows us to integrate heterogeneous sources of data in a principled manner. Measuring the relatedness of two nodes in the graph can be achieved using the RandomWalks with Restarts (RWR) theory [20]. Starting from a node x, a RWR is performed by randomly follow￾ing a link to another node at each step. Additionally, in every step, there is a probability a to restart at x. Let p(t) be a column vector where p(t) i denotes the probability that the random walk at step t is at node i. q is a column vector of zeros with the element corre￾sponding to the starting node set to 1, i.e. qx = 1. Also let S be the column normalised adjacency matrix of the graph. In other words, S is the transition probability table where its elements Si,j give the probability of j being the next state given that the current state is i. The stationary, or steady-state, probabilities for each node can be obtained by recursively applying (1) until convergence, p(t+1) = (1 − ˛)Sp(t) + ˛q. (1) where ˛∈ [0,1]. The stationary probabilities give us the long term visit rate of each node given a bias towards a particular starting node. Therefore, p(l) i , where l is the state after convergence, can be considered as a measure of relatedness between nodes x and i. 5.2. Social graph Random Walks with Restarts has recently attracted the interest of researchers in many different areas within Information Retrieval, starting from link analysis [25] to image annotation and retrieval [26,39], text classification [42], click-through data analysis [10] and collaborative recommendations [13]. In this study, we aim to evaluate the effect of tag categorisation in the context of folksonomy-based item recommendation using data crawled from the multi-topic social networking system of Flickr. RWR allows us to directly predict the preference of users to particular photos (to which we shall refer to as items from now on) from the data collection acquired, by taking into account not only their personal profiles in terms of item preferences (UI) but also their tagging behaviour, social network as well as similarly tagged items. Specifically, we create our social graph by representing users, items and tags as nodes. User relationships (UU) are encoded using either uni- or bi-directional edges between the correspond￾ing nodes. Similarly, we add edges between items and tags (ITg) as well as users and tags (UTg). More details are given in a later section

L Contador et al/Web Semantics: Science, Services and Agents on the World wide Web 9(2011)1-15 6. Experiments Table 4 in the case of the full 6.1. Data collection tag space, and in the case of random selection of 4K tag ection 6.6) 4K tags 6.1x10-3 folksonomy-based item recommendation, we collected live 2.2×1 data from the Flickr social network. Flickr is a photograph and 2.2×10-4 short-video oriented social network that users to upload = 2.2×10-4 2.2×10-4 2.2×10-4 and share their media with other users. In order to evaluate ou tag categorisation strategy, we decided to use a dataset from Social graph 2.2×10-4 22×10-4 Flickr because this is a multi-domain social system. Our approach could also be tested on a single-domain repository such as Last. fm ing those contact relations which were not linking to owners and (music)or MovieLens (movies). In doing so, however, our con- fans of most interesting items. To reduce the size of the item space clusions may be biased, as long as we would not be covering a we discarded those items that were not favourite of at least two of n categorising social tags. Nonetheless, a comparison of tag and tags not associated to正m categorisation and recommendation results obtained with sin point. Tags were also cut down if they were not used by at least two Ind multi-domain datasets constitutes an interesting study. We users to tag their items, and were exposed to a cleaning proces postpone it as future work. In this paper, we focus on the study (stemming, stop words removal, misspelling and compound noun of the feasibility of our automatic tag categorisation proposal in a processing, etc ) which is exemplified in Section 4.2, and explained generic framework with a wide range of topics and domains. in detail in previous works 36, 37]. The main characteristics of the data collection acquired could be summarised as follows. e The third part dealt only with the tags collected so far. First of all, we machine translate them if necessary, using Google tran lat Our main focus w photos(items) rather than short videos, it was not English). Then, each tag was assigned one or more cat- since the former are more widely accepted by the Flickr commu- egories following the process described earlier. In case either of nity at the moment these two steps failed for a certain tag, then this was not included We consider two types of relationship between users and items: in the final set Users can either own photos or become fans of them, i.e. add them The outcome of this filtering process was a reduced data to their favourite items list collection of 2022 users, 24, 263 items and 41, 742 tags(20,055 Tags in Flickr are categorised as social (i.e. not specified by content-based, 8300 context-based, 9013 subjective, and 4374 experts ), meaning that only the owner of an item can annotate organisational). with the derived sub-matrices'densities shown (tag)it. in Table 4, and which is as well made available at(blind for review ) Items can be grouped by their owner into item-sets, based on his her personal notion of similarity among them. 6.2. Dataset Friendships are essentially uni-directional, established when a user decides to add another user into his contact list(similar The combination of the UU. Ul, plus UTgall, ITgall, tgTgall to followers in micro-blogs like Twitter). Along with uni- from now on we shall refer to as the whole tag space)sub-m directional friendships, we also consider bi-directional bonds derived by the data collection method described above, resu (whic of friendship, defining them as mutual uni-directional links the full social graph S, shown in Fig. 5. between two users and regard them in our analysis different our case, most of these sub-matrices are binary, either by definition(e.g, in the case of the Ul sub-matrix, we only have evi- work comprising of 3223 users, 240, 648 items and 190, 105 tags, item, which is essentially binary information: Same thing applies for the lTgsub-matrix: an item may or may not be associated with This initial datase exposed to a three part filtering pro- a single tag)or on purpose. Given the fact that the aforementioned cess. For the first part, our intention was to collect users who have sub-matrices were naturally binary, we opted to keep everything intense activity in their profiles. This can be interpreted as the else bounded between 0 and 1 fact that they have popular items in their profiles, which means More specifically, in the UU sub-matrix, we represent each lots of contacts that might link to them both through friendship uni-directional bond of friendship with the value of 0.5 and each bi- establishment and becoming fans of their items. directional with 1. In this way, we tend to favour the latter category As a result, we collected the 500 items that were characterised of friendships under the assumption that they are more concrete as the most interesting on the 1st of January 2009. For these item similar to real life. What is more, bi-directional friendships are usu- we extracted their owners profiles, composed of their 150 top tags, ally the norm in many other social networks such as Facebook b and the items tagged with these tags, and their contacts. Then, for each Last. fm [17 In the UTgall sub-matrix, each edge is a normalised of the above items, we also obtained a list of 10 fans(the first weight between 0 and 1, indicating the frequency of use of each tag 0 users provided by Flickr API). Similarly to the owners profile btaining step, for each fan we extracted the 150 top tags, the items taggedwiththesetagsandtheircontactsInthepreviousstepswe1Googletranslatehttp:/translategoogle.com 14 Note that due to ambiguity a tag may belong to more than one category See For the second part, we aimed to maintain a dense graph on the Section 6.5 for more details user space. Firstly, we filtered all the gathered contacts, by discard 15 In Flickr system, a photo can only be tagged by one user(the owner), and thus and each tag is binary. This is different to other tagging systems, where users be associated to an item-tag relation, in general based on the number of times the vitter. com 12Flickrdatasethttp://mir.dcs.glaac.uk/flickr 16Facebook-socialnetworkinghttp://www.facebook.com

I. Cantador et al. / Web Semantics: Science, Services and Agents on the World Wide Web 9 (2011) 1–15 9 6. Experiments 6.1. Data collection For the purposes of automatic tag categorisation and folksonomy-based item recommendation, we collected live data from the Flickr social network. Flickr is a photograph and short-video oriented social network that allows users to upload and share their media with other users. In order to evaluate our tag categorisation strategy, we decided to use a dataset from Flickr because this is a multi-domain social system. Our approach could also be tested on a single-domain repository such as Last.fm (music) or MovieLens (movies). In doing so, however, our con￾clusions may be biased, as long as we would not be covering a significant part of the knowledge base (WordNet and Wikipedia) when categorising social tags. Nonetheless, a comparison of tag categorisation and recommendation results obtained with single￾and multi-domain datasets constitutes an interesting study. We postpone it as future work. In this paper, we focus on the study of the feasibility of our automatic tag categorisation proposal in a generic framework with a wide range of topics and domains. The main characteristics of the data collection acquired could be summarised as follows: • Our main focus was on photos (items) rather than short videos, since the former are more widely accepted by the Flickr commu￾nity at the moment. • We consider two types of relationship between users and items: Users can either own photos or become fans of them, i.e. add them to their favourite items’ list. • Tags in Flickr are categorised as social (i.e. not specified by experts), meaning that only the owner of an item can annotate (tag) it. • Items can be grouped by their owner into item-sets, based on his/her personal notion of similarity among them. • Friendships are essentially uni-directional, established when a user decides to add another user into his contact list (similar to followers in micro-blogs like Twitter11). Along with uni￾directional friendships, we also consider bi-directional bonds of friendship, defining them as mutual uni-directional links between two users and regard them in our analysis differently. We extracted a representative portion of the Flickr social net￾work comprising of 3223 users, 240,648 items and 190,105 tags, which are freely available12 for other researchers. This initial dataset was exposed to a three part filtering pro￾cess. For the first part, our intention was to collect users who have intense activity in their profiles. This can be interpreted as the fact that they have popular items in their profiles, which means lots of contacts that might link to them both through friendship establishment and becoming fans of their items. As a result, we collected the 500 items that were characterised as the most interesting on the 1st of January 2009. For these items, we extracted their owners’ profiles, composed of their 150 top tags, the items tagged with these tags, and their contacts. Then, for each of the above items, we also obtained a list of 10 fans (the first 10 users provided by Flickr API). Similarly to the owners’ profile obtaining step, for each fan we extracted the 150 top tags, the items tagged with these tags, and their contacts. In the previous steps, we discarded those users without tagged items. For the second part, we aimed to maintain a dense graph on the user space. Firstly, we filtered all the gathered contacts, by discard- 11 Twitter – Social messaging, http://www.twitter.com. 12 Flickr dataset, http://mir.dcs.gla.ac.uk/flickr. Table 4 Densities of the sub-matrices that comprise the social graph S, in the case of the full tag space, and in the case of random selection of 4K tags (see Section 6.6). All tags 4K tags User-User (UU) 6.1 × 10−3 User-Item (UI) 2.2 × 10−4 User-Tag (UTgall) 5.7 × 10−4 2.2 × 10−4 Item-Tag (ITgall) 6.5 × 10−4 2.2 × 10−4 Tag-Tag (TgTgall) 2.2 × 10−4 2.2 × 10−4 Social graph (S) 2.2 × 10−4 2.2 × 10−4 ing those contact relations which were not linking to owners and fans of most interesting items. To reduce the size of the item space, we discarded those items that were not favourite of at least two of the available users. Finally, we removed users with no tagged items, and tags not associated to an item existing in the collection at this point. Tags were also cut down if they were not used by at least two users to tag their items, and were exposed to a cleaning process (stemming, stop words removal, misspelling and compound noun processing, etc.), which is exemplified in Section 4.2, and explained in detail in previous works [36,37]. The third part dealt only with the tags collected so far. First of all, we machine translate them if necessary, using Google trans￾late tool,13 which automatically detected the language of origin (if it was not English). Then, each tag was assigned one or more cat￾egories following the process described earlier. In case either of these two steps failed for a certain tag, then this was not included in the final set. The outcome of this filtering process was a reduced data collection of 2022 users, 24,263 items and 41,742 tags (20,055 content-based, 8300 context-based, 9013 subjective, and 4374 organisational14), with the derived sub-matrices’ densities shown in Table 4, and which is as well made available at (blind for review). 6.2. Dataset The combination of the UU, UI, plus UTgall, ITgall, TgTgall (which from now on we shall refer to as the whole tag space) sub-matrices derived by the data collection method described above, resulted in the full social graph S, shown in Fig. 5. In our case, most of these sub-matrices are binary,15 either by definition (e.g., in the case of the UI sub-matrix, we only have evi￾dence as of the ownership or preference of a user towards a certain item, which is essentially binary information; Same thing applies for the ITgall sub-matrix; an item may or may not be associated with a single tag) or on purpose. Given the fact that the aforementioned sub-matrices were naturally binary, we opted to keep everything else bounded between 0 and 1. More specifically, in the UU sub-matrix, we represent each uni-directional bond of friendship with the value of 0.5 and each bi￾directional with 1. In this way, we tend to favour the latter category of friendships under the assumption that they are more concrete, similar to real life. What is more, bi-directional friendships are usu￾ally the norm inmany other social networks such as Facebook16 and Last.fm [17]. In the UTgall sub-matrix, each edge is a normalised weight between 0 and 1, indicating the frequency of use of each tag 13 Google translate, http://translate.google.com. 14 Note that due to ambiguity, a tag may belong to more than one category. See Section 6.5 for more details. 15 In Flickr system, a photo can only be tagged by one user (the owner), and thus the relation between a certain photo and each tag is binary. This is different to other tagging systems, where users can annotate any item, and thus a weight can be associated to an item-tag relation, in general based on the number of times the item has been annotated (by different users) with that particular tag. 16 Facebook – Social networking, http://www.facebook.com

L Cantador et al Web Semantics: Science, Services and Agents on the world Wide Web 9(2011)1-15 Users Items Tags Note that in the case of the rWr method, we cannot directly compute the rating (or equivalently the predicted preference ornot of a user for a certain item, as in our case with Flickr where ratings STall are considered binary)for each item as in standard collaborative filtering evaluation methodology Instead we are only able to get a rank of the items in order of predicted preference. As a result, we are forced to evaluate the method as if it was being used in real-time urposes, i.e. judging both the predictive accuracy and precisi of the system at the same time by using standard retrieval met rics such as recall. mAP and number of relevant retrieved items similarly to 36]. 6. 4. Experi (UTgTi(ITgay! TgTgo In this section, we illustrate the methodology for the individual recommendation experiments conducted using the rWr method. The outcome of each experiment was the aggregation of the lists containing the top 1000 items in descending order for each user. Fig. 5. Social graph S and the comprising sub-matrices which were tested against the ground truth, i.e. the items owned or being indicated as favourite by a user. As described in Section 5. 1, there is a restart probability param- for a specific user, extracted directly by the tag cloud in the profile eter a, which we set to the value of 0. 8, so as to suppress the model of each user from the Flickr website. Finally, the TgTg sub-matrix to return to the initial query vector q more often and consequently is the item-based co-occurrence of tags, calculated using Eq(2): perform random walks in the neighbouring elements of a, what TtG=∫((g)2.(mg), (2) was interpreted as stronger personalisation in [17]. After setting a, we then conducted two series of experiments, which aimed to validate our main hypothesis concerning tag categorisation. f i The first series was preliminary using Ul, the whole tag space f(a1,j=0 if i=j and parts of UU, namely different versions of the matrix that included only uni-directional friendships Uu(i.e. with aij being the element of TgTg at the ith and jth position. bi-directional bonds were considered of equal importance to uni- directional), only bi-directional friendships UUbi, and both. The purpose of this series of experiments was to determine whether 6.3. Evaluation protocol the inclusion of friendships were of benefit in the social graph, and We evaluated the tag categorisation technique under study thus be able to justify whether they should be included in the next series using the RWr method in order to perform item recommendation, with either the whole tag space or parts of it, as will be clarified in As will be shown and explained in the next sections, friendship vere not found to be of significant importance and thus were not the following section. In every experiment, we follow the same pe considered furthermore. As a result the second series of user evaluation protocol adopted by [17 which we describe here nents were conducted on a part of the social graph that cont Ul and versions of uTgall, ITgall tgTgall with either content-based or each individual user in the dataset, we randomly select a context-based, subjective or organisational tags only Four exper list of 20% of the items he or she is only a fan of, and set zeros to iments were thus performed using all the tags in each category the corresponding elements of Ul and ur sub-matrices. It should However, taking into account that there was not enough balance noted, that it is important not to include owned items, since we as to the number of tags within each category (Section 6.1), we also do no them to be recommended back to each user. What is performed another five experiments with a reduced tag-set of more,as stated earlier it is the case in flickr that only the owners 4374(4K tags)in each category, i.e. the number of tags in the organi- can assign tags to their owned items. As a consequence, if we merely sational category The reduced tags were chosen randomly from the remove links in the ul sub-matrix then the recommendation would original tag-set. Fin in order still be biased towards the owner'sitems unless we also remove the the performance of the recommendation is ascribed to the discrim links in the UTg sub-matrix. However, this is no longer necessary inative power of tags belonging to different categories, rather than ecause we are only including the items that each a fan of the density of the graph, we performed a single experiment for the nd thus there are no left links in the UTg sub-matrix. content-based tags only that contained 8500 tags, i.e. of equal size We then create a query vector q so that qi-1 if Sua, i>0, and to context-based and subjective tags qua = 1, where i=[. .. N]. Su.i is the i-th element of S correspond g to the u-th user, ua is the current user under evaluation, and n is the total number of columns of S. Next, we normalise q so that 6.5. Categorisation results Then, we perform a Random Walk on S which returns the sta In this section, we present and discuss the results obtained by tionary probability vector corresponding to ua of all the items in the categorisation of the social tags existing in the Flickr dataset he dataset. From this vector, we remove the remaining 80% of described in Sections 6. 1 and 6.2 items user ua was a fan of, so as to avoid recommending back items Table 5 shows the percentage of tags assigned to each purpose- which were used while performing the RwR. We then re-order th oriented category before and after translating non-English tags. By remaining items in descending order, with the first element having been assigned the highest probability, denoting higher preference. This vector is pruned to contain the top 1000 items. 17 One for each tag category plus another being a subset of the whole tag space

10 I. Cantador et al. / Web Semantics: Science, Services and Agents on the World Wide Web 9 (2011) 1–15 Fig. 5. Social graph S and the comprising sub-matrices. for a specific user, extracted directly by the tag cloud in the profile of each user from the Flickr website. Finally, the TgTgall sub-matrix is the item-based co-occurrence of tags, calculated using Eq. (2): TgTgall = f((ITg) T · (ITg)), (2) where f(ai,j) = ai,j if i =/ j 0 if i = j with ai,j being the element of TgTgall at the ith and jth position. 6.3. Evaluation protocol We evaluated the tag categorisation technique under study using the RWR method in order to perform item recommendation, with either the whole tag space or parts of it, as will be clarified in the following section. In every experiment, we follow the same per user evaluation protocol adopted by [17] which we describe here briefly. For each individual user in the dataset, we randomly select a list of 20% of the items he or she is only a fan of, and set zeros to the corresponding elements of UI and UIT sub-matrices. It should be noted, that it is important not to include owned items, since we do not want them to be recommended back to each user. What is more, as stated earlier it is the case in Flickr that only the owners can assign tags to their owned items. As a consequence, if wemerely remove links in the UI sub-matrix then the recommendation would still be biased towards the owner’s items unless we also remove the links in the UTg sub-matrix. However, this is no longer necessary because we are only including the items that each user is a fan of and thus there are no left links in the UTg sub-matrix. We then create a query vector q so that qi = 1 if Sua,i > 0, and qua = 1, where i = [1, ..., N], Su,i is the i-th element of S correspond￾ing to the u-th user, ua is the current user under evaluation, and N is the total number of columns of S. Next, we normalise q so that ||q||1 = 1. Then, we perform a Random Walk on S which returns the sta￾tionary probability vector corresponding to ua of all the items in the dataset. From this vector, we remove the remaining 80% of items user ua was a fan of, so as to avoid recommending back items which were used while performing the RWR. We then re-order the remaining items in descending order, with the first element having been assigned the highest probability, denoting higher preference. This vector is pruned to contain the top 1000 items. Note that in the case of the RWR method, we cannot directly compute the rating (or equivalently the predicted preference or not of a user for a certain item, as in our case with Flickr where ratings are considered binary) for each item as in standard collaborative filtering evaluation methodology. Instead we are only able to get a rank of the items in order of predicted preference. As a result, we are forced to evaluate the method as if it was being used in real-time purposes, i.e. judging both the predictive accuracy and precision of the system at the same time by using standard retrieval met￾rics such as Recall, MAP, and number of relevant retrieved items, similarly to [36]. 6.4. Experimental setup In this section, we illustrate the methodology for the individual recommendation experiments conducted using the RWR method. The outcome of each experiment was the aggregation of the lists containing the top 1000 items in descending order for each user, which were tested against the ground truth, i.e. the items owned or being indicated as favourite by a user. As described in Section 5.1, there is a restart probability param￾eter ˛, which we set to the value of 0.8, so as to suppress the model to return to the initial query vector q more often and consequently perform random walks in the neighbouring elements of ua, what was interpreted as stronger personalisation in [17]. After setting ˛, we then conducted two series of experiments, which aimed to validate our main hypothesis concerning tag categorisation. The first series was preliminary using UI, the whole tag space and parts of UU, namely different versions of the latter sub￾matrix that included only uni-directional friendships UUuni (i.e. bi-directional bonds were considered of equal importance to uni￾directional), only bi-directional friendships UUbi, and both. The purpose of this series of experiments was to determine whether the inclusion of friendships were of benefit in the social graph, and thus be able to justify whether they should be included in the next series. As will be shown and explained in the next sections, friendships were not found to be of significant importance and thus were not considered furthermore. As a result, the second series of experi￾ments were conducted on a part of the social graph that contained UI and versions of UTgall, ITgall, TgTgall with either content-based, context-based, subjective or organisational tags only. Four exper￾iments were thus performed using all the tags in each category. However, taking into account that there was not enough balance as to the number of tags within each category (Section 6.1), we also performed another five experiments17 with a reduced tag-set of 4374 (4K tags) in each category, i.e. the number of tags in the organi￾sational category. The reduced tags were chosen randomly from the original tag-set. Finally, in order to depict even more clearly that the performance of the recommendation is ascribed to the discrim￾inative power of tags belonging to different categories, rather than the density of the graph, we performed a single experiment for the content-based tags only, that contained 8500 tags, i.e. of equal size to context-based and subjective tags. 6.5. Categorisation results In this section, we present and discuss the results obtained by the categorisation of the social tags existing in the Flickr dataset described in Sections 6.1 and 6.2. Table 5 shows the percentage of tags assigned to each purpose￾oriented category before and after translating non-English tags. By 17 One for each tag category, plus another being a subset of the whole tag space.