Topic modelling is based on the assumption that each document can be described as a random mixture of topics and each topic as a multinomial distribution over terms. In our approach we employ topic modelling by using the well known Latent Dirichlet Allocation model [ 3 ] across the whole stream of messages. This process is applied after the end of the event, when all the messages are available. However, topic modelling in micro-blog messages is problematic due to the short length of their text. To overcome this, a lot of approaches have been proposed. To avoid changes on standard LDA, a relative simple solution is message pooling, in which messages are pooled together to form larger documents. We experimented with four methods of message pooling in a similar way as [ 10 ]. First, we tried to merge messages using constant length time bins. Then, we merged messages of the same author to form a single document. As a third option, we pooled messages together based on their hashtags. Messages with multiple hastags assigned to multiple documents and messages without any hashtag were assigned to the document with the highest textual similarity. As a fourth option, we used a 1NN clustering algorithm to cluster messages with high textual similarity. Each of those clusters formed a single document for the LDA method. In addition, for all of the pooling methods we ltered out messages having only one term and removed standard stopwords to discard the non informative terms.

Another drawback of LDA is that the number of topics must be de ned; obviously, the number of topics in not known a priori in the context of large events. To determine the optimal number of topics for a given set of documents D we calculate two metrics, perplexity and average similarity across topics for di erent number of topics and choose a value that minimizes both metrics. For the calculation of perplexity we slit D into training and test documents, we estimate LDA over a range of possible numbers of topics using Dtrain and calculate the total perplexity of the documents in the test dataset Dtest [ 18 ]. The perplexity of a document d given a trained model is de ned as follows: perplexity(d) = exp logP (dj ; ; G)

Ld (1) perplexity(Dtest) = exp d2D logP (dj ; ; G)

P Ld d2D (2)

For the similarity between two topics, we calculate the Jaccard coe cient on the sets of top N terms of each topic.

After the detection of topics we have to associate messages with topics. We use the LDA model, estimated from the merged documents, to infer the probabilities of each message over the set of topics. We assign each message to the topic with the highest probability under the condition that this probability exceeds a prede ned threshold. Although thresholding in this step leaves some messages unassigned, this is a desirable feature of the procedure as most of the unassigned messages are of low quality. In other words these mesages can be considered as spam messages that cannot contribute any valuable information in the summary. Next, assignments are used for the creation of a data structure named StreamGrid. The rst dimension of this grid comprises the detected topics and the second corresponds to time, divided into regular time intervals. Each cell c(i; j) of StreamGrid contains the set of messages Mij associated with topici, at time interval j. Each message m is represented as a tf idf vector. The idf components are pre-computed over the whole set of messages. The tf part is the frequency of a term in the message normalized by the maximum frequency. Due to the short length of the documents in micro-blogging platforms, this component often equals to one. Using the set of associated messages in each cell, we calculate a merged tf idf vector vij . In addition, we calculate a weight for each message and rank them according to it. The weight of a message m, associated with topici, in a speci c time window j is de ned as the sum of the weights of the terms contained in m. To calculate the weight of each term t, we use the following tf idf scheme: W (t; i; j) = tfij (t) idf (t) W (m; j) = X W (t; i; j) t2m (3) (4) where Ld is the number of terms in document d, is the document-speci c topic distribution, is the word distribution for topics, and G is the set of topics in the trained model. The total perplexity over dataset Dtest is de ned as where tfij (t) is the frequency of term t 2 vij into the cell c(i; j) of StreamGrid, and idf (t) is the inverse document frequency over the whole corpus, W (t; i; j) is the weight of term t in c(i; j), and W (m; j) the weight of message m in time interval j.

To detect the time intervals that a speci c topici of StreamGrid is active, we create a topic timeline by using time intervals as bins, and counting the associated messages of topici in bin j. Then, we apply the peak detection algorithm used in [ 9 ] to detect time frames in the timeline that exhibit bursty behaviour. The algorithm identi es windows with high activity by nding signi cant increases in the timeline, compared to the historical mean value of activity. The time windows reported by the algorithm are used to set the active topics of each time interval. For example, if for a speci c topic i, the algorithm identi es a time window [a; b] with high activity, then we de ne all the time intervals a j b as active moments of topici. After this step, the cells of StreamGrid, have a ag that indicates whether a speci c cell is active or not. We use this ag to select a summary subset of messages, as described in the next paragraph. Also for each active topici in a speci c time interval j, we calculate a score that captures its signi cance over the rest of the active topics A in the same time interval.

Signif icance(topici; j) = jMij j

P topick2A jMkj j

In addition, to have an overall estimation of the importance of each topic throughout the event, we calculate two measures for each topic using a similar approach as [ 14 ]. More speci cally we de ne the peakiness of a topic as:

peakiness(topici) = persistence(topici) = maxjMij j P jMij j 8j tpaeavkg<j Pj MjMijijjj j<atvpgeak Pj MjMijijjj and its persistence as where tpeak is the time that the maximum peak of the timeline occurs. 3.3

Our goal is to use the StreamGrid to summarize the event for an arbitrary time frame. As summary we denote a set of representative messages that mention the key aspects of the selected time period. Assuming that topics can capture these aspects, we use the active topics for that period to create a summary that meets the following criteria: a) as many aspects as possible are covered and b) redundancy due to near duplicate messages is minimized. To achieve this, we (5) (6) (7) use an adapted version of the greedy algorithm used in [ 17 ]. The algorithm selects messages that are associated with di erent topics and that simultaneously have low degree of textual similarity between each other. The selection process is detailed by Algorithm 1. For an arbitrary time frame F = [a; b], we rst nd the sequence of time intervals in StreamGrid that covers F . Then we get the set of active topics. A topici is active in F if any cell c(i; j) contained in F is active. Also, the signi cance score of an active topic in F is de ned as the maximum signi cance score across all time intervals in F . The weight W (t; i; F ) of a term t for topici in F is de ned as the sum of the weights in each cell c(i; j) 2 F . In a similar way, we de ne the weight W (m; F ) of message m over F . Note that although a message belongs to a speci c time interval, we use the term weights across the whole time frame to calculate the weight of m.

Figure 2 shows the perplexity and average similarity for di erent numbers of topics K. Although there is signi cant variance for the di erent values of K, the main trend for perplexity is to decrease as K increases. As we can see from Figure 2, the average similarity between all pairs of topics appears to stabilize for values of K larger than 100 topics. However, having a large number of topics creates topics with very few associated messages. We found that for K > 200 there is a substantial proportion of topics that have no associated message. Taking into account these facts, we set K = 200 for the rest of the evaluation. Regarding the pooling scheme, merging tweets having the same hashtags into single documents gave us the best performance with respect to perplexity and average topic similarity. The rst part of Table 2 contains the top ve topics with respect to the peakiness and the second one the topics with the highest persistence ratio. Examining the set of persistent topics we conclude that they can be divided into two main categories: The rst comprises the truly persistent topics that are regularly discussed during the event, while the second category is made up of multiplexed topics that LDA failed to split further. This is due to the fact that some topics are conceptually di erent but share a similar set of related terms. This obviously a ects summarization performance, as for each topic we select only the top weighted message. Thus, if the topic contains more than one concepts then the summarization algorithm selects only one concept and ignores the rest.

Figure 3 depicts the timelines of the same two sets of topics respectively. It becomes obvious that peaky topics are highly localized, while persistent topics sustain for the whole duration of the event. To provide a visual representation of the StreamGrid structure over the whole duration of the event, we represent it as a heat map (Figure 4). The coloured cells in the grid represent the time intervals, in which the corresponding topics are active, and the color of the cell gives the signi cance of each active topic at this point. As shown in Figure 4, StreamGrid appears to be sparse, as only a few cells in it contain active topics. However, one can also observe several topics (rows) that exhibit consistent activity over the whole duration of the event. 4.4

Baselines: To evaluate the summaries produced with StreamGrid, we used ve baseline methods. Given an arbitrary time interval, we rst get the set of messages posted during this interval and then we apply the following baselines to produce a summary of constant length L.

Random Summarizer: For the set of tweets we choose randomly a subset of L tweets.

Popularity Summarizer: We select the L most retweeted messages to form a summary. This favours the tweets that have attracted the attention of the audience. However, niche topics and potentially interesting events that gathered less attention tend to be missed. tf idf Summarizer: We use the tf idf weighting scheme described in the previous section to get the L highest weighted tweets.

Cluster-based Summarizer: Instead of active topics, we divide the tweets of the time interval into L clusters using k-means clustering. For each cluster produced this way, we pick the highest weighted tweet using the tf idf scheme.

LexRank Summarizer: We create a graph where nodes represent tweets and the weights of edges between nodes represent their pairwise cosine similarity. The total weight of a tweet is the sum of the weights of the adjacent edges. The summary consists of the L highest weighted tweets in the graph.

Finally, we compare the results of the StreamGrid Summarizer to the ones of the baseline methods for ve time intervals that are connected with high activity during the main event. We detect these intervals by applying the peak detection algorithm of the previous section to the timeline of the whole dataset. We rank the detected bursts according to the rate of tweets and use the top ve of them. The details of these intervals are provided in Table 1.

Table 3 contains summaries consisting of ve tweets using StreamGrid and three of the baselines for the time period around the Awards Ceremony of Sundance Film Festival. Unsurprisingly, this is the time period with the highest peak during the event. During this period what may be reasonably considered as important pertains to the lms that won awards. Such messages are usually posted by authoritative users and become highly retweeted. For this reason, summaries based on the number of retweets cover quite e ectively the winning lms. However, in other cases choosing very popular tweets does not lead to informative summaries. For example in the third time interval, the summary consists of tweets like \So freaking cool. #sundance http://t.co/C7a8rSaw" and \#Sundance day 4- leavin for Vegas now. Bye for now http://t.co/C2aRZnEC". These tweets were retweeted a lot, but may be considered as non-informative for the event. On the other hand, StreamGrid-based summaries for the Awards Ceremony contain tweets about winning lms, even though these messages are not very popular. That is an indication that StreamGrid may detect an important topic even in cases that this does not attract attention from many users. Regarding the Cluster-based Summarization, an interesting feature is that avoidance of redundancy is inherent in the method, as similar messages are clustered together, and only the most weighted of them are selected for the summary. However, the weakness of the method is that not all clusters represent important aspects of the event.

Another indication of how topic modelling can improve summarization is the fact that StreamGrid, compared to the other baselines, tends to include tweets that mention lms. The reason that this happens is that most of the topics detected by LDA are about lms, so when the proposed summarization algorithm selects a set of tweets from the pool of active moments, this leads to the selection of lm-associated tweets. We expect that, for other types of events, it will naturally generalize to other pertinent entities of interest that occur frequently, thus leading to the creation of topics. A noticeable disadvantage of baselines such as tf idf and LexRank is the remarkable existence of redundancy. For example in case of LexRank four out of ve tweets are related to the 'Fruitvale' lm. This indicates that redundancy minimization is a necessary component of any summarization approach.

Finally, to evaluate how well the proposed method can create visual summaries, we apply it on the subset of tweets with embedded pictures. These tweets that comprise about 10% of the dataset create a considerably sparser StreamGrid as the bursty periods in this subset are much fewer. An example of a multimedia summary using StreamGrid for the Awards Ceremony is shown in Figure 5. Comparing the StreamGridbased multimedia summaries with the ones produced by the popular images (6), we observe that StreamGrid does not perform noticeably better in this task. This can be explained by the fact that tweets with embedded media have text of very low length and informativeness, which leads LDA to inferior performance with respect to the creation of representative topics and the assignment of messages to them. Regarding the redundancy in multimedia summaries, we found that using cosine similarity on the text of images as a metric of similarity between them is not appropriate to minimize redundancy. This can be seen in the LexRank-based summary in Figure 7. To this end, a combination of visual and textual features is foreseen as a more suitable means for discarding similar images. 5

tf idf