Online social networking is a huge trend. On Facebook or MySpace people connect with their friends or make new friends. They form new (indirect) connections by reading and adopting from other peoples' blogs or tweets. Similarly, in tagging systems like Delicious or Flickr people share tagged resources with friends or unknown, similar users. Ofine social networks have long been studied in sociology, epidemiology, etc. However, the new online networks o er new ways to revisit old theories as well as to nd emerging trends with respect to information di usion and sharing in the Web 2.0. The goal is to explore and exploit relational ties in a way to enable the mining of useful knowledge and e ective information propagation/di usion. Assuming no or only potential ties explicitly given, the focus is rst on the analysis of collaborative tagging and its potentials for user pro ling, recommendations and search. Some rst related studies, approaches and ideas for future work address the identi cation and exploitation of weak and strong ties in online networks.
With the advent of the Web 2.0 online social networking has
become a huge trend. On platforms like Facebook or
MySpace people connect with their friends or make new friends.
They form new (indirect) connections by reading and
adopting from other peoples' blogs or tweets. Similarly, in
collaborative tagging systems like Last.fm, Delicious or Flickr
people share bookmarks and tagged resources with friends
or unknown, similar users. Reasons are manifold: staying in
touch, socializing, nding answers/experts, share resources
and knowledge, etc. O ine social networks have long been
studied under the perspective of sociology, epidemiology,
and even thermodynamics. However, online networks o er
new ways to revisit old theories as well as to nd emerging
trends in information di usion and sharing in the Web. For
search and recommendation, the topic of tie strength is
interesting. In `real' social networks, strong (i.e. family, close
friends) and weak ties (loose acquaintances) have been found
to show di erent characteristics e.g. with respect to services
o ered (see section 3). As McAfee [
sphere, Bulletin boards, Folksonomies)
The goal is to explore and exploit relational ties in a way to
enable the mining of useful knowledge and e ective
information propagation/di usion so that people are provided the
information they need. Focusing on absent, potential and
weak ties, we will present rst research results, algorithms
and ideas for future work. To better understand
`collective intelligence' expressed via tags, i.e. statistical patterns
found in folksonomies, we start by describing an analysis
of di erent tagging systems and summarize some
experiments on how to exploit social annotations to enrich
metadata for multimedia resources. Web 2.0 tools and
environments like the personalized Internet radio and social music
network Last.fm1 have made collaborative tagging so
popular: any user can assign freely selected words, in the form
of keywords or category labels, to shared content { thereby
describing and organizing these resources. As a result, a
huge amount of manually created metadata describing all
kinds of resources as well as user interests is now available.
Such semantically rich user generated annotations are
especially valuable for recommending, searching and browsing
multimedia resources, such as music, where these metadata
enable retrieval on the newly available textual descriptions
represented by tags. However users' motivations for tagging
resources, as well as the types of tags di er across systems.
These tags represent quite a few di erent aspects of the
resources they describe [
As they o er a promising way to estimate similarity between resources, users and resources or between di erent users, the usefulness and reliability of tags is important for many search and recommendation algorithms. In the rst section the focus will be on analyzing tag usage patterns and their implications for user pro ling, search and recommendation. Then, we will present approaches exploiting tags to enrich resources or user pro les with additional information { music moods and themes as well as picture moods.
Here we present results of an in-depth study [
Our analysis revealed the necessity and usefulness of a common tag classi cation scheme for di erent collections, which allows the comparison of the types of tags used in di erent tagging environments. For example, the distributions of tag types strongly depend on the resources they annotate: for Flickr and Delicious the most frequently used tags (50% of the cases) refer to topic concepts (i.e. what the resource is about), while for Last.fm, type-related tags (e.g. genres) are the most prominent ones. Other interesting results of this analysis refer to the added value of tags to existing content: More than 50% of existing tags bring new information to the resources they annotate. For the music domain this is even the case for 98.5% of the tags. Especially for multimedia data, such as music, pictures or videos, the gain provided by the newly available textual information is substantial, since with most prominent search engines on the Web, users are currently still constrained to search for multimedia using textual queries. A large amount of tags is also accurate and reliable; in the music domain for example 73.01% of the tags also occur in online music reviews written by experts. Regarding search, our studies showed that most of the tags can be used for search and that in most cases tagging behavior exhibits approximately the same characteristics as searching behavior. However, some noteworthy di erences have also been observed. Namely, for the music domain, the usage context (i.e. situation suitable for listening to a particular song { e.g. \pool party") is very useful for search, yet underrepresented in the tagging material. Similar, for pictures and music opinions or qualities (e.g. characteristics, moods) queries occur quite often, although people tend to neglect this category for tagging. Clearly, supporting and motivating tags within these categories could provide additional information valuable for search.
Our analysis [
For our experiments we gathered data from several sources
(for details please refer to [
in the task of mood and theme recommendation, we also obtained the lyrics for our tracks from lyricsdownload.com and lyricsmode.com.
For the purpose of deriving mood labels for pictures,
we manually selected Flickr groups that correspond
to the emotion/mood labels in the hierarchy of
human emotions presented in [
The assumption on which we base our recommendation is that the existing tags attached to music songs or photos can possibly provide information regarding the corresponding mood (or theme). The user given tags are used as input features for training a classi er over all mood or theme classes. Here we also make use of the Weka2 implementation for the Nave Bayes Multinomial classi er, which produces for all pictures in the test set probability distributions over all classes of moods. For music, training and evaluation is done using the Allmusic.com ground truth, created manually by music experts. All distinct tags span the feature vector of a song, weighted by the frequency with which the tag occurred for a song. Similarly, all pictures pertaining to a speci c mood class (i.e. social group on Flickr ) represent the positive training examples, while pictures taken randomly from the rest of the classes build up the set of negative examples. The number of positive and negative examples for a class was equally balanced. In order to ensure a fair classi cation of the data, here all tags related to a mood or emotion were deleted using WordNet synset information.
Music. Di erent experimental runs were performed using
either tags, lyrics, or both plus varying classes to be
predicted. Since the 178 mood terms from Allmusic.com are
hardly distinguishable for a non-expert, these labels were
manually mapped to the hierarchy of basic human primary
and secondary emotions (see 2.2.1). This resulted in 22
secondary mood terms and six primary classes. For themes,
the eleven classes were reduced to nine by applying a
WordNet based clustering accounting for word overlap in synsets.
The best performing methods are those using tags as input
features, while classi cation based on lyrics performs worst.
Combining tags and lyrics achieves good results, sometimes
even slightly outperforms tag-based method. While
incorporating lyrics features led to good results for genre [
Pictures. A rst set of experiments aimed at recommending mood labels corresponding to the primary human emotions. In this case, the classes to be learned by the classiers consisted of the union of all data belonging to all underlying secondary emotions (e.g. the Love class comprises all data gathered from the Flickr groups for A ection, Lust and Longing). For the experimental runs on secondary emotion label recommendations, each secondary emotion class represented a class to be learned. We perform a 10-fold cross validation and evaluate the performance of our method according to standard IR metrics. All recommendations corresponding to the primary human emotions achieved very high quality, with a value close to 1 for H@3 and even a H@1 between 0.61 and 0.91 - they clearly outperform a baseline random classi er. We also compute the overall performance over all primary emotion classes, as averages weighted by the number of instances corresponding to each class. The results are very good, with a value of 0.97 for H@3 and 0.93 for M RR. For primary emotions, correlation between class size and performance is medium: Pearson's r is 0.45 for H@3 and 0.63 for H@1, RP , and M RR. Thus, when misclassifying instances the classi er is biased to incorrectly assigning one of the two dominant classes \Fear" or \Sadness". The overall weighted results for the secondary human emotion label recommendations are almost identical with the case of primary emotions. Again, we nd a classi er bias towards popular classes, correlation between a priori probability of a class and performance is smaller for secondary emotions (Pearson's r is between 0.32 and 0.37 for the di erent evaluation measures). Looking at the di erent mood classes individually, six out of 17 achieve 0.88 or higher for H@1 and 0.93 or more for H@3. For four moods, \A ection", \Zest", \Irritation" and \Lust", performance is considerably lower with H@3 ranging from 0.18 to 0.52. The main reason is the relatively small number of pictures contained in each of these groups, which made learning more di cult. Compared to the music mood and theme recommendations, inference of moods/emotions for picture resources is of higher quality. This is probably due to the data which was used as ground truth: mood-related Flickr groups, manually created by users. The ground truth gathered from AllMusic.com had to be mapped to the hierarchy of human emotions to reduce the extremely high number of classes. This process potentially introduces some noise into the data. The results con rm once more the hypothesis on which we based our recommendation approach: existing tags can give good indications regarding the corresponding moods of the pictures/ moods and themes of music songs.
From sociology as well as social network analysis as a
discipline in its own right quite some descriptive statistics and
generative models have become popular to characterize
social networks. Well-known is that weak ties often act as
bridges and thus hold potential for new information and the
generation of creative ideas, job o ers (e.g. [
indicators found in online social networks? How can these ties be characterized? Do we nd homophily and heterophily as expected from o ine social relations? How do these ties evolve over time?
recommendation (information propagation)? How can they be incorporated to show their potential bene t in information systems (e.g. diversity/non-redundancy)? Are there restrictions by contexts or domains? We address related work, open issues for both topics in the following sections to then conclude with planed future work.
In sociological theory, an impressive amount of work has
been done regarding the measurement of tie strength. A lot
of reliable indicators have been identi ed, e.g. interaction
frequency, duration, intimacy (e.g. [
In a similar work, Gilbert and Karahalios [
Approaches for e ciently searching and propagating
information in online communities build strongly upon methods
developed in social networks analysis. Real networks like the
WWW, the Internet, spreading of diseases/epidemics,
social, biological and linguistic networks have so far been
studied mostly with respect to structure. Graph theoretic
measures like density, indegrees, outdegrees, centrality,
diameter, (structural) cohesion, etc. indicate the potentials and
bottlenecks of a network. As an example, one experimental
nding recently receiving a lot of attention is the
`smallworld phenomenon' (also `6 degrees of separation')[
Similarly, social search and recommendation algorithms try
to exploit the communication and interaction patterns found
in social networks as well as, for example, the trust and
similarity typical for strong ties. Referral Web is a rst
approach to integrate social networks and Collaborative
Filtering (CF) [
Online social networks o er great data to analyze and experiment with for enhancing user pro ling, search and recommendation. The concept of tie strength seems a promising framework for identifying the diverse potentials di erent online social relations can bring. First, collaborative tagging provides reliable, non-redundant and interpersonally valuable metadata, that can be used to enhance searchability of resources as well as estimate user-user or user-item similarities. For this, no explicit friendship relationships have to be given. The results of our comparative tagging analysis provide more insight into the use of di erent kinds of tags for improving search. With respect to weak and strong ties, more research is needed on how to model ties based on explicit or implicit (e.g. tags) indicators. We plan to conduct experiments on learning tie strength and exploiting it for search and recommendation within other kinds of social networks, e.g. the music platform Last.fm. For different domains, system designs and available transactional data, results may deviate from the previous studies. So far, there are still no unambiguous results regarding homophily in recent online networks. Characterizing the relationships people form online and studying how these relations (or their attributes like taste pro le similarity) evolve over time are important to assess the value of ties for improving search and recommendations. Applying standard social network analysis procedures on the new large datasets will also shed additional light on larger community structures around strong and weak ties in general. More importantly, few work has been done so far on how to incorporate tie strength into information retrieval and recommendation. First experiments will use tie strength within the similarity computation of users (to users and items). Information di usion within personal networks will be studied and a model derived on which social recommendations can be build.
This work was partially supported by the GLOCAL project funded by the European Commission (Contract No. 248984).