Anes Bendimerad

Marc Plantevit

Éline Robardet

Sihem Amer-Yahia

C Robardet

User-driven geolocated event detection in social media

Keywords: Event detection, social media analysis, pattern mining

Event detection is one of the most important research topics in social media analysis. Despite this interest, few researchers have addressed the problem of identifying geolocated events in an unsupervised way, and none includes user interests during the process. In this paper, we tackle the problem of local event detection from social media data. We present a method to automatically identify events by evaluating the burstiness of hashtags in a geographical area and a time interval, and at the same time integrating user feedback. We devise two algorithms to discover user-driven events. The first one relies on an exact enumeration process, while the other directly samples the space of events. In our empirical study, we provide evidence that geolocated events cannot be detected by non location-aware methods. We also show that our methods (i) outperform by a factor of two to several orders of magnitude state-of-the-art methods designed to discover geolocated events, (ii) are more robust to noise, (iii) and produce high quality events with respect to user interests.

INTRODUCTION

Social microblogging (Twitter, Weibo, Instagram, etc.) gives people the ability to interact at a worldwide scale by broadcasting their interests, feelings, reactions to their daily life and surrounding events. As such, they are an incredibly rich mean to know the pulse of the world, or of a specific neighborhood, in real time. Analyzing the abundant usergenerated content can provide high valued information. Social media data have been analysed for several purposes, e.g. to understand the concerns of a population [START_REF] Xiao | Discovering topically and temporally coherent events in interaction networks[END_REF], study disease dynamics [START_REF] Carchiolo | Using twitter data and sentiment analysis to study diseases dynamics[END_REF], or predict real-world outcomes [START_REF] Asur | Predicting the future with social media[END_REF].

Event detection has long been a research topic and has received much attention in the data mining community over the last decade [START_REF] Chen | Non-parametric scan statistics for event detection and forecasting in heterogeneous social media graphs[END_REF][START_REF] Dong | Multiscale event detection in social media[END_REF][START_REF] Li | Tedas: A twitter-based event detection and analysis system[END_REF]. Whereas real-life events are considered as phenomena that unfold over space and time, from a data mining point of view they are conventionally regarded as a set of terms (e.g. hashtags, user mentions, words) whose frequency bursts [START_REF] Kleinberg | Bursty and hierarchical structure in streams[END_REF]. However, a bursting term is not necessarily related to an event, and real-life events can be blurred by pointless bursting terms. Several terms can also depict the same event, and thus detection methods must address problems related to synonymy. Furthermore, some methods are defined in supervised settings which require huge effort to collect labeled examples [START_REF] Li | Tedas: A twitter-based event detection and analysis system[END_REF], [START_REF] Zhang | Triovecevent: Embedding-based online local event detection in geo-tagged tweet streams[END_REF][START_REF] Akbari | From tweets to wellness: Wellness event detection from twitter streams[END_REF][START_REF] Becker | Beyond trending topics: Real-world event identification on twitter[END_REF][START_REF] Wei | Overlapping target event and story line detection of online newspaper articles[END_REF][START_REF] Sakaki | Earthquake shakes twitter users: real-time event detection by social sensors[END_REF]. In this paper, we address these pitfalls by considering geolocated events. Focusing on terms that burst for a geographical area meets the natural and intuitive notion of event. Extracting such events remains challenging because geolocated events depict small scale phenomena that are covered by much fewer terms than global events (i.e., large scale events). For instance, in a very large city like New York City, dozens of events can take place simultaneously and it can be tricky to find those that stimulate users' curiosity.

This paper responds to these concerns by [START_REF] Xiao | Discovering topically and temporally coherent events in interaction networks[END_REF] proposing efficient algorithms to detect geolocated events and (2) integrating user interests into the extraction process through interactions with the system. This is the first attempt to the discovery of user-driven events. In our approach, posts (e.g., tweets) are modeled as a labeled graph whose vertices encode geographical areas and edges depict neighborhood relationships. Time series of term occurrences are associated to vertices. In this unsupervised framework, a geolocated event is considered as a set of terms whose number of occurrences is large enough in a connected subgraph and a time interval. Events are then extracted in a time window and the user has the possibility to tag those he/she likes. This interactive process allows to extract events of interest to users. User preferences are then integrated in the quality measure used to define and rank events. This measure conveys user interest and promotes events that involve topics or geographical areas the user is interested in.

Fig. 1 describes our approach. From a social network, we extract time-stamped geolocated posts published during a given period. This set of posts, B (e.g., tweets), is used to generate a graph G H of term co-occurrences. A second graph G V depicts adjacency relations between geographic areas from which posts were emitted. Those graphs are used to guide the event discovery process making it possible to solve term synonymy problems as well as the spatial variability (size and location). Moreover, these graphs are the support of an interactive process with the user and are used to rank the identified events according to her preferences. By liking or not events, the user selects some events that are then used by the algorithm to derive locations and topics of preference. These preferences are then used to give a greater importance to events related to preferred geographical areas or terms of interest. If there is no interaction with the user, only data-driven events are detected.

The main contributions of this paper are the following:

• Problem formulation. We define, in a unified view, the problem of user-driven and data-driven geolocated event discovery. We propose an event interestingness measure that is guided by user interests.

• Algorithms and analysis. We propose two algorithms to discover geolocated events in social media. SIGLER-Cov 1 is based on the generate-and-test paradigm. It efficiently exploits upper and lower bounds that make it usable on large-scale microblogging data such as Twitter. SIGLER-Samp directly computes a sample of the geolocated events and retrieves interesting geolocated events in a very short time.

• Evaluation. We report a thorough empirical study that provides both quantitative and qualitative performances of our approach. First, we establish that data driven geolocated events cannot be discovered by non location-aware approaches. Second, we compare our method with MED [START_REF] Dong | Multiscale event detection in social media[END_REF] and GeoBurst [START_REF] Zhang | Geoburst: Real-time local event detection in geotagged tweet streams[END_REF], the state-ofthe-art data driven geolocated event mining algorithms. We demonstrate that SIGLER (1) is several orders of magnitude faster than MED and three times faster than GeoBurst, and ( 2) is more robust to noise compared to both methods. Finally, the ability of our method to extract interesting user-driven events is experimentally validated. To that end, we ran experiments using a crowdsourcing platform on several cities (e.g., New York, Los Angeles, London) with different settings (e.g., unpaired and paired samples).

• Source code and datasets are publicly available: https: //tinyurl.com/yywy2fqc.

The rest of the paper is organized as follows. Section 2 reviews the related work. Section 3 presents a unified framework for data-driven and user-driven geolocated event detection. Section 4 introduces the user-driven approach. Section 5 presents our event detection algorithms: SIGLER-Cov, an efficient event detection algorithm with coverage guaran-1. SIGLER stands for SubjectIve GeoLocated Event discoveRy. tee, and SIGLER-Samp that directly computes a sampling of the output space of user-diven geolocated events. Section 6 provides experimental results. Section 7 concludes and provides future directions.

RELATED WORK

This paper focuses on space-time event detection from social media with user interaction during the detection process. Detecting events in social media has raised great interest in the last decade. Several papers propose to identify targeted events using supervised [START_REF] Li | Tedas: A twitter-based event detection and analysis system[END_REF], [START_REF] Akbari | From tweets to wellness: Wellness event detection from twitter streams[END_REF][START_REF] Becker | Beyond trending topics: Real-world event identification on twitter[END_REF][START_REF] Wei | Overlapping target event and story line detection of online newspaper articles[END_REF][START_REF] Sakaki | Earthquake shakes twitter users: real-time event detection by social sensors[END_REF] or semi-supervised approaches [START_REF] Hua | STED: semi-supervised targeted-interest event detectionin in twitter[END_REF], [START_REF]Automatic targeted-domain spatiotemporal event detection in twitter[END_REF]. Such methods require a certain amount of labeled data to detect domain specific events, as opposed to the unsupervised problem considered in this paper.

In the seminal unsupervised approach [START_REF] He | Analyzing feature trajectories for event detection[END_REF], events are detected using signal processing methods on word occurrence time series. As several bursty terms can be associated to one real event (synonyms or correlated words), clustering-based approaches [START_REF] Aiello | Sensing trending topics in twitter[END_REF][START_REF] Ifrim | Event detection in twitter using aggressive filtering and hierarchical tweet clustering[END_REF][START_REF] Weng | Event detection in twitter[END_REF] are used to group terms with similar temporal patterns. In our experimental study, we show that these approaches fail to detect geo-spatial events. Other methods [START_REF] Chen | Non-parametric scan statistics for event detection and forecasting in heterogeneous social media graphs[END_REF], [START_REF] Aggarwal | Event detection in social streams[END_REF] model the data as a heterogeneous interaction graph with content-related features associated to the nodes. Non-parametric statistics or clustering techniques are then applied on it to extract subgraphs. However, the subgraphs of strong interaction describe hardly local events that are generally not related to direct interactions within the graph. In fact, an event can be characterized with a sparse interaction network corresponding to tweets posted by people who mainly do not know each other. It is important to note that as non location-aware event detection methods fail to detect geolocated events, post-processing such events in order to promote events according to the user interest is not a solution.

Few approaches integrate spatial information during the event detection process. Among them, Triovecevent [START_REF] Zhang | Triovecevent: Embedding-based online local event detection in geo-tagged tweet streams[END_REF] discovers local events based on multimodal embedding. However, this method is supervised and requires a trained classifier to judge whether a detected cluster of tweets is related to an event or not. Several demo papers [START_REF] Houdyer | Gazouille: Detecting and illustrating local events from geolocalized social media streams[END_REF][START_REF] Walther | Geo-spatial event detection in the twitter stream[END_REF][START_REF] Watanabe | Jasmine: A realtime local-event detection system based on geolocation information propagated to microblogs[END_REF][START_REF] Garcia-Gasulla | Social network data analysis for event detection[END_REF] present simple systems designed to identify groups of messages that have been posted close in time and space, and assimilate them to events based on the co-occurrence of their terms. A more sophisticated Multiscale Event Detection (MED) method [START_REF] Dong | Multiscale event detection in social media[END_REF] computes the similarity between tweets based on the time series of the occurrences of their common terms considered at different temporal and spatial scales. The most appropriate scale is used to derive a similarity graph on top of which events are detected by a graphbased clustering process. Another state-of-the-art approach is GeoBurst [START_REF] Zhang | Geoburst: Real-time local event detection in geotagged tweet streams[END_REF]. It is based on an authority measure that captures the geo-topic correlations among tweets. These correlations make it possible to group the tweets using some elaborate clustering techniques. In [START_REF] Zhang | Geoburst: Real-time local event detection in geotagged tweet streams[END_REF] the authors show that GeoBurst provides better results than two other local event detection approaches: EVENTWEET [START_REF] Abdelhaq | Eventweet: Online localized event detection from twitter[END_REF] and WAVELET [START_REF] Chen | Event detection from flickr data through wavelet-based spatial analysis[END_REF]. EVENTWEET is based on a clustering of spatially and temporally bursting terms. WAVELET uses wavelet analysis to extract events from geo-tagged Flickr photos. Thus, MED and GeoBurst are the main competitive approaches we consider in Section 6. We show the superiority of our approach towards these two competitors in terms of computation time and noise robustness.

Local event detection can be seen as a local modeling problem. Indeed, local events are related to specific parts of the data space. Discovering such peculiarities is the aim of local pattern mining, especially subgroup discovery [START_REF] Atzmueller | Subgroup discovery[END_REF] and exceptional model mining [START_REF] Duivesteijn | Exceptional model mining[END_REF]. Our approach is rooted in the local pattern mining framework.

The problem of taking user interest in pattern mining was early identified in [START_REF] Silberschatz | On subjective measures of interestingness in knowledge discovery[END_REF] and has seen a renewed interest in the last decade. User-driven and interactive pattern mining can be divided into three groups: [START_REF] Xiao | Discovering topically and temporally coherent events in interaction networks[END_REF] The approaches based on a prior model. Among them, the prominent work of de Bie [START_REF] De Bie | An information theoretic framework for data mining[END_REF] defines a general and statistically-founded framework of exploratory data analysis. Information theory is used to formalize the subjective interest as the divergence to prior belief; [START_REF] Carchiolo | Using twitter data and sentiment analysis to study diseases dynamics[END_REF] The approaches that integrate user feedback interactively during the mining task [START_REF] Dzyuba | Interactive discovery of interesting subgroup sets[END_REF][START_REF] Bhuiyan | Interactive knowledge discovery from hidden data through sampling of frequent patterns[END_REF][START_REF] Wu | Interactive discovery of coordinated relationship chains with maximum entropy models[END_REF]; [START_REF] Asur | Predicting the future with social media[END_REF] The methods which aim to learn an explicit model of user interests [START_REF] Xin | Discovering interesting patterns through user's interactive feedback[END_REF] and rank patterns in post-processing [START_REF] Üping | Ranking interesting subgroups[END_REF]. There is no approach in the literature that detects userdriven events. The one proposed in this paper integrates user feedback during the mining task by building a model of user interest on the fly.

A UNIFIED FRAMEWORK FOR DATA-DRIVEN AND

USER-DRIVEN GEOLOCATED EVENTS

In this section, we introduce the problem of data and user driven geolocated event discovery in a unified view. Table 1 summarizes the definitions and notations used along the paper. From microblogging social media, we consider a set of posts B, a batch 2 , where each element b is described by: (1) the set of terms that appear in b (b.terms), ( 2 The set of terms that occur in posts B.

T = Jt 1 , tmK
The ordered set of m timestamps of the posts.

G V = (V, E)
A graph where the vertices of V are geographical areas and the edges of E connect adjacent areas.

G H = (H, H ⇥ H)
A weighted term co-occurrence graph. The weight W (h i , h j ) is the number of posts in which h i and h j co-occur.

f (h, v, t)
The number of occurrences of a term h 2 H, for a vertex v 2 V and a time t 2 T . score(h, v, t)

The burstiness of the term h 2 H in the space time (v, t).

H(v, t) H(v, t) = {h 2 H | score(h, v, t) > 0}.
The set of terms that burst in the space time (v, t). For the sake of simplicity, we generalize H(S, I) = T v2S T t2I H(v, t) for S 2 V and I v T .

P = (S, I, K)

A geolocated pattern defined with a set of vertices S ✓ V , a time interval I v T , and a set of terms K ✓ H. We use P = (S, I) instead of P = (S, I, H(S, I)).

M, Mu M(P ) is the data-driven quality measure of the pattern P , and Mu(P ) is the userdriven quality measure of P .

A threshold on the minimum quality Mu(P ) required to consider P as an event. A function that measures how much the pattern P 2 covers the pattern P 1 . minCov A minimum threshold on the cover value to consider that a pattern covers enough another one.

Qu(h, v)

The user interest on the term h and the vertex v. It is the average between Q u,H (h), the user interest on h, and Q u,H (v) the user interest on v. These functions take their values in [1, maxPref], with maxPref > 1.

TABLE 1

Notations.

interval made of m timestamps 3 , and (3) V = {v 1 , ..., v n }, the districts obtained after discretizing the geographical space in n areas. For example, the geographical area defined by the square [min b2B b.loc.x, max b2B b.loc.x] ⇥ [min b2B b.loc.y, max b2B b.loc.y] can be divided along a grid and each square is associated to an element of V . Let area : R 2 ! V be the function that maps GPS coordinates (x, y) to V . V is hereafter considered as the vertices of a graph G V = (V, E) whose edges E connect vertices corresponding to adjacent areas.

Our approach is based on the detection of strong variations in term occurrences for a vertex and a timestamp. To this end, we consider the number of occurrences of a term 3. In our experiments, a timestamp corresponds to an interval of 3 hours.

h 2 H, for a vertex v 2 V and a time t 2 T as function f :

f (h, v, t) = |{b 2 B | (h 2 b.terms) and (area(b.loc) = v)
and (b.time = t)}|.

As generally admitted [START_REF] Zhang | Geoburst: Real-time local event detection in geotagged tweet streams[END_REF], [START_REF] Abdelhaq | Eventweet: Online localized event detection from twitter[END_REF], a geolocated event reflects that a large number of messages deal with the same subject during the same time and place. Each topic is associated with the set of its representative terms. For instance, in Fig. 12, the first detected event in New York is the New York Comic Con, associated with the terms (#nycc, #nycc2016, etc.). These terms burst in a period of three days, and around the location of Jacob K. Javits Convention Center where the convention took place at that time. Thus, a term is likely to correspond to an event in a space-time zone if its number of occurrences is significantly greater than what is observed in the other times for the same space zone.

To that end, we compute the mean µ(h, v) and standard deviation (h, v) of f over all the timestamps Jt 1 , t m K. If the difference between f (h, v, t) and its average value is greater than ✓ times the standard deviation, then the number of occurrences of h is said to be significant for v and t. ✓ 0 is a parameter that controls the sensibility of the method, and whose default value is set to 1. Then, to reduce the impact of very frequent terms, the significance of each term is weighted by the normalized inverse document frequency factor [START_REF] He | Analyzing feature trajectories for event detection[END_REF]

: idf(h) = 1 log f (h,V,T ) log f (H,V,T )
. Hence, the score function is:

score(h, v, t) = ✓ f (h, v, t) µ(h, v) + ✓ (h, v) ◆ ⇥ idf(h), with (h, v) = q 1 m 1 P t2T (f (h, v, t) µ(h, v)) 2 and µ(h, v) = P t2T f (h,v,t) m
. A term h is bursting for (v, t) if its score value is positive. The set of bursting terms for a space-time zone (v, t) is thus defined by:

H(v, t) = {h 2 H | score(h, v, t) > 0}.
For the sake of simplicity, given S 2 V and I v T , we generalize H(S, I) = T v2S T t2I H(v, t). We consider a geolocated pattern P as a tuple (S, I, K) where S ✓ V , I v T , and K ✓ H. We aim to identify patterns P = (S, I, K) corresponding to events described by a location S, a time interval I and a set of terms K. The ability for P to represent an event is evaluated by the measure M(P ):

M(P ) = X h2K X v2S X t2I score(h, v, t).
The larger M(P ), the higher than expected the frequency of the terms in (S, I). This means that when M(P ) is large, the pattern P = (S, I, K) is likely to be an event. In our problem formulation, we are only interested in patterns P = (S, I, H(S, I)) where H(S, I) are terms that burst in all the space-time (S, I). This makes it possible to filter out a large part of noisy terms. In fact, it is not likely that a noisy term bursts simultaneously in all the space-times of (S, I). Consequently, in what follows, we are only considering patterns P = (S, I, H(S, I)) and denote them P = (S, I) (since K is uniquely determined by S and I).

In practice, the interest of an event strongly depends on the end-user. Indeed, a user may be much more interested in events related to some subjects (e.g., sport, music) or may prefer events happening in some specific locations (e.g., near her residence). To take user interests into account, we propose to integrate the proper interests of the user through an interactive process. To this end, we define the quality measure M u (P ) that includes the user's preferences as:

M u (P ) = X h2H(S,I) X v2S X t2I score(h, v, t) ⇥ Q u (h, v),
where Q u increases with the interest of u on h and v. Thus, if P contains some terms h or vertices v that are of interest according to user's feedback, then M u (P ) increases. When no user feedback is available for a pair (h, v), Q u (h, v) is equal to 1. We thoroughly discuss in Section 4 how the function Q u is defined.

A user-driven geolocated event must be both spatially compact and have a significant value on its quality measure: Definition 1 (User-driven geolocated event). Given a set of posts B, a set of timestamps T , a graph G V = (V, E), and a threshold > 0, a pattern P = (S, I), with S ✓ V and I v T (an interval of T ), is a user-driven geolocated event iff (1) G V [S] is connected and (2) M u (P ) .

If the user does not provide any feedback, the measure M u is equal to M. In such particular case, we speak of datadriven geolocated events. Different geolocated events may overlap in terms, geographical area, and timestamps they share, depicting the same real-life event. This has two main disadvantages: (1) the size of the result set may be uselessly very large and redundant, and (2) the method performance may degrade due to the size of the output. Therefore, instead of finding the complete set of events, our goal is to return a concise summary that covers sufficiently all the events. To this end, we use the coverage measure cov. This function, defined for two sets or intervals A and B, measures how much the set B covers the set A: cov(A, B) = |A\B| |A| . This coverage measure has been used in several problems in order to avoid the redundancy in the results [START_REF] Wang | Redundancy-aware maximal cliques[END_REF], [START_REF] Bendimerad | Unsupervised exceptional attributed sub-graph mining in urban data[END_REF]. To measure how much a pattern P 2 = (S 2 , I 2 ) covers a pattern P 1 = (S 1 , I 1 ), we impose that P 2 sufficiently covers P 1 in all the dimensions. The function cover is thus:

cover(P 1 , P 2 ) = min{cov(S 1 , S 2 ), cov(I 1 , I 2 ), cov(H(S 1 , I 1 ), H(S 2 , I 2 ))}.
To get a set of patterns that cover all user-driven geolocated events while eliminating some redundancy, we propose to only retrieve a coverage guaranteed event summary. Definition 2 (Coverage guaranteed event summary). Given a threshold minCov 2 [0, 1], a coverage guaranteed event summary R 1 of the set of all geolocated events R fulfills the following property:

8P 2 R, 9P 0 2 R 1 , such that cover(P, P 0 ) minCov.
The last drawback that may appear is that two concomitant events in time and space are merged by our approach. To ensure that an event-pattern is semantically coherentthat is its related terms correspond to the same real life event -a post-processing of the event patterns is performed. In Section 5.3, we explain how we apply a Louvain clustering [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] on terms to achieve this goal. The similarity between terms is computed based on their co-occurrences, since event-related terms tend to co-occur in the posts.

We propose two approaches to detect geolocated events: SIGLER-Cov that computes a coverage guaranteed event summary R 1 , and SIGLER-Samp that samples the pattern space according to the value of M u . These approaches are formally defined in Section 5. The following section details the computation of the user-driver weight used in the quality measure M u (P ).

INTEGRATION OF USER FEEDBACK INTO QUAL-ITY MEASURE

Let us now consider how to incorporate user interest into the geolocated event discovery process. Once a set of events has been identified, a user u appraises the detected events and indicates if she likes it. In doing so, she constructs a partial order on the patterns that is used to favor the discovery of the forthcoming geolocated events toward those of interest for u. User interest is expressed by

Q u (h, v) = Q u,H (G H ,h)+Q u,V (G V ,v) 2
, the average of two interest measures on terms and vertices:

1) Q u,H : (G H , h)
Q u,H (G H , h) is close to maxPref. Otherwise, it tends to 1. 2) Q u,V : (G V , v
) takes as parameters the graph G V and a vertex v 2 V . It takes its value in [START_REF] Xiao | Discovering topically and temporally coherent events in interaction networks[END_REF]maxPref] and the closer v is to other liked vertices in G V , or the more recently it has been liked, the more

Q u,V (G V , v) is close to maxPref. maxPref > 1 represents the maximum value that Q u can reach.
The choice of maxPref depends on how much we want to take into account the user preferences into the process. In the following, we use the value maxPref = 3, empirically chosen as the one that maximizes the number of liked events on NYC dataset (see the description of the experiment in section 6.3).

Both functions Q u,H (G H , h) and Q u,V (G V , v) are constructed above a weighted graph G X = (X, Y, W ) with X a set of vertices, Y a set of edges and W the function that associates a weight to the edges (W : Y ! N).

• Q u,H is evaluated on G H , the term co-occurrence graph, such that X = H, Y = H ⇥ H and 8h i , h j 2 H, W (h i , h j ) equals the number of posts in which h i and h j appear simultaneously:

W (h i , h j ) = |{b 2 B | h i 2 b.terms and h j 2 b.terms}|.
Related terms may co-occur in several posts and thus will tend to be connected by a shorter path whose sum of weights is high in G H . • Q u,V is evaluated on the graph G V , with X = V , Y = E and W : E ! 1. In a similar way to PageRank score [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF], we valuate the vertices of the graph such that (1) a high score associated to a vertex is transferred to its neighbors, with whom it is connected with a high weight, and (2) this effect decreases all the more as the neighboring vertex is far from the source vertex in the graph. However, unlike PageRank score, which is based on a random walk, we use a concentric model from the vertex to be valued. The vertex score is only influenced by the weights of its neighbors and not by their degrees:

Q X (G X , x) = ↵ P (x,x 0 )2Y W (x,x 0 ) deg(x) ⇥ Q X (G X , x 0 ) + (1 ↵) 1 |X| , with deg(x) = P (x,x 0 )2Y W (x, x 0 ). The first term, P (x,x 0 )2Y W (x,x 0 ) deg(x) ⇥ Q(G X , x 0 ), is simply the weighted av- erage of qualities Q X (G X , x 0 ) of the neighbor vertices. The second term, 1
|X| , is a constant corresponding to the probability to directly reach a vertex. ↵ 2]0, 1[, whose default value is 0.7, is a balancing parameter between the two terms.

We propose to integrate the user preferences in the second term by replacing the constant value with the function B u (x), a weight that amplifies the importance of the vertices involved in recently liked events:

Q Xu (G X , x) = ↵ X (x,x 0 )2Y W (x, x 0 ) deg(x) Q Xu (G X , x 0 ) + (1 ↵)B u (x)
B u (x) depends on the direct relation between x and the liked events. Let rank(x) be the number of events that have been liked since the last event that (1) contained x and (2) was liked by the user. Fig. 2 shows the values of rank for terms that appear in an ordered set of liked events {P 0 , ..., P z }. P 0 is the latest liked event, thus rank(h 1 ) = 0. The user liked P z , but she liked z events after that, so rank(h 5 ) = z. Particularly, if a term or a vertex x does not belong to any liked event, then rank(x) = +1. We define

B u (x) as B u (x) = 1 + maxPref 1 1+log2(1+rank(x))
. We can observe that B u (x) 2 [1, maxPref], and if rank(x) = +1, then

B u (x) = 1. It increases if x is related to a recently liked event (if rank(x) = 0, B u (x) = maxPref).
The log 2 function is used to smooth the effect of past liked events.

Q Xu (G X , x) can be rewritten as the matrix equation

A.Q Xu = B with (1) a ij = 1 if i = j, and a ij = ↵ W (xi,xj ) deg(xi) otherwise; (2) b i = (1 ↵)B u (x i )
. This equation can be solved thanks to the Jaccobi method, as the convergence condition below is satisfied. Proposition 1. The matrix A is strictly diagonally dominant.

COMPUTING GEOLOCATED EVENTS

We first present SIGLER-Cov, an algorithm that computes a set of patterns R 1 whose quality M u exceeds the threshold . In addition, R 1 is a coverage guaranteed event summary (see Definitions 1 and 2). Then, we present SIGLER-Samp, a sampling event detection approach. Finally, we explain the post-processing step as introduced before.

Event Detection with Coverage Guarantee

We propose to extract user-driven geolocated events using a generate and test approach. It first enumerates a time interval I, and then explores the connected subgraphs S corresponding to areas where posts were sent during I. The quality measure M u (S, I) evaluates whether the terms of the posts sent from G V [S] during I are characteristic of this time frame. As the number of such generated events is very large, especially the number of possible subgraphs, we propose several pruning techniques that makes the extraction feasible on real-life generated sets of posts.

Algorithm 1 enumerates all the intervals [t i , t j ] included in T = Jt 1 , t m K thanks to the two loops in lines 2 and 4. For each interval I, it explores the connected subgraphs of G V [C] -the graph induced by the vertices for which there exists at least a term that bursts during the interval I -calling the function SGEnumerate presented in Algorithm 2. This backtracking algorithm uses two sets of vertices: S ✓ V , the current enumerated subgraph induced by S, and C ✓ V \ S the vertices that are still to be explored. Initially, S = ; and C contains all the vertices for which there exists a bursting term in I. Algorithm 2 enumerates vertices from C \ N (S), with N (S) the neighbors of vertices of S:

N (S) = {v 2 V \ S | 9u 2 S : (u, v) 2 E}.
Once the candidate set C is empty, P is tested to only be retained if it satisfies definitions 1 and 2 (lines 11 to 15). Fig. 3 (a) shows an example of sets S, N (S) and C. In the next step of this example, SGEnumerate will choose v 7 or v 8 (in the intersection of C and N (S)) and add it to S. We can notice that some vertices do not belong to C (e.g., v 4 ) because they have already been enumerated and removed from C.

We use three pruning mechanisms without which the algorithm does not scale. The first one -the anti-monotonicity of H(P ) -is used line 6 of Algorithm 1 to prune vertices given a time interval. This property is defined up to the intuitive partial order ✓: P 1 ✓ P 2 if and only if S 1 ✓ S 2 and

I 1 ✓ I 2 .
, v 2 }, t) = {a, b}.
The second pruning mechanism is based on the computation of an upper-bound of M u (P ) (used line 3 in Algorithm 2). Definition 3 (Upper-bound on M u ). Let S ✓ V , I v T , and J ✓ H. UB is defined as: ✓ S [ C and H(P 0 ) ✓ H(P ), we have

UB(S, I, J) = X v2S X t2I X h2J max score(h, v, t)⇥Q u (h, v
UB(S [ C, I, H(P )) = X v2S 0 X t2I X h2H(P 0 ) max score(h, v, t) ⇥ Qu(h, v), 0 + X v2S[C X t2I X h2H(P )\H(P 0 ) max score(h, v, t) ⇥ Qu(h, v), 0 + X v2S[C\S 0 X t2I X h2H(P 0 ) max score(h, v, t) ⇥ Qu(h, v), 0 X v2S 0 X t2I X h2H(P 0 ) max score(h, v, t) ⇥ Qu(h, v), 0 X v2S 0 X t2I X h2H(P 0 ) score(h, v, t) ⇥ Qu(h, v) = Mu(P 0 ) ⇤
The last pruning technique is built on the coverage measure. As stated in Definition 2, there may exist several coverage guarantee summaries of geolocated events. Whereas it might be interesting to have a summary of smallest cardinality, the problem of finding the set of minimal size is NP hard. A practical approach consists in constructing the summary during the enumeration. We also use the coverage measure to prune large parts of the subgraph search space thanks to a lower bound LB (lines 4 to 6 in Algorithm 2) that will be defined next. The intuition behind is to prune a search space (I, S, C) if it is covered by an already found pattern P r . Proposition 4. Given a geolocated event pattern P r = (S r , I r ) and a pattern P 0 = (S 0 , I) in (I, S, C), we have cov(S 0 , S r ) cov(S [ (C \ S r ), S r ). Proof 4.

As S 0 = S [ C 0 s.t C 0 ✓ C, we have: cov(S 0 , S r ) = |S 0 \Sr| |S 0 | = |S\Sr|+|C 0 \Sr| |S|+|C 0 \Sr|+|C 0 \Sr| |S\Sr|+|C 0 \Sr| |S|+|C\Sr|+|C 0 \Sr| . We define g(x) = |S\Sr|+x |S|+|C\Sr|+x , with x = |C 0 \ S r |. Knowing that the derivative g 0 (x) = |S|+|C\Sr| |S\Sr| (|S|+|C\Sr|+x) 2 0, g(x)
takes its lower value when x is minimal, that is when x = 0. Thus g(x)

|S\Sr| |S|+|C\Sr| = cov(S [ (C \ S r ), S r )
and we conclude that cov(S 0 , S r ) cov(S [(C \S r ), S r ). ⇤ For instance, in Fig. 3, S r covers S and a part of C. cov(S [ {v 9 , v 10 }, S r ) = 3 5 is a lower bound of cov(S 0 , S r ) for all (S 0 , I) 2 (I, S, C). In fact, S [ {v 9 , v 10 } contains only the vertices of C that are not in S r , which minimizes the coverage of S r . Definition 4. Let H(P ) \ H(P r) = {h 1 , . . . , h q } -the set of terms of P covered by those of P r -be ordered by

h i  UB h j iff UB(S [ C, I, {h i }) UB(S [ C, I, {h j }).
We consider the minimal set {h 1 , . . . , h q ? } of terms that can be added to H(P ) \ H(P r ) while still satisfying the upper-bound:

q ? = argmin r2{1...q} UB(S[C, I, H(P )\H(P r )[{h 1 , • • • , h r })
and define H ? as

H(P ) \ H(P r ) [ {h 1 , • • • h q ? }.
In other words, H ? ✓ H(P ) is the set of terms that overlaps the least with H(P r ) while verifying the condition UB(S [ C, I, H ? ) Proposition 5. For each pattern P 0 = (S 0 , I) 2 (I, S, C) such that M u (P 0 )

, we have cov(H(P 0 ), H(P r )) cov(H ?

, H(P r )). Proof 5. We know that |H(P 0 ) \ H(P r )| q ? , otherwise UB(S 0 , I, H(P 0 )) < and M u (P 0 ) < . We can rewrite cov(H(P 0 ), H(P r )) = , we have cover(P 0 , P r ) LB(P, C, P r ). Proof 6. It is sufficient to prove that : cov(S 0 , S r ) cov(S [ (C \ S r ), S r ) and cov(H(P 0 ), H(P r )) cov(H ?

, H(P r )) and cov(I, I r ) cov(I, I r ) The first two equations are respectively guaranteed with Propositions 4 and 5, and the third one is trivial. ⇤

The exploration of the search space (I, S, C) is stopped if there exists P r 2 R 1 such that LB(P, C, P r ) minCov, because all the subsequent patterns are covered by it.

Pattern Sampling Based Event Detection

In this section, we explore another approach to discover geolocated events: Pattern sampling [START_REF] Bhuiyan | Interactive knowledge discovery from hidden data through sampling of frequent patterns[END_REF]. Given a time budget, the proposed algorithm SIGLER-Samp mines events using a random exploration of the search space that favors events with high M u values. Such an approach enables instant mining which is required in interactive pattern mining.

The pattern sampling process we consider is based on a random walk on a graph whose vertices are patterns P = (S, I) and edges (transitions) are chosen following a probability measure that overweights high quality patterns. The random walk starts from a singleton pattern P = (S, I) where S = {v} and I = [t, t]. Next, P is expanded by adding randomly drawn vertices from N (S), the neighborhood of S, or by adding a timestamp to I. The random walk is basically composed of two main steps described in Algorithm 3:

1) M u (P ) is computed for each pattern P = (S, I), where S = {v}, v 2 V and I = [t, t], t 2 T . The probability of drawing a singleton pattern P is defined as

P(P ) = Mu(P ) P v 0 2V,t 0 2T Mu({v 0 },[t 0 ,t 0 ])
2) From a current pattern P = (S, I) with I = [t i , t j ], the next step consists to draw a pattern P 0 from the set:

Next(P ) = {(S, I)} [ {(S, [t i 1 , t j ])} [ {(S, [t i , t j+1 ])} [ {(S 0 , I) | S 0 = S [ {v}, v 2 N (S)}
This is done based on P(P 0 |P ), the probability to reach the pattern P 0 2 Next(P ) from P : P(P 0 |P ) = Mu(P 0 ) P P 2 2Next(P ) Mu(P2) . This distribution of probabilities rewards transitions toward patterns P 0 with large M u (P 0 ) values. After drawing P 0 , if P 0 6 = P , we continue the expansion by repeating Step 2 using the new pattern P 0 . If P 0 = P , the pattern P is returned to the user and the sampling is repeated from Step 1 until the whole consumption of the time budget. • For n = 2, P is such that |S| = 1 and |I| = 1 (in other cases, M u (P ) = 0). P can be drawn in the first step, and if it is chosen from Next(P ) in step 2, it is added to R 2 . Thus, P(P 2 R 2 )

Mu(P ) P v 0 2V,t 0 2T Mu({v 0 },[t 0 ,t 0 ]) ⇥ Mu(P ) P P 2 2Next(P ) Mu(P2) > 0.
• Let us suppose that the proposition is true for n. Let P = (S, I) be a pattern such that |S| + |I| = n + 1 and M u (P ) > 0. Let P 0 = (S 0 , I 0 ) ✓ P be a pattern containing one less vertex or one less timestamp than P . This means that |S 0 |+|I 0 | = n, by the recursion hypothesis we have P(P 0 2 R 2 ) > 0. Thus, the probability P(P 0 ) to reach P 0 is not null. Since P can be reached from P 0 during the random walk, then: P(P 2 R 2 ) P(P 0 ) ⇥ Mu(P ) P Fig. 4 gives an example of an iteration in SIGLER-Samp. The current generated pattern is P = ({v 4 }, [t 3 , t 4 ]). In the next iteration, one of the neighbors of P , or P , is randomly chosen. The neighbors are generated by either adding {v 2 } or {v 6 }, vertices connected to v 4 in the graph of Fig. 3, or increasing the time interval.

Discussion

We discuss here some potential issues that may appear, and the related post-processing to fix them. By applying one of the aforementioned algorithms, we find the set of patterns R 1 or R 2 , let's denote it R ⇤ . In some particular cases, two real life events happen at the same time and the same location. However, these two events will be merged in the same pattern P 2 R ⇤ . It is important to separate them before displaying the result to the end user. Therefore, for each pattern P = (S, I, H(S, I)) 2 R ⇤ , we apply a community detection algorithm on the terms H(S, I) in order to partition them into groups K 1 , ..., K d where (1) 8i 2 J1, dK :

K i ✓ H(S, I) (2) [ i K i = H(S, I) (3
) each K i corresponds to a single real life event. We use Louvain community detection algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF], and we express its result by the function Louvain 1 (P ) = {K 1 , ..., K d }. The similarity measure sim 1 used in this clustering is defined for two terms h 1 , h 2 2 H(S, I) w.r.t the pattern P : In other words, sim 1 (h 1 , h 2 , P ) = 1 if h 1 and h 2 co-occur at least once in the space S and the time interval I. Thus, each cluster K i 2 Louvain 1 (P ) would be a set of terms that co-occur in this space-time. Each cluster K i gives a pattern (S, I, K i ) with the same space-time than the current P . After applying this clustering to each P 2 R ⇤ , we have the post-processed result R 0 = [ (S,I,H(S,I))2R⇤ {(S, I, K) | K 2 Louvain 1 (S, I, H(S, I))}

sim 1 (h 1 , h 2 , P ) = 8 < : 1, if |{b 2 B | ({h 1 , h 2 } ✓ b.terms
In order to deal with the redundancy issue, we have defined SIGLER-Cov that computes a summary R 1 . However, it is not necessarily the optimal summary, that is to say the summary of minimal size whose events partially cover each geolocated events that does not belong to the summary. Indeed, the computation of an optimal summary is NP hard. Thus, some redundancy can still remain in the result, we post-process the set R 0 to fix this issue. We apply Louvain algorithm on patterns P 2 R 0 to merge the ones with similar location, time interval, and terms. We define a similarity measure sim 2 for two patterns P = (S, I, K) and P 0 = (S 0 , I 0 , K 0 ): sim 2 (P,

P 0 ) = |S\S 0 | |S[S 0 | ⇥ |I\I 0 | |I[I 0 | ⇥ |K\K 0 | |K[K 0 |
. The result will be the communities: C 1 , ..., C l where each community C i ✓ R 0 is a set of similar patterns. From each community C i we reconstitute a pattern P Ci = [ (S,I,K)2Ci (S, I, K). The final result set of pattern is: R 00 = {P C1 , ..., P C l }.

EXPERIMENTS

In this section, we report our experimental results. We start by describing the real-world datasets we use, as well as the questions we aim to answer. Then, we provide a thorough comparison with the state-of-the-art algorithms and we report a performance study. Eventually, we evaluate the ability of our approach to take user interests into account through different testbeds 4 .

SIGLER is implemented in C++ and the experiments were executed on a machine equipped with i7 CPU @ 2.5GHz, and 16GB main memory, running macOS Sierra version 10.12.2. For reproducibility purposes, the source code and the data are available 5 .

Experimental Setting

Experiments are performed on 3 real-world datasets that contain the tweets obtained by querying three different cities on Twitter: New York (NYC), Los Angeles (LA) and London. For each city, we collected geolocated public tweets and removed those produced by bots (i.e, accounts that produce more than 100 tweets in a period of 10 days). We only retained tweets containing hashtags or user mentions. The main characteristics of these datasets are given in Table 2. This empirical study aims to answer the following questions: Are SIGLER-Cov and SIGLER-Samp more effective and efficient than their competitors? Do they scale well according to the size of the dataset and the different parameters? Does SIGLER-Samp capture all the events? Is the approach able to make use of user feedback to discover userrelevant events?

dataset
In the first bunch of experiments, we compare our approach with two local event detection approaches: (1) Multiscale Event Detection algorithm (MED) [START_REF] Dong | Multiscale event detection in social media[END_REF], a state-of-the-art algorithm which aims to identify geolocated events based 4. We report experiments performed on a crowd-sourcing platform with real-users in this paper. Additional experiments with virtual users are reported in supplementary material.

5. https://tinyurl.com/yywy2fqc on a wavelet analysis of time series of terms, (2) GeoBurst [START_REF] Zhang | Geoburst: Real-time local event detection in geotagged tweet streams[END_REF], an online local event detection method, that first detects geo-topic clusters using a random walk on a keyword cooccurrence graph, and then ranks all the clusters with a weighted combination of spatial and temporal burstiness. We also considered INSIGHT [START_REF] Ifrim | Event detection in twitter using aggressive filtering and hierarchical tweet clustering[END_REF] and EDCOW [START_REF] Weng | Event detection in twitter[END_REF], two non location-aware event detection methods. INSIGHT is one of the best methods to detect events in tweets, as it won a recent challenge [41]. These experiments show that (1) non location-aware approaches are not appropriate to detect geolocated events, and (2) MED and GeoBurst algorithms are less robust to noise than our approaches, and encounter scalability issue. Finally, we demonstrate the ability of our methods to extract interesting user-driven events via experiments performed on a crowdsourcing platform.

Effectiveness

We first study the ability of our approach to detect userdriven geolocated events. Using the method described in [START_REF] Dong | Multiscale event detection in social media[END_REF], we generate artificial datasets for which the groundtruth geolocated events are known. Twenty events, denoted hereafter R 0 , are artificially created. Each of them lasts between 2 and 8 timestamps, involves from 2 to 16 vertices and is defined by 10 unique terms. The datasets contain 1024 vertices, 32 timestamps and 1200 unique terms. Posts are artificially produced and sent at different timestamps and spatial locations. Each post contains between 9 to 13 terms. These posts are either related to embedded events, or are randomly drawn: (1) Event-related posts are uniformly distributed over the vertices and times stamps of its associated event and contain 5 of the 10 event-related terms as well as between 4 to 8 other terms; (2) Nonevent related posts are uniformly distributed over the other timestamps and vertices. The terms they contain are drawn using a Zipf law probability distribution [START_REF] Pérez-Melián | Zipf's and benford's laws in twitter hashtags[END_REF] among the 1000 non-event related terms. 10 to 50 event-related posts are randomly drawn and the number of non-event related posts is controlled by the noise rate parameter.

Let R = {e 1 , . . . , e k } be the set of discovered events. The quality of R is assessed based on the following adapted F score measure: GeoBurst . The F score of our approaches remains high even when the noise rate increases, whereas MED and GeoBurst F score decreases almost linearly. More precisely, MED and GeoBurst keep a good recall but the precision decreases when the noise rate increases. 3) Furthermore, the F score of SIGLER-Samp is obviously bounded by the F score obtained by SIGLER-Cov which adopts a more exhaustive exploration of the search space. Nevertheless, the bigger the time budget, the better the F score. Non location-aware event detection approaches are not able to detect geolocated events. MED fails in presence of noise. Runtime of SIGLER-Cov increases from 10ms to 2.5s when the noise rate increases.

F score(R, R 0 ) = 2 ⇥ P recision(R, R 0 ) ⇥ Recall(R, R 0 ) P recision(R, R 0 ) + Recall(R, R 0 ) with P recision(R, R 0 ) = P e2R max e 0 2R
We also study the impact of parameters of our approach on the value of F score. To this aim, we variate minCov and and we show the value of F score in Fig 6 . The highest F Score is achieved with values of between 1 and 2, this leads to the best trade-off between precision and recall. Increasing allows to increase the precision, but decreases the recall. Although the value of F score slightly increases when minCov is higher, this parameter does not significantly impact the quality of the result. Ideally, one would prefer to perform the effectiveness study based on real world dataset. However, we do not have the ground truth of such data. This makes it very hard to achieve an objective comparison on them. Nevertheless, in supplementary materials, we display and compare the top 10 events returned by SIGLER-Cov, MED and GeoBurst in the New York dataset. We show that there are several events that are identified by both SIGLER-Cov and MED. We also show that GeoBurst provides events that are much smaller than the ones of SIGLER-Cov and MED. We also discuss the quality of these top 10 events. MED and GeoBurst tend to detect false positive events.

Efficiency

To evaluate the scalability of the algorithms, we consider New York tweets, our largest dataset. Fig. 7 reports the runtime and the number of events obtained by SIGLER 6 , MED, and GeoBurst when dataset parameters are varying. However, MED is only reported for at most 10,000 tweets because of its scalability issues (in the figures at left).

MED, GeoBurst, and SIGLER-Cov discover a comparable number of events but MED performances raise scalability issues. Indeed, SIGLER-Cov outperforms MED with several orders of magnitude for all the configurations, especially when the number of tweets increases. Even if MED uses some indexing techniques, its computational complexity is quadratic in the number of tweets, and MED fails to handle large datasets. Although MED is able to process one day of tweets in our experiments, it is without considering the fact that the Twitter API gives access to less than 1% of the posted tweets. MED scale limitation is therefore a real issue on these data.

In Fig. 7 -right, we report the runtime and the number of discovered events with higher numbers of tweets (we consider the whole dataset). We observe that the execution time of SIGLER-Cov increases with the number of tweets, but there is no order of magnitude change (non-logarithmic scale). Although GeoBurst runtime also increases linearly, it is considerably higher than the one of SIGLER-Cov.

We also study the impact of number of vertices and time granularity on our methods. We show their behavior in Fig. 8 when these two dimensions are varying. The execution time of SIGLER-Cov increases when the number of vertices and time granularity increase. The execution time of SIGLER-Samp is controlled by a parameter and we can observe that its number of results tends to the one of SIGLER-Cov when the time budget increases.

To go further on evaluating the discovered events, Fig. 9 investigates the ability of SIGLER-Samp to capture similar events as SIGLER-Cov, that is to say it verifies that the computed event sample well covers all the events obtained with the exhaustive approach. To this end, we compare the events provided by SIGLER-Samp (denoted R 1 ) with the events discovered by SIGLER-Cov (denoted R 2 ) as follows. Using the Jaccard similarity measure of two patterns P 1 = (S 1 , I 1 ) and P 2 = (S 2 , I 2 ), J(P

1 , P 2 ) = 1 3 ⇥ ⇣ |S1\S2| |S1[S2| + |I1\I2| |I1[I2| + |H P 1 \H P 2 | |H P 1 [H P 2 | ⌘ , the similarity of R 1 and R 2 is defined by Sim(R 1 , R 2 ) = P P 1 2R 1 max P 2 2R 2 J(P1,P2) |R1|+|R2| + P P 2 2R 2 max P 1 2R 1 J(P1,P2)

|R1|+|R2|

. We executed SIGLER-Samp with different time budgets and post-processed the result R 2 by removing redundant patterns (using minCov = 0.8) and low quality ones (using = 40). Fig. 9 reports the Sim values with respect to SIGLER-Samp time budget for 300K tweets (left) and the whole dataset (right). The runtimes of SIGLER-Cov for these two cases are respectively 95s and 173s. With a time budget fixed to 11% of the execution time of SIGLER-Cov (around 9s and 19s), SIGLER-Samp retrieves most of the high-quality patterns (sim > 0.9 ). Finally, Fig. 10 evaluates the impact of the two main parameters, minCov and , on the results. minCov is a very intuitive parameter that eliminates a pattern if it is covered at least by minCov% of a pattern belonging to the solution. When minCov=1, only non maximal patterns are removed, and the more minCov decreases, the more disjoint the patterns. From Fig. 10 we can observe that this parameter has also a major impact on the execution time. Indeed, this parameter is involved in the computation of the upper-bounds and when large, it drastically reduces the execution time. In our experiments, we set this parameter to 0.8 to remove highly redundant events while allowing some intersections.

The quality of an event is evaluated by the measure M, also used to rank the patterns when presented to the user (see next subsections). The function of the parameter is to cut the tail of the pattern distribution in order to only keep those of high quality. So the larger , the smaller the number of patterns and the faster the execution.

For the following experiments, we fixed the value of according to the number of events that we wanted to present to the user. Thus, we fixed value so as to have around 800 events for NYC, which contains 3 months of tweets, and around 400 events for LA and London that contain 70 days

User-driven discovery of geo-located events

To evaluate the ability of SIGLER to take benefit of user feedback, we performed interactive event detection process with real users on real datasets. We used a crowdsourcing platform -Figure Eight 7 -to hire people living in the country where the data is located. Indeed, our user feedback requires some expertise about the city and its events. To this end, we developed a graphical application 8 and deployed it on Figure Eight. For each user, the process consists in several iterations. At each of them, a batch containing the tweets emitted for 6 consecutive days is given as input to the algorithms (with a recovery of 3 days between 2 batches). Geolocated events are computed using either M (datadriven detection), or M u (user-driven detection). Then, the user is asked to mark the events that she likes. Finally, the batch index is incremented and the process iterates. Since evaluating with the overall datasets can be very long and exhausting for real users, we limited the number of batches to 10, that is approximately 33 days of data.

We used two different settings 9 to compare the datadriven and the user-driven approaches. In the paired sample (also referred to as comparative evaluation), each of the 40 participants evaluated both approaches in a blind way, i.e. the two lists of events were randomly displayed to the user. In the unpaired sample (also known as independent evaluation), 60 participants evaluated either the data or the user-driven approach while not being aware of the type of method used.

Fig. 11 reports the results of this crowdsourcing-based evaluation. For the paired sample, the number of likes is greater or equal in the user-driven setting than in the datadriven one, while results are less obvious for the unpaired sample. The purpose of paired samples is to get better statistics by controlling for the effects of other "unwanted" variables. And so, as our sample sizes are quite small, results obtained on paired samples are probably the most reliable. In addition, the test of Wilcoxon [START_REF] Demsar | Statistical comparisons of classifiers over multiple data sets[END_REF] is applicable on the paired sample, while it is not on the unpaired ones. However, even for paired samples, the Wilcoxon test does not allow to reject the null hypothesis "the number of likes are similar", and the difference is not considered as significant. Considering the average ranks of liked events, we can observe that they are always better in the user-driven configuration than in the data-driven one. The difference in the values is considered as significant by both Wilcoxon and Nemenyi tests [START_REF] Demsar | Statistical comparisons of classifiers over multiple data sets[END_REF]. The Nemenyi test value is shown in Fig. 11: when the rank difference on the graduated line is greater than the CD value, the rank difference is considered not due to chance.

Thus, this experience with real users leads to nuance the claim that the user-driven approach makes it possible to identify more interesting events than the data-driven one. However, it confirms that the identified events are of much better quality for the user-driven setting than for the datadriven one. Similar experiments with simulated users are reported in supplemental material.

Illustrative results

Finally, we show some examples of events detected by our approach. Fig. 12 reports the top 3 events detected in New York, London, and Los Angeles datasets. Each event is described by the locations, time interval and top 8 most frequent terms of its related tweets.

The first event in New York is the Comic Con 10 , which 10. https://goo.gl/BR7kgp is an annual convention mainly dedicated to comics. It was organized in Jacob K. Javits Convention Center, the location associated to the related tweets. The two other events correspond to USA presidential elections, and the celebration of Halloween. In London, the first event is a Pride Parade organized in July 8th, 2017. The remaining are two geolocated events corresponding to a soccer event and a concert of U2. In Los Angeles, the top 3 events are respectively: the Official Disney Fan Club, E3 11 (a video game related event), and the FYF Fest 12 (a music festival).

CONCLUSION

In this paper, we introduced the novel problem of userdriven geolocated event discovery in social media. We handled the discovery of data-driven and user-driven event detection in a unified view. We designed two different algorithms to efficiently and effectively discover events based on geolocation and user feedback. Experiments demonstrate that, in the data-driven setting, our approach outperforms state of the art methods by a factor of two to several orders of magnitude. Furthermore, our approach is more robust to noise. We also provide evidence that non location-aware event detection approaches fail to discover geolocated events. Thus, user feedback cannot be considered by post-processing the events obtained by existing approaches. We also showed the ability of our method to directly discover geolocated events that are of interest for the user based on her feedback with crowdsourcing-based experiments. We believe that this work opens new directions for future research. For example, the event detection can be enhanced by thoroughly taking into account prior knowledge to detect really unexpected events and better propagate user feedback to the semantic neighborhood of liked events. Another interesting direction is to learn an explicit model of user interests and provide active learning based heuristics to foster the interactive process. to the Wilcoxon test, except for the NYC dataset, where the number of likes is considered to be similar. Indeed, SIGLER-Cov is more exhaustive and finds more events than SIGLER-Samp, which explains this point.

Notice that in this simulation between 300 and 800 events are presented to the virtual-users who, on the contrary to human users, have the ability to evaluate all of them. As already mentioned above, the order in which the events are presented to the users is essential. In order to evaluate this point, Fig. 1 presents the average ranks of events liked by both data and user-driven settings. Clearly the setting for which the liked events are ranked first is advantageous in real situations. We can observe that the average rank is always lower in the user-driven setting than in the datadriven one. This difference is considered significant by the Wilcoxon test on all datasets. This is also confirmed, in a more visual way, by the Nemenyi tests [START_REF] Demsar | Statistical comparisons of classifiers over multiple data sets[END_REF] displayed on the figure. When comparing the average ranks obtained by SIGLER-Cov and SIGLER-Samp, it appears that the later obtains significantly better ranks (smaller) for liked events that the former. Thus SIGLER-Samp identifies fewer events, but that are of high quality for users.

This simulation with virtual users allows us to conclude that the user-driven setting makes it possible to identify more relevant events than the data-driven one, whether in terms of quantity and quality. Besides, SIGLER-Samp identifies fewer geolocated events than SIGLER-Cov, but they are of better quality.

COMPARATIVE STUDY IN REAL WORLD DATASET

Based on synthetic data, we have studied in Section 6.2 the ability of our approach to detect local events, and we compared it with other state-of-the-art methods. Ideally, one would prefer to use real world datasets to perform such evaluation. However, we do not have the ground truth of the studied real world data. This makes it very hard to achieve an objective comparison on them. Nevertheless, we show in Table 2 the top 10 events returned by SIGLER-Cov, MED, and GeoBurst, on the first 10k tweets of NYC dataset, and we make a discussion about them. The number of tweets is limited to only 10k, in order to be able to compare with MED which has scalability issues.

We can notice that there are some similar results of SIGLER-Cov with those of MED and GeoBurst. In fact, SIGLER-Cov and MED have both returned the New York Comic Con 3 (1, 4 and 8 in SIGLER-Cov, 3 and 4 in MED), Beyoncé Concert 4 (2 in SIGLER-Cov, 5 and 8 in MED), and Taylor Mac concert 5 (5 in SIGLER-Cov and 10 in MED) .

TABLE 2

Top 10 events returned by SIGLER-Cov, MED, and GeoBurst, in NYC dataset, for the first 10k tweets (the day of 8 Oct. 2016). True positive events are market in bold while false negative events are not.

Both SIGLER-Cov and GeoBurst identified the FOLD Festival of Nile Rodgers 6 (9 in SIGLER-Cov and 1 in GeoBurst). However, the rest of top results of GeoBurst are different from the ones of other approaches. GeoBurst seems to give more importance to small events. In fact, each of the top 10 events of GeoBurst contain at most 10 tweets, while the number of tweets in top results of SIGLER-Cov (resp. MED) varies between 43 and 3k (resp. between 42 and 1280).

We believe that the results 1, 2, 7, and 9 of MED, and the result 4 of GeoBurst are not relevant. Indeed, they are defined with terms that do not correspond to any real life event (e.g., nyc, job, hiring, foodporn, etc.). Concretely, The terms "nyc, newyork, love, manhattan, job, hiring, newyorkcity, photo, repost" are very frequent in New York dataset. Each of them appear at least 30 times in 90% of the days. The term "saturday" is frequently used in Saturday (more than 30 times in 80% of cases). The terms "food, foodie, yummy, eeeeeats" also appear in a large number of posts where people want to share their feeling about some food experience. Each of them is used at least 7 times in 50% of the days. The term "ridetheferry" is used by people who pass by the NY Waterway Ferry. It occurs between 1 and 6 times in 22 different days.

Fig. 1 .

 1 Fig. 1. Overview of the user-driven event detection system.

  ) the time at which b was sent (b.time), (3) the GPS coordinates of the post of b (b.loc). From such a batch, we collect the following data: (1) H, the set of terms H = S b2B b.terms; (2) T = Jt 1 , t m K, the time 2. The posts emitted consecutively in a given period of time. Symbols Definitions B = {b 1 , b 2 , ...} The set of posts. Each post b 2 B is described by (1) its terms b.terms, (2) the time b.time at which it was sent, (3) and b.loc the GPS coordinates of b. H = {h 1 , h 2 , ...}

Fig. 2 .

 2 Fig. 2. Examples of liked events {P 1 , P 2 , ..., Pz}, and the values of rank for terms associated to these events.

Fig. 3 .

 3 Fig. 3. A toy example that illustrates (a) the subgraph enumeration, and (b) the scores of terms in some vertices. Proof 1. As P i6 =j |a ij | = ↵ P i6 =j

Algorithm 1 : 6 C {v 2 CAlgorithm 2 :

 1622 SIGLER-Cov( , minCov, R 1 ) Input: the quality threshold, minCov the coverage threshold Output: R 1 a set of coverage guaranteed geolocated events | H({v}, I) 6 = ;} 7 SGEnumerate(I, ;, C,R1, , minCov) SGEnumerate(I, S, C, R 1 , ,minCov) Input: I a time interval, S the current explored subgraph, C the candidate sets, the quality threshold, minCov the coverage threshold Output: R 1 the set of events

Proposition 3 .

 3 ), We denote by (I, S, C) the set of all patterns that can be reached when expanding S by adding vertices from C: (I, S, C) = {(S 0 , I) | S 0 ✓ S [ C and S ✓ S 0 }, that is to say, the patterns that are generated from SGEnumerate(I, S, C, R 1 , , minCov). The following property states that UB(S [ C, I, H(S, I)) upper bounds M u for all subsequent patterns: Let S ✓ V , I v T , and C ✓ V \S. For all patterns P 0 = (S 0 , I) 2 (I, S, C), UB(S [ C, I, H(S, I)) M u (S 0 , I). Proof 3. Since S 0

Definition 5 .Proposition 6 .

 56 |H(P 0 )\H(Pr)| |H(P 0 )\H(Pr)|+|H(P 0 )\H(Pr)| = q ? +x |H(P 0 )\H(Pr)|+q ? +x with x 0. Let's denote g(x) = q ? +x |H(P )\H(Pr)|+q ? +x . We have cov(H(P 0 ), H(P r )) g(x) as H(P 0 ) ✓ H(P ). Knowing that the derivative g 0 (x) = |H(P )\H(Pr)| (|H(P )\H(Pr)|+q ? +x) 2 0, then g(x) takes its lower value when x = 0. Thus, g(x)q ?|H(P )\H(Pr)|+q ? = cov(H ?, H(P r )) and we conclude the proof. ⇤ We define the function LB as LB(P, C, P r ) = min{cov(S [ (C \ S r ), S r ), cov(I, I r ), cov(H ? , H(P r ))} For each pattern P 0 = (S 0 , I) 2 (I, S, C) such that M u (P 0 )

Proposition 7 .Proof 7 .

 77 The two main steps are repeated (lines 8 to 21) until P 0 = P . At each iteration, the pattern P = (S, I) is extended by adding a vertex to S or a timestamp to I. Since S and I are respectively bounded by V and T , this loop necessarily stops after at most |V | + |I| iterations. All patterns with nonzero M u value have a non zero probability to be generated. For each pattern P = (S, I), if M u (P ) > 0 then P(P 2 R 2 ) > 0 Let us prove it by induction on n = |S| + |I|.

P 2 Fig. 4 .

 24 Fig. 4. A step of SIGLER-Samp: P 0 are the patterns that can be generated from the current P when considering the graph of Fig.3.

  ) and (area(b.loc) 2 S) and (b.time 2 I)}| 1 0, otherwise

1 )

 1 the F score values achieved by the different approaches when noise rate is varying. From this figure we can draw the following conclusions: Non location-aware event detection approaches cannot detect geolocated events, as INSIGHT and EDCOW F score is always lower than 0.2. 2) SIGLER, MED and GeoBurst perform well with low noise rate. However, both SIGLER-Cov and SIGLER-Samp are more robust to noise than MED and

Fig. 5 .

 5 Fig. 5. Average and error bars of F score values obtained over 10 generated datasets for a given noise rate value ( = 5 and minCov = 0.8).Non location-aware event detection approaches are not able to detect geolocated events. MED fails in presence of noise. Runtime of

Fig. 6 .

 6 Fig. 6. Average and error bars of F score obtained according to and minCov. Default values are: noiseRate = 0.8, minCov = 0.8, = 5.

6 .

 6 The runtime for SIGLER corresponds to the complete process including the post-processing step described in Section 5.3. This explains the slight variation of the runtime of SIGLER-Samp for different configurations.

Fig. 7 .

 7 Fig. 7. Runtime and number of events of SIGLER-Cov, SIGLER-Samp, MED and GeoBurst when varying the number of tweets (default values of SIGLERs: 2000 vertices, t = 3h, = 10 and minCov = 0.8).

Fig. 8 .

 8 Fig. 8. Number of events by SIGLER-Cov and SIGLER-Samp and runtime of SIGLER-Cov according to the number of vertices, and the time granularity when considering the whole dataset (default values: 652k tweets, 2000 vertices, t = 3h, = 10 and minCov = 0.8).

Fig. 9 .

 9 Fig. 9. Similarity of the results of SIGLER-Cov with the ones of SIGLER-Samp with respect to SIGLER-Samp time budget.

  of tweets. This led us to set = 40 for NYC, and = 15 for London and LA dataset.

Fig. 10 .

 10 Fig. 10. Runtime and number of discovered events by SIGLER-Cov according to minCov and (default value minCov=0.8, = 40).

Fig. 11 .

 11 Fig. 11. Ability to take user feedback into account with real users: number of likes (left), average ranks of liked events (center), Nemenyi tests on average ranks (right) for paired samples.

Fig. 12 .

 12 Fig. 12. Top 3 events detected in New York (left), London (center), and Los Angeles (right).

AnesFig. 1 .

 1 Fig. 1. Virtual user-driven geo-spatial event detection with SIGLER-Cov and SIGLER-Samp. Number of likes (1st column) and average ranks of events liked by both data and user-driven settings (2nd column), Nemenyi tests on number of likes and average ranks (3rd and 4th columns).

  = {a, b, d}. If S 0 is expanded with a vertex x, the new set H(S 0[ {x}, t) is necessarily included in the previous one. For example, H({v 1

	1 P	(S, I)

2 if C \ N (S) 6 = ; then 3 if UB(S [ C, I, H(P )) then 4 for Pr 2 R1 do 5 if LB(P, C, Pr) minCov then 6 return 7 Choose a vertex v 2 C \ N (S) 8 SGEnumerate(I, S [ {v}, C \ {v}, , minCov) 9 SGEnumerate(I, S, C \ {v}, , minCov) 10 else 11 if Mu(P ) then 12 for Pr 2 R1 do 13 if cover(P, Pr) minCov then 14 return 15 R1 R1 [ {P } Proposition 2 (anti-monotony of H(P )). Considering two patterns P 1 = (S 1 , I 1 ) and P 2 = (S 2 , I 2 ), if P 1 ✓ P then H(P 2 ) ✓ H(P 1 ). Proof 2. If h 2 H(P 2 ), then 8v 2 S 2 , 8t 2 I 2 , score(h, v, t) > 0. As S 1 ✓ S 2 and I 1 ✓ I 2 , thus, 8v 2 S 1 , 8t 2 I 1 , score(h, v, t) > 0, and thus h 2 H(P 1 ). ⇤ In Fig. 3 (b), the bursting terms of S 0 = {v 1 } are: H(S 0 , t)

TABLE 2

 2 Description of the real-world datasets.

  7. https://www.figure-eight.com 8. 134.214.104.134:6001 and 134.214.104.134:6002.

  9. The evaluation frameworks are available at: (1) for the paired sample: 134.214.104.134:6002, (2) for the umpaired sample: 134.214.104.134: 6001

  3. https://goo.gl/BR7kgp 4. https://goo.gl/FrZEBu 5. https://goo.gl/9pM6z3

	#	time	SiglerCov top 5 terms	time	MED top 5 terms	time	GeoBurst top 5 terms
	1	0h to 23h	nycc, nycc2016, cosplay, ny comic con, newyorkcomiccon.	0h to 23h	nyc, newyork, love, manhattan, saturday.	15h to 23h	nilerodgers, foldfest, bettemidler, foresthillsstadium, walkeratconcert.
	2	0h to 21h	formationworldtour, beyonce, formationtour, beyhive, theformationworldtour.	0h to 23h	newyork, job, hiring, newyorkcity, photo.	15h to 21h	raniahatoum, thelondonnyc, tripleb, blackbridalbliss, bridalgown.
	3	6h to 18h	rnrbrooklyn, runrocknroll, halfmarathon, brooklynwerunhard.	0h to 23h	nycc2016, cosplay, nycc, newyorkcomiccon, wonderwoman.	18h to 23h	intercoiffure, wella, icamoments, nerolisalonspa, wellapro.
	4	12h to 21h	smashingnycc, nigelthornberry, nigel, smashing, wildthornberries.	0h to 23h	nycc, ny comic con, cosplay, comiccon, marvel.	9h to 15h	ridetheferry.
	5	12h to 21h	24decadehistoryofpopularmusic, sawtaylormac, 24decades, marskado, afraidoffun.	0h to 23h	formationworldtour, beyonce, beyhive, metlifestadium, beyonce.	18h to 23h	sturgillsimpson, kingsbklyn, asailorsguidetoearth.
	6	15h to 23h	greenday, websterhall, revrad, saturdaynight, 90s.	0h to 23h	brooklyn, bushwick, williamsburg, sigurros, music.	0h to 12h	elitefridays, cityscapesny, imsobx, reposting, cityscapesnyc.
	7	18h to 21h	dosgualas, livvinyl, monies, freeze, megaman.	0h to 23h	repost, montanoy27, regram, alofokemusicnet, parkslopemoms .	18h to 23h	descendents.
	8	12h to 18h	ronswwadventure, 75thanniversary.	0h to 23h	formationtour, beyonce, theformationworldtour, nj, kendricklamar.	0h to 15h	50cent, dozadrumdealer, mynameisjuan, industrykilla, narcotechs.
	9	15h to 21h	foresthillsstadium, nilerodgers, fold, bettemidler, foresthills.	3h to 23h	foodporn, food, foodie, yummy, eeeeeats.	0h to 12h	deadrabbitnyc.
	10	18h to 21h	knicks, nets, nyknicks, brooklynnets, preseason.	0h to 23h	24decadehistoryofpopularmusic, sawtaylormac, 24decades, proofoflifenumber, marskado.	0h to 23h	doomocracy, pedroreyes, doomacracy, creativetime.

ACKNOWLEDGMENT

This work was supported by Group Image Mining (GIM) which joins researchers of THALES Group and LIRIS Lab, and by the ACADEMICS grant of the IDEXLYON, project of the Université of Lyon, PIA operated by ANR-16-IDEX-0005. The authors would like to warmly thank the reviewers for their valuable remarks, and Adnene Belfodil and Aimene Belfodil for interesting discussions.

User-driven geolocated event detection in social media -Supplementary material Anes Bendimerad, Marc Plantevit, C éline Robardet, Sihem Amer-Yahia F

USER-DRIVEN DISCOVERY BASED ON SIMU-LATED USERS

In this section, we provide supplementary experiments of the user-driven approach. We simulated virtual users who, depending on their "own interest", tend to prefer events of a given type. We evaluate their "satisfaction" according to the number of events that the system presents to them that they are inclined to like. Thus, virtual users having topics and/or location preferences are simulated and the experiment consists in studying the number of liked events when considering or not user feedback during the event discovery process.

To that end, we first extracted events in the three real datasets 1 and retain those spanning at least over 2 timestamps (the set E). Then, we manually annotated the events. The tags used for the annotation are Topics = {Business/Economics, Politics, Science/Technology, Art/Culture, Celebration, Music, Sport, Accident/Disaster}. Each event P can be annotated with several topics and the function Tag(P, ⌧ ) ! [0, 1] expresses the importance of the topic for the event (with P ⌧ 2Topics Tag(P, ⌧ ) = 1). Some detected events did not match to any category and the obtained distributions are presented in Table 1. • M. Plantevit is with University of Lyon, University Lyon 1, CNRS UMR 5205

• S. Amer-Yahia is with University of Grenoble Alpes, CNRS.

1. To obtain around 800 events on NYC, we used = 40, and to obtain around 400 events on LA and London, we used = 15. On all datasets we set minCov = 0.8.

A virtual user u prefers a specific topic, or location, or both of them. The function P u (P ) captures the preferences of the user u for the event P . It is defined according to 3 cases:

• If ⌧ is the preferred topic of u, P u (P ) = Tag(P, ⌧ ) • If `is the preferred location of u, we consider that u is interested in events at a distance from `at most equal to L and P u (P ) = max( L dist(`,P ) L , 0). Based on the surface area of the cities, we choose L = 5km for New York, and L = 10km for Los Angeles and London.

• If u has both topic and location interests, P u (P ) = Tag(P,⌧)+max( L dist(`,P)

Topics with fewer than 20 events were discarded. For the preferred locations, we consider several well-known places for each city 2 . Finally, to be able to automatically annotating computed events on these datasets, we used the Tag function to annotate hashtags and locations (for x = h, v, Tag 0 (x, ⌧ ) = P P 2E s. t. x2P Tag(P, ⌧ )) and then use them to automatically annotate events (Tag ? (P, ⌧ ) = P x2P Tag 0 (x, ⌧ )).

To evaluate how SIGLER-Cov and SIGLER-Samp effectively discover user-driven events, we simulate the same interactive process that we did with the real users in Section 6.4, but with virtual users this time.

Fig. 1 presents results of these experiments when simulating between 19 and 29 virtual users depending on the number of considered locations and topics on each dataset. For each dataset, we show boxplots of the average number of likes using SIGLER-Cov and SIGLER-Samp in the data and user-driven settings. We can observe that (1) the average number of likes in the user-driven setting is always greater than the one in data-driven configuration. This difference is considered as significant by the Wilcoxon and the Nemeny post-hoc [START_REF] Demsar | Statistical comparisons of classifiers over multiple data sets[END_REF] tests (the later is shown on