Streams of user-generated content in social media exhibit patterns of collective attention across diverse topics, with temporal structures determined both by exogenous factors and endogenous factors. Teasing apart different topics and resolving their individual, concurrent, activity timelines is a key challenge in extracting knowledge from microblog streams. Facing this challenge requires the use of methods that expose latent signals by using term correlations across posts and over time. Here we focus on content posted to Twitter during the London 2012 Olympics, for which a detailed schedule of events is independently available and can be used for reference. We mine the temporal structure of topical activity by using two methods based on non-negative matrix factorization. We show that for events in the Olympics schedule that can be semantically matched to Twitter topics, the extracted Twitter activity timeline closely matches the known timeline from the schedule. Our results show that, given appropriate techniques to detect latent signals, Twitter can be used as a social sensor to extract topical-temporal information on real-world events at high temporal resolution.
Streams of user-generated content from social media and microblogging systems exhibit patterns of collective attention across diverse topics, with temporal structures determined both by exogenous factors, such as driving from mass media, and endogenous factors such as viral propagation. Because of the openness of social media, of the complexity of their interactions with other social and information systems, and of the aggregation that typically leads to the observable stream of posts, several concurrent signals are usually simultaneously present in the post stream, corresponding to the activity of different user communities in the context of several different topics. Making sense of this information stream is an inverse problem that requires moving beyond simple frequency counts, towards Copyright c 2014 held by author(s)/owner(s); copying permitted only for private and academic purposes.
Published as part of the #Microposts2014 Workshop proceedings, available online as CEUR Vol-1141 (http://ceur-ws.org/Vol-1141) the capability of teasing apart latent signals that involve complex correlations between users, topics and time intervals.
The motivation for the present study is twofold. On the one hand, we want to devise techniques that can reliably solve the inverse problem of extracting latent signals of attention to specific topics based on a stream of posts from a micro-blogging system. That is, we aim at extracting the time-varying topical structure of a microblog stream such as Twitter. On the other hand, we want to deploy these techniques in a context where temporal and semantic metadata about external events driving Twitter are available, so that the relation between exogenous driving and time-varying topical responses can be elucidated. We do not regard this as a validation of the methods we use, because the relation between the external drivers and the response of a social system is known to be complex, with memory effects, topical selectivity, and different degrees of endogenous social amplification. Rather, we regard the comparison between the time-resolved topical structure of a microblog stream and an independently available event schedule as an important step for understanding to what extent Twitter can be used as a social sensor to extract high-resolution information on concurrent events happening in the real world.
Here we focus on content collected by the Emoto project1 from Twitter during the London 2012 Olympics, for which a daily schedule of the starting time and duration of sport events and social events is available and can be used for reference. In this context, resolving topical activity over time requires to go beyond the analysis and characterization of popularity spikes. A given topic driven by external events usually displays an extended temporal structure at the hourly scale, with multiple activity spikes or alternating periods of high and low activity. We aim at extracting signals that consists of an association of (i) a weighted set of terms defining the topic, (ii) a set of tweets that are associated to the topic, together with the corresponding users, and (iii) an activity profile for the topic over time, which may comprise disjoint time intervals of nonzero activity. We detect time-varying topics by using two independent methods, both based on non-negative matrix or tensor factorization. In the first case we build the full tweet-term-time tensor and use non-negative tensor factorization to extract the topics and their activity over time. We introduce an adapted factorization technique that can naturally deal with the special tensor structure arising from microblog streams. In the second case, which in principle affords on-line computation, we build tweet-term frequency matrices over consecutive time intervals of fixed duration. We apply non-negative matrix factorization to extract topics for each time interval and we track similar topics over time by means of agglomerative hierarchi
We then apply both methods to the Twitter dataset collected during the Olympics, which reflects the attention users pay to tens of different concurrent events over the course of every day. We focus on topical dynamics at the hourly scale, and find that for those sport events in the schedule that can be semantically matched to the topics we obtain from Twitter, the activity timeline of the detected topic in Twitter closely matches the event timeline from the schedule.
This paper is structured as follows: Section 2 reviews the literature on collective attention, popularity, and topic detection in microblog streams. Section 3 describes the Olympics 2012 Twitter dataset used for the study, the event schedule we use as an external reference, and introduces some notations and conventions used throughout the paper. Section 4 and Section 5 describe the two techniques we use to mine time-varying topical activity in the Twitter stream. Section 6 discusses the relation between the time-varying topics we obtain and the known schedule of the Olympics events for one representative day, and provides some general observations on the behavior of the two methods. Finally, Section 7 summarizes our findings and points to directions for further research.
The dynamics of collective attention and popularity in social media
has been the object of extensive investigation in the literature.
Attention can suddenly concentrate on a Web page [
Within the broad context of social media, Twitter has emerged as
a paradigmatic system for the vision of a “social sensor” that can be
used to measure diverse societal processes and responses at scale [
As we will discuss in detail, microblog activity can be represented
using a tweet-term-time three-way tensor, and tensor factorization
techniques can be used to uncover latent structures that represent
time-varying topics. Ref. [
The following notations are used throughout the paper. Scalars are denoted by lowercase letters, e.g., x, and vectors are denoted by boldface lowercase letters, e.g., x, where the i-th entry is xi. Matrices are denoted by boldface capital letters, e.g., X, where the i-th column of matrix X is xi, and the (i, j)-th entry is xij . Third order tensors are denoted by calligraphic letters, e.g., A. The i-th slice of A, denoted by Ai, is formed by setting the last mode of the third order tensor to i. The (i, j)-th vector of A, denoted by aij , is formed by setting the second to last and last modes of A to i and j respectively, and the (i, j, k)-th entry of A is aijk.
The Emoto dataset consists of around 14 million tweets collected during the London 2012 Summer Olympics using the public Twitter Streaming API. All tweets have at least one of 400 keywords, including common words used in the Olympic Games – like athlete, olympic, sports names and twitter accounts of high followed athletes and media companies. Tweets were collected during all the interval of 17 days comprising the Olympic Games, from July 27 to August 12 2012.
In order to investigate the relation between the extracted time- varying topics and the sport events of the Olympic Games, we use the schedule available on the official London 2012 Olympics page2, where the starting time and duration of most events is reported together with metadata about the type of event (discipline, involved teams or countries, etc.)
For the text analysis performed in this paper, URLs are removed from the original tweet content. The remaining text is used to build a vocabulary composed of the most common 30,000 terms, where each term can be a single word, a digram or a trigram. 352 common words of the English language are also removed from the vocabulary.
In order to localize Twitter users, we examine the user profile descriptions and use an adapted version of GeoDict3 to identify, if possible, the user country. To study the relation between the extracted topical activity and the schedule of the Olympic events, we focus on tweets posted by users located in the UK, only. This allows us to avoid potential confusion arising from tweets posted in countries, such as the USA, where Olympics events were broadcasted with delays of several hours due to time zone differences. This selection leaves us with a still substantial amount of data (about 2http://www.london2012.com/schedule-and-results/ 3https://github.com/petewarden/geodict one third of the full dataset) and simplifies the subsequent temporal analysis, even though it probably oversamples the attention payed to events that involved UK athletes.
For the scope of this study, we represent the data as a sparse thirdorder tensor T ∈ RI×J×K , with I tweets, J terms and K time intervals. We aggregate the tweets over 1-hour intervals, for a total of K = 408 intervals. The tensor T is sparse: the average number of terms (also referred as features in the following) for each tweet is typically no more than 10, compared to the 30k terms of our term vocabulary. Moreover, as each tweet is emitted at a given time, each interval k has a limited number of active tweets, Ik. A tensor slice Tk ∈ RI×J is a sparse matrix with non-zero values only for Ik rows. Tk represent the sparse tweet-term matrix observed at time k. The term values tijk for each tweet i are normalized using the standard Term Frequency and Inverse-Document Frequency (TF-IDF) weighting, tijk = tf(i, j) × idf(j), where tf(i, j) is the frequency of term j in tweet i, and idf(j) = log 1+|{|dD:j|∈d}| where |D| is the total number of tweets and |{d : j ∈ d}| is the number of tweets where the term j appears.
The methods that we present in this paper are able to extract
topicaltemporal structures from T . Such topical-temporal structures can
be represented a stream matrix S ∈ RR×K with R topics and K
intervals. Each component R is also characterized by a term-vector
h ∈ RJ that defines the most representative terms for that
component. In order to visualize such topical-temporal structures
represented as a stream matrix, we use the method described by Byron
and Wattenberg [
As explained in section 3, the tensor T ∈ RI×J×K with I tweets, J terms and K intervals is a natural way to represent the tweets and their contents with respect to the time. The tensor has the advantage to directly encompass the relationship between tweets posted at different hours and consequently between topics of the different hours. The tensor factorization as described below allows to uncover topics together with their temporal pattern.
Before describing the process of factorization itself and its output, one needs to introduce the concept of canonical decomposition (CP). CP in 3 dimensions aims at writing a tensor T ∈ RI×J×K in a factorized way that is the sum of the outer product of three vectors:
RT T = X r=1 ar ◦ br ◦ cr (1) where the smallest value of RT for which this relation exists, is the rank of the tensor T . In other words, the tensor T is expressed with a sum of rank-1 tensors. The set of vectors a{1,2,...,R} (resp. b{1,2,...,RT },c{1,2,...,RT }) can be re-written as a matrix A ∈ RI×RT (resp B ∈ RJ×RT ,C ∈ RK×RT ) where each of the RT vectors is a column of the matrix. The decomposition of Eq. 1 can also be represented in terms of the three matrices A, B, C as JA, B, CK. A visual representation of such a factorization, also called Kruskal decomposition, is displayed on Fig. 1.
Regarding the extraction of topics, the aim is not to decompose the tensor in its exact form but to approximate the tensor by a sum of rank-1 tensors with a number of terms smaller than the rank of the original tensor. This number R corresponds to the number of topics that we want to extract (see Fig. 1). Such an approximation of the tensor leads to minimize the difference between T and JA, B, CK: (2) 2
Am,Bin,C kT − JA, B, CKkF where kk is the Frobenius norm. We transform the 3-dimensional problem (Eq. 2) in 2-dimensional sub-problems by unfolding the tensor T in three different ways. This process called matricization gives rise to three modes X(1), X(2), X(3). The mode-n matricization consists of linearizing all the indices of the tensor except n. The three resulting matrices have respectively a size of I ×J K,J ×IK and K ×IJ . Each element of the matrix X(i=1,2,3) corresponds to one element of the tensor T such that each of the mode contains all the values of the tensor. Due to matricization, the factorization problem given by Eq.1 can be reframed in factorization of the three modes. In other terms, maximizing the likelihood between T and JA, B, CK is equivalent to minimizing the difference between each of the mode and their respective approximation in terms of A, B, C. The factorization problem (PARAFAC) in Eq.2 is converted to the three following sub-problems where we added a condition of non-negativity of the three modes: min kX(1) − A(C A≥0 min kX(2) − B(C B≥0 min kX(3) − C(B C≥0
B)T k2F
A)T k2F
A)T k2F
where is the Khatri-Rao product which is a columnwise
Kronecker product, i.e. such that C B = [c1 ⊗ b1c2 ⊗ b2 . . . cr ⊗ br].
If C ∈ RK×R and B ∈ RJ×R, then the Khatri-Rao product
C B ∈ RKJ×R. In our case of study, A, B, C will give each
access to a different information: A allows to know at which topic
belongs a tweet, B gives the definition of the topics with respect to
the features and C gives the temporal activity of each topic.
Several algorithms have been developped to tackle the PARAFAC
decomposition. The two most common are one method based on
the projected gradient and the Alternating Least square method
(ALS). The first one is convenient for its ease of implementation
and is largely used in Singular Value Decomposition (SVD) but
converges slowly. In the ALS method, the modes are deduced
successively by solving Eq 5. In each iteration, for each of the
sub(3)
(4)
(5)
problem, two modes are kept fixed while the third one is computed.
This process is repeated until convergence. In our case, we use a
nonnegativity constraint to make the factorization better posed and
the results meaningful. One thus uses nonnegative ALS (ANLS
[
We cannot directly perform the NTF on the tensor [Tweets × Features × Interval] built as explained aboved as this tensor has a “block-disjoint” structure peculiar to the tweets. Indeed each tweet has non-zero values only at one interval because a tweet is emitted only at a given time. Each interval k has only Ik active tweets. In each slice Tk of the tensor, only Ik rows have meaningful values. So, we are only interested in reproducing the tensor part which contains the meaningful values. In order to focus on these meaningful values, one needs to consider an adapted version of the tensor T . We first consider the tensor T built as explained above. We generate a first set of matrices A, B, C which could approximate the tensor. At the next step, one tries to decompose a tensor T¯ where the values are a combination of the values of T¯ and of the values of JA, B, CK. More exactly, this tensor has the same size than T and the same values than T for the rows Ik of each slice T¯k. The complementary values are given by JA, B, CK. In other terms, at each step, the tensor that we approximate is updated by: T¯ = T
W + (1 − W )JA, B, CK (6)
where is the Hadamard product (element-wise product) and W is
a binary tensor of the same size than T with 1-values only when the
values of T at this position are meaningful. The particular
structure of the tensor (disjoint blocks in time) could be perceived as a
“missing values” problem in the tensor, this problem has been for
example tackled in [
Concretely, the implementation is an adaptation of a Matlab
program [
We calculate the strength of each topic with respect to the time by using both the information about the link between each topic and each tweet and about temporal pattern of the topics. These informations are available through A and C and the consequent strength of a topic r on each interval of time k is given by: srk =
X air ∗ ckr i|k (7) where Pi|k is a sum over the tweets indexed by i occurring at the interval indexed by k. The set of elements s{r,k} with r = J1, RK and k = J1, KK forms the stream matrix S. Each topic is then defined by a terms vector and each of this term vector is given by a column of B.
Wm,iHn kTk − W(k)H(k) 2
kF ,
where kk is the Frobenius norm, subject to the constraint that the
values in W(k) and H(k) must be non-negative. The non-negative
factorization is achieved using the projected gradient method with
sparseness constraints, as described in [
Ik zfk = X wi(fk)
F i=1 P wi(fk0) f0=1 where zfk is the strength of factor f at interval k.
In order to track topics over time, we need to merge components
into topics depending on how similar they are. Since each
component is defined by a term vector, we can calculate a similarity
matrix of all possible pairs of term vectors using cosine similarity.
This matrix is fed to a standard agglomerative hierarchical
clustering algorithm, known as UPGMA [
When constructing the stream matrix, the number of topics R in the stream matrix is given by the number of clusters generated by the clustering step. In order to calculate the entries srk of the resulting stream matrix S, we aggregate the strengths of the clustered components. We build a stream matrix S ∈ RR×K , with R topics and K intervals, given by (8) (9) (10) srk =
X f∈Crk zfk Finally, we extract the term vectors that are associated to each cluster. Each cluster will be associated to a term vector h(rk) ∈ RJ that is the average of all term vectors h(fk) associated to that cluster in the component clustering step.
We now move to the analysis of the London 2012 Twitter dataset and its relation with the known schedule of the Games. We focus on one representative day, July 29th, during which several sport events took place at different times and concurrently. We use both topic detection methods, show the signals they extract, and check to what extent they are capable of extracting signals that we can understand in terms of the schedule.
The topic detection methods are set up as follows. For the masked NTF method, we decompose the tensor using a fixed number of components, using a tolerance value of 10−4 for the stopping condition, and limiting the number of iterations to 50. For the agglomerative NMF method, we decompose each interval matrix using a fixed number of components. We use a tolerance value of10−4 for the stopping condition, and limit the number of iterations to 20. We use 250 topics for the Masked NTF, and 50 components per time intervals in the Agglomerative NMF.
Figure 2 shows a streamgraph representation of time-varying topics extracted using the two methods we have discussed. Two global activity peaks are visible in both streamgraphs: the peak at about 2.30pm UTC was triggered when Elizabeth Armistead won the silver medal in road cycle; the peat at about 7pm UTC is driven by the bronze medal in 400m freestyle to Rebecca Adlington. In the stream graphs, for clarity, each topic is annotated using only its topmost weighted term. This makes it difficult to assess a visual correspondence between the same topics across the two representations, as the term with top weight may be different for the two term vectors even though the vectors are overall very similar (in terms of cosine similarity). On closer inspection, many precise correspondences can be established between the topics extracted by the Masked NTF method and those extracted by the Agglomerative NMF method: for example, the topic armistead in the top streamgraph matches the topic congratulation in the bottom one. An interactive streamgraph visualization of the London 2012 Twitter dataset is available at http://www.datainterfaces.org/projects/emoto/.
In order to show the possible correspondence between the extracted topics and sport events, we manually annotate the schedule collected from the official London 2012 Olympics page for July 29th, 2012. As the number of events in a day can be substantial and we want to focus on events with higher impact on social media, we retain events that are either finals or team sports match. We annotate each event with a set of at most three terms extracted from the schedule, as described in Section 3. For a team sport, we use the sport name and the countries of the two teams, otherwise, we put the name of the sport and its characteristics, e.g., the discipline for swimming.
For each event, we use a matching criteria to select one of the extracted topics from each of the set of topics produced by the methods. Since we want to select a topic in which all event annotated terms appear with a high weight in its term vectors, we define our matching score based on the geometric average of the weights of the event annotated terms in the topic’s term vectors: hwi = pnhw1r hw2r . . . hwnr (11) For Masked NTF, for each event, we choose the topic with the highest corresponding geometric average hwi. In the agglomerative NMF case, for each event, we choose the topic with the highest corresponding geometric average hwi weighted by log(n) where n is the number of components in the selected cluster. We use log(n) in order to favor the selection of clusters with a higher number of aggregated components, otherwise the most detailed clusters which aggregates only one component are always selected. Since the Agglomerative NMF method produces a tree structure in which each node agglomerates a set of components and represents topic activity, we have to calculate such matching result for each node, and select the node for which such matching result is the highest.
At this point, we have, for each event, a topic which was selected in each method, and the corresponding matching result. In Figure 3, we show the schedule events for the top 20 highest matching results. In the lefthand figure, we show, for each one of the top 20 matching results, the topic extracted by the Masked NTF method, while in the righthand figure, we show the topic extracted by the Agglomerative NMF method. The results are sorted by the corresponding matching weight.
For each event, on its top left corner, we show the manually annotated terms used for the matching. The shaded blue area shows the exact interval during which the event was occurring according to the official Olympics schedule. In the same area, the solid green line represents the temporal structure of the topic with higher matching result according to our matching criteria. Such values roughly represent the amount of activity for such topic and are normalized according to the peak of activity. We show the value for this peak in the top right side, along with the matching results between parenthesis. In the Agglomerative NMF graph (on the right) we show as a dotted line the activity in time for the given terms regarding the number of tweets that have such terms (tweet count). We remark that by considering only the dotted line the timing of many events on the right side of the figure does not match the schedule timings, i.e., merely counting tweets is not sufficient at this resolution level. We also measured the number of tweets where the terms are co-ocurring, and in this case the number of tweets is so small that it does not allow the detection of any structure in time. We evaluated these activity profiles using the CrowdFlower Webbased crowdsourcing platform (restricted to Amazon Mechanical Turk workers). Each work unit asks a worker to visually inspect and compare two timelines: the one to be evaluated, and a reference timeline corresponding to the known time intervals for sport events taken from the Olympic schedule. Each work unit looks like a row from Figure 3. Our evaluation was based on 100 work units evenly distributed among 5 types: 1) (NMF) work units based on the results of Agglomerative NMF; 2) (CNT-NMF) work units with activity profiles generated by simply counting the number of tweets with the terms used in matching the NMF topics; 3) (NTF) work units from the Masked NTF approach; 4) (CNT-NMF) same as (CNT-NMF) for Masked NTF; 5) synthetic work units (“gold” units) used to assess worker quality. For each work unit, we asked the workers whether the two timelines matched exactly (Yes), matched partially (Partially) or not at all (No). 95% of the judgments Masked NTF teamgb,judo
teamsegabt,,svpoolnlesoyrball seat,ticket Agglomerative NMF swim for gold work units were correct. We only retained those users who correctly judged more than 80% of the gold units. Figure 4 shows the distribution of judgements for the different types of work units. The left hand side of the figure shows the distribution obtained for all work units, while the right hand side shows the distribution restricted to work units with more than 80% of agreement across different workers. According to this evaluation, both NTF and NMF outperform the count-based methods.
We see that for most of the events there is a close temporal alignment between the event schedule and the topic structure, at the scale of the hour or less. We see that such temporal alignment is much closer than when compared to the peaks of activity generated by counting tweets.
We observe that the mismatches in the temporal alignment are caused by two different factors. The first one is due to a low matching results, like the event annotated with (football, mexico, gabon). It means that the term vectors for the given topic does not represent with high confidence the terms used to annotate the event. The second one is due to a different behaviour in collective attention. This happens for example in the case of swimming events, where the first part of the event is related to eliminatories and the second part is related to the finals. In such cases, the peak in activity arrives when the event finishes and the attention goes to the winner.
The topic detection techniques we discussed here afford tracking the attention that a community of users devotes to multiple concurrent topics over time, teasing apart social signals that cannot be disentangled by simply measuring frequencies of term or hashtags occurrences. This allows to capture the emergence of topics and to track their popularity with a high temporal resolution and a controllable semantic granularity. The comparison with an independently available schedule of real-world events shows that the response of Twitter to external driving retains a great deal of temporal and topical information about the event schedule, pointing to more sophisticated uses of Twitter as a social sensor.
The work described here can be extended along several directions. It would be interesting to develop and characterize on-line versions of the techniques we used here, so that topic emergence and trend detection could be carried out on live microblog streams. Because of its temporal segmentation, the Agglomerative NMF case lends itself rather well to on-line incremental computation, whereas a dynamic version of the Masked NTF technique would be more challenging to achieve.
Another interesting direction for future research would be to augment the tweet-term-time tensor with a fourth dimension representing the location of the users, so that the latent signals we extract could expose correlation between topics, time intervals and locations, exposing geographical patterns of collective attention and their relation to delays, e.g., in the seeding by mass media across different countries.
The Authors acknowledge the Emoto project www.emoto2012.org and its partners for access to the Twitter dataset on the London Olympics 2012. The Authors acknowledge inspiring discussions with Moritz Stefaner and Bruno Goncalves. The Authors aknowledge partial support from the Lagrange Project of the ISI Foundation funded by the CRT Foundation, from the QARACNE project funded by the Fondazione Compagnia di San Paolo, and from the FET Multiplex Project (EU-FET-317532) funded by the European Commission. swim, 400m, freestyle canoe football, spain, honduras road cycle, medal swim, 4x100m, freestyle basketball, usa, france archery, korea, china hockey, gb, japan judo, final volleyball, bulgaria, gb football, egypt, new zealand football, teamgb, uae swim, 200m, freestyle football, brazil, belarus swim, breaststroke, 100m football, senegal, uruguay archery, japan, russia basketball, russia, gb swim, 100m, breakstroke water polo, romania, gb #Microposts2014