Hugues Mandon

Stefan Haar

Loïc Paulevé

Relationship between the Reprogramming Determinants of Boolean Networks and their Interaction Graph

In this paper, we address the formal characterization of targets triggering cellular trans-differentiation in the scope of Boolean networks with asynchronous dynamics. Given two fixed points of a Boolean network, we are interested in all the combinations of mutations which allow to switch from one fixed point to the other, either possibly, or inevitably. In the case of existential reachability, we prove that the set of nodes to (permanently) flip are only and necessarily in certain connected components of the interaction graph. In the case of inevitable reachability, we provide an algorithm to identify a subset of possible solutions.

Introduction

In the field of regenerative medicine, an emerging way to treat patients is to reprogram cells, leading, for instance, to tissue or neuron regeneration. Such a challenge has become realistic after first experiments have shown that some of the cell fate decisions can be reversed [START_REF] Takahashi | A decade of transcription factormediated reprogramming to pluripotency[END_REF]. Whereas the cells go through several multipotent states before reaching a differentiated state, the differentiation process can be inversed, producing induced pluripotent stem cells (iPSCs) from an already differentiated cell. By using a distinct differentiation path, this allows to "transform" the type of a cell. Alternatively, it is also possible to directly perform a trans-differentiation without necessarily going (back) through a multipotent state [START_REF] Graf | Forcing cells to change lineages[END_REF][START_REF] Del | Concise review: A population shift view of cellular reprogramming[END_REF].

In the aforementioned work, the de-and trans-differentiation has been achieved by targeting specific genes, that we refer to as Reprogramming Determinants (RDs), through the mediation of their transcription factors [START_REF] Takahashi | A decade of transcription factormediated reprogramming to pluripotency[END_REF][START_REF] Crespo | Detecting cellular reprogramming determinants by differential stability analysis of gene regulatory networks[END_REF].

The computational prediction of RDs requires to assess multiple features of the cell dynamics and the reprogramming strategy, such as the impact of the kind of perturbations (persistent versus temporary) and of their order; the nature of targeted cell type (differentiated/pluripotent), and the desired inevitability of their reachability (fidelity); the nature and duration of the triggered cascade of regulations (efficiency); and finally, the RD robustness with respect to initial state heterogeneity among cell population, and with respect to uncertainties in the computational model. So far, no general framework allows to efficiently encompass those features to systematically predict best combinations of RDs in distinct cellular reprogramming events.

In this paper, we address the identification of RDs from Boolean Networks (BNs) which model the dynamics of gene regulation and signalling networks. The state of the components (or nodes) of the networks are represented by Boolean variables, and the state changes are specified by Boolean functions which associate the next state of nodes, given the (binary) state of their regulators [START_REF] Thomas | Boolean formalization of genetic control circuits[END_REF][START_REF] Aracena | Maximum number of fixed points in regulatory boolean networks[END_REF]. BNs are well suited for an automatic reasoning on large biological networks where the available knowledge is mostly about activation and inhibition relations [START_REF] Abou-Jaoudé | Model checking to assess t-helper cell plasticity[END_REF]. Such activation/inhibition relations between components form a signed directed graph, that we refer to as the Interaction Graph.

In this work, we make the assumption that the differentiated cellular states correspond to the attractors of the dynamics of the computational model, i.e., the long-run behaviours. In the scope of BNs, those attractors can be of two kinds: either a single state (referred to as a fixed point), or a terminal cyclic behaviour.

The relationship between the IG of BNs and the number of their attractor has been extensively studied [START_REF] Aracena | Maximum number of fixed points in regulatory boolean networks[END_REF][START_REF] Richard | Positive circuits and maximal number of fixed points in discrete dynamical systems[END_REF][START_REF] Richard | Negative circuits and sustained oscillations in asynchronous automata networks[END_REF]. However, little work exists on the characterization of the perturbations which trigger a change of attractor. Currently, most of RDs prediction are performed using statistical analysis on expression data in order to rank candidate transcription factors [START_REF] Chang | Systematic search for recipes to generate induced pluripotent stem cells[END_REF][START_REF] Owen | A predictive computational framework for direct reprogramming between human cell types[END_REF][START_REF] Jo | An integrated systems biology approach identifies positive cofactor 4 as a factor that increases reprogramming efficiency[END_REF]. Whereas based on network models, those approaches do not allow to derive a complete set of solution for the reprogramming problem. In [START_REF] Crespo | Detecting cellular reprogramming determinants by differential stability analysis of gene regulatory networks[END_REF], the authors developed a heuristic to derive candidate RDs from a pure topological analysis of the interaction graph: the RDs are selected only in positive cycles that have different values in the started and target fixed points. However, there is no guarantee that the derived RDs can actually lead to a change of attractor in the asynchronous dynamics of the Boolean networks, and neither that the target fixed point is the only one reachable. Finally, [START_REF] Gao | On the stability of conjunctive boolean networks[END_REF] gives a formal characterization of RDs subject to temporal mutations which trigger a change of attractor in the synchronous semantics of conjunctive Boolean networks.

Contribution This work relies on model checking and reachability analysis, that have been proved useful and successful in previous studies [START_REF] Abou-Jaoudé | Model checking to assess t-helper cell plasticity[END_REF][START_REF] Paulevé | Goal-oriented reduction of automata networks[END_REF].

Given a BN, all of whose attractors are fixed points, given an initial fixed point and a target fixed point, we provide a characterization of the candidate RDs (set of nodes) with respect to the interaction graph and for two settings of cellular reprogramming:

with a permanent perturbation of RDs, the target fixed point becomes reachable in the asynchronous dynamics of the BN; with a permanent perturbation of RDs, the target fixed point is the sole reachable attractor in the asynchronous dynamics of the BN.

For the first case, we prove that all the RDs are distributed among particular strongly connected components of the interaction graph, and we give algorithms to determine them in both settings. In the second case, we prove that only some of them are distributed among strongly connected components of the interaction graph. We provide an algorithm to identify possible combination of permanent perturbations leading to inevitable reachability of the target fixed point. Whereas the algorithm may miss some solutions, all returned solutions are correct.

Outline Section 2 gives the definitions and basic properties of BNs and of their asynchronous dynamics.

) i = x i 2 Background
In this section, we give the formal definition of Boolean networks, their interaction graph and transition graph in the asynchronous semantics. Finally, we recall the main link between their attractors and the positive cycles in their interaction graph.

Definitions

Boolean Network (BN): A BN is a finite set of Boolean variables, each of them having a Boolean function. This function is a logical Boolean function depending from the network's variables and determining the next state of the variable.

Definition 1 (Boolean Network (BN)). A Boolean Network is a function f such that:

f : {0, 1} n → {0, 1} n x = (x 1 , ..., x n ) → f (x) = (f 1 (x), ..., f n (x)) Example 1. An example of BN of dimension 3 (n = 3) is f 1 (x) = x 3 ∨ (¬x 1 ∧ x 2 ) f 2 (x) = ¬x 1 ∨ x 2 f 3 (x) = x 3 ∨ (x 1 ∧ ¬x 2 )
Interaction Graph: To determine the RDs, we rely on a simplification of the interactions between the genes, and of the concentrations. A gene will either be active or inhibited. Gene interactions are simplified likewise, a gene either activates or inhibits another gene, and we ignore time scales. With this in mind, an interaction graph (Def.2) can be build: genes are the vertices, and the interactions are the oriented arcs, labelled either + or -, if it is an activation or an inhibition.

Definition 2 (Interaction Graph

). An interaction graph is noted as G = (V, E), with V being the vertex set, and E being the directed, signed edge set,

E ⊂ (V × V × {-, +})
A cycle between a set of nodes C ⊆ V is said positive (resp. negative) if and only if there is an even (odd) number of negative edges between those nodes.

An interaction graph can also be defined as an abstraction of a Boolean network: the functions are not given and not always known, but if a vertex u is used in the function f v , there is an edge from u to v, negative if f v (x) contains ¬x u and positive if it contains x u .

Definition 3 (Interaction Graph of a Boolean network (G(f ))

). An interaction graph can be obtained from the Boolean network f : the vertex set is [n], and for all u, v ∈ [n] there is a positive (resp. negative) arc from u to v if f vu (x) is positive (resp. negative) for at least one x ∈ {0, 1} n (For every u, v ∈ {1, ..., n}, the function f vu is the discrete derivative of f v considering u, defined on {0, 1} n by :

f vu (x) := f v (x 1 , .., x u-1 , 1, x u+1 , .., x n ) -f v (x 1 , .., x u-1 , 0, x u+1 , .., x n )).
Given an interaction graph G = (V, E), and one of its vertex u ∈ V , P u denotes the set of ancestors of u, i.e., the vertices v for which there exists a path in E from v to u. Similarly, p u is the set of the parents of u, i.e., v ∈ p u ⇒ (v, u, s) ∈ E. Furthermore, G[P u ] is the induced subgraph of G with P u as vertex set.

Fig. 1 gives an example of an interaction graph, which is also equal to G(f ), where f is the Boolean network of Ex.1.

Transition Graph: We model the dynamics of a Boolean network f by transitions between its states x ∈ {0, 1} n . In the scope of this paper, we consider the asynchronous semantics of Boolean networks: a transition updates the value of only one vertex u ∈ [n]. From a single x ∈ {0, 1} n , one has different transitions for each vertex u such that f u (x) = x u . This leads to the definition of the transition graph (Def. 4) where vertices are all the possible states {0, 1} n , and edges correspond to asynchronous transitions. Attractors, Fixed point : BN's Attractors are the terminal strongly connected components of the transition graph, and can be seen as the long-term dynamics of the system. Note that an attractor is always a set of states, but it can contain either multiple distinct nodes, that is the system oscillate between multiple states (cyclic attractor ) or a unique point, i.e the system stays in the same state (fixed point).

→ x{u} | x ∈ {0, 1} n , u ∈ [n], x u = (f (x)) u }. An existing path from x to y is noted x → * y.
Definition 5 (Attractor).

S ⊆ {0, 1} n is an attractor ⇔ S = ∅ (1)
and ∀x ∈ S, ∀y ∈ {0,

1} n \ S, x → y (2)
and ∀x ∈ S, S \ x does not verify (2)

(3)

If |S| = 1 then S is a fixed point. Otherwise S is a cyclic attractor. Given a BN f , FP(f ) ⊆ {0, 1} n denotes the set of its fixed points (∀x ∈ FP(f ), f (x) = x).
Example 2. The BN of Ex.1 has 3 attractors that correspond to the 3 terminal strongly connected components of Fig. 2: {010, 110} (cyclic attractor), {101} and {111} (fixed points).

On the link between attractors and the interaction graph

Theorem 1 is a conjecture by René Thomas [START_REF] Thomas | Boolean formalization of genetic control circuits[END_REF] that has been since demonstrated for Boolean and discrete networks [START_REF] Aracena | Maximum number of fixed points in regulatory boolean networks[END_REF][START_REF] Remy | Graphic requirements for multistability and attractive cycles in a boolean dynamical framework[END_REF]: if a Boolean network has multiple attractors then its interaction graph necessarily contains a positive cycle. In the case of multiple fixed points, any pair of fixed point differ at least on a set of nodes forming a positive cycle.

Theorem 1 (Thomas' first rule). If G = (V, E) has no positive cycles, then f has at most one attractor. Moreover, if f has two distinct fixed points x and y, then G has a positive cycle between vertices C ⊆ V such that x v = y v for every vertex v in C.

We can also remark that for a vertex to stay at a value y v where y is a fixed point, it only needs its ancestors to have the same values as in y.

Remark 1. ∀y ∈ FP(f ), ∀u ∈ [n], ∀z ∈ {0, 1} n , z verifying ∀j ∈ P u , z j = y j , we have f u (y) = y u = f u (z).
Proof. Let u be a vertex in [n]. f (u) only depends of the incoming arcs in u, so it only depends of p u , which in turn depends on its parents. By induction, f u (y) only depends of P u , and so, if

f u (y) = y u in G, then f u (y) = y u in G[P u ].

Formalisation of the BN Reprogramming with Permanent Perturbations

Given two fixed points x and y of Boolean network f , we want to identify sets of nodes, referred to as Reprogramming Determinants (RDs), that when changed in x enable to switch to y. As our theorems rely on the differences between the fixed points, we chose to focus on fixed points solely. Further work will extend, if possible, these theorems and algorithms to all kind of attractors. In the scope of this paper, by "change" we mean permanently set the vertex to a new fixed value. If we "change" u to 1 (resp. 0), then f u (x) = 1 (resp. 0) for all x. When switching to y (by changing I) is possible, we have two cases : it either means that y is reachable from x [x I =y I ] (existential reachability, Def. 6), or that y is the only reachable fixed point from x [x I =y I ] (inevitable reachability, Def. 7). These are two different approaches that we will both consider. To remove the temporal aspect, we make all the changes at the same time (hence x [x I =y I ] , otherwise an order should be visible), and only watch if y is reachable. This also means that there is no indication of how long it takes for y to be reached. can be defined as IR F (x, y) → w where w is the set of all minimal vertices sets

I such as ∀z ∈ {0, 1} n , x [x I =y I ] → * z ⇒ z → * y.
These two functions will give different results, and have different meanings, as shown in the examble below.

Example 3. Let us consider the BN f of Fig. 3 and its transition graph reproduced in Fig. 4. f has 4 fixed points: 0000, 0001, 1100 and 1101. Let x = 0000 and y = 1100. Fixing the node {1} to 1 in x makes y reachable : 1100 (=y) is reachable from x [x1=1] = 1000 with the Boolean network f defined by f 1 (x) = 1 and

f 2 = f 2 , f 3 = f 3 , f 4 = f 4 .
The transition graph of f , considering the first node being active, corresponds to the left part of the transition graph in Fig. 4. One can then remark that y is not the only fixed point reachable: from 1000, 1101 is also reachable. If we also fix the node {4} to 0, y is the only reachable fixed point from x [x1=1,x4=0] in the Boolean network f such that f 1 (x) = 1,

f 2 = f 2 , f 3 = f 3 , and f 4 (x) = 0.
Therefore, with the previous definitions, {1} ∈ ER F (0000, 1100) but {1} / ∈ IR F (0000, 1100); and {1, 4} ∈ IR F (0000, 1100) but {1, 4} / ∈ ER F (0000, 1100). Moreover, we also have {1, 2} and {1, 3} ∈ IR F (0000, 1100). In this section, we show the link between the RDs and the Strongly Connected Components (SCCs) of the interaction graph of the Boolean network f . Our results make the assumption that all the attractors of f are fixed points (no cyclic attractors).

f1(x) = x1 f2(x) = x1 f3(x) = x1 ∧ ¬x3 f4(x) = x3 ∨ x4

SCC Ordering

To switch from x to y, we want to change the value of each vertex u that has different values for x and y (x u = y u ) and to prevent each vertex v that verifies x v = y v from changing value. We know that changing the value of a vertex can have an impact on other vertices, but we also know that it will only impact its descendants. So, if a vertex has a different value in x and y but none of its ancestors do, then it is necessary to change this vertex. So, to know which vertices need to be changed first, the best way is to order them, with a topological order for example. Of course, if there are loops, an order is impossible to determine, we have to reduce all SCCs to single "super-vertices" to achieve it. In the remaining of this paper, we will consider SCCs which contain at least one positive cycle, because they are known to change between fixed points (Theor.1), we call O the SCC set that contains all such SCCs. Reducing the graph to its SCCs makes possible to rank them from 1 to k with any topological order, noted ≺:

for all i, j ∈ [k], j > i ⇒ O j ≺ O i . Let C 0 be the set {O i ∈ O | O j , O j ≺ O i },

and recursively define slices

C K = {O i ∈ (O \ l∈{1,..,K-1} C l ) | O j , O j ≺ O i }.
Given the definition of the slices, for all topological orders, the slice set will be the same. The slices are numbered from 1 to c.

From this order, we know which SCCs need to be impacted, still, SCCs ranked lower in the hierarchy need not be impacted by the change in their ancestors (see ex.5) The relation ≺ only gives an order to make the changes, from which one can determine if further changes are needed.

Example 4. Showing that only using the topological order is not sufficient. Any algorithm that only used the topological order without computing the reachable fixed points would not suffice, as the example from Fig. 5 shows : the switch from the fixed point 01100 to 10101 would be computed by just modifying {1}, but in fact {4} will always be fixed at 0, because {4} is always inhibited by {3}, so {5} needs to be changed too.

f1(x) = ¬x2 f2(x) = ¬x1 f3(x) = x1 ∨ x2 f4(x) = x2 ∧ ¬x3 f5(x) = x4 ∨ x5

SCC Filtering

Whether we want y to be the only reachable attractor, or merely to be one of potential several such attractors, the ordering from the previous part is the same, but the filtering will differ.

Theorem 2. If a vertex u such as x u = y u and u is not in a positive cycle, then modifying u's ancestors is sufficient to modify u. More generally, to switch from x to y, modifying only those strongly connected components that contain at least a positive cycle is sufficient.

Proof. Let u be a vertex such that x u = y u and u does not lie in a positive cycle. If u is in a negative cycle, the incoming arc from the cycle is irrelevant : given that x and y are fixed points and that u has a distinct value in each, the negative cycle does not change u's value. Given that u is not in a positive cycle, u is not in a SCC (or not relevant if it is in a negative cycle). That means that none of the ancestors are descendants of u. Let z be the state where all of P u (u's ancestors) have the same value that in y. By the remark from Sect.2, for all v ∈ G[P u ], we have f v (z) = z v = y v . So, either f u (z) = y u , and the theorem is proven, either f u (z) = y u , then, by Theor.1, u is in a positive cycle, contradiction.

By recursion over the first part, modifying all the SCCs that contain positive cycles so their vertices have the same value as in y modifies all their children, and then all the children of their children, and so on, until the whole graph has the same values as y.

Selecting the SCCs will differ with the two methods. It relies on the same base, searching the higher SCC that should have its values modified and that is not already selected. "Modified" means that all the values of the SCC are fixed to their values in y. The set of the selected SCCs is S.

SCC Filtering for Existential Reachability

We consider the RDs for the BN reprogramming with Existential Reachability. We give an algorithm to identify different sets of SCCs for which the mutation in the initial fixed point ensure the reachability of the target fixed point. We will prove that the identified combination of SCCs is complete and minimal.

Basically, the algorithm reviews linearly the SCC slices according to ≺ and adds the minimal combinations of SCCs to S that are different in y and the fixed points reachable from x [x S =y S ] :

1. S := ∅ 2. For i ranging from 1 to c:

-

T := ∅ -∀s ∈ P (C i ) such that s minimal ∃z ∈ {0, 1} n , z Ci\s = y Ci\s , x [x I =y I |I∈S] → * z, T := T ∪ s. -S := S ×T .
With × being a product and union : for a set I of subsets I 1 , .., I k and a set J 1 , .., J l , this product × is defined by : I ×J = {I 1 ∪J 1 , .., I 1 ∪J l , I 2 ∪J 1 , ...., I k ∪J l } Complexity : In the worst case, the above algorithm perform c × 2 l reachability checks (PSPACE-complete [START_REF] Cheng | Complexity results for 1-safe nets[END_REF]), where l is the size of the largest slice.

Existence of a solution and proof of correctness : Forcing all SCCs of such problem that differ on x and y to have the same value as in y is one solution. In the worst case, that is what the algorithm will find. Since the algorithm tests reachability, and a solution exists, it will find one.

Example 5. We apply the algorithm on the BN of Fig. 6 with x = 00000 and y = 11011.

1. S := ∅ 2. C 1 : s minimal ⇔ s = {1} 3. S := S ×{1} = {{1}} 4. C 2 : s minimal ⇔ s = ∅ 3 5. S := S ×∅ = {{1}}.
We now prove the completeness of the algorithm and the minimality of the returned sets of SCCs (Theorem 3) and that any RDs in ER(x, y) is spans only and necessarily in one of the set of SCCs identified by the algorithm (Theorem 4). Theorem 3. S only contains minimal SCC sets, and S is complete.

f1(x) = x1 f2(x) = x1 f3(x) = x1 ∧ ¬x2 f4(x) = x3 ∨ x4 f5(x) = x2 ∨ x5
Proof. Minimality : Inside every slice, the SCCs are totally independant one another. Moreover, given the order exploiting, we can deduce that the sum of the minima on each slice is the minimum on the whole graph.

Completeness : Let I be a minimal SCC set such as x [x J =y J |J∈I] → * y, then, for every slice C i , I ∩ C i is minimal, since once all the SCCs in a slice can be changed to the way they are in y, we can always choose the path that allows this change. Hence I ∈ S.

SCC Filtering for Inevitable Reachability

We now give an algorithm to identify a set of SCCs for which the mutation in the initial fixed point is sufficient to ensure the Inevitable Reachability of the target fixed point.

The algorithm computes all reachable fixed points from x with the SCCs in S modified, and find the one, z, that has the lower SCC (in the ranking given by ≺) in which a vertex u is such that z u = y u . As we are looking for all reachable fixed points, this will always return the same SCC (even if the order is only partial), thus allowing the algorithm to be deterministic. We add this SCC to S, and repeat until y is the only reachable fixed point.

1. S := ∅ 2. While ∃z ∈ FP(f ), z = y, x [x I =y I |I∈S] → * z -S := S ∪ {O i }, with i = min a∈{1,..,k} (a | ∃z ∈ FP(f ), z Oa = y Oa , x [x I =y I |I∈S] → * z)
If two (or more) SCCs A and B are such that they are differently ordered in two distinct orders, then A has no influence on B and neither has B on A. Then, the algorithm will select both SCCs if neither are impacted by the previous changes, so the order does not matter.

Existence of a solution and proof of correctness : A solution is to fix all the SCCs of the graph to their value in y. Since there exists a solution and the algorithm tests if y is the only reachable point, and follows the order given by ≺, it will end and find a solution.

Complexity : Computing all fixed points reachable is PSPACE-complete [START_REF] Chatain | Characterization of reachable attractors using Petri net unfoldings[END_REF]. It is used k times (number of SCCs) in the worst case. Theorem 5. S is minimal.

(x) = x1 f2(x) = x1 f3(x) = x1 ∧ ¬x2 f4(x) = x3 ∨ x4 f5(x) = x2 ∨ x5
Proof. If a set S 1 exists such that S 1 has a lower cardinal than S and modifying S 1 makes y the only reachable point, then we can reduce S 1 to a subset of S.

Let s be a SCC in S \ S 1 , thus there exists a fixed point z such that z s = y s and by construction of S, z is reachable from x modified by S 1 .

We remark that, contrary to the case of Existential Reachability, the RDs for Inevitable Reachability of the target fixed point are not necessarily in SCCs containing positive cycles. Indeed, in Ex.3, we showed that IR F (x, y) can refer to nodes that do not belong to O (such as the node 2 for the BN of Fig. 3). But we can also remark that if a RD v is not in a SCC containing a positive cycle, then

x v = y v . Theorem 6. ∀v ∈ IR(x, y), x v = y v ⇒ ∃scc ∈ O, v ∈ scc Proof. Let v ∈ IR(x, y) such that for all scc ∈ O, v ∈ scc. By Theor.1, if v is such that x v = y v , then modifying the SCC in O is enough to modify v. But v ∈ IR(x, y) and IR(x, y) is minimal, thus x v = y v .

Identifying Determinants within SCCs

We know that modifying all the SCCs selected is enough to switch from x to y, but to reduce the genes selected, we could try to modify only some of the vertices to achieve the same result. But, as dynamics are involved, there could be unwanted changes (or wanted and unpredicted changes, in the case where we want y to be reachable) in the descendants.

An idea could be to select the feedback vertex set of the SCC : by fixing the vertices from this set, we effectively destroy every circle, thus the only reachable state of the SCC is the one having the same values as y. This, however, does not solve the problem : in Ex.7, {1} is the feedback vertex set, and we still have the same issue. Moreover, it miss some of the possible solutions (modifying {2} or {3} could work to change the whole SCC in Ex.7) or even dismiss the best solution (in Ex.7, changing {3} makes y the only reachable fixed point and solves the issue).

Example 7. Illustration of the problem with dynamics.

f1(x) = ¬x3 ∧ ¬x2 f2(x) = ¬x1 f3(x) = ¬x1 f4(x) = x2 ∧ ¬x1 ∧ ¬x3 f5(x) = x4 ∨ x5 1 2 3 4 5
Fig. 8. BN of dimension 5 (left) and its interaction graph (right)

We decide that x = 10000 and y = 01100, and 01101 = z, those are all fixed points. Let's suppose we want y to be the only fixed point reachable. The algorithm will see that if the whole first SCC is modified {1, 2, 3}, y is the only reachable fixed point. It could pick {1} to be modified, but instead of 00000 → 00100 → 01100, we can have 00000 → 01000 → 01010 → 01011 → 01111 → 01101 This leads to z being reachable by only modifying {1}, and so the algorithm would be wrong. This leaves to two kinds of approaches : either a way to modify the SCC so that it does not impact its descendants can be found, either we need to select the vertices to be modified in the SCC as a intermediary step in the process, and redesign S as a list of vertices instead of a list of SCCs.

By exploiting the results of the preceding section, we show an algorithm to compute a set of RDs which guarantees the Inevitable Reachability of the target fixed point. The algorithm recursively picks a vertex u in the lowest SCC in the order given by ≺ in O, and modify its associated function to become the constant value y u . The interaction graph of the resulting Boolean network is a sub-graph of the initial interaction graph, where all the input edges of the node u have been removed. Hence, the SCC O 1 is split in the new interaction graph. If necessary, another vertex can be picked in the lowest SCC in the new interaction graph: RecursiveAlgorithm(f , rd) : • return rd Remark that the algorithm always find at least one solution: if the target fixed point is not the only reachable fixed point, then there is at least one positive cycle (and hence a SCC) which has a different state (and hence will be selected by our algorithm).

-If ∃z ∈ FP(f ), x [x rd =y rd ] → * z then : • res = ∅ • i =
Example 8. Applied to the BN of Fig. 8 with x = 10000 and y = 01100, the above algorithm returns, for instance, the RD {2, 5}: indeed, {2} belongs to O 1 . When fixing f 2 = 1, the new interaction graph has two SCCs with positive cycles: {1, 3} and {5}. From the state 11000, two fixed points are reachable: 01100, 01101. Hence, because the SCC {1, 3} has the same values than in y in those two fixed points, the next vertex in picked in the SCC {5}. Finally, from the state 11001, y is the only reachable fixed point.

This paper provides the first formal characterization of the Reprogramming Determinants (RDs) for switching from one fixed point to another in the scope of the asynchronous dynamics of Boolean networks.

In the case of reprogramming with existential reachability of the target fixed point, we prove that all the possible minimal RDs modify nodes in particular combinations of SCCs of the interaction graph of the Boolean network. We give an algorithm to determine exactly those combinations of set of nodes. Our characterizations rely on the verification of reachability properties.

In the case of reprogramming with inevitable reachability of the target fixed point, we show that the RDs are not necessarily in SCCs. However, we provide an algorithm which identifies RDs that guarantee the inevitable reachability by picking nodes in appropriate SCCs. The algorithm relies on the enumeration of reachable fixed points.

One of the main limitation of our algorithms is the numerous reachability checks it needs to perform. Future work will consider methods and data structures for factorizing the exploration of the Boolean network dynamics.

The present work considered only permanent mutations: when a node is mutated, it is assumed it keeps its mutated value forever (its local Boolean function becomes a constant function). Considering temporary mutations, i.e., where the local Boolean function of mutated nodes is restored after some time, is a challenging research direction: one should determine the ordering and the duration of mutations, and the set of candidate mutations is a priori no longer restricted to connected components, as it is the case for permanent mutations.

Fig. 1 .

 1 Fig. 1. Interaction graph of Ex.1 A "normal" blue arrow means an activation, and a "flattened" red arrow means an inhibition.

Fig. 2 Fig. 2 .

 22 Fig.2gives the transition graph of the asynchronous dynamics of Boolean network of Ex.1.

Fig. 4 . 3 4

 43 Fig. 3. A BN of dimension 4

Fig. 5 .

 5 Fig. 5. BN preventing changes in the lower SCC

Fig. 6 .

 6 Fig. 6. BN of dimension 5 (left) with its interaction graph (right). Slices are enclosed in boxes. C1 = {{1}}, C2 = {{4}, {5}}.

Theorem 4 .

 4 ∀c ∈ ER(x, y), ∃I ∈ S, ∀u ∈ c, ∃scc ∈ I, u ∈ scc. Proof. Let c be a vertex set in ER(x, y) and u one of the vertices. If u ∈ O, then c is not minimal, by Theorem 2. If for all I ∈ S, u is in o ∈ (O \ I) then there exists a path such that changing o's ancestors makes o's change possible, and the ancestors need to be changed as well, by construction of I. So c \ u would have the same effect, and c would not be minimal. If u ∈ o, then there exists I ∈ S and scc ∈ I, such as u ∈ scc.

Example 6 .

 6 We apply the algorithm on the BN of Fig.7. with x = 00000 and y = 11011. Starting from S := ∅, the only reachable fixed point is (0)00(0)(0) (the SCCs from O are parenthesized). The smallest SCC o such asx [x S =y S ],o = y o is O 1 , so S := ∅ ∪ {O 1 } = {O1 }. The reachable fixed points from x [x I =y I |I∈S] = 10000 are now: (1)10(1)(1) and (1)10(0)(1). The smallest SCC o such that x [x S =y S ],o = y o is O 3 . We set S := S ∪ O 3 = {O 1 , O 3 } and we obtain that the only reachable fixed point from x [x I =y I |I∈S] = 10010 is (1)10(1)(1) which is y. So the algorithm stops.

  f1

Fig. 7 .

 7 Fig. 7. BN of dimension 5 (left) with its interaction graph (right) on which the SCCs containing positive cycles (O) are boxed.

  min a∈{1,..,k} (a | ∃z ∈ FP(f ), z Oa = y Oa , x [x I =y I |I∈S] → * z) • For all u ∈ O i : * g := f with g u := y u * res := res∪ RecursiveAlgorithm(g, rd ×{u}) • return res else :

  Similarly, given x, y ∈ {0, 1} n , x [x I =y I ] denotes the state where for all i ∈ I, (x [x I =y I ] ) i = y i and for all i / ∈ I, (x [x I =y I ]

		The formalization of the BN reprogramming problem
	with permanent perturbations of nodes is established in Sect. 3. Section 4 states
	the main results on the characterization of RDs with respect to the interaction
	graph of BNs. An algorithm to enumerate all RDs by exploiting this character-
	ization is given in Sect. 5. Finally, 6 discusses the results and sketches future
	work.
	Notations
	Given a finite set I, 2 I is the power set of I, |I| the cardinality. Given a positive
	integer n, [n] = {1, . . . , n}.
	Given a Boolean state x ∈ {0, 1} n and set of indexes I ⊂ [n], xI is the
	state where xi	I = x i if i / ∈ I and xi

I = 1 -x i if i ∈ I.

  Definition 6 (Existential Reachability). With the boolean network F, a function ER F can be defined as ER F : 2 2 [n] , with ER F (x, y) → v where v is the set of all minimal vertex sets I such that x [x I =y I ] → * y.

Definition 7 (Inevitable Reachability). Similarly, a function IR F : 2 2 [n]

with the path 10000 → 10100 → 10110 → 11110 → 11111 (and the fixed point is the next step, → 11011 but there is no need to go further than 11111.)


Using Named Entities to Discover Heterogeneous Events on Twitter

Keywords: Event Detection, NLP, Supervised Classification, Named Entities

Social media sites such as Twitter 1 and Facebook 2 have emerged as powerful means of communication that allow people to exchange information about their daily activities, latest news or real-world events. Aside social interactions among users, social medias are expected to provide added value services in a variety of domains (e.g sentiment analysis, trend analysis and event detection). Detecting events on social medias poses new challenges due to the sparsity and the informal nature of social media posts. One of the main challenges in detecting events in social media is to differentiate event and non event messages. To face this challenge, we propose to take advantage from the knowledge that can be extracted from the Linked Opened Data (e.g. DBpedia 3 ) to enrich the short textual messages with contextual information brought by the presence of named entities. We evaluate our approach on two goldstandard datasets and the preliminary results show that exploiting the ontological categories of the named entities has a positive impact on the classification output.

Problem Statement and Motivation

The analysis of social media streams, particularly Twitter, has gained a lot of interest, both within the academic and business communities. The capability to understand and analyse the stream of messages on Twitter is an effective way to monitor what people think [START_REF] Kaplan | Users of the world, unite! the challenges and opportunities of social media[END_REF], what trending topics are emerging [START_REF] Ritterman | Using prediction markets and twitter to predict a swine flu pandemic[END_REF], and which main events are affecting people's lives. For this reason, several automated ways to track and categorise events on Twitter have been proposed in the literature. However, the sheer amount of information contained in Twitter makes it a challenge compared to other source of information such as media news. There are two main reasons for this. One is the larger and real time amount of information compared to media news. Second, the characteristics of tweets (e.g. limited to 140 characters long) and specific language. More importantly, contrary to media news, not all information from Twitter is related to events [START_REF] Java | Why we twitter: understanding microblogging usage and communities[END_REF].

In the recent years, detecting events by analyzing tweets have been widely researched in the field of information retrieval. Although several approaches have focused on the detection and the analysis of large-scale events from Twitter, most of them are concentrated in detecting events of particular types [START_REF] Abel | Semantics+ filtering+ search= twitcident. exploring information in social web streams[END_REF][START_REF] Earle | Twitter earthquake detection: earthquake monitoring in a social world[END_REF][START_REF] Sakaki | Earthquake shakes twitter users: real-time event detection by social sensors[END_REF]. Such approaches are highly dependant of the target events and generally rely on specific keywords to filter event-related tweets. Their strong connection to the target event makes them unsuitable for detecting events at Twitter's scale.

The different definition carried out within the Topic Detection and Tracking (TDT) and Natural Language Processing (NLP) communities do not seem to capture the particularities of events in social media contents. Commonly, an event is defined as "Something that happens at certain time in certain place and the unavoidable consequences" [START_REF]Annotation Manual[END_REF]. Based on this definition and while observing posts on Twitter, we can observe a strong connection between events, and the cited Named Entities (NE) that are involved. In the NLP community, NEs are defined as words or sequence of words on a natural language text that are reference to objects, for example persons, places and organisations. Thus, the presence of the NEs in the content of the tweets might be a good indicator that the tweet is related to event.

In this paper, we experiment with ways of detecting and classifying realworld events on Twitter by relying on the knowledge that can be extracted from knowledge bases such as DBpedia, to enrich tweets with contextual information brought by the presence of named entities involved in the events.

Related Works

Existing works on event detection on Twitter can be classified into two main categories:

1. Close-domain : interested in detecting known event type (e.g. earthquake [START_REF] Sakaki | Earthquake shakes twitter users: real-time event detection by social sensors[END_REF], flu [START_REF] Achrekar | Predicting flu trends using twitter data[END_REF][START_REF] Ritterman | Using prediction markets and twitter to predict a swine flu pandemic[END_REF] or incidents [START_REF] Abel | Semantics+ filtering+ search= twitcident. exploring information in social web streams[END_REF]) 2. Open-Domain : interested in detecting unknown event Although, our goal is to identify heterogeneous events (i.e. event of unknown types), approaches that target a particular event types are useful to stress the challenges in detecting events on tweets. This, in the reminder of this section, we review existing works in both categories.

Close-Domain or Known Event Type

Close-domain works mainly focus on monitoring tweets for detecting known events such as earthquake [START_REF] Sakaki | Earthquake shakes twitter users: real-time event detection by social sensors[END_REF], incidents [START_REF] Abel | Semantics+ filtering+ search= twitcident. exploring information in social web streams[END_REF][START_REF] Abel | Twitcident: fighting fire with information from social web streams[END_REF][START_REF] Schulz | What is good for one city may not be good for another one: Evaluating generalization for tweet classification based on semantic abstraction[END_REF] or social activities [START_REF] Ilina | Social event detection on twitter[END_REF]. Usually, a set of keywords related to the target event is used to query the Twitter stream for related tweets. Thus, messages containing one or many of such keywords are considered as event-related or ignored otherwise.

Sakaki et al. [START_REF] Sakaki | Earthquake shakes twitter users: real-time event detection by social sensors[END_REF] describe an approach for detecting earthquake by monitoring Twitter messages. The keywords earthquake and shake are used to retrieve relevant tweets on the Twitter stream. To eliminate off-context tweets (e.g. tweets containing 'shake hand'), SVM is used to train a binary classifier using eventrelated features.

Attardi et al. use discriminative word embeddings as continuous features for training an SVM classifier in the aim of separating tweets related to natural disasters from the others using words related or indicative of disasters as lexicon.

Twitter is also used to extract additional information on existing events. For example, Ritterman et al. [START_REF] Ritterman | Using prediction markets and twitter to predict a swine flu pandemic[END_REF] use successfully Twitter to predict swine flu pandemic in 2009. Achrekar et al. [START_REF] Achrekar | Predicting flu trends using twitter data[END_REF] use tweets related to flu as early indicators of influenza-like illness. Abel et al. [START_REF] Abel | Semantics+ filtering+ search= twitcident. exploring information in social web streams[END_REF][START_REF] Abel | Twitcident: fighting fire with information from social web streams[END_REF] use semantic linking to filter relevant information from tweets about reported incidents in an emergency broadcasting service. Keywords related to the reported incident are used to extract relevant tweets. Semantic linking is used to find particular information pieces in the relevant tweets.

In [START_REF] Schulz | What is good for one city may not be good for another one: Evaluating generalization for tweet classification based on semantic abstraction[END_REF], NEs are experimented in the task of generalizing a binary model trained for detecting incidents in a city to a different city. The authors show that the replacement of NEs helps in holding the performance of a supervised model when using different corpora as training and test set. However, the scope of this work was limited to incidents and only named entities of type location are used. Moreover, their datasets were collected using keywords related to incident (e.g. crash, traffic or explosion) and limited to two cities in the U.S.

Works that target a particular event type are focus on keywords to identify tweets that are related to events. Also, the event type is used to create event patterns for detecting fine-grained topics [START_REF] Nichols | Summarizing sporting events using twitter[END_REF][START_REF] Tanev | Real-time news event extraction for global crisis monitoring[END_REF][START_REF] Wang | Automatic crime prediction using events extracted from twitter posts[END_REF] or labels for training Machine Learning classifiers [START_REF] Anantharam | Extracting city traffic events from social streams[END_REF][START_REF] Sakaki | Earthquake shakes twitter users: real-time event detection by social sensors[END_REF]. Due to their strong connection to the target event, such approaches cannot be applied to event detection at Twitter's scale unless one knows the keywords corresponding to each event which is not trivial.

Open-Domain or Unknown Event Type

Usually, two main techniques are used to detect open-domain events on Twitter : Document-Pivot or Feature-Pivot techniques [START_REF] Atefeh | A survey of techniques for event detection in twitter[END_REF]. In the former, documents are clustered on the basis of their textual similarity, while the latter monitors bursty terms (terms that are observed at an unusual rate) in a collection of documents where a bursty term is considered as indicator of an event.

Petrovic et al. [START_REF] Petrović | Streaming first story detection with application to twitter[END_REF] address the task of First Story Detection by analysing solely the contents of tweets. The presented approach is based on local sensitive hashing, a randomized technique that reduces time needed to find a nearest neighbor in a vector space. Each new tweet is assigned to the thread that contains the most similar tweets where similarity is built using cosine similarity score. The growth rate of thread is used to eliminated non-event related threads, such that threads that grow fastest are considered as event-related and conversely.

Ritter et al. [START_REF] Ritter | Open domain event extraction from twitter[END_REF] modeled events on Twitter as a 4-tuple representation including NEs, temporal expressions, event phrases and event type. NEs and temporal expressions are extracted using Twitter specific tools [START_REF] Ritter | Named entity recognition in tweets: an experimental study[END_REF] while event phrases are extracted using a supervised method. The system recognizes event triggers as a sequence labeling task using Conditional Random Field; then an unsupervised approach is used to classify the events into topics. In addition, the authors consider the association strength between named entities and temporal expressions to decide whether or not a tweet is related to event. This assumption restricts the approach to tweets that explicitly contain temporal expressions and NEs.

In [START_REF] Xie | Topicsketch: Real-time bursty topic detection from twitter[END_REF], tweets are grouped according to a time-window and BOW is used as document vector. The most frequent terms during the time-window are considered as bursty topics and considered as indicator of events. Bursty terms in the whole historical data are estimated by observing the distribution of terms in the considered time-window following an optimization problem.

Most existing works on open-domain event detection in Twitter are based on the velocity of which the clusters are growing; thus, clusters that grow fastest are considered as event-related [START_REF] Ritter | Open domain event extraction from twitter[END_REF][START_REF] Xie | Topicsketch: Real-time bursty topic detection from twitter[END_REF] or simply discarded otherwise. Although this assumption helps in discovering large-scale events [START_REF] Osborne | Bieber no more: First story detection using twitter and wikipedia[END_REF], it is less suitable for events with a small audience on Twitter. In our approach, instead of creating event clusters on the whole Twitter data; we propose to separate event and nonevent tweets in a separated task. Second, we create event clusters using only tweets that are related to events. By doing this, we minimize the risk of false alarms due to non-event related tweets in the clusters and second, we reduce the time needed to create the clusters.

Research Questions

Our overall research question is: how to detect open-domain events by monitoring Twitter messages? What is the best approach to build a event detection model that can hold good performance as time passes? To answer this, the following research questions will be investigated: RQ 1: Is it possible to use supervised classification to separate event-related and not event-related tweets? What is the impact of in-domain data on classification, especially on overfitting? RQ 2: How information contained on the LOD (as knowledge about NEs) can contribute to this task in order to mitigate the effects of overfitting on indomain data? RQ 3: How can we cluster/categorize events into finer-grained topics?

Hypothesis

Based on the research questions listed in Section 3, we make the following hypotheses:

H 1: Separating event-related and non-event related tweets can contribute in reduction the computational time of event detection algorithms

H 2:
The presence of NEs in the content of a post is a good indicator that it is related to an event. H 3: Replacing NEs in tweets by their corresponding category in an ontology can reduce the negative effect of overfitting on a classifier.

Our Approach

We now describe our approach for detecting heterogeneous events on Twitter i.e. unknown event types. Based on the research questions and the hypothesis, we present our approach in three steps:

1. First, we separate event-related tweets from the rest of the micro-posts by combining techniques from Machine Learning (ML), NLP and LOD. 2. Second, we classify the tweets that are related to events into coarse-level categories as described in the TDT manual [START_REF]Annotation Manual[END_REF] including: Science, Armed Conflicts, Politics, Economy, Culture, Sports, Accidents and Miscellaneous. 3. Third, we propose to cluster the tweets in each category into finer-grained topics by grouping similar tweets using a feature-pivot technique.

In the remainder of this section, we detail how we plan to carry out our work on each step.

Identifying Event-Related Tweets

In previous works [START_REF] Ritter | Open domain event extraction from twitter[END_REF][START_REF] Schulz | What is good for one city may not be good for another one: Evaluating generalization for tweet classification based on semantic abstraction[END_REF], events are typically defined according to time, space and agents involved such as locations, persons or organisations, denoted as Named Entities (NE). For the first and second step, we propose to build a classification model based on semantic abstraction on the NEs. The semantic abstraction consists in replacing the NEs cited in tweets by their ontological categories(e.g. types in DBpedia) and use the modified content to extract features for training a supervised model. First, we link the NE mentions in tweets to resources in a knowledge base (e.g. DBpedia); second, we replace the NEs by their category in the ontology, and third, we create a feature vector with the modified content. Finally, we use the feature vector to train the supervised model.

Named Entity Recognition, Linking and Replacement We utilize the NERD-ML [START_REF] Van Erp | Learning with the web: Spotting named entities on the intersection of nerd and machine learning[END_REF] tool to perform Named Entity Recognition (NER) and entity linking. Our choice of NERD-ML is motivated by the work in [START_REF] Derczynski | Analysis of named entity recognition and linking for tweets[END_REF], which has found that NERD-ML performs better on Twitter data than other Twitterspecific NLP tools such as Tweet NLP [START_REF] Ritter | Named entity recognition in tweets: an experimental study[END_REF]. We use the SPARQL 4 query language to retrieve the categories of the NE in the knowledge base. Additionally, we sort the output of the query according to the hierarchy of the ontology. We experiment two NER techniques, namely generic and specific replacement. In the former, the NEs are replaced by their most generic category;5 in the latter we replace the NEs by their most specific category. 6 Two example outputs of the Entity Replacement module are reported in Table 1. The rationale behind the replacement of entity mentions with their type is to generalise over single mentions, thus avoiding overfitting in supervised settings. Classification Approach In order to separate event tweets and non events tweets and to associate a coarse-level category [START_REF]Annotation Manual[END_REF][START_REF] Mcminn | Building a large-scale corpus for evaluating event detection on twitter[END_REF] to event-related tweets, we use a supervised method. We consider two ways to build the supervised model: (1) A binary classifier that classifies the tweets into events and non events provides the input to second model to associate an event category to the tweets.

(2) A single multi-class classification: A model trained on 9 classes, including the 8 event categories plus a non event-related class. We plan to experiment the two approaches and select the one that gives the best results.

Extracting Event Topics

The third step of our approach is topic detection. Giving a set of tweets label as related to events in the previous tasks, the goal is to detect fine-grained event topic (e.g. The death of Amy Winehouse). Contrary to the first step, it is inconceivable to build a supervised model for this task since the possible event topics in Twitter are unknown in advance [START_REF] Ritter | Open domain event extraction from twitter[END_REF]. Instead, we propose to build an unsupervised model exploiting the event categories output by the supervised model.

We create topic clusters in each event category by grouping together similar tweets. Due to the sparsity of tweets, we propose to use a feature-pivot techniques instead a document-pivot techniques [START_REF] Atefeh | A survey of techniques for event detection in twitter[END_REF]. Instead of considering each word in a tweet as a bursty candidate, we reduce the feature space by considering relationship between NEs and event phrases (i.e. action verbs) as in [?]. Furthermore, using the relationship between NEs and event phrases is useful to separate events sharing a common type into specific event topics (e.g. an accident that occurs in different places). Also, we use Wordnet [START_REF] Miller | Wordnet: a lexical database for english[END_REF] to extract the synsets for the event phrases in order to group similar clusters.

Finally, following the state of the art approaches, emergent event topics are identified by monitoring the growth of each clusters. Since this task is connected to the classification task, we are sure that the clusters are related to events; thus, we use the growth rate of the clusters to sort the events according to their popularity in Twitter such that clusters that grow fastest are the most popular.

Evaluation Plan

In this section, we defined the evaluation strategies for our research questions. Since we are interested in detecting events on Twitter, our approaches are evaluated on two gold-standard datasets. In the reminder of this section, we will present the characteristics of each dataset as well as the valuation strategies for each research question.

Datasets

For our experiments, we choose two gold-standard corpus of tweets collected over two distinct periods and cover very different topics. Both datasets are manually annotated and tweets related to events are annotated either with a coarse-level event category (e.g. Culture) and fine-level event type (e.g. The death of Amy Winehouse).

The Events 2012 Corpus [START_REF] Mcminn | Building a large-scale corpus for evaluating event detection on twitter[END_REF] A total of 120 million tweets were collected from October to November 2012 from the Twitter streaming API,7 of which 159,952 tweets were labeled as event-related. 506 event types were gathered from the Wikipedia Current Event Portal, and Amazon Mechanical Turk was used to annotate each tweet with one of such events. Besides, each event was also associated with an event category following the TDT annotation manual [START_REF]Annotation Manual[END_REF]. Events covered by this dataset include for example the US presidential debate between Barack Obama and Mitt Romney, the US presidential election results or the Chemistry Nobel prize. According to Twitter policies, only tweet identifiers can be released. Therefore, we use these identifiers to download the original contents of the tweets from the Twitter platform. After removing duplicated tweets and those that are no-longer available, we are left with ∼ 92 million tweets from which 42,334 tweets related to events.

First Story Detection Corpus (FSD) [START_REF] Petrović | Streaming first story detection with application to twitter[END_REF] This corpus consists of a set of 50 million Twitter messages collected from July 2011 until September 2011 using the Twitter API. Two human annotators annotated the tweets related to events with one out of 27 event types extracted from the Wikipedia Current Event Portal; agreements between the annotators using Cohen's kappa was 0.65. In total, 3,035 tweets were labeled as related to events and annotated with a corresponding event topic (e.g. 'death of Amy Winehouse', 'earthquake in Virginia' or 'plane crash of the Russian hockey team'). After removing tweets that are no more available, we are left with ∼31 million tweets from which 2,250 are related to events.

Contrary to the Event 2012 corpus, the events in the FSD corpus are not associated with event categories. Therefore, in order to merge the two corpora in a single dataset for our experiments, we extended the FSD corpus by labelling each event topic with one of the event categories of the Event 2012 corpus [START_REF]Annotation Manual[END_REF][START_REF] Mcminn | Building a large-scale corpus for evaluating event detection on twitter[END_REF]. The task was manually performed by three annotators: the labels were first assigned independently, and then adjudicated by majority vote in case of disagreements. 8Agreement between the three annotators, measured using Krippendorffs alpha coefficient, was (alpha = 0.758). Table 2 shows the number of tweets in each corpus divided into categories.

Evaluation Strategies for the First and Second Research Question

To demonstrate the importance of NLP in detecting open-domain events on Twitter, we compare our NLP-based approach against a baseline which does not make use of NLP nor LOD. On the other hand, our evaluation aims to prove that it is feasible to use supervised machine learning to separate event related tweets and non event related tweets.

Since both corpora contain much more non-event related than event related tweets, resulting in a very skewed class distribution, we reduced the number of negative instances by randomly selecting a sample of non event-related tweets. The final amount of tweets in the two datasets is reported in Table 3.

We consider two evaluation settings namely, Setting 1 and Setting 2. In Setting 1, we evaluate the model using 10-fold cross validation only with the Event 2012 corpus. In Setting 2, we use the Event 2012 as training set and the FSD corpus as test set. Our focus is on Setting 2 (i.e. train the model on a corpus and test it on an other); however, Setting 1 is useful to understand the effect of only in-domain data on the output of supervised method.

Evaluation Strategies for the Third Research Question

To evaluate our approach for detecting event topic, we will use the event topics described in the datasets we described in Section 6.1 as our ground truth. Our evaluation strategy is two fold: [START_REF]Annotation Manual[END_REF] We evaluate the ability to determine the correct event topics and (2) we compare the summary of the topics with the summary of each events in the datasets. For each evaluation strategy, we will use human annotators to evaluate measure the similarity between the topics associated to each tweet by our approach and the correct topic in the datasets. Using the human annotations, we can compute the evaluation metrics such precision and recall.

Preliminary Results

We have already made some experiments to evaluate our approach for separating tweets related to events from the rest of tweets. We compare the results of our approach against a simple baseline which does not make use of NLP nor LOD on the basis of precision, recall and f-measure. We train two models according using Setting 1 and Setting 2; the results are depicted in Tables 4 and5.

Experimental Setup

Before training the classifiers, we further clean up the datasets. We remove any Twitter-specific features such as URLs, user mentions, emoticons and duplicate tweets. 9 We also perform common prepossessing tasks such as stop words removal and stemming. We employ character sequence n-gram features [START_REF] Ilina | Social event detection on twitter[END_REF] and model the feature vector using bag-of-words weighted by TF-IDF.

We consider the NER techniques as described in Section 5 for training a binary classifier to separate event and non event tweets. For each setting, we select all tweets related to events as positive instances and randomly selected an equivalent number of non event-related tweets as negative instances. Finally, we use the Weka10 tool to train a Naive Bayes and an SVM classifier.

Results

Table 4 depicts the evaluation of our approach as well as the baseline, on the Setting 1 (i.e train and test on the same dataset). In setting 1, the baseline outperforms our method in precision and recall for both NB and SVM classifier. Our results are similar to those obtained by Ilina et al. [START_REF] Ilina | Social event detection on twitter[END_REF] who found that training and testing on the same datasets obtain higher performance than training and testing on different datasets. A plausible reason for that is overfitting due to the similarity between training and testing instances.

We also conduct the experiments with Setting 2 (i.e we train on the Event 2012 dataset and test on the FSD dataset) and reports the results in Table 5. With this configuration, the best performing method is obtained when the NEs are replaced by their most generic class in the DBpedia ontology outperforming the baseline. As expected, both methods obtain lower performance regarding Setting 1. Nevertheless, our method yields a drop of 0.028, the baseline yields a drop of 0.167 in f-measure. These preliminary results show that using the ontological categories of the NEs, we mitigate the impact of overfitting on the output of our supervised model. approach exploits the relation between events and NE but also NLP and LOD techniques to build a supervised method to separate event and non event tweets. The output of the supervised modeled is used as input for a clustering approach in which event categories are exploited to detect finer-grained event topics. We found that the replacement of the NEs in tweets by their associated concepts in the DBpedia ontology has proved to be efficient in reducing the negative effect of overfitting in the output of our model. Our preliminary results show that the proposed approach holds higher precision and recall compared to a baseline when the training and test sets are different. For future works we plan to improve the approach by considering categories from other ontologies such as Yago; we also plan to experiment other classifiers such as Neural Network.

Table 1 .

 1 Examples of the output of the Entity Replacement module on tweets. For simplicity, in this table we only show categories in DBpedia ontology.

	Original Tweets			Generic Categories Specific Categories
	Cambodia's	ex-King	Norodom	[Place] ex-king [Person]	[Country] ex-king [Roy-
	Sihanouk	dead	at	89	die at [number]	alty] die at [number]
	http://q.gs/2IvJk #FollowBack
	Amy Winehouse, 27, dies at her	[Person], [number], die	[Person], [number], die
	London flat http://bit.ly/nD9dy2	at her [Place] flat [Per-	at her [Settlement] flat
	#amyWinehouse			son]	[Person]

Table 2 .

 2 Tweets in each event category

	Event Category Event 2012 FSD
	Arts	2589	710
	Attacks	7079	56
	Politics	16383	58
	Sports	8812	0
	Economy	2881	342
	Science	1537	296
	Accidents	2479	778
	Miscellaneous	574	10
	Total	42334	2250

Table 3 .

 3 Total number of tweets per dataset

		Event-related Non event-related Total
	Event 2012 42,334	48,239	90,573
	FSD	2,250	3,040	5,290

Table 4 .

 4 Evaluation on setting 1: A NB and an SVM classifier are trained and tested with tweets from the same dataset using 10-fold cross-validation.8 Discussion and Future WorkThis paper presents a proposal to tackle the problem of detecting open-domain events on Twitter and our preliminary results. The main idea of the proposed

			Naive Bayes		SVM
	Approach	Prec.	Rec.	F1	Prec.	Rec.	F1
	dbp:generic.	0.897	0.896	0.896	0.906	0.903	0.904
	dbp:specific.	0.871	0.869	0.870	0.887	0.884	0.885
	Baseline	0.919	0.918	0.918	0.951	0.949	0.950

Table 5 .

 5 Evaluation on setting 2: A NB and an SVM classifier are trained with tweets from the Event 2012 dataset and tested with tweets from the FSD dataset.

http://twitter.com/

http://facebook.com/

http://wiki.dbpedia.org/about

https://www.w3.org/TR/rdf-sparql-query/

i.e. The last category in the hierarchy (excluding the Thing class)

https://dev.twitter.com/streaming/overview

The Web interface used for annotation is available at http://www.i3s.unice.fr/ ~edouard/events/agreements.html

After removing Twitter-specific features and replacing named entities, we remove the duplicates tweets.

http://www.cs.waikato.ac.nz/ml/weka/

Acknowledgments. The author would like to thanks Elena Cabrio, Sara Tonelli and Nhan Le-Than for helping to develop this research plan, their writing tips and the kind review of the early drafts of this paper. I am also grateful to the anonymous reviewers for their valuable and constructive feedback.