Twitter, currently the most popular microblogging tool available, is used to publish more than 140,000,000 messages a day. Many users use hashtags to categorize their tweets. However, hashtags are not restricted in any way in terms of usage or syntax which leads to a very heterogeneous set of hashtags occurring in the Twitter universe and therefore, decreases the search capabilities. In this paper, we present an approach for the recommendation of highly appropriate hashtags to the user during the creation process. The recommendations aim at encouraging the user to (i) use hastags at all, (ii) use more appropriate hashtags and (iii) avoid the usage of synonymous hashtags. Therefore the vocabulary of hashtags becomes more homogenous regarding both syntax and semantics.
let the world know what they're up to or simply to share some information they
consider useful. The probably most important feature of Twitter is the retweet
functionality. It enables users to further broadcast tweets they consider worth
spreading within the Twitter network. Mostly, the retweeted message remains
unchanged. A retweeted message contains "RT: @originaluser\ followed by
the original message. This retweeting, which was also heavily analysed in [
In this paper we introduce an approach for the recommendation of hashtags. Our approach computes recommendations based on an analysis of existing tweets by other users and recommends suitable hashtags for the currently entered message to the user. This recommendation mechanism aims at encouraging the user to make use of hashtags and creating a more homogeneous hashtag vocabulary in order to enhance the quality of search result. Additionally, we present general statistics about the use of hashtags within Twitter and an evaluation of our approach.
The remainder of this paper is organized as follows. Section 2 describes the basic concepts of Twitter and hashtags. Section 3 is concerned with the process of hashtag recommendations. Section 4 contains the experiments and evaluations of the presented approach. Subsequently, Section 5 describes important related work and Section 6 concludes the paper.
Hashtagging is a simple and convenient way for users to categorize their own tweets. Such a hashtag within a tweet can simply be speci ed by adding a hash - '#' - followed by the tag itself. One tweet may also contain multiple hashtags, like in the following example tweet: "Don't forget! Only 7 days till the #SASWeb submission deadline #umap2011 http://bit.ly/dKgS82. #recsys #um #adaptivity #web3.0 #ontologies\ which was posted by the SASWeb workshop (@sasWeb2011).
The most popular hashtags are either related to long-term popular topics or
to current events or topics, e.g. the hashtag #tdf was extensively used during the
crawling period as the Tour de France was taking place during this time. Typical
long-term topics are e.g. #Apple or #Obama which are featured in thousands of
messages a day [
In order to be able to analyse the hashtagging behaviour of Twitter users and to build up a database which forms the basis for all recommendation computations, we had to crawl tweets. Overall, we collected about 16,000,000 tweets from July 2010 until February 2011 via the Twitter Application Programming Interface.
In order to retrieve a diverse and highly representative data set to base our evaluations and analysis on, we decided to use Twitter's API2. The basis for our search queries was an English dictionary containing more than 32,000 words. We iterated over the words contained in the dictionary and used them as search keywords for the Twitter Search API. All search results were stored whereby only tweets containing hashtags were used for further analysis. Another approach was to retrieve the public timeline, which basically consists of the ten latest tweets. The timeline is displayed on the Twitter website and is also available via the API. However, these tweets are only updated once a minute. Therefore, only 600 tweets could be retrieved per hour and considering the fact that only 20% of all tweets contain hashtags, this approach was not feasible for crawling a su ciently large dataset.
After having crawled the data, we had to perform multiple preprocessing steps. This included removing all non-english messages (based on Twitter's language classi cation mentioned in the metadata of every tweet) and all messages not containing hashtags at all. Furthermore, all messages were transformed to lower-case. Table 1 contains an overview about the crawled data set and its characteristics. Out of the crawled tweets, more than 3 million tweets contained at least one hashtag, which marks 20% of all crawled tweets. The hashtags ltered from all tweets were further analysed in regards to their usage and popularity. Figure 1 displays the long tail distribution of hashtags and their usage. The fact that stands out about this distribution is that 86% of all hashtags within the data set were used within less than ve tweets. On the other 2 http://search.twitter.com/search hand, the most popular hashtags within the data set (#jobs, #nowplaying, #zodiacfacts, #news and #fb) were used in 8% of all messages containing hashtags. Another interesting fact is the distribution of the number of hashtags used per tweet which can be seen in Figure 2. We expected the number of hashtags per message to be decreasing steadily. This is mostly the case for messages contains less than 15 hashtags. However, the sudden amplitude at 17 hashtags per message is somewhat surprising. We therefore examined these messages and discovered that these were spam tweets which only contained hashtags and a URL, like e.g. "RT @Bhupesh tweet: #Quad #loop-http://bit.ly/ciHX2U #retweet #India #Jobs #World #news #canada #ad #win #USA #tdf #oea #hacking #icantstop #sdcc #game\. Such tweets typically also feature a high retweet-rate by using a spam network consisting of many Twitter users created for spam purposes.
Characteristic
Hashtags occuring only once 16,034,195 3,209,281 12,824,914 2,556,617 3,073,948 5,097,545 510,170 1.5884
23 437,266 328,348 384,187 Value Percentage 100% 20% 80% 16% 19% { { { { { { { The aim of the approach presented in this paper is to nd a set of hashtags suitable for any tweet the user enters. These hashtags are then recommended to the user during the creation process of the new tweet. Recommendations are basically be computed by performing the following steps: 1. nding the most similar messages in the crawled data set for the tweet just entered by the user )e 10000 l -scag o l (s 1000 e c n e rrc u c 100 O fr o e ubm 10 N
1 1e+07 1e+06 100000 e 10000 sg sseaM 1000 100 10 1 0
Hashtags ids (ordered by popularity) 2. retrieving the set of hashtags used within these most similar messages 3. ranking the computed set of hashtag recommendation candidates These steps for the computation of hashtag recommendations are discussed in the following sections. 3.1
In order to be able to determine similar tweets, a similarity measure for the comparison of two at most 140 character long messages has to be introduced. This metric is used to rank the results gathered from searching similar tweets within the crawled data set. These similar messages are subsequently considered to contain valuable hashtag recommendation candidates. A straightforward solution is to use the term frequency - inverse document frequency measure for the comparison of tweets. In order to be able to use tf/idf for the computation of the similarity of tweets, the formula stated in Equation (1) is used. tf idft;d = tft;d idft (1) idft = log
jDj jfd : t 2 dgj (3)
In the case of searching a set of tweets, the set D of documents which have to be searched is the set of tweets in the system. The term frequency basically is the number of occurrences of a term t within a given document d (tweet). The inverse document frequency (idf) constitutes the importance of a term t within the whole set of documents which are searched. This is computed by taking the number of all documents (jDj) within the index and dividing it by the number of documents which contain the searched term (jfd : t 2 dgj). The computation of the tf/idf measure for a given search query (in our case the tweet inserted by the user), is subsequently accomplished by computing the sum of all tf/idf of all terms t occurring within the search query d: Pt in d tf idf (t). Futhermore, the nal score is increased if more of the terms of the query are matched. The nal set of similar tweets (those obtaining the highest tf/idf-based score ratings) is restricted to a set of tweets having a score above a certain treshold corresponding to the total number of results and the speci ed limit of total results. 3.2
After having obtained the set of the most similar messages to the tweet the user just entered, the hashtags are extracted from these tweets. These hashtags are referred to as hashtag recommendation candidates throughout the remainder of this paper. The ranking of these hashtag recommendation candidates is crucial for the success of recommendations. This is due to the fact that both the cognition of the user and the space available for displaying the recommendations is limited. In most cases a set of 5-10 recommendations is most appropriate which also correspond to the capacity of short-term memory (Miller, 1956). Therefore the top-k recommendations are shown to the user, where k denotes the size of the set of recommended hashtags presented to the user. This restricted set is based on the set of all hashtags which were extracted from the most similar messages to the newly created tweet. To present the most suitable top-k hashtags to the user, the recommendation candidates have to be ranked. For our approach, we evaluated three ranking methods, which can be summarized as follows: { OverallPopularityRank: This ranking approach is based on the popularity of the hashtag recommendation candidates. It basically considers the number of occurrences of the respective hashtag within our data set. The more popular a hashtag is overall, the higher the resulting rank of the hashtag. { RecommendationPopularityRank: This ranking method basically counts the occurrences of each hashtag within the set of recommendation candidates. The higher the number of occurrences, the more (similar) messages contain this hashtag. Therefore, it is likely that the hashtag is suitable for the tweet the user just entered. { SimilarityRank: This ranking method is based on the similarity value between the tweet entered by the user and the tweet which provides a hashtag recommendation candidate. The more similar the messages are, the more likely it is that the hashtags contained in this similar message are suitable for the tweet entered by the user. In the case that multiple tweets contain the hashtag which has to be ranked, the similarity of the most similar tweet is used. As a metric for the similarity of tweets, we used tf/idf as described in 3.1. 4
A recommendation engine prototype implementing this approach has been developed based on Apache's Lucene3 fulltext index. We used the fulltext index to store the crawled tweets which enabled us to nd the most similar messages by using Lucene's Search Index. 4.1
The evaluation was done on a CentOS release 5.1 machine with 8 GB of RAM. The evaluation of the hashtag recommendation approaches was conducted by performing a leave-one-out test. This test was based on the data set described in Section 2.1. Based on the crawled data set, we built a fulltext index comprising all 3.2 mil. cleaned messages without hashtags of this data set. From this index, we randomly chose 10,000 messages with less than six hashtags for each test run. For each of these messages, the contained hashtags were removed from the message and the resulting string was used as the input tweet for the recommendation engine. Naturally, the currently used tweet was removed from the Lucene Index and was not considered for the computation of recommendation candidates. Additionally, no retweets were used as test input tweets as search for similar messages would return an identical retweeted message which would obviously distort the evaluation results.
Based on the hashtag recommendations computed by the recommendation engine, we evaluted the three ranking methods described in 3.2. This was done by computing the precision and recall values of the top-k recommendations with k = 1, k = 2,..., k = 10 as described in the next section. 4.2
For the evaluation of the quality of the computed recommendations, we chose to use the precision and recall values of the recommendations. These metrics are de ned as follows: precision (Hrec) = jHrec \ Horigj jHrecj (4) 3 http://lucene.apache.org/ where Horiginal is the set of original hashtags which were removed from the original tweet and Hrecommended is the set of top-k recommendations. We performed ten test runs for each ranking method with k = 1, k = 2,..., k = 10. Each test run computed the respective average recall and precision value of 10,000 test tweets. Thus, the evaluation is based on the computation of 100,000 top-k recommendation sets for each ranking method. (5) 4.3
The experiments conducted showed that the approach is feasible of recommending suitable hashtags. The recall values for the top-k recommended hashtags can be seen in Figure 3. In this gure, the recall values for k (the number of recommended hashtags) being between 1 and 10 has been evaluated for the three considered ranking methods. This Figure shows that ranking based on the overall popularity of the hashtag (OverallPopularityRank) and also based on the popularity of the hashtag within the hashtag recommendation candidates (RecommendationPopularityRank) do not perform well. In contrast, SimilarityRank (ranking based on the similarity of the original tweet and the tweet containing the recommendation candidate) is able to perform signi cantly better. This ranking method leads to promising recall values which are well above the 40% mark for k > 2.
The precision values for the computed recommendation sets decrease with an increasing k. This is due the fact, that we only use test tweets with at most 5 hashtags per message. Therefore even a set of 10 recommendations featuring a recall value of 100% only results in a precision of 50% as ve of the ten recommended hashtags are not applicable as the original message only features ve hashtags.
Overall, the evaluations showed that our approach is suitable for the recommendation of hashtags. Another fact which can be derived from the evaluations is that our approach shows the best performance when restricting the set of recommended hashtags to k = 5, as the recall value does not improve much with additional recommendations and the precision value is still reasonable. 5
The recommendation of Twitter hashtags can bene t from various other elds of research. These areas are (i) tagging of online resources, (ii) traditional recommender systems, (iii) social network analysis and (iv) Twitter analysis. However, to the best of our knowledge, there is no other approach aiming at recommending hashtags to Twitter users.
The recommendation of tags of online resources like images, bookmarks or
bibliographic entries is directly related to our approach. Such approaches can
be based on the co-occurrence of tags, like e.g. in [
Kwak et al. [
As for the recommender system facilitated in our approach, many publications
are focused around collaborative ltering. The papers by Resnick [
In this paper, we presented an approach for the recommendation of hashtags within the Twitter microblogging application. The presented algorithm is based on the analysis of similar tweets and the hashtags contained in these tweets. Our evolutions were based on a self-crawled data set consisting of 12 million tweets. The preliminary evaluations showed promising results as the recall values of the recommendations are about 45-50%. Future work will include integrating the social graph of Twitter users for the recommendation. Furthermore, the ranking of hashtag recommendation candidates is also subject to further research and improvements. The enhancement of the recommendations of synonymous hashtags based on a semantic analysis for the exclusion of synonymous hashtags and their recommendation is also part of future work.