Micro-blogging activity taking place in sites such as Twitter gains everyday more importance as a source of real-time information and news spreading medium. Finding relevant information sources among the increasing number of Twitter members is essential for users needing to cope with real-time information. In this paper we study Twitter aiming at generating a set of recommendations to a target user consisting in people who publish tweets that might be interesting to him/her. We evaluate and compare two recommendation approaches: the first selects a set of candidate recommendations using only the network topology and the second exploits the user-generated content available in their tweets. We report the results of a set of controlled experiments with real users carried out to evaluate and compare the performance of both algorithms.
Twitter is a social networking site that has been selected for many users as a means
of disseminating (and reading) news and information. There are three main factors for
choosing Twitter for this goal. First, unlike many other online social networks such as
Facebook, Hi5, Orkut, LinkedIn or MySpace, connections in Twitter are unidirectional.
This means that a user decides to “follow” other users with no need of this relation
to be accepted or reciprocated. Second, the 140-characters length restriction applied to
the messages that users can post in Twitter (which are called tweets) enable users to
receive their followees updates in almost any mobile device or to quickly read a bunch
of them directly on the Internet or within a desktop application. Finally, any user can
easily “retweet” another user’s post. In this way the information will be spread out from
the author followers to other users’ followers. Kwak et al. [
In this work we study Twitter from a user modeling perspective. Our goal is to provide recommendations to information seekers about users that publish tweets that might be of their interest. In order to be valuable, the recommended followees should be in the category of information broadcasters, since these users will probably generate content that the target user may be interested in reading.
Unlike traditional recommendation systems, we do not have any explicit information available about the user’s interests in the form of ratings on items he/she likes or dislikes. For profiling a Twitter user the structure of the followers/followees network and the tweets published in this network is the only information available. Both are considered in this paper as a means to recommend people either belonging to the user’s neighborhood or sharing content-related interests.
In this article we present two recommendation algorithms using two different
techniques: a collaborative filtering technique [
Unlike other works that focus on ranking users according to their influence in the
entire network [
The rest of this work is organized as follows. Section 2 describes some aspects about Twitter and discuss how related work is related to our research. Next, in Section 3 we describe our approach to the problem of followee recommendation in Twitter. In Section 4 we present the experiments we performed to validate our proposal. Finally, in Section 5 we discuss the results we obtained and present our conclusions and future work.
http://yearinreview.twitter.com/whosnew/. Accessed on April 2011
Twitter is a social network with micro blogging service that enables users to send and receive messages with a length shorter than 140 characters that are called “tweets” or status updates. Relationships in Twitter are unidirectional: a Twitter user U interested in the tweets published by another user registers himself as a “follower”. Although user U has no need to follow their followers back, it is possible for him/her to obtain the list of users following him/her.
As stated above, the Twitter network is populated with tweets. Tweets can have any (textual) content; however there exist users that only publish tweets about a particular subject, such as sports, movies, music or a about a particular rock band. These users can be considered as information sources or broadcasters. In contrast, many people uses Twitter to get information on particular subject, as a form of RSS reader, registering themselves as followers of their favorite artists, celebrities, bloggers, or TV programs. For this last type of users finding high quality and reliable information sources in the constantly increasing Twitter community becomes a challenging issue.
Several recent research efforts have been dedicated to understand micro-blogging
as a novel form of communication and news spreading medium. Java et al. [
The influence of users in Twitter has also been subject of several studies. In [
While the mentioned studies focus on analyzing micro-blogging usage, other works
try to capitalize the massive amount of user-generated content as a novel source of
preference and profiling information for recommendation. Chen et al. [
In contrast to the previous works that address the problem of suggesting potentially
relevant content from micro-blogging services, we concentrate in recommending
interesting people to follow. In this direction, Sun et al. [
Finally, the problem of helping users to find and to connect with people on-line to
take advantage of their friend relationships has been also studied in the context of social
networks. For example, SONAR [
We have designed two different algorithms for followee recommendation on Twitter. The first algorithm is only based on the topology of the followers/followees network and suggests users that are neighboring the target user up to some distance. The second algorithm is content-based and aims at suggesting users that may not be in the neighborhood of the target user, but whose tweets may be interesting to him/her. 3.1
The general idea behind this algorithm is to suggest users that are in the neighborhood of the target user and that can be potential followees. A user’s neighborhood is determined from the follower/followee relations in the social network. We apply the following heuristic to obtain the list of candidate users for recommendation: 1. Starting with the target user uT , obtain the list of users he/she follows, let’s call this list S, i.e. S(uT ) = [ f .
8 f 2 f ollowees(uT ) 2. For each element in S get its followers, let’s call the union of all these lists L, i.e.
L(uT ) = [ f ollowers (s).
8s2S 3. For each element in L obtain its followees, let’s call the union of all these lists T , i.e.T (uT ) = [ f ollowees (l).
8l2L 4. Exclude from T those users that the target user is already following. Let’s call the resulting list of candidates R, R = T S.
Each element in R is a possible user to recommend to the target user. Notice that each element can appear more than once in R, depending on the number of times that each user appears in the the followees or followers lists obtained at steps 2 and 3 above.
The rationale behind this heuristic procedure is that the target user is an information seeker that has already identified some interesting users acting as information sources, which are his/her followees. Other people that also follows some of the users in this group (i.e. is subscribe to some of the same information sources) have interests in common with the target user and might have discover other relevant information sources in the same topics, which are in turn their followees.
Finally, we give each unique user uc 2 R a score given by the Equation 1: score(uc) = occurrences(uc; R) jRj j f ollowers(uc) j j f ollowees(uc) j j mentions(uc) j
M (1)
The first term corresponds to the number of occurrences of the user in the final list of jRj candidates for recommendations. The number of occurrences of a user uc in this final list is an indicator of the amount of (indirect) neighbors that also have uc as a (direct) connection itself.
The second term is the relation between the number of followers a user has with
respect to the number of users that he/she follows. Since we seek for information sources
to be recommended, we assume that this kind of users will have many followers and
that they will follow few people. In [
For the reason expressed above, we finally add a factor that considers the number of
times that a user has been mentioned in the social network in recent posts. According
to Kwak et al. [
Information seekers are characterized for posting few tweets themselves, but follow people that generate content more actively. It is assumed that users actively select their followees expecting that their tweets will be interesting to them. Then, in order to develop a content-based followees recommender algorithm, we assumed that the interests of the target user can be described by the content of the tweets published by the users he/she follows. Let tweets(u f ) = ft1; t2; ; tkg be the set of tweets published by user u f , pro f ilebase(u f ) the term vector built from tweets(u f ), and f ollowees(uT ) = f f1; f2; ; fl g the followees of user uT . Then the profile of a user uT is defined as the union of term vectors of his/her followees: pro f ile(uT ) =
[ 8u f 2 f ollowees(uT ) pro f ilebase(u f )
In order to search for candidate recommendations, this algorithm does not take candidate users from the topology of the social network. Instead, it aims at discovering new users that may not be connected to the target user by a short path in the graph but appear in an information stream provided by Twitter which is known as public timeline. This stream contains the collection of the most recently published tweets, and is fed by all accounts that are not configured to be private. The public timeline can be considered as the current flow of information in Twitter, and is a good source to obtain active users in the social network.
The content-based algorithm we designed works as follows: 1. Obtain the authors of the most recent publications that appear in Twitter’s public timeline, U = fu1; u2; . . . ; umg. 2. For each user uC 2 U , build pro f ilebase(uC). That is, we build the term vector corresponding to each uC . 3. For each user uC 2 U , compute
sim(uC; uT ) = max8i: fi2 f ollowees(uT )simcos [pro f ilebase( fi); pro f ilebase(uC)]
If sim(uC; uT ) > g, add uC to the list of recommendations ordered by similarity. 4. Repeat steps 1 to 4 until the desired number of recommendations is obtained. In order to build the term vectors associated to users, we first detect the language of the tweets2 and then we apply the corresponding stop-word and stemming filters. We use a term frequency weighting scheme in the term vectors.
We use a similarity threshold of g = 0:1 to consider a user relevant for recommendation. This threshold was set very low so that the desired number of recommendations could be obtained in a reasonable time. However, it can be adjusted according to the recommender application. For example, if recommendations can be calculated off-line the threshold can be set to a higher value, likely improving the precision of recommendations, at expense of some additional calculation time. 4 4.1
In order to evaluate the proposed algorithms, we have carried out a preliminary experiment using a group of 26 users. These users, 20 males and 6 females, were in the last years of their course of studies and were students of a “Recommender Systems” course dictated at our university as an elective course during 2010. The students selected for the experiment were volunteers familiarized with Twitter. We asked these users to create a new Twitter account3 and to follow at least 20 Twitter users who publish information or news about a set of particular subjects of their interest. The general interests expressed by users ranged among diverse subjects. Some users only concentrated on one particular subject while others distributed their followees among several topics. Then we provided these users with a desktop tool that allowed them to login to Twitter and ask for recommendations using both methods (topology-based and content-based). The tool offered the logged user 20 recommended users and we asked them to explicitly evaluate whether the recommendations were relevant or not according to the same topical criteria they have chosen to select their followees as information sources.
For each recommendation in the resulting ranking the application showed the user name, description, profile picture and a link to the home page of the corresponding account. This link could be used to read the tweets published by the recommended user in the case that the information provided by the application was not enough to determine the student’s interest in the recommendation. The question we asked students
3 We asked students to create a new Twitter account so that they did not need to reveal their real account and the people they follow to ask themselves to determine whether a recommendation was relevant or not was “Would you have followed this recommended user in the first place (when selecting which users to follow in the first part of the experiment), if you had know this account?” For example, if a given student was interest in technology and he/she had not discovered the account @TechCrunch during his/her first selection of followees, that would be an interest recommendation because @TechCrunch tweets about news on technology. 4.2
The quality of lists of top-N followee recommendations generated by each algorithm was first evaluated in terms of their overall precision. Precision can be defined as the number of relevant recommendations over the number of recommendations presented to the user and it can be also computed at different positions in the ranking. For example, P@5 (“precision at five”) is defined as the percentage of relevant recommendations among the first five, averaged over all runs. Figure 1 shows the precision obtained for both algorithms at four different positions of the ranking: P@1, P@5, P@10 and P@20.
In general, both algorithms perform similarly at different positions of the ranking, with the exception of P@1 for which the content-based approach clearly outperforms the topology-based algorithm (61% of relevant recommendations for the content-based algorithm against 35% of relevant recommendations for the topology based-algorithm). For P@5 we obtained 48% of relevant recommendations for the content-based algorithm and 46% of relevant recommendations for the topology based algorithm. At this point we should point out that although we report precision up to 20 recommendations, recommender systems generally present to users shorter recommendations lists aiming at helping them to focus on the most relevant results. In these small lists the contentbased algorithm reached good levels of precision, recommending mostly interesting users.
For recommendations lists longer than 5, performance decreases and we can observe that the topology based algorithm tends to give better results than the content-based algorithm. However the difference in performance of both algorithms is always lower than 5%. Due to the reduced number of users who participate in the experiment, we performed the Student’s t-test of significance on the results obtained. The Student’s ttest looks at the average difference between the performance scores of two algorithms, normalized by the standard deviation of the score difference. For this test we obtain that only the difference in precision at the first position of the ranking (P@1) is statistically significant.
Although precision measure gives a general idea of the overall performance of the
presented algorithms, it is also very important to consider the position of relevant
recommendations in the ranking presented to the user. Since it is known that users focus
their attention on items at the top of a list of recommendations [
Discounted cumulative gain (DCG) is a measure of effectiveness used to evaluate ranked lists of recommendations. DCG measures the usefulness, or gain, of a document based on its position in the result list using a graded relevance scale of documents in a list of recommendations,. The gain is accumulated from the top of the result list to the bottom with the gain of each result discounted at lower ranks. The premise of DCG is that highly relevant documents appearing lower in a list should be penalized as the graded relevance value is reduced logarithmically proportional to the position of the result. The DCG accumulated at a particular rank position k is defined as DCG@k = rel1 + åik=2 loregl2i i . DCG is often normalized using an ideal DCG that is computed by sorting documents of a result list by relevance. Figure 2 shows the normalized DCG obtained for both algorithms at four different positions of the ranking: nDCG@1, nDCG@5, nDCG@10 and nDCG@20.
Success at rank k (S@k) is another metric commonly used to evaluate ranked lists of recommendations. The success at rank k is defined as the probability of finding a good recommendation among the top k recommended users. In other words, S@k is the percentage of runs in which there was at least one relevant user among the first k recommended users. Figure 3 shows the results we obtained for this metric for values of k ranging from 1 to 6.
S@1 is equivalent to P@1 by definition. Then, we can see that the content-based algorithm always positions relevant users earlier in the ranking than the topology-based algorithm. Indeed, all users in the experiment found a relevant recommendation before position 4 in the ranking using the content-based algorithm. For the topology-based algorithm, most users found a relevant recommendation before position 5 except for one user that found the first relevant recommendation at rank 6. 5
In this article we presented two simple but effective algorithms for recommending users in the Twitter social network. The first algorithm models a given user from his/her connections in the social graph whereas the second algorithm models users using the content of the tweets published by his/her followees. We evaluated the proposed algorithms with real users and found that they work fairly similar in finding users that might result interesting for the target user to start following.
From the experiments presented we can conclude that although the average precision tend to be similar for both algorithms, if we consider the position on the recommendations in the ranking the content-based approach is better at giving good recommendations. We believe that results obtained with the content-based algorithm can be improved by setting a higher threshold for the similarity measure used for filtering the term vectors representing users. However, this will increase the response time of the algorithm since users are taken randomly from Twitter’s public timeline.
Among the advantages of the topology-based algorithm, on the other hand, we can mention that recommendations can be found quickly based on a simple analysis of the network structure, without considering the content of the tweets posted by the candidate user.
Although the results reported seems promising, we are planning to repeat the experiment this year in order to involve more users in the experiment and obtain more statistical significance about the two proposed algorithms.
A natural extension in which we are currently working on is a hybrid algorithm that combines the best of both algorithms presented in this paper. This hybrid algorithm filters the candidate recommendations found with the topology-based method with a content-based analysis of the tweets posted by the candidate users. We are also very optimistic about the potential improvements that could be obtained with this hybrid approach.
As a possible limitation of our approach, we can mention that, we assumed that
the target user is an information-seeker user, according to the categorization proposed
by [
The experiments presented make us feel optimistic about the potential of a followee recommender system for Twitter using the methods described in this article or a combination of them. This work is the first step towards exploring the great potentials of this new platform to build recommendation systems.