Tiphaine Viard

Matthieu Latapy

Clémence Magnien

Computing maximal cliques in link streams

Keywords: link streams, temporal networks, time-varying graphs, cliques, graphs, algorithms

A link stream is a collection of triplets (t, u, v) indicating that an interaction occurred between u and v at time t. We generalize the classical notion of cliques in graphs to such link streams: for a given ∆, a ∆-clique is a set of nodes and a time interval such that all pairs of nodes in this set interact at least once during each sub-interval of duration ∆. We propose an algorithm to enumerate all maximal (in terms of nodes or time interval) cliques of a link stream, and illustrate its practical relevance on a real-world contact trace.

Introduction

In a graph G = (V, E) with E ⊆ V ×V , a clique C ⊆ V is a set of nodes such that C ×C ⊆ E. In addition, C is maximal if it is included in no other clique. In other words, a maximal clique is a set of nodes such that all possible links exist between them, and there is no other node linked to all of them. Enumerating maximal cliques of a graph is one of the most fundamental problems in computer science, and it has many applications [START_REF] Rowe | Automated social hierarchy detection through email network analysis[END_REF][START_REF] Samudrala | A graph-theoretic algorithm for comparative modeling of protein structure[END_REF].

A link stream L = (T, V, E) with T = [α, ω] and E ⊆ T ×V ×V models interactions over time: l = (t, u, v) in E means that an interaction occurred between u ∈ V and v ∈ V at time t ∈ T . Link streams, also called temporal networks or time-varying graphs depending on the context, model many real-world data like contacts between individuals, email exchanges, or network traffic [START_REF] Casteigts | Timevarying graphs and dynamic networks[END_REF][START_REF] Holme | Temporal networks[END_REF][START_REF] Viard | Identifying roles in IP network with temporal and structural density[END_REF][START_REF] Wehmuth | A Unifying Model for Representing Time-Varying Graphs[END_REF].

For a given duration ∆, a ∆-clique C of L is a pair C = (X, [b, e]) with X ⊆ V and [b, e] ⊆ T such that |X| ≥ 2, and for all {u, v} ⊆ X and τ ∈ [b, max(e-∆, b)] there is a link (t, u, v) in E with t ∈ [τ, min(τ + ∆, e)]. Notice that ∆-cliques necessarily have at least two nodes.

More intuitively, all nodes in X interact at least once with all others at least every ∆ from time b to time e. ∆-clique C is maximal if it is included in no other ∆-clique, (i.e. there exists no ∆-clique C = (X , [b , e ]) such that C = C, X ⊆ X and [b, e] ⊆ [b , e ]). See Figure 1 for an example.

In real-world situations like the ones cited above, ∆-cliques are signatures of meetings, discussions, or distributed applications for instance. Moreover, just [START_REF] Casteigts | Timevarying graphs and dynamic networks[END_REF][START_REF] Johnson | On generating all maximal independent sets[END_REF]) (top right), ({b, c}, [START_REF] Bron | Algorithm 457: finding all cliques of an undirected graph[END_REF][START_REF] Johnson | On generating all maximal independent sets[END_REF]) (bottom left), and ({a, c}, [START_REF] Casteigts | Timevarying graphs and dynamic networks[END_REF][START_REF] Koch | Enumerating all connected maximal common subgraphs in two graphs[END_REF]) (bottom right). Notice that ({a, b, c}, [START_REF] Bron | Algorithm 457: finding all cliques of an undirected graph[END_REF][START_REF] Johnson | On generating all maximal independent sets[END_REF]) is not a ∆-clique since during time interval [START_REF] Bron | Algorithm 457: finding all cliques of an undirected graph[END_REF][START_REF] Eppstein | Listing all maximal cliques in large sparse real-world graphs[END_REF] of duration ∆ = 3 there is no interaction between a and c. Notice also that ({a, b}, [START_REF] Bron | Algorithm 457: finding all cliques of an undirected graph[END_REF][START_REF] Rowe | Automated social hierarchy detection through email network analysis[END_REF]), for instance, is not maximal: it is included in ({a, b}, [0, 9]).

like cliques in a graph correspond to its subgraphs of density 1, ∆-cliques in a link stream correspond to its substreams of ∆-density 1, as defined in [START_REF] Viard | Identifying roles in IP network with temporal and structural density[END_REF]. Therefore, ∆-cliques in link streams are natural generalizations of cliques in graphs.

In this paper, we propose the first algorithm for listing all maximal ∆-cliques of a given link stream. We illustrate the relevance of the concept and algorithm by computing maximal ∆-cliques of a real-world dataset.

Before entering in the core of the presentation, notice that we consider here undirected links only: given a link stream L = (T, V, E), we make no distinction between (t, u, v) ∈ E and (t, v, u) ∈ E. Likewise, we suppose that there is no loop (t, v, v) in E, and no isolated node (∀v ∈ V, ∃(t, u, v) ∈ E).

We finally define the first occurrence time of (u, v) after b as the smallest time t ≥ b such that (t, u, v) ∈ E, and we denote it by f buv . Conversely we denote the last occurrence time of (u, v) before e by l euv . We say that a link

(t, u, v) is in C = (X, [b, e]) if u ∈ X, v ∈ X and t ∈ [b, e].

Algorithm

One may trivially enumerate all maximal cliques in a graph as follows. One maintains a set M of previously found cliques (maximal or not), as well as a set S of candidate cliques. Then for each clique C in S, one removes C from S and searches for nodes outside C connected to all nodes in clique C, thus obtaining new cliques (one for each such node) larger than C. If one finds no such node, then clique C is maximal and it is part of the output. Otherwise, if the newly found cliques have not already been found (i.e., they do not belong to M ), then one adds them to S and M . The set S is initialized with the trivial cliques containing only one node, and all maximal cliques have been found when S is empty. The set M is used for memorization, and ensures that one does not examine the same clique more than once. In [START_REF] Johnson | On generating all maximal independent sets[END_REF] the authors use this framework to enumerate all maximal cliques of a graph in lexicographic order.

Our algorithm for finding ∆-cliques in link stream L = (T, V, E) (Algorithm 1) relies on the same scheme. We initialize the set S of candidate ∆-cliques and the set M of all found ∆-cliques with the trivial ∆-cliques ({a, b}, [t, t]) for all (t, a, b) in E (Line 2). Then, until S is empty (while loop of Lines 3 to 24), we pick an element (X, [b, e]) in S (Line 4) and search for nodes v outside X such that (X ∪ {v}, [b, e]) is a ∆-clique (Lines 6 to 10). We also look for a value b < b such that (X, [b , e]) is a ∆-clique (Lines 11 to 16), and likewise a value e > e such that (X, [b, e ]) is a ∆-clique (Lines 17 to 22). If we find such a node, such a b or such an e , then ∆-clique C is not maximal and we add to S and M the new ∆-cliques larger than C we just found (Lines 10, 16 and 22), on the condition that they had not already been seen (i.e., they do not belong to M ). Otherwise, C is maximal and is part of the output (Line 24).

Algorithm 1 Maximal ∆-cliques of a link stream input: a link stream L = (T, V, E) and a duration ∆ output: the set of all maximal ∆-cliques in L (Lines 19 to 22) being symmetrical. For a given ∆-clique (X, [b, e]), we set b to f -∆, which is the smallest time such that we are sure that (X, [b , e]) is a ∆-clique without inspecting any link outside of (X, [b, e]). Indeed, all links in X × X appear at least once in the interval [f -∆, f ]: f is the latest of the first occurrence times of all links in this ∆-clique, and so all links appear at least once in

1: S ← ∅, R ← ∅, M ← ∅ 2: for (t, u, v) ∈ E: add ({u, v}, [t, t]
for v in V \ X do 7: if (X ∪ {v}, [b, e]) is a ∆-clique
[b, f ] ⊆ [f -∆, f ]. If b = b, then the ∆-clique (X, [b , e]) is added to S (Line 13).
We display in Figure 2 an example of a sequence of such operations from an initial trivial ∆-clique to a maximal ∆-clique in an illustrative link stream. The algorithm builds this way a set of ∆-cliques of L, which we call the configuration space; we display the configuration space for this simple example in Figure 3 together with the relations induced by the algorithm between these ∆-cliques. From left to right and top to bottom: the algorithm starts with ({a, b}, [START_REF] Holme | Temporal networks[END_REF][START_REF] Holme | Temporal networks[END_REF]), and finds ({a, b}, [START_REF] Cazals | A note on the problem of reporting maximal cliques[END_REF][START_REF] Holme | Temporal networks[END_REF]) thanks to Lines 11 to 16 of the algorithm. It then finds ({a, b, c}, [START_REF] Cazals | A note on the problem of reporting maximal cliques[END_REF][START_REF] Holme | Temporal networks[END_REF]) thanks to Lines 6 to 10. It finds ({a, b, c}, [START_REF] Cazals | A note on the problem of reporting maximal cliques[END_REF][START_REF] Johnson | On generating all maximal independent sets[END_REF]) from Lines 17 to 22, and finally ({a, b, c}, [START_REF] Casteigts | Timevarying graphs and dynamic networks[END_REF][START_REF] Johnson | On generating all maximal independent sets[END_REF]) from Lines 11 to 16.

To prove the validity of Algorithm 1, we must show that all the elements it outputs are ∆-cliques, that they are maximal, and that all maximal ∆-cliques are in its output. Lemma 1. In Algorithm 1, all elements of S are ∆-cliques of L.

Proof. We prove the claim by induction on the iterations of the while loop (Lines 3 to 24).

Initially, all elements of S are ∆-cliques (Line 2). Let us assume that all the elements of S are ∆-cliques at the i-th iteration of the loop (induction hypothesis). The loop may add new elements to S at Lines 10, 16 and 22. In all cases, the added element is built from an element C = (X, [b, e]) of S (Line 4), which is a ∆-clique by induction hypothesis.

It is trivial (from the test at Line 7) that Line 10 only adds ∆-cliques. Let us show that (X, [b, l + ∆]), where l is computed in Line 17, necessarily is a ∆-clique. As (X, [b, e]) is a ∆-clique all links in X × X appear at least once every ∆ from b to l ≤ e. Moreover, since l is the earliest last occurrence time of a link in C, for all u and v in X there is necessarily a link (t, u, v) in E with l ≤ t ≤ e. Notice also that l ≥ e -∆, otherwise (X, [b, e]) would not be a ∆-clique. Therefore a link between u and v occurs at least once between l and l + ∆ for all u and v in X. Finally, (X, [b, l + ∆]) is a ∆-clique.

The same arguments hold for Line 11. Finally, at the end of the (i + 1)-th iteration of the loop, all the elements of S are ∆-cliques, which ends the proof. Lemma 2. All the elements of the set returned by Algorithm 1 are maximal ∆-cliques of L.

Proof. Let C = (X, [b, e]) be an element of R returned by the algorithm. Only elements of S are added to R (at Line 24), and so according to Lemma 1 C is a ∆-clique. Assume it is not maximal; then we are in one of the three following situations.

There exists v in V \X such that (X∪{v}, [b, e]) is a ∆-clique. Then v is found at Lines 6-7, and Line 8 sets the boolean isMax to false. Therefore, Line 23 ensures that C = (X, [b, e]) is not added to R, and we reach a contradiction.

There exists e > e such that (X, [b, e ]) is a ∆-clique and we assume without loss of generality that there is no link between nodes in X from e to e . Then, let us consider l ∈ [b, e], computed in Line 17, which is the earliest last occurrence time of a link in C. We necessarily have l ≥ e -∆ because (X, [b, e ]) is a ∆-clique. Since e > e, this implies l > e -∆. As a consequence, the test in Line 19 of the algorithm is satisfied, and Line 20 sets the boolean isMax to false. Like above, we reach a contradiction.

If there exists b < b such that (X, [b , e]) is a ∆-clique, then similarly to the previous case we reach a contradiction.

Finally, C necessarily is maximal, which proves the claim.

Before proving our main result, which is that all maximal ∆-cliques are returned by the algorithm, we need the following two intermediate results. Proof. Since C is a ∆-clique and by definition of s, for all u, v in X there exists at least one link (t, u, v) such that s ≤ t ≤ e. Assume e < s + ∆; then for all u, v in X there also exists a link (t, u, v) such that s ≤ t ≤ e < s + ∆. Therefore (X, [b, s + ∆]) is a ∆-clique and C is included in it, which means that C is not maximal and we reach a contradiction.

C 0 → C 1 → • • • → C k such that for all i C i = (X, [s, e i ]
) with e i+1 > e i . In other words, the algorithm builds C i+1 from C i in Lines 17 to 22 (notice that e ≥ s + ∆ from Lemma 3 and so C 0 is included in C).

We prove that C k = (X, [s, e]) by contradiction. Assume this is false, and so that e k = e. As C is maximal, we then necessarily have e k < e. In addition, e k = l+∆ where l is the earliest last occurrence time of a link in C k-1 computed at Line 17. Since C k is the last ∆-clique in the sequence, l is also the earliest last occurrence time of a link in C k (otherwise there would be a clique C k+1 satisfying the constraints of the sequence above). Therefore there exist u, v ∈ X such that (l, u, v) ∈ E and such that there is no occurrence of a link (u, v) between l and e k = l + ∆. This ensures that there exists an such that l + ∆ + < e and such that there is no link between u and v from l + to l + ∆ + , which contradicts the assumption that C is a ∆-clique.

We now show that the algorithm builds C from C k to end the proof. Since C is maximal, there exists u, v ∈ X such that (b + ∆, u, v) ∈ E and such that there is no other link between Proof. It is easy to check that if S contains a maximal ∆-clique then it is added to the set R returned by the algorithm, and only these ∆-cliques are added to R. We therefore show that all maximal ∆-cliques are in S at some stage.

Let C = (X, [b, e]) be a maximal ∆-clique of L, let s be the earliest occurrence time of a link in C, and let u, v ∈ X be two nodes such that there exists a link between them at s (i.e., (s, u, v) ∈ E). We show that there is a sequence of steps of the algorithm that builds C from ∆-clique C 0 = ({u, v}, [s, s]) (which is placed in S at the beginning of the algorithm, Line 2).

Lines 17 to 22 builds

C 1 = ({u, v}, [s, s + ∆]) from C 0 .
Notice that for all subset Y of X, (Y, [s, s + ∆]) is a ∆-clique. Therefore the algorithm iteratively adds all elements of X at Lines 6 to 10, finally obtaining

C = (X, [s, s + ∆]) from C 1 .
We finally apply Lemma 4 to conclude that the algorithm builds C from C .

From these lemmas, we finally obtain the following result.

Theorem 1. Given a link stream L and a duration ∆, Algorithm 1 computes the set of all maximal ∆-cliques of L.

In order to investigate the complexity of our algorithm, let us denote by n = |V | the number of nodes and m = |E| the number of links in L. First notice that the number of elements in the configuration space built by the algorithm is bounded by the number of subsets of V times the number of sub-intervals of T .

Moreover, for all ∆-clique C = (X, [b, e]) in the configuration space, there exists a link (b, u, v) or a link (b + ∆, u, v) in E. Indeed, the initial trivial ∆cliques are in the first case, and all ∆-cliques obtained from them are also in this case until Line 16 is applied. The ∆-cliques built after this are in the second case. Likewise, there exists a link (e, u, v) or a link (e -∆, u, v) in E. Therefore, the number of possible values for b and e for any ∆-clique in the configuration space is proportional to the number of time instants at which a link occurs, which is bounded by the number of links m. The number of sub-intervals of T corresponding to a ∆-clique in the configuration space is therefore in O(m 2 ). This bound is reached in the worst case, for instance if the stream is a sequence of links occurring once every ∆ time interval.

The trivial bound O(2 n ) for the number of subsets of V is also reached in the worst case, for instance if there is a link between all pairs of nodes at the same time: the algorithm will enumerate all subsets of V .

Therefore, the number of elements in the configuration space is in O(2 n m 2 ). This leads to the space complexity of our algorithm: it is proportional to the space needed to store the configuration space, which is in O(2 n nm 2 ) since each element may be stored in O(n) space.

We estimate the time complexity by studying the complexity of operations performed on each element of the configuration space, (i.e., the complexity of each iteration of the while loop at Lines 3 to 24). Let us consider a ∆-clique C = (X, [b, e]) picked from S by the algorithm at Line 4.

The while loop is composed of three blocks: (1) searching for ∆-cliques of the form (X ∪ {v}, [b, e]) larger than C (Lines 6 to 10); (2) searching for a ∆-clique (X, [b , e]) larger than C (Lines 11 to 16); and (3) searching for a ∆clique (X, [b, e ]) larger than C (Lines 17 to 22). The third block has the same complexity as the second one, so we focus on the time complexity of the two first blocks.

Given a node v / ∈ X, Line 7 tests whether for all nodes u in X there is a link (t, v, u) ∈ E in each time interval of duration ∆. This requires at most |X| • m tests, and so it is in O(nm). Then, Line 9 searches for the found ∆-clique in M , which has a size in O(2 n m 2 ). Since the comparison between two ∆-cliques can be performed in O(n) time, this search therefore is in O(n log(2 n m 2 )) = O(n 2 + n log m) time. The algorithm repeats these operations for all nodes v ∈ V \ X, and thus less than n times, hence the complexity of Lines 6 to 10 is in O(n(nm

+ n 2 + n log m)) = O(n 2 m + n 3 ).
Computing f in Line 11 may clearly be done with at most m tests. Lines 13 and 14 are all trivial computations. Lines 15 and Line 16 are in O(n 2 + n log m). The complexity of Lines 11 to 16 is therefore in O(m + n 2 + n log m).

Finally, each iteration of the while loop costs at most O(n

2 m + n 3 + m + n 2 + n log m) = O(n 2 m + n 3 ) time.
We bound the overall time complexity of the algorithm by multiplying this by the number of iterations of the while loop, which is the number of elements in the configuration space. It is therefore in

O(2 n m 2 (n 2 m + n 3 )) = O(2 n n 2 m 3 + 2 n n 3 m 2 ).
From this analysis, we obtain the following result: Notice that enumerating the maximal cliques in a graph G = (V, E) is equivalent to enumerating the maximal ∆-cliques in L = ([0, 0], V, E ) where (0, u, v) ∈ E if and only if (u, v) ∈ E. The problem of enumerating maximal ∆-cliques in a link stream is therefore at least as difficult as enumerating maximal cliques in a graph, which has an exponential time complexity (in particular, there can be an exponential number of maximal cliques). Therefore any algorithm for enumerating maximal ∆-cliques in a link stream is at least exponential in the number of nodes.

Notice also that several optimizations may speed up our algorithm (without changing its worst-case complexity). In particular, f and l, computed in Lines 11 and 17, are necessarily in [b, min(e, b + ∆)] and [max(b, e -∆), e], respectively. One may therefore focus the search on these intervals rather than [b, e]. Likewise, if V (C) is the set of nodes satisfying condition of Line 7, then the set V (C ) of nodes satisfying this condition for the ∆-cliques C added to S at Lines 10, 16 and 22 is included in V (C). One may therefore associate to each element of S a set of candidate nodes to be considered at Line 6 in place of V \ X, thus drastically reducing the number of iterations of this loop.

Experiments

We implemented Algorithm 1 with the optimizations discussed above in Python (2.7) and provide the source code at [START_REF] Viard | Source code in python for computing cliques in link streams[END_REF]. We illustrate here its practical relevance by computing maximal ∆-cliques of the link stream from the Thiers-Highschool dataset, which is a trace of real-world contacts between individuals, captured with sensors. It was collected at a French high school in 2012, see [START_REF] Fournet | Contact patterns among high school students[END_REF] for full details. It induces a link stream of 181 nodes and 45, 047 links, connecting 2, 220 distinct pairs of nodes over a period of 729, 500 seconds (approximately 8 days). Each link (t, u, v) means that the sensor carried by individual u or v detected the sensor carried by the other individual at time t, which means in turn that these two individuals were close enough from each other at time t for the detection to happen. We call this a contact between individuals u and v. We also have the information of the class to which students belong.

We computed all maximal ∆-cliques for ∆ = 60 seconds, ∆ = 900 seconds (15 minutes), ∆ = 3, 600 seconds (1 hour), and ∆ = 10, 800 seconds (3 hours). We handpicked these values because of the rhythm of school day: on a typical day, courses usually last roughly two hours, with two 15 minutes breaks during the day, and a longer 1 hour lunch break. Our Python implementation took an hour on a standard server1 to obtain the results. Although many discovered ∆-cliques are very small, we also found rather large and long ones. See Table 1 for a summary of these computations. We present in Figure 4, for each value of ∆, the complementary cumulative distributions for the size |X| and duration e -b of all maximal ∆-cliques (X, [b, e]). By definition, larger values of ∆ trivially induce larger and longer ∆-cliques. Indeed, if ∆ > ∆ then every (maximal) ∆-clique also is a ∆ -clique (not maximal in general). More intuitively, small values of ∆ detect local bursts, but are unable to find periodic behaviors if the period is larger than ∆. Notice that when ∆ grows the number of maximal ∆-cliques generally decreases, but this is not always true, as seen in Table 1. For an example of how the impact of ∆ on the number of maximal ∆-cliques is not trivial, consider the stream presented in Figure 1: it contains four maximal 1-cliques, six maximal 2-cliques, and four maximal 3-cliques. Notice now that Algorithm 1 makes no assumption on the order in which elements of S are processed, which corresponds to the way we explore the configuration space. In particular, if S is a first-in-first-out structure (a queue), the algorithm performs a BFS of the configuration space; if it is a last-in-first-out structure (a stack) then it performs a DFS. The execution time is essentially the same in all cases. The size of S may vary, but the space complexity of the algorithm is dominated by the size of M , that does not change. Still, the data structure impacts the order in which ∆-cliques are found.

We illustrate this in the practical case where ∆ = 3600 seconds (1 hour), see Figure 5. It shows that DFS rapidly discovers many cliques, and that those cliques are non-trivial cliques (cliques involving more than 2 nodes or lasting a substantial amount of time). In this case, using a DFS is therefore more interesting than a BFS, as it outputs results and exhibits non-trivial ∆-cliques faster. However, this behavior is dependent on the dataset, and deciding on the most appropriate exploration strategy in a given case remains an open question.

Consider now G = (V, E) the graph induced by link stream L = (T, V, E): V = V and E = {(u, v) : ∃(t, u, v) ∈ E}. In other words, this is the graph where a link exists between two nodes u and v if and only if there is at least one contact between u and v in the link stream. The graph G contains 1742 cliques, the largest one involving 14 nodes. Approximately 70% of them involve students in the same class.

If (X, [b, e]) is a (maximal) ∆-clique of L, then by definition X is a clique of G (in general not maximal). However, as ∆-cliques capture time information they shed light on different patterns. For instance, L contains a 60-clique involving 4 students of different classrooms during roughly 5 minutes, which is likely to be the signature of a coffee break. Such ∆-cliques are non-trivial outputs of our algorithm, but they are invisible when considering graph cliques.

Conclusion

We introduced the notion of ∆-cliques in link streams, and proposed the first algorithm to compute the maximal such ∆-cliques. We implemented this algorithm and detected interesting ∆-cliques in real-world data.

Clearly, our algorithm may be improved further. Trying to adapt the Bron-Kerbosch algorithm [START_REF] Bron | Algorithm 457: finding all cliques of an undirected graph[END_REF] and some of its variants [START_REF] Tomita | The worst-case time complexity for generating all maximal cliques and computational experiments[END_REF][START_REF] Koch | Enumerating all connected maximal common subgraphs in two graphs[END_REF][START_REF] Cazals | A note on the problem of reporting maximal cliques[END_REF][START_REF] Eppstein | Listing all maximal cliques in large sparse real-world graphs[END_REF], the most widely used algorithms for computing cliques in graphs, is particularly appealing. Indeed, the configuration spaces built by these algorithms are trees, which avoids redundant computations. This is achieved by maintaining a set of candidate nodes that may be added to previously discovered cliques, which does not directly translate to our situation because of time in link streams. Still, we believe that progress is possible in this direction.

We also consider the case of links with duration as a promising perspective: each link (b, e, u, v) means that u and v interact from time b to e. In this case there is no need for a ∆ anymore, as density in this context is nothing but the probability that two randomly chosen nodes are linked together at a randomly chosen time. The definition of cliques in link streams with durations follows directly, and our algorithm may be extended to compute maximal such cliques.

Figure 1 :

 1 Figure 1: Examples of ∆-cliques. We consider the link stream L = ([0, 9], {a, b, c}, E) with E = {(3, a, b), (4, b, c), (5, a, c), (6, a, b)} and ∆ = 3. There are four maximal 3-cliques in L: ({a, b}, [0, 9]) (top left), ({a, b, c}, [2, 7]) (top right), ({b, c}, [1, 7]) (bottom left), and ({a, c}, [2, 8]) (bottom right). Notice that ({a, b, c},[START_REF] Bron | Algorithm 457: finding all cliques of an undirected graph[END_REF][START_REF] Johnson | On generating all maximal independent sets[END_REF]) is not a ∆-clique since during time interval[START_REF] Bron | Algorithm 457: finding all cliques of an undirected graph[END_REF][START_REF] Eppstein | Listing all maximal cliques in large sparse real-world graphs[END_REF] of duration ∆ = 3 there is no interaction between a and c. Notice also that ({a, b},[START_REF] Bron | Algorithm 457: finding all cliques of an undirected graph[END_REF][START_REF] Rowe | Automated social hierarchy detection through email network analysis[END_REF]), for instance, is not maximal: it is included in ({a, b}, [0, 9]).

  ) to S and to M 3: while S = ∅ do 4: take and remove (X, [b, e]) from S

  then

9 :

 9 if (X ∪ {v}, [b, e]) not in M then 10: add (X ∪ {v}, [b, e]) to S and M 11: f ← max u,v∈X f buv latest first occurrence time of a link in (X, [b, e]) 12: set b to f -∆ 13: if b = b then 14: set isMax to False 15: if (X, [b , e]) not in M then 16: add (X, [b , e]) to S and M 17: l ← min u,v∈X l euv earliest last occurrence time of a link in (X, [b, e]) 18: set e to l + ∆ 19: if e = e then 20: set isMax to False 21: if (X, [b, e ]) not in M then 22: add (X, [b, e ]) to S and M 23: if isMax then 24: add (X, [b, e]) to R 25: return R Let us explain the choice of b (Lines 11 to 16) in details, the choice of e

Figure 2 :

 2 Figure 2: A sequence of ∆-cliques built by our algorithm to find a maximal ∆-clique (bottomright) from an initial trivial ∆-clique (top-left) in the link stream of Figure 1 when ∆ = 3.From left to right and top to bottom: the algorithm starts with ({a, b},[START_REF] Holme | Temporal networks[END_REF][START_REF] Holme | Temporal networks[END_REF]), and finds ({a, b},[START_REF] Cazals | A note on the problem of reporting maximal cliques[END_REF][START_REF] Holme | Temporal networks[END_REF]) thanks to Lines 11 to 16 of the algorithm. It then finds ({a, b, c},[START_REF] Cazals | A note on the problem of reporting maximal cliques[END_REF][START_REF] Holme | Temporal networks[END_REF]) thanks to Lines 6 to 10. It finds ({a, b, c},[START_REF] Cazals | A note on the problem of reporting maximal cliques[END_REF][START_REF] Johnson | On generating all maximal independent sets[END_REF]) from Lines 17 to 22, and finally ({a, b, c},[START_REF] Casteigts | Timevarying graphs and dynamic networks[END_REF][START_REF] Johnson | On generating all maximal independent sets[END_REF]) from Lines 11 to 16.

Figure 3 :

 3 Figure 3: The configuration space built by our algorithm from the link stream of Figures 1 and 2 when ∆ = 3. Each element is a ∆-clique and it is linked to the ∆-cliques the algorithm builds from it (links are implicitly directed from top to bottom). Plain links indicate ∆-cliques discovered by Lines 11 to 16 or Lines 17 to 22 of the algorithm, which change the time span of the clique. Dotted links indicate ∆-cliques discovered by Lines 6 to 10, which change the set of nodes involved in the clique. The bold path is the one detailed in Figure 2. Colors correspond to the maximal ∆-cliques displayed in Figure 1.

Lemma 3 .

 3 Let C = (X, [b, e]) be a maximal ∆-clique of L, and let s be the earliest occurrence time of a link in C. Then e ≥ s + ∆.

Lemma 4 .

 4 Let C = (X, [b, e]) be a maximal ∆-clique of L and let s be the earliest occurrence time of a link in C. If (X, [s, s + ∆]) is in S at some stage of Algorithm 1, then C is in the set returned by the algorithm. Proof. Assume C 0 = (X, [s, s + ∆]) is in S and consider the longest sequence of steps of Algorithm 1 of the form:

Lemma 5 .

 5 u and v from b to b + ∆. By definition of s, b + ∆ ≥ s. Therefore the latest first occurrence time of a link in C k , f , is equal to b + ∆ and Lines 11 to 16 build C from C k . All maximal ∆-cliques of L are in the set returned by Algorithm 1.

Theorem 2 .

 2 Let L = (T, V, E) be a link stream with |V | = n and |E| = m, and let ∆ be a duration, then Algorithm 1 computes the set of all maximal ∆-cliques of L in O(2 n nm 2 ) space and O(2 n n 2 m 3 + 2 n n 3 m 2 ) time.

Figure 4 :

 4 Figure 4: Left: complementary cumulative distribution of ∆-clique sizes for different values of ∆. Right: complementary cumulative distribution of ∆-clique durations for different values of ∆. The sharp drop at 2 • ∆ is due to ∆-cliques involving only one link.

Figure 5 :

 5 Figure5: Behavior of our algorithm depending on the way it explores its configuration space (DFS or BFS). Left: number of maximal cliques discovered as a function of the number of iterations of the main loop of the algorithm. Right: maximal size of discovered cliques as a function of the number of iterations of the main loop of the algorithm. A clique size is estimated here by its number of nodes times its duration (in seconds).

Table 1 :

 1 Experimental results for computing all maximal ∆-cliques on the Thiers-Highschool dataset. |R| is the size of the set returned by our algorithm, (i.e., the number of ∆-cliques found). For information, storing the dataset in RAM requires 51 MB.

	∆ (s)	|R|	Max	Max e -b	Running	Memory
			|X|	(s)	time (s)	(MB)
	60	14 664	5	6 820	150	537
	900	8 214	7	17 420	555	4 755
	3 600	7 170	7	36 340	1 080	23 186
	10 800	7 416	7	59 560	3 100	30 453

A Debian machine with a

2.9 GHz CPU and 64 GB of RAM.

Acknowledgments.

We warmly thank the anonymous reviewers, who helped us improve this paper much. This work is supported in part by the French Direction Générale de l'Armement (DGA), by the Thales company, by the CODDDE ANR-13-CORD-0017-01 grant from the Agence Nationale de la Recherche, and by grant O18062-44430 of the French program PIA -Usages, services et contenus innovants.


João Sérgio Onofre
email: onofre@holos.pt

Paulo Pimentão

Pedro Sousa

João Paulo Pimentão

Georeferenced Dynamic Event Handling

Keywords: Multi-agents, surveillance, distributed systems, geographic position, mobile, collective behavior, human-machine cooperation, task assignment

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The surveillance systems have been used as an important tool in protecting people and goods. These systems have evolved, from simple monitoring cameras to complex systems that detect different types of events automatically.

DVA's architecture is based in a multi-agent architecture, where events, sensors and human resources are georeferenced. The cooperation between these georeferenced components, allows the creation of a comprehensive surveillance system able to display collective intelligence, supported by the collective awareness in the performance of surveillance and security functions [START_REF] Onofre | Geo-referenced multi-agent Architecture for Surveillance[END_REF].

Event assignment to a human resource depends on several criteria, such as: proximity (distance and "time to"), type of event, workload and profile.

This paper begins by presenting some current approaches used to perform task's assignment, and then introduces a new approach to event assigning and processing, based in the new architecture for Surveillance Systems developed under the scope of the DVA project (http://dva.holos.pt).

Relationship to Cloud-based Solutions

Using current technological innovations, DVA implements, as basis for its data repository, a Cloud storage system. The use of Cloud allows to recover events' data and status, actions history and latest agents' positions in order to minimize system failures in case of malfunctions.

All the actions executed, GPS positions, event status and agent assignments are saved in the cloud after its executions or when changes occur, storing in, real time, a snapshot of the system is current status. In case of failure of one software agent, the system will deploy another software agent to replace its task, using as reference data stored in the cloud.

Dynamic Task Assignment

There are several approaches to the problem of dynamic task allocation, especially when it involves different parameters such as tasks type or location and performing agents assigned types or locations. These parameters can encompass a large amount of data that needs to be correlated.

One of the approaches to visualize and interpret large high-dimensional data sets is Self Organizing Maps (SOM). SOM could be used to visualize process states or financial results, by representing the central dependencies within the data on the map [START_REF] Kohonen | The self-organizing map[END_REF]. There are several approaches to task assignment based in SOM using neural networks. One of the most recent is presented by Huan Huang et al [START_REF] Huang | Dynamic Task Assignment and Path Planning for Multi-AUV System in Variable Ocean Current Environment[END_REF], where a dynamic task assignment and path planning for Multi-AUV (autonomous underwater vehicles) systems in variable oceanic currents environment is proposed. In this work, the authors present two algorithms used to solve their problem: SOM-based algorithmto assign targets to AUVs; velocity synthesis -to plan the path for each AUV in complex ocean current environment.

Another approach for AUV is presented by Sanem Sariel et al in "Naval Mine Countermeasure Missions" [START_REF] Sariel | Naval Mine Countermeasure Missions[END_REF], where DEMiR-CF's distributed framework is presented for multirobot teams. This framework integrates incremental task selection schemes, distributed allocation methods, and several precaution routines. Also based in SOM, Anmin Zhu and Simon X. Yang [START_REF] Zhu | A neural network approach to dynamic task assignment of multirobots[END_REF], propose a dynamic task assignment for multirobots in arbitrarily non stationary environments, where: initial neural weights of the network to select the winner, update of the weights, and neighborhood function are defined.

In "UAV Task Assignment", Brett Bethke et al [START_REF] Bethke | UAV Task Assignment[END_REF], present a health-aware task assignment algorithm for control and coordination of actions of multiple autonomous vehicles in a dynamic environment, improving team's operational reliability and capabilities through better system self-awareness and adaptive mission planning.

A distributed market-based coordination algorithm for a team of robots is presented by Nathan Michael et al [START_REF] Michael | Distributed multi-robot task assignment and formation control[END_REF]. In this case agents will bid for task assignment, assuming that the agents have knowledge of all tasks as well as the maximum number of agents that can be assigned to every individual task. A distributed auction algorithm described in "Distributed Task Assignment for Mobile Agents" by Brandon J. Moore and Kevin M. Passino [START_REF] Moore | Distributed Task Assignment for Mobile Agents[END_REF], is used to assign mobile agents to spatially distributed tasks. This approach controls the motion of the agents during the algorithm's progress.

Finally in the "Dynamic Task Assignment in Robot Swarms" by James McLurkin and Daniel Yamins [START_REF] Mclurkin | Dynamic Task Assignment in Robot Swarms[END_REF], four algorithms are described for dynamic assignment of tasks in multi-robot systems: Random-Choice, Extreme-Comm, Card-Dealer's and Tree-Recolor.

These approaches could be used in different systems as described, nevertheless all of them assume that agents have the same characteristics, not differentiating their suitability for a given task. Also these approaches are not assuming different types of tasks. These assumptions work on general systems, but not on systems that have different types of task to assignment and different types of agents to execute them. Another important issue is the fact that the full set of events is not known at the beginning, with events emerging during execution with different requirements such as agent profile or priority. Also, events' processing time (time used by agents to solve the event) is not the same for each event. This time constrains agent's action to the event, giving more relevance to the workload of each agent.

Georeferenced Dynamic Event Handling

Considering the weakness of current surveillance systems in terms of cooperation between humans and machines, this paper presents a new approach to events' assignment, improving the efficiency and time response to events. The next sections briefly describe the DVA, the dynamic georeferenced event assignment algorithm and the event handling process.

The DVA System

DVA's surveillance architecture is a multi-agent system, which allows a distributed approach to surveillance by assigning tasks among the agents. Each agent is responsible for very specific tasks according to its profile. The main types of agents present in DVA are: Sensors, Processors, Inference, Action, and Mobile [START_REF] Onofre | Geo-referenced multi-agent Architecture for Surveillance[END_REF]. In summary, Sensor Agents interact directly with the sensors (for example a camera or temperature sensor) and send the data to the Processor Agents. These agents transform raw data into parameters with: value, type of parameter, unit, timestamp and coordinates. The parameters are used by the Inference Agent that, with a set of rules, can infer the existence or not of a given event. If an event is detected, the system automatically creates an Action Agent, which will be responsible by its handling.

Events are described by: event type, priority, location, time of occurrence, status and associated parameters. Event statuses are: To be checked, Confirmed, Concluded and Canceled.

In DVA, associated to each status, different actions can be defined, such as:

• Concluded and Cancelled: Send email notification; Send SMS notification;

• To be checked and Confirmed: Send email notification; Send SMS notification; • To be checked: Assign event for confirmation;

• Confirmed: Assign event for processing. Email and SMS notifications can be used to alert users of a new event occurrence, sending event's complementary information.

Fig. 3 Georeferenced assignment process

Event assignment process, illustrated in figure 3, uses different criteria (such as agent's types, location and workload) to search and assign an agent to event's confirmation and processing. The event assignment process, executed by the Action Agent, starts by identifying all the Mobile Agents presented in the system and then sorting then, using the algorithm described in the next section, to determine which must be selected.

Dynamic Georeferenced Event Assignment

As mentioned before, in DVA's system, events are typed, prioritized and georeferenced. Also, Mobile Agents (human agents) are typed, according with their function, locomotion mean, georeferenced and tagged with their current workload. This categorization, in terms of events and agents, provides information used to improve the assignment process. Resuming, in terms of categorization:

Events have a: Type (Fire, Earthquake, Flood, Intrusion and Gas); Priority/severity (High, Medium and Low); Location (GPS coordinates).

Agents have a: Type (Profile: Fire-fighter, Policeman, Security Agent or Civil Protection); Workload (Number of Event assigned); Location(GPS coordinates); Locomotion (on foot, by car).

Using these categorizations as criteria, the system can locate and select the most appropriated agent according with event's type, priority and location.

Distance and Time Criterion DVA uses Google Maps services to calculate distance and time between two locations, on foot and by car, depending of agent's locomotion means. These values will be used as inputs to determine which agent is closest to event's location. Nevertheless, to ensure DVA's independence from external services, in case of service failure, DVA's system uses Haversine's formula [START_REF] Sinnott | Virtues of the Haversine[END_REF], to calculate the distance between locations. The formula used is:

              - +       - = 2 sin ) cos( ) cos( 2 sin arcsin 2 1 2 2 2 1 1 2 2 λ λ φ φ φ φ r D (1)
Where: D = Distance between two locations; r = Radius of earth (6371000); ϕ1, ϕ2 = Latitude of location 1 and location 2; λ1, λ2 = Longitude of location 1 and location 2;

Using the calculated distance, is possible to estimate the time to reach the location on foot, by car, or other type of vehicle, defining an average speed to each case.

For example, considering 5km/h for walking/running and 50km/h for car's use, to determine the time in minutes, the formula used is: As mentioned before, the lowest calculated time (according with agent locomotion) will be used as a criterion to determine the event's assignment. Noteworthy that for the car's use the time delay in case of transit must also be considered, nevertheless in this paper will be considered zero for simplicity.

Workload Criterion

Each agent can have one or more events assigned and each represents a workload's increase. In addition, event's processing time is undetermined, being different for each event. For example, a small fire event could be solved in 5 minutes with a Fire extinguisher and large fire could last a morning or a day to be extinct. Given this fact, at this time, just the number of events is considered. Nevertheless as the system tested in practice, one may get further insight on how to deal with this issue. The workload criterion will represent, therefore, the number of events currently assigned to an agent.

Profile Criterion

Depending of the agent's profile, its capability to respond to a given event's type will be different. For example, a policeman will find it harder to respond to a fire than an intrusion, likewise fire-fighters respond better to fires than to intrusions. The next table shows an example of classification, identifying performances of each agent's profile according event's type. In this case, "1" represents the best performance and "5" the lowest.

Priority and Events List Criteria

When a new event arises, an agent either be free, processing an event or on the way to an event. If the agent is not free, the new event's priority will be compared with current agent's events list priority. The result of this comparison will influence event's assignment, even changing its previous assignments. Current agent's events list could change distance and time to the new event, by adding to the route all current's events that have the same or higher priority than the new event.

For example, if an agent is underway to an event of highest criticality 10km away from its current position and the new event is on the opposite direction, the distance to consider to the new event is not the one from the current position, but the distance to the current event over a distance up to the new event. Nevertheless, if the current event has less criticality than the new one, the agent can interrupt its way, so the current position is considered to calculate the distance. This criterion will influence the distance and time criteria, changing time to reach event according agent's events list and events priority.

Winner Agent

To identify which agent is the most adequate for event's assignment, an adaptation of the Euclidean formula for three dimensions is used. The three dimensions to consider in the Euclidean formula will be: Time, Workload and Profile. In Euclidean 3D space formula, the distance between two points is defined as:

( ) ( ) ( ) 2 1 2 2 1 2 2 1 2 z z y y x x d - + - + - = (3)
Where "d" is the calculated distance, and "x", "y", "z" represent the different dimensions. The direct application of this formula works when the three-dimensions are defined with same magnitudes i.e. normalized. In DVA, the three-dimensions have very different magnitudes (Time, Workload and profile), thus being necessary to rescale them. Considering this special case, the Euclidean formula was adapted to:

2 2 2 5 5 30       +       +       = a a a a p l t Sc (4)
Where "Sca" is agent "a" scores to new event, "ta" the time to agent "a" reaches the event, "la" agent "a" workload and "pa" agent "a" profile. In DVA 30 minutes is considered by our consultant security experts as the maximum allowable to reach a location, under duress 5 as the maximum workload by agent and 5 as the lowest adequate profile. These values were used to normalize the formula's parameters.

The winner agent will be the one that has the lowest score for the set of agents. } ,.., , { min arg

2 1 n i a Sc Sc Sc W = (5)

Event Reassignment Procedure

If the assigned agent has to interrupt a previous event handling, caused by a new event (with higher priority) assignment, a new event assignment will be executed for the event whose handling was been interrupted. This procedure will be executed until all the events have an assigned agent.

Example

This section illustrates an example of DVA's Dynamic georeferenced event assignment application. This example will not use Google Maps services, but the formulas presented to calculate distance and time.

In this example's application, DVA has five agents available to handle events. As a start point, two events will be considered. These two events are already assigned to agents A4 and A2 respectively. Agent A2 is already in its event's location, processing it and agent A4 is on the way to event E1. When a new event arises, represented as E3, a new assignment process will start. Table 2 illustrates the current system's events list, with its values, and the current situation of agents are shown in table 3. Using these two tables as inputs, all the criteria will be calculated, according to the agents' profiles setups and locations, its events list and workload. The next table presents the calculated values for each criterion, and the final score for each agent. the calculated scores, Agent 1 will be the agent assigned to E3. In this case, it will not be necessary to perform any event reassignment.

Conclusions

DVA was developed to react geographically to events such as intrusion, fires, gas leakage, earthquakes or floods. This system can help prevent or minimize events that can compromise the safety of persons or property. The assignment process described in this paper aims to improve the current surveillance systems, reducing event's time response and increasing efficiency, by using geographical position of events and humans together with other functional characteristics.

This new approach, may also contribute to reduce the surveillance system dependency on humans, by automating event detection and assignment, thus minimizing human errors and personnel costs. Also, this approach could fulfill some of the gaps found in related work in the literature, such as use of agents with different characteristics, such as speed and profile, and different events types and priorities.

DVA is currently in test, being used as a support system to surveillance of Madan Parque (Science and Technology park). The current tests will allow us to validate the application of the assignment process. Some preliminary results of these tests allowed us to identify areas where the system can be improved. One of the already identified areas for improvement is the relation between agent profile and performance on event types. In fact, we found that the allocation of "hard" values to this relationship is not consensual and the performance could be improved by the use of fuzzy logic.

Table 1 .

 1 Profile vs event performance.

		Police Firefighter Security	Civil protection
	Fire	3	1	3	3
	Flood	3	1	4	2
	Intrusion	1	5	2	5
	Earthquake	3	2	4	2
	Gas	3	3	4	2

Table 2 .

 2 System's events list.

		Event 1	Event 2	Event 3
	Latitude	38,64885 38,66601 38,63088
	Longitude -8,88107 -8,96553 -8,91523
	Priority	High	High	Low
	Type	Fire	Intrusion Intrusion

Table 3 .

 3 Agents current status.

		Agent 1	Agent 2	Agent 3	Agent 4	Agent 5
	Latitude	38,68316	38,66601 38,63195 38,64161 38,67807
	Longitude	-8,91026	-8,96553 -8,94150 -8,90579	-8,94150
	Workload	0	1	0	1	0
	Event list	-	Event 2	-	Event 1	-
	Status	Stooped	Handling Stooped	On way	Stooped
	Profile	Police	Security	Police	Police	Firefighter
	Locomotion Motorcycle	Walk	Walk	Car	Car

Table 4 .

 4 Agents calculation and scoring.

		Agent 1	Agent 2	Agent 3	Agent 4	Agent 5
	Profile	5	4	5	5	2
	Distance	5,83	9,57	2,28	5,87	5,72
	Vehicle Time	7,00			7,04	6,87
	Walking Time	69,95	114,87	27,41	70,44	68,65
	Score	0,23	70,31	27,41	0,31	0,64
	Comparing

S. Onofre, J. Pimentão and P. Sousa

S. Onofre, J. Pimentão and P. Sousa


Manja Görner

Thomas Göschel

Stephan Kassel

Thomas Klein

Sabrina Sander

Thomas Goerner

Stephan Goeschel

Thomas Kassel

Sabrina Klein

Sander

Implementation of User-oriented Smart Services into an Innovative DC Low Voltage Net

Keywords: DC voltage, services, smart home, interoperability

In this paper a concept of smart services implemented in an innovative DC net (direct current) is described. It shows how various components with different DC-energy-level-demands and user-based requirements can be connected interoperable. Thus smart services can be defined in that technical environment. The implemented system is able to remember the residents' individual preferences to provide a comfortable living situation.

Introduction

In terms of smart homes and cyber-physical systems it is a general effort to provide house systems with more intelligence to achieve an enhanced usability. At the same time, in terms of scarcity of natural resources and increasing environmental awareness, energy and cost efficiency is indispensable for a profitable operation.

Today's households' demand for electricity is fulfilled either via the public energy network or internal measures. The most widespread system for generating own electricity are photo-voltaic (PV) systems. But in 2012, less than one percent of the German households supplied themselves with self-generated electricity on the basis of a PV system. [START_REF]Eigenerzeugung und Selbstverbrauch von Strom. Stand, Potentiale Trends[END_REF] A PV system produces power with DC voltage. This is normally converted into AC voltage before it is fed into the home network. But many household appliances operate with DC voltage. Therefore, a rectifier is installed in the power supplies of the appliances. Both the inverter and the rectifier lead to conversion losses. [START_REF] Hermanns | Demand-Response Management for Dependable Power Grids[END_REF] In this paper a model room with an innovative DC net is presented. This DC net is supplying the electric and electronic devices in a residential unit directly with DC voltage. The necessary adaptation of the appliances is described. Based on these appliances a smart services environment is defined. The services build a platform for an interoperable connection between these appliances and, at the same time, serve as a gateway for individual user intervention.

The paper gives an overview about the projects main ideas and the project partners' contributions.

Relationship to Cloud-based Solutions

In this paper, the preliminary results of a project are presented, which is igniting subsequent projects. Therefore it represents a fundamental conceptual basis. The actual prototypical model room includes a central local control. A following project will dissolve this restriction by shifting significant portions of the control into a cloud. Firstly this offers the user ubiquitous access to the system. Furthermore, by outsourcing of information the system would be less affected. It would handle only the information it needs at that moment. An expensive performance improvement of the components would not be necessary, yet strong functionality would be guaranteed.

Related Literature

Currently there are various ideas for services in a smart home, but most of them are based on an AC net with AC appliances. The differences in the approaches of provided services are resulting from their intentions. For example, one of the greatest German energy companies, RWE, is including into the definition of services the opening and closing from windows, blinds and heating as well as the lighting and consumer electronics. The target of these services is to provide home safety, by increasing the protection from burglary and fire, as well as to maximize comfort and convenience. [START_REF] Rwe | [END_REF] Regarding the implementation of DC networks in buildings, many studies and approaches already exist, like the project "Stroomversnelling" from the Netherlands. The aim is to implement a DC system, with only one AC socket connection, within three steps. [4] There are more similar conceptions like in [5] and [6], but nearly all of them are only focusing on the implementation of a DC net, without a smart interconnection of the appliances. This situation is unsatisfactory, especially when, simultaneously, the number of devices in households is permanently increasing.

The problem is also mentioned by the Energy Information Agency (EIA). According to their studies, consumer electronics and small appliances are the fastest growing sectors of residential electricity use. Twenty years ago, in 1993, this category played no role in their investigations. But eight years later, they already counted more than ten devices in that category. Last year, some members of the IEEE listed all small appliances and consumer electronics devices in their houses. They counted to more than fifty. [7] This is an important argument to perform research how the small appliances and consumer electronics should be integrated in a smart home.

Research Contribution and Innovation

Based on these observations, the project EGNIAS was launched. The project team decided to combine a DC approach for the technical energy network with the ideas of the smart home, to let DC appliances interact with each other.

For defining the services, a technical base has been created. The system was built as a model room with an inside dimension of approximately 140x90x50 cm (WxDxH). The room is divided into an entrance area, a working area, a dining area, a lounge area and a reading area. The model has been populated with furniture built by the universities faculty of wood design. The central PLC is responsible for the room observation and control as well as the residential unit's energetic supervision. This includes determining the energetic subscription and usage sizes which allows the determination of user-dependent power efficiencies, as well as the monitoring of the energy storage. Thus, power supply reliability can be achieved, combined with the possibility for an ex-post review of the power storage characteristic.

The model room was equipped with a DC voltage based power supply system. Therefore, a PV element and an energy storage have been connected to the room. With the PLC based room controller various components (sensors, actuators, power supply, operator controls ...) are interoperable connected via various transmission media (KNX, radio, etc.).

The challenge was set by configuring reasonable and suitable services for the inhabitants based on the DC low voltage appliances. The highest power supply voltage into the pattern room can maximum achieve 24 volt. The project team decided, according to the statement of the Energy Information Agency (EIA), to install in a first step only consumer electronics like a television, a radio, a personal computer, a tablet and a telephone as well as a standard lamp, three ceiling lights and one wall light. Including all of these components, a set of services should be designed.

The plugs from a number of these appliances have been changed, so that the appliances can be connected to the newly designed power supply system, requesting the suitable voltage level.

With these appliances, individualized settings for well-being should be created. Special attention is given to the creation of an intelligent interface between the deterministic system behavior and the complexity of human perception. (The same brightness can be perceived differently in various situations.) Furthermore, external influences, like sunlight, have to be taken into consideration for the models.

In these appliance settings, services have been defined. A service is defined as a process to influence physical environmental parameters selectively. Input variables of these processes are the actual values of the environmental parameters and planned activities of the users. The resulting values of the output parameters are derived from the planned activities (of the selected services).

Special attention was given to the matching of the provided services with the user's needs. They should provide an appropriate room climate. This concept has been implemented so far, that different room regions are differently illuminated and that the combination of services is restricted to reduce possible distractions. For example during the meal service the TV is turned off, so that the people are not distracted and the communication is encouraged at the table. A service is therefore not responsible for the control of one appliance. It provides a combination of control commands for a multitude of devices.

Because the environment is perceived differently by each person, the user can change the room situation as desired, and customize the services individually. Appliances can be turned on or off and the light intensity can by adjusted. These individual settings for the services can be stored for later replaying after a service change.

The built-in brightness sensors are considering the effects of external light sources as well. This guarantees that external influences are taken into account when controlling the illumination. Overall, the system architecture includes three layers: the hardware layer, the abstract layer and the user-oriented layer. The user-oriented layer is the interface to the user. It provides the user's access to the system. In particular a tablet computer interface offers different views to the system, according to differing demands of several user groups. There are technicallyskilled users, who want a detailed access, and technical-agnostic users who want a very simple and easy-to-use interface.

The hardware layer is the technical foundation. It is the layer, where the DC net is physically implemented and the appliances are connected and switched.

Between these two layers, there is an abstract layer. This layer serves as the translator between the other two layers. Here are the connection points established. It does not only interface with the two other layers. In this layer, all information and signals of the whole system are collected. The service processes, which were introduced earlier in this paper, are running here. This layer makes the system smart.

Discussion of Results and Critical View

It has been shown that different components with different DC-energy-level-demands and user-based requirements can be connected interoperable. In particular the appliances power slots are designed in a new and innovative way, so the appliances are directly provided with DC voltage. This makes the use of AC and DC converters unnecessary. It allows increasing the energy efficiency of the overall system.

The system is able to remember the resident's individual preferences of a feel-good atmosphere. The room is able to react on its environmental variables, for example the intensity of the solar radiation.

Because the appliances landscape is not yet very flexible, the implementation of services has to be classified as a static implementation. Each device has to be manually integrated into the system. This does not reflect the dynamics a user likes to have in his apartment. In fact, during the day he connects various appliances to the power supply and removes them again. This is not represented in the actual model.

Conclusions and Further Work

Within the built model it is shown how different voltage levels are provided to different consumers in a DC network. Using their specifically designed plugs the appliances get access to the relevant voltage level from the energy net, so no converter has to be used at this point. That increases the energy efficiency of the system significantly and user-side mistakes are prevented in advance.

In the next step, this interface should be made more intelligent, so that the appliances can tell the system what kind of devices they are (and what energy they need). Technically, this should be implemented by a NFC tag (near field communication) that is attached to the power plug of the appliance and behind the socket of the power outlet. By plugging the plug into the socket a data exchange connection is built like the universal plug&play method. So the information is exchanged, which voltage level must be provided to the appliances and how the devices may be integrated into the already existing services. This should be visualized for the user on his tablet-based user interface. If new room usage options are resulting from the enhanced appliances (like plugging in a media server), the definition of new high-level services will be possible. Technical alternative to the NFC technology may be a Bluetooth based technology.

In the basic model, the user accesses directly to the PLC program via the tablet's user interface or the control buttons in the room. The evolution plan of the project envisions the changing of this interface. Appropriate control variables should no longer be stored in the memory module of the PLC, but in a cloud. If the user wants to use a new service, the PLC gets a signal to download corresponding parameters from the cloud to be able to control the appliances. Thus, a continuous exchange of information is not necessary, limiting the information exchange. To manage his housing unit, the user does no longer need to be within the house. He only needs to be able to connect to the cloud and can control his home environment via a remote interface.

Fig. 1 .

 1 Fig. 1. The model room Technically, the room controller is implemented with a PLC (Programmable Logic Controller). It is connected by an IO-unit with the model apartment. The power outlets are controlled by a digital output terminal; the lamps are connected to a dimmer with an analog output terminal. The feedbacks of the achieved luminosities come from light sensors, which are connected to the analog inputs of the PLC. The control button next to the door in the entrance area is connected with the system by a KNX-communication terminal.The central PLC is responsible for the room observation and control as well as the residential unit's energetic supervision. This includes determining the energetic subscription and usage sizes which allows the determination of user-dependent power

Fig. 2 .

 2 Fig. 2. The systems layer-based architecture

M. Görner et al.


Fernando Luis-Ferreira

Sudeep Ghimire

Ricardo Jardim-Gonçalves

Ricardo Jardim-Goncalves

Brain Inspired Health Monitoring Supported by the Cloud

Keywords: Cloud, Health Monitoring, Internet of Things, Brain Models

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

A person living in modern societies is surrounded by an ever-growing number of technological devices [START_REF] Sundmaeker | Vision and Challenges for realising the Internet of Things[END_REF]. The pervasiveness of computing and sensing devices offers different types of services that, ultimately, represent a source of data that can be used for the most different objectives and applications. As a person makes daily family or work activities, he/she is permanently exposed to an environment with which is necessary to properly interact and get valuable output for his/her life.

With the emerging developments of mobile devices and the Internet of Things becoming a reality, the offering of information provided by sensors or integrated services is growing fast. It would be desirable that a citizen could benefit from the best performance of all those systems, being supported by accurate context awareness thus improving quality of life, and security. In that direction, the information that devices and systems either portable or installed in surrounding environment (e.g. car, house, city, etc.) [START_REF] Luis-Ferreira | A behavioral framework for capturing emotional information in an internet of things environment[END_REF].

Most of animals have surveillance mechanisms, in which mammals stand out by the complexity of their sensorial organs and brain functions. Humans have, a sensorial capacity and processing at brain that detect and identify dangerous (e.g. fire in the surroundings) or risky situations (e.g. if you step there you may fall). In fact much of these mechanisms rely on how the brain makes assessment of the environment and what are the present dangers and the risk of following actions. In the current environment, of applications in portable devices, (e.g. smartphones) such equipment should be empowered to identify the situations surrounding us and, eventually, warning us about identified risks in the proximities. That strategy is pursued by the emerging research area on context awareness [START_REF] Gellersen | Towards a Better Understanding of Context and Context-Awareness[END_REF]. Our current research, alike the brain, tries to identify our current physiological situation (e.g. temperature and heartbeat) and that of the surrounding environment (e.g. temperature, humidity) in order to evaluate our current health status and potential risks.

In the next section, the perspective of personal health monitoring powered by cloud with real-time data collection is explored. Section 3 provides research questions and hypothesis in close relation with the ongoing doctoral studies. Section 4 contains a discussion on methodology and concepts proposed by this research work and finally, section 5 presents conclusions and future work.

Personal Health Information Management using the Cloud

Sensors and sensor networks are in expansion with the need to obtain data from persons or from the environment. Devices with the ability to capture data can have different capabilities; they can be standalone (e.g. RFID tags) or be part of a larger setup (e.g. data from meteorological stations). That range of devices includes devices that need to be small and cheaper so that they can be installed in many places (e.g. clothes) but also devices that must operate alone for long periods of time (e.g. car identifiers). That means the need to make those devices as simple as possible with low consumption with consequent constraints in their capabilities. The need for additional computational resources is an identified problem for small sensors and similar devices as they have small or inexistent computational power, they also may be passive, and must have low energy consumption.

The usage of small (and cheaper) low consumption devices, with limited or inexistent computational power, can be empowered by the usage of external resources. For that, the cloud can be a differentiating factor to overcome the limitation of small devices, either sensors or actuators, by providing storage capacity and computational power. The cloud can be used to ensure that sensors can generate data that is stored remotely at the cloud and processed remotely where computational power is available. In what refers to personal health information management, the usage of services at the cloud can provide reasoning over knowledge bases to evaluate a person's health and to generate evaluation reports in real-time [START_REF] Luis-Ferreira | A Pervasive Computing Framework Supported by the Cloud for Personal Health Management[END_REF]. For a person doing normal life, wearable or local sensors can permanently monitor generic activities or a specific exercise (e.g. jogging, playing sports). Data being permanently sent to the cloud can be remotely analyzed and, if dangerous events are identified, the adequate warnings will be issued and, eventually, request medical assistance.

Followed Research Method

The observation of the current fitness and eHealth oriented devices and how they are operating makes us to question about its potential usefulness, for users, and how it can be improved. The problems of real-time evaluation of a person and her circumstances lead to the following question.

Research Question: How to adopt lessons learned from the brain and neurophysiology to computing devices in order to monitor, inform and assist users for self-help when necessary?

Hypothesis: We propose, by hypothesis, that if we monitor bodily functions along with environmental condition, it will be possible to establish an overview of a person's health status and warn about potential risks by utilizing computation in cloud.

Background Observation

The brain and the nervous system permanently monitor a person's body. Information is acquired by our sensorial organs, is perceived and interpreted by the brain using existing knowledge, gained by learning and experience. The reasoning is based on a combination of different inputs, acquired by sensorial organs [START_REF] Oie | Human multisensory fusion of vision and touch: detecting non-linearity with small changes in the sensory environment[END_REF], which generate better assessment (e.g. I felt a spike on my feet, the sand is red so i have a cut and I am bleeding). Thus the brain uses multiple inputs to assess if there is danger for the person or if we only need to take care, avoiding multiple attendances to a doctor.

People use many devices that have computational power and embedded sensorial capacities. Smartphones have processing capacities, usually are equipped with a GPS, have a camera and can capture sound. They also have schedulers and planners where people can shape their foreseen activities for the day. Fitness devices provide information about physiological measurements (e.g. heartbeat) and are also capable of determining at what pace you are walking or running and in general the amount of calories being spent [START_REF]Fitbit® Flex, One & Zip Wireless Activity & Sleep Trackers[END_REF] [START_REF]Nike+ FuelBand. Tracks your all-day activity and helps you do more[END_REF]. Based on all those capabilities, it is possible these days to determine if you are jogging (e.g. reading your electronic scheduler) and measuring your pace, or determine that you are in a work meeting. In those cases, an elevated heartbeat has different interpretations; in one case it is normal that you have higher heart frequency as you are running as in the other case you can be facing some disturbance, as a work meeting is not going as you would like. Using all this information it is possible to make an assessment on the health status of a person and, eventually, warn her to slow exercise or to control their reaction to a meeting.

In summary, with the existing devices and services, it is possible to monitor health status according to the context, and trigger events to inform or warn actions to be executed.

Methods and Associated Concepts

In this section we will first address the data processing flow to be followed in the proposed system, which starts with data acquisition from the real world until the actions to be performed in the real world. Fig. 1 shows the data processing flow. In the first step data is captured from the real world by various types of sensors or from other service providers. Thus collected data act as measurement of the parameter under consideration like temperature, humidity etc. In the next step, data infusion is performed leading towards more meaningful state like the temperature and humidity of an object at a particular instant, which leads to the generation of virtual sensors (VS). VSs will have data infusion rules such as if the temperature > x and humidity < y then activate VS. These are useful for generating simple instances of events, with multiple parameters, thus allowing more understanding of the real world and may lead to reflex-like reactions as appends in the human body. The next step termed "Pre-Processing" is used for pattern extraction and will remove the unwanted data from the collected samples of instances thus providing filter over useful data. The patterns detected in this phase are passed to for post-processing, where domain knowledge and rules, are applied over the collected samples to generate facts. Interpretation of facts leads to generation of actions to be taken, over which actors can decide the follow-up procedures.

In the processing flow diagram, we also see that in each stage actions are generated, which we term as "reflex"-immediate response to the state of the real world. In order to act over the reflexes users should use their own knowledge and understanding of the overall scenario. The final actions are suggested based on wider processing of the scenario thus allowing users to respond with lower level of understanding. It is important to define some important concepts for further understanding of the methodology.

Sensor: Sensors are devices that are capable of reading physical and physiological parameters. A sensor S can be defined by a tuple <D, C> where D represents datastream and C the context of the sensor. D will have a data-type and an ordered set of readings obtained at various time which can be represented as D=<DataType, {R1,…,Rn}>. C is used for understanding the contextual use of the sensor and can have an URI to an external Sensor Networks Ontology1 or can also be linked with other instances of metadata resources.

Virtual Sensor (VS): VS are termed virtual because they don't have physical occurrence but are formed by logical infusion of various sensors. So, a VS can be defined by a relation ʘ s.t. VS= Sx ʘ Sy, where Sx and Sy are sensors as defined previously. The relation ʘ can have different syntax and semantics as needed based on the type of data infusion that should be established between sensors. For instance if VS is used for taking into consideration humidity and temperature of a body part (e.g. arm, armpit) at the same time then a one to one union over the reading of the sensors for humidity and temperature will give an ordered set of reading for this new VS. And if the operator is to find the difference of the reading of two sensors (e.g. environment and body temperature) then the ordered difference between each element of the reading of two sensors will give the dataset for the VS. Note that the context of the VS can always be obtained by the union of the individual contexts of the sensors forming the VS.

Complex-Event Processing (CEP): CEP is a widely accepted term which is used to combine data from multiple sources (e.g. sensors or virtual) to infer events by observing specific patterns over observed data. This is important to identify meaningful events or threats by observing a series of patterns and an application of possible rules. For instance if it is observed that a person is having heartbeat above a given threshold and the difference between the outside and body temperature crossed a defined limit, then by comparing to similar patterns recorded as dangerous for that person, a warning is issue signalling that some immediate action has to be taken. Also note that based on the concept of adding context to the sensors and propagated to VS will be determinant for CEP to take into consideration the context of the environment. Same patterns can raise different scenarios in different contexts thus adding more value to the CEP.

For further understanding of the concepts of sensors and VSs, let us consider a simplified scenario in which body temperature, heartbeat and Scheduler is regularly monitored to detect critical situations. Table 1 shows a snapshot of some of the situations. The data are read by individual sensor, which is infused to produce warnings by considering situations that can arise at a particular instance. This can be modelled with the definitions of sensors and VSs given before. Note that context of sensors (which can be position, data type, personal identity etc.) is not considered for simple understanding of the modelling process.

Sensors are: ST_body={36,36. This model shows the fusion of data from sensors and VS to detect warning. The VSWarning thus detects the situation that the person is at work, has body temperature above 36 and heartbeat above 80 or if the heartbeat is above 150. In the scenario as shown in Table 1, this VS issues a warning for the last column, as expected.

Conceptual Architecture and Technology adoption

This section will present the conceptual architecture that is being followed for the realization of the system. The system should have layered architecture with welldefined interfaces and clear distinction between the independent components to be implemented at each stage of data processing flow. Fig. 2 shows the conceptual architecture with distinct layers divided, with components designated for specific functionality, and a clear demarcation on the cloud and private deployments. Data Collection Layer: This layer is responsible for the collection of data via different sensors deployed in real world. Sensors interact with this layer through the adaptors. Adaptors are sensor specific implementations that act as sink for sensors, the output of which is data streams. The context of the sensor can be registered through admin configuration. This configuration will also define the adaptor for the particular type of sensor. This methodology allows easy integration of the sensor into the system with minimal changes for the new type of sensor. This layer also consists of VSs, which collect data from the outputs of the adaptors. The operation to be performed on the data for generation of outputs for virtual sensors is defined in the configuration details assigned to the virtual sensor. VS configs are the configuration files (XMLs), which will generate a new set of outputs by selecting parameters from other sensors or VSs. Since VS can also be specified with constraints, some simple events (or reflexes) will be generated and notified to the user through local application within the reach of user even in the offline mode.

Pre-Processing Layers: This layer implements CEP functionality and provides a module for publication and subscription to data. It also provides interface to query over data, patters and events that have been generated by this or lower layers. Events Generation Module is an implementation of CEP and is used for sampling and filtering of data, the rules for which are defined in the configuration file (configs). Publish/Subscribe module acts as a subscriber of events from the data collection layer and publisher for Post-Processing Layer. This module pulls data from the lower layer, passes it to modules for processing and pushes the pre-processed data towards postprocessing layer for further treatment. The query interface is utilized by the application for providing notifications and statistics to the user.

Post-Processing layer: This is a heavy-duty layer of the overall system, where critical processing of the data is performed such as reasoning and learning. This layer makes use of domain knowledge created by experts and reasoning algorithms based on logical reasoning, and/or probabilistic reasoning, to extract new facts for understanding of the overall situation. This layer also implements a learning mechanism to keep the knowledge base updated with new facts generated by automated reasoning. This layer thus acts like a decision support system (DSS) to help the responsible person to have better insight of the real-world scenario.

User-Interface: This layer is used for interaction with the users supported by local applications and applications deployed as SaaS. Local applications are for immediate response and notification of reflexes upon detected events. Other applications are provided as SaaS, in the cloud, and deliver detailed analysis of the scenario, historical data and suggested actions to be taken. The 'admin' functionality allows configuration changes of the sensors and virtual sensors. The applications can be configured to trigger alarms to the user, case an emergency situation is detected.

Technology Adoption

For the purpose of system implementation this research work adopts services and enablers, being developed by projects, under the European FI-PP program like FI-WARE2 and FITMAN3 , which provide enablers for data acquisition from the physical world, complex event processing, context aware data handling, data analysis etc. Shop-floor Data Collection4 (SFDC) is the implementation for data collection from various sensor networks (protocol agnostic methodology), and also for integration of tagged objects into the system. SFDC implements creation and configuration of the VSs and provides adaptors for some standard sensors with easy integration of new types of sensors. VSs are created by writing XML with defined schema. Complex Event Processing (CEP) 5 and Publish/Subscribe Context Broker6 are configured and used in the data pre-processing layer. Both of these enablers are the important components, which are adapted for the realization of events generation and publish/subscribe modules respectively. In the implementation of post-processing layer it is very important to consider knowledge extraction over real time data, which we have adopted from some current research work as described in [START_REF] Angelov | Nature-Inspired Methods for Knowledge Generation from Data in Real-Time[END_REF] and [START_REF] Gama | Knowledge discovery from data streams[END_REF]. This module also makes use of ANN with semantics for implementing probabilistic learning algorithm, which have been inspired by some works as described in [START_REF] Mikolov | Context dependent recurrent neural network language model[END_REF] and [START_REF] Bowman | Recursive Neural Networks for Learning Logical Semantics[END_REF].

Concluding Remarks and Future Work

Research presented in this paper has potential impact in many societal and business aspects. New business models can be deployed to support real-time monitoring as proposed and, from the human side, a citizen can be monitored and assisted while performing a normal life. As by research presented in this paper, those objectives can be achieved by building computational methodology to integrate sensorial data and their interpretation, generating advice or asking for support as needed. This research work provides a framework for raw data collection from real world and multi-stage processing of data leading towards automated understanding of the surrounding. Proposed methodology will leverage cloud computing to utilize open linked data in the domain of health and big data processing for more reliable self-help health monitoring services. On-going validation and iterative testing of the implemented system in real scenarios is the most important task to be completed in a near future.

Fig. 1

 1 Fig. 1 Data processing flow

Fig. 2

 2 Fig. 2 Conceptual Architecture

Table 1 -

 1 Data generated by the sensors and analyzed by the framework

	Time [H]	9h00	9h30	10h00	10h30	11h00
	T_body [º]	36	36.5	37	36.2	36.5
	Heartbeat [BPM]	70	110	80	70	90
	Scheduler	Jogging	Jogging	Showering	Work	Work
	Result	0OK	1OK	2OK	3OK	4Warning

http://www.w3.org/2005/Incubator/ssn/ssnx/ssn

http://www.fi-ware.org/

http://www.fitman-fi.eu/

http://catalogue.fitman.atosresearch.eu/enablers/shopfloor-data-collection

http://catalogue.fi-ware.org/enablers/complex-event-processing-cep-ibm-proactivetechnology-online

[START_REF]Fitbit® Flex, One & Zip Wireless Activity & Sleep Trackers[END_REF] http://catalogue.fi-ware.org/enablers/publishsubscribe-context-broker-orion-context-broker

Acknowledgments. The research leading to these results has received funding from the EC 7th Framework Programme under grant agreement FITMAN nr 604674 (http://www.fitman-fi.eu)