With the growing popularity of social networking services, real time short messages, such as Facebook news feeds and Twitter tweets, are becoming increasingly important information sources. People use these services to search for and consume content about interesting topics and events. Given a keyword search for a certain topic, simply returning those messages often does not give a comprehensive summary of the topic, primarily due to the brevity and redundancy of the messages. To address this challenge, we propose a topic centric entity extraction system where interesting entities pertaining to a topic are mined and extracted from short messages returned as search results on the topic. Speci cally, we leverage signals from three main aspects: message content, social connections (i.e., message sender's follower network), and referenced Web pages (i.e., URLs embedded within the messages), and propose: 1) page ranking algorithms for identifying relevant pages embedded within the messages; and 2) entity ranking algorithms for identifying relevant entities extracted from those URLs. Comprehensive experiments using real Twitter data show that our ranking algorithms are e cient and outperform baseline algorithms signi cantly in terms of extraction quality.
Social networking sites such as Twitter [
A typical information exploration paradigm on those social networking sites is to search (using keywords) for information related to a certain topic of interests to the user (e.g., Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. This article was presented at The Workshop Very Large Data Search (VLDS) 2011.
Copyright 2011 VLDB Endowment. \Libya"), and browse through the messages returned. While such results are useful, going through them for many popular topics su ers from the well known information overload problem, i.e., too many messages are returned and multiple messages are often conveying the same information. A conventional approach is to rank those messages and return the most relevant ones rst. However, unlike Web pages, those social text messages are very short (e.g., Twitter has a length limitation of 140 characters on individual posts), and current ranking mechanisms that are designed for Web pages, do not perform well on those short messages. Furthermore, simply reading through a few messages ranked at the top typically cannot provide a user with enough information about the topic. In this paper, we propose an alternative approach, where we present the users with a summary of the topic of interest in the form of a set of participating entities and relevant URLs.
Speci cally, we address the following problem: given a social text stream associated with a topic of interest (de ned as a keyword query), e ciently identify a ranked list of URLs and entities associated with the given topic. The following example provides an overview of the system that we have built to solve this problem.
Example Consider a user looking for recent news about \Tiger Woods." She would submit the hashtag #tigerwoods to the system, which in turn contacts Twitter through its API and obtains a large list of recent tweets associated with the requested topic. The system then extracts URLs (e.g., http://bit.ly/lsHHWP) from those tweets, ranks them, and prunes away those that are considered to be not useful. The remaining URLs are sent to the entity extraction system1, which extracts entities from those URLs. Finally, the extracted entities are ranked and returned to the user as the summary result. For #tigerwoods, this will contain \Elin Nordegren" and \Rachel Uchitel" as people, \Sweden" and \Orlando" as locations, etc.
As this example shows, we adopt Twitter [
Since tweets are restricted to 140 characters, users have come up with creative ways to maximize information sharing and one common practice is to embed shortened URLs in tweets (as the example illustrates). This presents us with two competing alternatives as the source for our entity extraction: the content of the tweets themselves or the content of the URLs mentioned within the tweets. We analyze both approaches and show that URL-based entity extraction provides signi cantly higher coverage for a variety of topics than tweet-based entity extraction. However, performing entity extraction from URLs within tweets presents two signi cant challenges. First, not all URLs in tweets are applicable to a topic and therefore we must detect the relevant ones. Second, fetching the page content of a URL and performing extraction over the content is an expensive process and therefore we must limit the number of URLs to be processed. Similar challenges are also evident when entities are extracted: they must also be ltered and ranked before they are displayed to the user.
Main contributions of the paper include: First, we introduce the novel social updates exploration paradigm of presenting users with a set of entities and URLs corresponding to a given topic. Second, we design and implement a machine learning based URL ranking component to identify embedded URLs that are relevant to the topic from the social updates. Third, we design and implement an entity ranking component that leverages information extraction and machine learning techniques to extract and rank entities that are relevant to the topic from those URLs. Finally, we provide a comprehensive evaluation of our approach using a range of topics over real Twitter data sets.
The remainder of this paper is organized as follows. Section 2 describes recent studies that are related to our work. Section 3 describes the machine learning based URL Ranker that aims to identify relevant URLs from the tweets of a given topic. Section 4 describes our Entity Ranker, which aims to identify relevant entities among those extracted from the relevant URLs. Both components use machine learning techniques and we will focus on describing the set of features we employed. In Section 5, we describe the set of comprehensive experiments conducted to evaluate the quality of the results produced by our system. Finally, we conclude in Section 6.
While our work is, to the best of our knowledge, the rst
to study the problem of searching for a comprehensive list
of entities from social updates for a given topic, there are a
few recent studies focusing on ranking Twitter content. For
example, in [
Entity extraction and ranking is another area that is closely
related to our work. For example, [
Given our goal of extracting topic-centric entities, one of the rst questions is where the entities should be extracted from. There are two main approaches. The rst approach is to directly apply the entity extraction on the textual content of the social updates (i.e., tweets), a strategy we call SourceT S. The second approach is to use the URLs embedded in those tweets and perform entity extraction on the page content of those URLs. The URL-based approach is more costly since it involves the additional step of fetching the page content. However, as our experimental analyses show in Section 5.1, the URL-based approach achieves substantially higher recalls with reasonable performance overhead. Therefore, we make the decision to leverage the URLs for entity extraction instead of simply relying on the tweets content alone.
Given the facts that there are often a large number of
URLs embedded in the tweets (especially for popular topics),
performing entity extraction on all those URLs is
impractical. Our focus in this section is therefore on identifying good
URLs from which entities can be extracted. We note that
while URL recommendation based on user's interests has
been studied previously [
We propose four main strategies for ranking informative URLs as outlined below. For each of those strategie, we assume a topic in the form of a hashtag (e.g., #tigerwoods) is given by the user and used to fetch the recent tweets containing the hashtag, until up to N URLs have been found in the tweets. We then aim to identify k most informative URLs, from which entities will be extracted2.
Fresh URLs (SourceF U ): We fetch the latest k URLs available in the Twitter stream and use them as the sources for entity extraction. This corresponds to the intuition that more recent URLs are more important.
Popular URLs (SourceP U ): We fetch the k URLs with most frequent appearances in the tweets. This corresponds to the wisdom of crowd intuition that URLs endorsed by more users are more important.
Authoritative URLs (SourceAU ): We fetch the k URLs that appeared in the tweets of users with the largest number of followers. This corresponds to the intuition that more authoritative users provide more useful information.
Mixed Feature URLs (SourceMF U ): Finally, we adopt
2N and k are empirically set to 100 and 15, respectively, in
our experiments.
a machine learning based ranking strategy and train an SVM
(Support Vector Machine) classi er to rank URLs based on
various features (described below). The k URLs with the
highest probability estimates [
The rst three strategies can be implemented in a straightforward way. In the rest of this section, we describe in details the features being used in the SourceMF U strategy, some of which are novel features proposed for rst time in this study.
Let S = ft1; t2; :::; tkg be the sequence of tweets that are retrieved using the topic hashtag, and let Lall = fl1; l2; :::; lmg be the set of URLs embedded in those tweets. For each URL l 2 L, the set T (l) = ft 2 S j t contains lg denotes all the tweets in S that contains l. Let ut be the publisher of tweet t, the set U (l) = fut j t 2 T (l)g denotes the set of authors who posted at least one tweet containing l. 3.1
We consider the following two tweet content based features for each URL l under consideration.
Subject Speci city, SS(l), is a novel feature that is computed as the average number of hashtags (i.e., topics) within each t 2 T (l). Intuitively, the more speci c an URL is to the given topic, the more likely it contains useful information about the topic.
Spam Likelihood, SL(l), measures how likely the URL
is a spam URL. Here we adopt a simple strategy based on the
set of pre-de ned spam phrases (e.g., \tweet to win"), and l
is marked as spam if at least t tweets in T (l) contain at least
one of the spam phrases. (t is usually set to a small
number such as 1 or 2.) Note that while more advanced spam
detection approaches such as [
Next, we look at some of the key properties of the candidate URL l itself.
Link Popularity, LP (l), measures how popular l is within the full social stream S, and is computed as LP (l) = jT (l)j . jSj Note that URL shorteners (e.g., bit.ly) are frequently employed to shorten the URLs so that they can t within the tweet length limit. To con rm two URLs being the same, we sometimes need to ping the shortener service when they are shortened by di erent shortener services.
Multimedia Likelihood, M L(l), measures how likely the URL points to a multimedia le such as a picture, video, etc. This feature is particularly interesting since the goal of URL ranker is to identify URLs that can help achieve the overall goal of extracting entities. As a result, URLs pointing to popular multimedia portals such as ickr and youtube or multimedia speci c sites such as twitpic and yfrog, while interesting, are not informative in this setting. We identify a dictionary of such domains and use this dictionary to predict whether a URL is likely to point to a multimedia page or a content page. 3.3
Tweet publishers' social characteristics play an important role in the quality of tweets. For this reason we choose to consider a comprehensive set of publisher social features for the candidate URL l.
Publisher Experience, P E(l), measures the average tenure of the publishers. Speci cally, let P E(u) be the number of days the publisher u has been a Twitter user, P E(l) = jU1(l)j Pu2U(l) (P E(u)).
Publisher Statuses, P S(l), which measures the average number of message each publisher in U (l) has contributed to Twitter. Let P S(u) be the number of messages the publisher u has published since joining Twitter, P S(l) = jU1(l)j Pu2U(l) (P S(u)).
Publisher Activity, P A(l), measures how active the publishers are on Twitter. Let P A(u) = PPES((uu)) represent how active of a publisher is on Twitter, P A(l) = jU1(l)j P (P A(u)).
Publisher Importance, P I(l), measures how important the publishers are within the Twitter communities. The importance is approximated with the number of followers a publisher has. Let P I(u) represent the number of Twitter followers the publisher u has, P I(l) = jU1(l)j Pu2U(l) (P I(u)).
Publisher Diversity, P D(l), is the fraction of the number of distinct users over the total number of tweets in T (l). Intuitively, it is a bad sign if all the tweets associated with the URL are published by a few publishers.
Publisher Entropy, P E(l), is a novel and more advanced measure of publisher diversity. Let jT u(l)j be the number of tweets in T (l) that are published by u, we can compute P E(l) = Pu2U(l) jTjTu((ll))jj log jTjTu((ll))jj .
Publisher Sociability, P S(l), measures the social connectivity of the publishers. We de ne the friends of publisher u, F (u), as the number of users who follows u and who u also follows. Hence, P S(l) = jU1(l)j Pu2U(l) (F (u)).
Follower to Followee Ratio, F F R(l), approximates the \celebritiness" of the publisher and is computed as F F R(l) = 1 P #users following u jU(l)j u2U(l) #users u follows . u2U(l)
The set of top URLs as identi ed by the URL Ranker are
submitted to AlchemyAPI [
Let S be the sequence of tweets as de ned in Section 3 and Ltop = fl1; l2; :::; lmg be the top URLs as ranked by the URL Ranker. Let E = fe1; e2; :::; eng be the set of entities extracted from Ltop and L(e) Ltop (e 2 E) be the set of URLs from which e is extracted and T (e) = ft j 9l 2 L(e) s.t. l is embedded in tg. Finally, let f(e;l) be the term frequency of entity e in the content of URL l, and h(e;l) = 1 if e can be extracted from the title of l.
We focus on three large categories of features: text features, which measure how important the entity is to the pages where it is extracted from; tweet features, which relate to the tweets where the entity is indirectly (i.e., through the embedded URL) extracted from; social features, which relate to the publishers who posted those tweets. A number of those features are proposed for the rst time in this study. where we take the logarithmic so that the feature is not dominated with extremely high frequencies.
Entity Distribution, ED(e), is a novel feature that measures the distribution of entities on the pages they were extracted from, and is computed as:
X
X fe;c log fe;c ED(e) = l2L(e) c2l jL(e)j where the content of each URL is divided into 10 equal sized chunks, c1; c2; :::; c10, and fe;c measures the frequency of the entities within the chunk c. Intuitively, only entities that are central to the page will have a high distribution value over the page and only entities that are central to the topic will have high distribution value across all pages.
Inverted Document Frequency, IDF (e), which is the equivalent of traditional term IDF and is computed as: IDF (e) = log jfl j l 2 L ^ fe;l > 0gj jLj
Is In Title Indicator, IIT i(e), which indicates the appearance of e inside a page title and is computed as: IIT i(e) = 1 : 9l 2 L(e); h(e;l) > 0 0 : otherwise 4.2
This set of features relate to the tweets that the candidate entity e is extracted from:
Subject Speci city, SS(e), is similar to SS(l) and measures the average number of hashtags with each t 2 T (e).
URL Frequency, U F (e), measures the average frequency the URLs containing e and is computed as U F (e) = jLLP(e(l))j ; l 2 L(e), where LP (l) is the Link Popularity as de ned earlier.
Hashtag in Entity, HIE(e), indicates whether the entity name overlaps with the topic hashtag itself. For example, the entity \National AIDS Commission" overlaps with the topic hashtag #aids, and therefore HIE(\National AIDS Commission") = 1 for the topic #aids.
Is In Tweet, IIT w(e), indicates whether e is found in any tweet t 2 T (e) directly. 4.3
Finally, we apply to the candidate entity e the similar set of social features that we apply to the URL as in Section 3.3. For completeness, we list the explicit de nitions here. Note that U (e) is the set of publishers who posted at least one ##uusesresrsfuollfoowllionwgsu . tweet t 2 T (e), and P E(u); P S(u); P A(u); P I(u); and F (u) are de ned in Section 3.3.
Publisher Experience, P E(e) = jU1(e)j Pu2U(e) (P E(u)). Publisher Statuses, P S(e) = jU1(1e)j Pu2U(e) (P S(u)). Publisher Activity, P A(e) = jU(e)j Pu2U(e) (P A(u)). Publisher Importance, P I(l) = jU1(e)j Pu2U(e) (P I(u)). Publisher Sociability, P S(e = jU1(e)j Pu2U(e) (F (u)).
Follower to Followee Ratio, F F R(e) = jU1(e)j Pu2U(e) 5.
We implemented our system as an application over Twitter using Python/Java and conducted an extensive set of experiments to evaluate the quality of the topic centric entity search results. All experiments are run on a Windows XP machine with 1GB RAM, 1.6GHz Intel Core Duo CPU, and 20Mbps Internet connection.
Tweet Data Set: We chose 20 topics that were newsworthy over a week time period in 2010 (November 1926, 2010) using Google Trends and identi ed corresponding most popular hashtags for each topic. Based on those hashtags, we fetched 380; 000 tweets using the Twitter API. We discarded any tweet whose publishers are no longer with Twitter, which left us with 350; 000 tweets. Among those, nearly 50% of the tweets (177; 000) contain embedded URLs.
Training/Testing Data: For each of those 20 topics, we
asked 10 volunteers to gather as many relevant entities as
possible through any medium they considered as appropriate
(newspapers, blogs, wikipedia, etc.). The result is a set of
golden entities for each topic. Among the 20 original topics,
10 topics involve multiple entities, and they are selected for
further study. For each of those 10 multi-entity topics, 100
most recently embedded URLs were extracted and rated by
the volunteers based on the URLs' relevances to the topic on
a scale of 0 to 2, representing \not relevant", \somewhat
relevant", \very relevant", respectively. This URL rating data is
used to evaluate our URL Ranker. Similarly, we performed
entity extraction using the Alchemy API [
Examples: Table 1 illustrates two example topics with top URLs and entities rated by the users. The rst one is the insider trading investigation involving various former employees of SAC Capital, which is founded by Steve Cohen. The second one is on the decision by Pope Benedict XVI to allow the use of condom for AIDS prevention. Our system is able to successfully identify most of the URLs and entities that are considered relevant.
Methodology: We perform 10-fold cross validation for the quality experiments. In each run, both rankers (URL and Entity) are trained on the rating data of 9 topics and tested on the remaining topic. The average number across all 10 runs are reported. We use nDCG@K (normalized discounted cumulative gain) as the measure to evaluate the quality of the various algorithms. 5.1
#insidertrading #aids http://goo.gl/wFxuz http://on.wsj.com/cPdOg9 http://viigo.im/5rcV http://hu .to/gWAPIC http://bbc.in/9mTIeA http://bit.ly/bd8ieh location
Vatican Rome organization
UN AIDS Agency Catholic Church person
Steven Fortuna Steve Cohen Howard Ja e Pope Benedict Peter Seewald
The rst question we ask is whether extracting from the page content of the URLs embedded in the tweets is worth the e ort, i.e., can we actually get a better coverage of the entities extracting from the URLs than simply extracting from the tweets? The answer is a resounding yes. As Table 2 shows, the four strategies (Section 3) that extract entities from URLs all achieve a signi cantly higher coverage (i.e., recall) of the golden entities for the topics than the strategy (SourceT S) that purely extracts entities from the tweets, even though the latter strategy goes over much more tweets3. The strategy that employs the machine learning approach achieves the highest increase in coverage at over 50%. It is interesting to see that authoritative URLs (SourceAU ) performs worse than popular URLs (SourceP U ) as an entity source, probably because the most authoritative URLs may be important but have highly overlapping content.
Furthermore, the much improved coverage comes at a reasonable performance overhead. As shown in Figure 1, extraction over the URL content incurs only about 16% overhead into the overall entity extraction latency (i.e., from a query topic being issued to the set of entities being returned). There are two main reasons for this surprisingly low overhead. First, content fetching can be done in parallel, which means the additional latency cost is only one page fetch even though 100 pages are retrieved. Second, the cost of actual entity extraction dominates the overall latency and therefore an additional page fetch is less signi cant in comparison4. 5.2
In this experiment, we compare the machine learned URL
ranking algorithm (M F U ) against all three baseline
algorithms, Fresh URL (F U ), Popular URL (P U ), and
Authoritative URL (AU ) in terms of the quality of the URL rankings
using nDCG. For M F U , the SVM classi er is trained using
libsvm [
In this experiment, we compared the machine learned
entity ranking algorithm against the two baseline algorithms:
3In this experiment, we do not rank the entities and use all
entities extracted from the top-15 URLs.
4We believe this is the case for the majority of advanced
extraction systems currently available.
random, which randomly chose k entities from the set of
extracted entities, and alchemy, which uses the extraction
condence (provided by the Alchemy API) to rank the entities.
We further provide detailed analysis of the importance of
each category of features (T EXT , T W EET , SOCIAL, see
Section 4) by using all possible combinations of the feature
categories. All classi ers are naive Bayes and trained using
Weka [
G C D N e g a vr e A 0.8 0.7 0.6 0.2 0.1 0
As shown in Figure 3, the machine learning based rankings performs signi cantly better than the two baseline algorithms in terms of nDCG. The extraction con dence based ranking performs identically with the random ranking, indicating that extraction con dence is a poor measure of how relevant the entity is to the given topic. Among the three categories of features, both T EXT and T W EET are su cient to achieve good results. In fact, when k = 10, T EXT features alone can achieve very good results. Contrary to what we believed prior to this study, ranking with SOCIAL features alone performs noticeably worse than rankings with at least some T EXT or T W EET features, indicating that popular Twitter users are not necessarily the best sources for a comprehensive summary of a topic.
Finally, gure 4 illustrates the precision-recall curve over the same set of rankings, where the recall is computed as the percentage of entities each ranking recovered over the golden set of entities for each topic. Similar to the nDCG study, all machine learned rankings perform signi cantly better than the baseline rankings and T EXT and T W EET are the more important feature categories than the SOCIAL features. 6.
In this study we design and implement a system to search for the most relevant named entities of a given topic from social updates. Our approach consists of two main components, URL Ranker and Entity Ranker. The former extracts and ranks top URLs from the sequence of social updates based on various features, while the latter leverages existing entity extraction to extract entities and machine learning techniques to rank the entities. An extensive set of experiments show that both our ranking algorithms signi cantly outperforms their respective baseline algorithms. We also study the various categories of features for entity ranking and show that text and tweet features are more important than social features for entity search. 7.