Rémy Chevrier
email: remy.chevrier@inrets.fr

Arnaud Liefooghe
email: arnaud.liefooghe@lifl.fr

Laetitia Jourdan
email: laetitia.jourdan@lifl.fr

Clarisse Dhaenens
email: clarisse.dhaenens@lifl.fr

On Optimizing a Demand Responsive Transport with an Evolutionary Multi-Objective Approach

Keywords: Dial-a-ride, Demand responsive transport, Multi-objective, Evolutionary algorithm, Optimization

This paper deals with a dial-a-ride problem with time windows applied to a demand responsive transport service. An evolutionary approach as well as new original representation and variation operators are proposed and detailed. Such mechanisms are used with three state-of-the-art multi-objective evolutionary algorithms: NSGA-II, IBEA and SPEA2. After introducing the general problem, the solution encoding and the algorithm mechanisms are depicted. The approach is assessed by applying the algorithms to both random and realistic dial-aride instances. Then a statistical comparison is provided in order to highlight the most suited evolutionary algorithms to optimize real-life transportation problems.

I. INTRODUCTION

The demand responsive transport (DRT) is a transport service which involves the satisfaction of a set of travel requests. A request corresponds to a customer to be carried from a pick-up location to a delivery at a predetermined time. In its usual form, DRT is related to the dial-a-ride problem (DARP) or to the vehicle routing problem (VRP) which both consist in optimizing the vehicles routes by reducing the number of vehicles and the travel durations [START_REF] Cordeau | The dial-a-ride problem: Models and algorithms[END_REF], [START_REF]The Vehicle Routing Problem: Latest Advances and New Challenges[END_REF]. Nevertheless, the main differences between the DARP and the VRP consist of the precedence constraints imposed by the customer journeys and their tolerance to the delays (quality of service [START_REF] Paquette | Quality of service in diala-ride operations[END_REF]). A DRT service is a specific case of the DARP, the latter being the academical formulation of routing with passengers.

The DARP involves antagonist objectives which have to be optimized concurrently. That is why the proposed approach has to cope with a multi-objective problem in which the criteria under study are not hierarchized. Furthermore, since the DARP is N P -hard [START_REF] Cordeau | The dial-a-ride problem: Models and algorithms[END_REF], we propose to use an Evolutionary Algorithm (EA) which is known to efficiently cope with scalable problems. Besides, an EA can produce multiple distinct solutions in a single run which could help the decision making. Given that it is almost unlikely to have a single optimal solution in a multi-criteria problem [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF], the multi-objective algorithm has to deal with a set of incomparable solutions. In this case, a Pareto approach is preferred for assessing incomparable solutions. Moreover using an EA paired to a Pareto approach has already been shown to efficiently solve multi-objective real-life problems [START_REF] Deb | Multi-objective Optimization using Evolutionary Algorithms[END_REF], [START_REF] Talbi | Metaheuristics: from design to implementation[END_REF].

Although a lot of metaheuristic methods exist for solving the DARP [START_REF] Bräysy | Evolutionary algorithms for the vehicle routing problem with time windows[END_REF], [START_REF] Cordeau | The dial-a-ride problem: Models and algorithms[END_REF], EA are generally used as single-criterion optimization methods aggregating multiple objectives in order to make the computation easier so that a single solution has to be found [START_REF] Chevrier | Comparison of three algorithms for solving the convergent demand responsive transportation problem[END_REF], [START_REF] Jørgensen | Solving the dial-a-ride problem using genetic algorithms[END_REF], [START_REF] Cubillos | Bio-inspired Modeling of Cognitive Tasks[END_REF]. As far as we know, only Chevrier [START_REF] Chevrier | Optimization of demand responsive transport in polarized territories[END_REF] used a Pareto-based three-objectives model to cope with the DARP with time windows (DARPTW).

In this paper, a new encoding mechanism based on a twodimensional representation as well as original operators are proposed for the DARPTW. They are integrated in three state-of-the-art algorithms: the Non dominated Sorting Genetic Algorithm II (NSGA-II) [START_REF] Deb | Parallel Problem Solving from Nature PPSN VI[END_REF], Strength Pareto EA 2 (SPEA-2) [START_REF] Zitzler | SPEA2: Improving the strength pareto evolutionary algorithm[END_REF] and Indicator Based EA (IBEA) [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF]. Then they are applied to benchmark instances and pairwise compared.

The paper is organized as follows. The problem formulation is described in Section II. Section III introduces the evolutionary multi-objective principles. Then the proposed encoding to represent the DARP, as well as the variation operators, are presented in Section IV. Experimental results for Chevrier's instances [START_REF] Chevrier | Optimization of demand responsive transport in polarized territories[END_REF] are provided and discussed in Section V. Finally, Section VI concludes the paper.

II. PROBLEM OVERVIEW

A. Formulation

The multi-objective problem (MOP) under study needs to be formulated as a set of three objective functions to be achieved (f = (f 1 , f 2 , f 3 )) and a set of constraints to be taken into account. The problem solving is based on specific parameters such as a relaxation and time windows which introduce more tolerance to slight delays and hence flexibility. For helping the reader, the symbols used in the paper are summarized in Table I. Since the DRT problem contains a DARPTW, the reader can refer to [START_REF] Cordeau | The dial-a-ride problem: Models and algorithms[END_REF] to have a mathematical model. Due to the lack of space in the paper, we only detail the specificities of the DRT problem and its multi-objective formulation.

f = (f 1 , f 2 , f 3 ) (1) f 1 = min |Λ| (2)
f 2 = min v∈Λ t v (3)
f 3 = min v∈Λ d v (4)

B. Objectives

In the DRT service under study, we aim at minimizing three objectives. The first (f 1 ) is economic and consists in minimizing the number of required vehicles (eq. ( 2)). The second corresponds to the duration reduction of the vehicle journeys (f 2 , eq. ( 3)) which could correspond to an environmental objective in so far as we look to limiting the emission of pollutants, and also in expectation of a hypothetical carbon tax. The last objective minimizes the likely delays (quality of service: f 3 , eq. ( 4)).

C. Introduction of delay tolerance and time windows

A usual DRT service uses the tolerance of the customers to accept more or less delays. Making detours allows a vehicle to group the customers more easily while producing a few delays. To model these delays, we introduce a coefficient of relaxation k r applied to the travel duration to define a maximal delivery time. Let t r + →r -be the slackened travel duration when k r > 1: t r + →r -= k r .t r + →r -. Consequently, the maximal delivery time h r -is defined as follows: h r -= h r + + t r + →r - In the case of VRP, time windows are generally used as time slots to make delivery easier. In the case of DARP, a time window facilitates the picking-up when a travel duration slightly exceeds the picking-up time. With such a mechanism, it is easier to bring together customers into a same vehicle. So, a time window at a point r + is denoted tw r + and is proportional to the theoretical travel duration to the point r -: tw r + = k w .t r + →r -, where k w is a coefficient indicating the percentage of the duration allocated to the time window.

D. Constraints

The flexibility is introduced by using relaxation and time windows while authorizing delays on the travels. Nevertheless, for limiting delays and for keeping a good quality of service, the likely delays must be limited by adding a set of constraints. Firstly, it is necessary to define what a feasible travel is. We denote x, y two arbitrary points to be potentially connected and H x the effective starting time at Point x. Indeed, there may be some accumulated delays that H x takes into account. The travel from x to y is feasible iff :

H x + t x→y ≤ h y + tw y if y ∈ V + H x + t x→y ≤ h y if y ∈ V -
Note that H is evaluated after each travel between two points and depends on the travel durations and whether the vehicle arrives before or after a theoretical starting time. Therefore, two cases may arise for determining H y which corresponds to the effective time at Point y coming from Point x:

H y = h y if H x + t x→y < h y H x + t x→y otherwise.
After calculating the effective visiting time, it is possible to evaluate the delay at a delivery point. A delay d corresponds to the difference between H and the theoretical arrival time, thus in a delivery point y, the delay d y is defined as follows

d y = H y -h y if H y > h y 0 otherwise.
The number of passengers in a vehicle is indicated by p v (initially, p v = 0). p v is updated whenever customers are delivered or picked-up. In this latter case, the capacity constraint must be checked if customers (w r ) are picked-up at a point r + :

p v + w r ≤ Q v

III. EVOLUTIONARY MULTI-OBJECTIVE OPTIMIZATION

A. Multi-objective Optimization

A general MOP can be defined by a set of n objective functions (f 1 , f 2 , . . . , f n ), a set X of feasible solutions in the decision space, and a set Z of feasible points in the objective space. Without loss of generality, we here assume that each objective function is to be minimized. To each solution x ∈ X is assigned an objective vector z ∈ Z on the basis of the vector function f :

X → Z with z = f (x) = (f 1 (x), f 2 (x), . . . , f n (x)
) as illustrated by Figure 1. An objective vector z ∈ Z is said to dominate 1 another objective vector z ∈ Z iff ∀i ∈ {1, 2, . . . , n}, z i ≤ z i and ∃j ∈ {1, 2, . . . , n} such as z j < z j . An objective vector z ∈ Z is said to be non-dominated iff there does not exist another objective vector z ∈ Z such that z dominates z. A solution x ∈ X is said to be efficient if its mapping in the objective space results in a non-dominated point. The set of all efficient solutions is the efficient set, denoted by X E . The set of all non-dominated vectors is the Pareto front, denoted by Z N . A possible approach in MOP solving is to find the minimal set of efficient solutions, i.e. one solution x ∈ X E for each non-dominated vector z ∈ Z N such as f (x) = z. However, generating the entire efficient set is usually infeasible due to the complexity of the underlying problem. Therefore, the overall goal is often to identify a good approximation of it. EAs are commonly used to this end as they are able to find multiple and well-spread non-dominated solutions in a single simulation run [START_REF] Deb | Multi-objective Optimization using Evolutionary Algorithms[END_REF].

B. Evolutionary Multi-objective Algorithms

1) NSGA-II: [START_REF] Deb | Parallel Problem Solving from Nature PPSN VI[END_REF] is probably the most widely used multiobjective resolution method. At each NSGA-II generation, solutions from the current population are ranked into several classes. Individuals mapping to vectors from the first front all belong to the best efficient set; individuals mapping to vectors from the second front all belong to the second best efficient set; and so on. Two values are then assigned to the population members. The first one corresponds to the rank the corresponding solution belongs to, and represents the quality of the solution in terms of convergence. The second one, the crowding distance, consists in estimating the density of solutions surrounding a particular point of the objective space, and represents the quality of the solution in terms of diversity. A solution is said to be better than another one if it has a best rank value, or in case of equality, if it has the best crowding distance. The selection strategy is a deterministic tournament between two random solutions. At the replacement step, only the best individuals survive, with respect to a predefined population size. Furthermore, note that, in addition to the original NSGA-II, we add an external population, the so-called archive, in order to store the whole set of potentially efficient solutions found during the search.

2) IBEA: [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF] is a more recent method that is a good illustration of the new trend dealing with indicator-based search, and started to become popular in recent years. The main idea of IBEA is to introduce a total order between solutions by means of a binary quality indicator. Its fitness assignment scheme is based on a pairwise comparison of solutions from the current population with regards to an arbitrary indicator I.

To each individual x is assigned a fitness value F (x) measuring the 'loss in quality' if x was removed from the current population P , i.e. F (x) = x ∈P \{x} (-e -I(x ,x)/κ ), where κ > 0 is a user-defined scaling factor. Different indicators can be used for such a purpose, and we choose to use the binary additive -indicator (I + ) as defined in [START_REF] Zitzler | Indicator-based selection in multiobjective search[END_REF]. I + (x, x ) gives the minimum value by which a solution x ∈ X has to or can be translated in the objective space to weakly dominate another solution x ∈ X. Selection for reproduction consists of a binary tournament between randomly chosen individuals. Selection for replacement consists in iteratively removing the worst solution from the current population until the required population size is reached; fitness information of the remaining individuals is updated each time there is a deletion. Similarly, we added an archive to store non-dominated solutions in order to prevent their loss during the stochastic search process.

3) SPEA2: [START_REF] Zitzler | SPEA2: Improving the strength pareto evolutionary algorithm[END_REF] is an extension of SPEA, where an improved fitness assignment strategy is proposed. It intrinsically handles an internal archive of fixed size that is used during the selection step to create offspring solutions. At a given iteration of SPEA2, to each population and archive member x is assigned a strength value S(x) representing the number of solutions it dominates. Then, the fitness value F (x) of solution x is calculated by summing the strength values of all individuals solution x currently dominates. Additionally, a diversity preservation strategy, based on a nearest neighbor technique, is incorporated. The selection step consists of a binary tournament with replacement applied on the internal archive only. At last, given that the SPEA2 archive has a fixed size storage capacity, a bounding mechanism, based on fitness and diversity information, is used when the size of the non-dominated set is too high. On the contrary, when the size of the non-dominated set is too small, some dominated solutions are allowed to be incorporated. As well, we added an external archive to store the whole set of non-dominated solutions found during the search.

IV. APPLICATION TO THE DARPTW

A. Solution encoding and initialization 1) Representation: The main idea of the representation is to simplify the reading of the vehicle routes. So, we use a two-dimensional representation (not a matrix but a vector of vectors) in which a gene corresponds to a single vehicle route (one vector). The sequence of data literally indicates the order of the points traversed by a vehicle. In order to ensure the points precedence, a cell indicates a request identifier and not the point itself in such a way that we can retrieve the associated point by counting the number of times the corresponding request identifier is encountered. If a request r appears for the first time, it is necessarily the pick-up point r + , otherwise it is the delivery point r -. Given that there are two points per request, a gene has necessarily an even number of cells.

The examples of Figures 2(b,c,d) are solutions to a DARPTW instance (Fig. 2(a)). For each solution, the associated encoding is depicted. Each gene i is a vector translating the route of vehicle v i . The order of the cell values indicates the sequence of the points visited by a vehicle, such as in the example 2(b), where the sequence (A, B, A, C, B, C) is the counterpart of the path (A + , B + , A -, C + , B -, C -). 2) Population initialization: The population is composed of N feasible solutions. To be sure of their feasibility we assign one request per vehicle, so that |Λ| = |R|. Hence, the DARP instance (Fig. 2(a)) requires three vehicles and the population P = {S i } could be initialized as follows:

S1 S2 S3 S4 v1 A A C C A A B B v2 C C A A B B A A v3 B B B B C C C C

B. Evaluation

The evaluation function f = (f 1 , f 2 , f 3 ) applied to a solution S computes three values corresponding to the respective objectives:

• f 1 = min |Λ|; • f 2 = min v∈Λ t v ,
that is the minimization of the sum of each vehicle route duration t v . • f 3 = min v∈Λ d v , that is the minimization of the amount of each vehicle delay d v . If a solution is not feasible and marked as wrong, its score is penalized in such a way that the solution is unlikely to be kept in the next population.

C. Crossover

The crossover aims at producing new individuals (offspring) from two individuals of the current population (parents). Let P 1 , P 2 be two parents in the population and C 1 , C 2 two solutions built from P 1 , P 2 . C 1 (resp. C 2 ) is the copy of P 1 (resp. P 2 ) with elements from P 2 (resp. P 1 ).

After creating C 1 , the next step consists in randomly choosing a gene of P 2 at position λ (vector v λ ). v λ contains the values that will be reassigned to C 1 . But, in order to avoid duplicated data, the values of C 1 matching those of v λ are removed. Then, the data of v λ can be inserted in Gene λ of C 1 at a random position.

In the example of Figure 3, Vector v 1 of P 2 is randomly chosen and the values (C C) have to be assigned to the counterpart vector of C 1 . These values are randomly inserted into Vector v 1 of C 1 and removed from Vector v 2 . If the solutions to be crossed do not have the same size, i.e. the vector to be filled does not exist, a new vector is created before filling it. Producing C 2 follows the same process by inverting P 1 and P 2.

Copying P1 and choosing v1

Assigning

(C C) to v1 C1 = P1 P2 ⇒ C1 v1 B A A B C C B A C A C B v2 C C D D A D D A D D v3 B B

D. Mutation

The mutation generally aims at bringing diversity into a population and prevents the population to converge towards local optima. Our operator mixes two mechanisms, each one used in half cases:

• an analogy to the well-known 2-OPT exchange operator which reverses a sequence of values (random size) of a randomly chosen gene (Fig. 4(a)). For example a sequence (C A C B) becomes (B C A C); • a shifting of a random customer from a vector to another (Fig. 4(b)), the pair values are randomly inserted in the host vector.

V. EXPERIMENTAL RESULTS

A. Benchmark Test Instances

Two sets of instances are used to evaluate our modeling on existing algorithms. Each instance has 100 trips and is built on geographically realistic data [START_REF] Chevrier | Optimization of demand responsive transport in polarized territories[END_REF]. All picking-up or delivery locations are geolocalized stops and the shortest duration matrix M is built using a GIS 2 .

The first set, denoted 'Rnd100', is composed of 10 randomly generated instances, whereas the instances of the second set, named 'Gravit100', are generated by a geographical model of flows. The 'gravity model' [START_REF] Haggett | Locational Analysis in Human Geography[END_REF], as well as other interaction models, allows to quantify people flows in a geographical space according to a calibration based on inhabitant densities, the time dimension, the transport facilities and attractive areas (malls, business parks...) Set 'Rnd100' has instances with an almost homogeneous distribution of customers while set 'Gravit100' has instances with a non-homogeneous distribution representing flows between 8:00am and 9:00am. This effect results from the existence of attractive areas which draw most flows instead of less attractive areas such as residential downtowns which are rather emission areas.

The algorithms the most suited to real-life applications can be highlighted by using realistic instances. Indeed, optimizing transport applications need efficient and robust algorithms.

B. Parameter Setting and Performance Assessment

The population of 100 individuals evolves over 10, 000 generations. A set of 20 runs per instance has been performed for each EA by using the ParadisEO-MOEO framework [START_REF] Liefooghe | A unified model for evolutionary multiobjective optimization and its implementation in a general purpose software framework: ParadisEO-MOEO[END_REF]. In order to evaluate the quality of the approximations for every instance we solved, we follow the protocol proposed in [START_REF] Knowles | A tutorial on the performance assessment of stochastic multiobjective optimizers[END_REF]. For a given instance, let Z all denote the union of the outputs we obtained during all our experiments. We first compute a reference set Z N containing all the non-dominated points of Z all . Second, we define z min = (z min ) denotes the lower (resp. upper) bound of the k th objective for all the points contained in Z all . In order to give a roughly equal range to the objective functions, values are normalized with respect to z min and z max . Then, to measure the quality of an output set A in comparison to Z N , we compute the difference between these two sets by using the unary hypervolume metric [START_REF] Zitzler | Performance assessment of multiobjective optimizers: An analysis and review[END_REF], z max being the reference point. The hypervolume difference indicator (I - H ) computes the portion of the objective space that is dominated by Z N and not by A. Furthermore, we also consider the additive -indicator proposed in [START_REF] Zitzler | Performance assessment of multiobjective optimizers: An analysis and review[END_REF]. The unary additive -indicator (I 1 + ) gives the minimum factor by which an approximation A has to be translated in the objective space to dominate the reference set Z N . Note that both I - Hand I 1 + -values are to be minimized. Thus, for each test instance, we obtain 20 I - H measures and 20 I + measures corresponding to the 20 simulation runs per algorithm. Once all these values are computed, we perform a statistical analysis for a pairwise comparison of methods. To this end, we use the Wilcoxon signed rank test. For a given test instance, and with respect to a p-value of 0.05 and to the metric under consideration, this statistical test reveals if the sample of approximation sets obtained by a given search method is significantly better than the one of another search method, or if there is no significant difference between both of them.

C. Results and Discussion

Table II details a statistical comparison of each algorithm vs each other (symbols ≺, , ≡ resp. indicate that the algorithm of a specific column is significantly 'better', 'worse' or 'equivalent' than the one of a specific row). The obtained results confirm that NSGA-II and IBEA are globally equivalent according to I - H , but that NSGA-II is always better (or at least equivalent) than IBEA according to I 1 + . SPEA2 is always outperformed by the other methods. Thus, it appears that NSGA-II is better than both IBEA and SPEA2 for optimizing randomly generated instances of DARPTW. Table III is the counterpart for the realistic instances. Contrary to Table II, IBEA is shown to be the best algorithm with respect to both I - H and I 1 + metrics (except for instance Gravit100-4). These unambiguous results indicate that IBEA is the most efficient (or at least equivalent) algorithm for optimizing realistic DARPTW instances while comparing pairwise algorithms. If we focus on the comparison of the two other algorithms, we see that SPEA2 is always better than NSGA-II with respect to I - H , while they are almost equivalent with respect to I 1 + . The main differences between the two kinds of instances are the densities of customers on the territory. Given the level of homogeneity of the distribution of the requests, the algorithms differently cope with the clustering effects. Hence, it seems that IBEA which uses a selection by indicator, appears to be more robust to the clustering effects due to the heterogeneous distribution of the customers.

VI. CONCLUSION AND PERSPECTIVES

This paper is devoted to solve a DARPTW applied to a Demand Responsive Transport service. After having formalised the general problem, an original evolutionary multiobjective approach was presented. Thanks to the Paretodominance principles, our approach is able to build a set of distinct non-dominated solutions which are provided to the decision maker in order to support and help his final choice. To fit the evolutionary algorithms to be compared, an original representation and variation operators were proposed and developed.

The candidate algorithms are: NSGA-II, IBEA and SPEA2. They were performed on two sets of transport instances. The first set is composed of random instances and the second of realistic instances. Such instances allow to assess the algorithm efficiency to cope with real-life applications.

The analysis of the results underline the more or less adapted behavior of the algorithms. It results of this comparative study that NSGA-II generally seems to be more efficient than IBEA for the random instances and SPEA2 is always outperformed by its counterparts. However, if we focus on the realistic instances, the results bring to light that IBEA is the best algorithm for solving realistic DARPTW.

Given that the algorithms are sensitive to the distribution of customers and flows, a preemptive and relevant work would be to integrate the geographical dimension. Indeed, the better results obtained by IBEA on the realistic instances invite us to take this dimension into account. Therefore, a lot of complementary analysis will have to be done in order to improve our understanding of the algorithm sensitivity. These analysis concern the inhabitants densities and the distribution of the stops. Indeed, the experiments on realistic instances seem to indicate the algorithm sensitivity to a specific topology. Then, it is necessary to evaluate the algorithms behavior according to the problem structures. Besides, an uncertainty integration [START_REF] Jin | Evolutionary optimization in uncertain environments -a survey[END_REF] in the method will help us to develop dynamic [START_REF] Xiang | The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments[END_REF] and multiobjective DARPTW services at the same time.

Fig. 1 .

 1 Fig.1. Representation of a solution (x 1 , x 2 ) in the decision space and the corresponding values in the objective space: (y 1 , y 2 , y 3 ) = f (x 1 , x 2 ).

Fig. 2 .

 2 Fig. 2. Examples of solution encoding: (a) Initial problem with three customers A, B, C, (b) a solution with one vehicle (one vector), (c) a solution with three vehicles (three vectors), (d) a solution with two vehicles (two vectors).

Fig. 3 .

 3 Fig. 3. Example of crossover of two solutions P 1 , P 2 for producing a new individual C 1 .

Fig. 4 .

 4 Fig. 4. Example of mutation of chromosome C 1 into chromosomes C 1 and C 1

1 ,

 1 . . . , z min n ) and z max = (z max 1 , . . . , z max n ), where z min k (resp. z max k

We will also say that a decision vector x ∈ X dominates a decision vector x ∈ X if f (x) dominates f (x ).

ACKNOWLEDGMENT

The authors would like to thank the anonymous reviewers for their contribution and their relevant remarks.

For each instance, the algorithms are opposed and compared by twos (NII: NSGA-II, I: IBEA, S2: SPEA2); Instance Ri indicates instance Rnd100-i

TABLE III STATISTICAL COMPARISON FOR REALISTIC INSTANCES. I -

For each instance, the algorithms are opposed and compared by twos (NII: NSGA-II, I: IBEA, S2: SPEA2); Instance Gi indicates instance Gravit100-i


Matthias Roth
email: mroth@eit.uni-kl.de

Lothar Litz
email: litz@eit.uni-kl.de

Jean-Jacques Lesage
email: jean-jacques.lesage@lurpa.ens-cachan.fr

IDENTIFICATION OF DISCRETE EVENT SYSTEMS: IMPLEMENTATION ISSUES AND MODEL COMPLETENESS *

Keywords: Discrete Event Systems, Identification, Implementation

 it is shown that under some conditions, the identified model language simulates the complete original system language even if only a subset of this language is available for identification. This model characteristic is crucial for many model-based techniques like diagnosis or verification. Analyzing the observed data of a laboratory facility it is shown how it can be decided if the conditions for a complete model hold for an existing application.

INTRODUCTION

Model-based techniques play a key role in many modern control applications. For systems that can be modeled as Discrete Event Systems (DES) various approaches to improve system dependability using model-based methods have been proposed in the last two decades. Examples for these methods are diagnosis [START_REF] Sampath | Failure diagnosis using discrete-event models[END_REF] and formal verification with model checking [START_REF] Machado | A generic approach to build plant models for DES verification purposes[END_REF]. A bottleneck for the application of model-based techniques is the process of model-building which is usually expensive due to high costs for the necessary specialists. A promising way to facilitate the use of model-based methods is to offer efficient identification methods in order to decrease the cost of model-building.

First approaches for the identification of DES have been proposed in the sixties and seventies of the last century in the field of computer science [START_REF] Biermann | On the synthesis of finite-state machines from the sample of their behavior[END_REF]. The identification of physical systems which is a typical interest in many engineering domains is not the aim of these works. More recent works especially on identification of Petri nets are summarized in [START_REF] Fanti | Fault diagnosis and identification of discrete event systems using petri nets[END_REF]. In the last years two main directions of constructing a Petri net from samples of its language have been followed: In the first class of approaches specific rules about interdependencies of observed events are used to identify a Petri net on the basis of observed firing and marking sequences [START_REF] Meda-Campana | Identification of concurrent discrete event systems using petri nets[END_REF]. The second class of approaches uses optimization techniques like integer programming to derive a Petri net structure according to given constraints [START_REF] Giua | Identification of freelabeled petri nets via integer programming[END_REF], [START_REF] Dotoli | Online identification of discrete event systems: a case study[END_REF].

The main obstacle for the application of these methods to real world systems is their relatively high degree of abstraction. The work is usually not focused on questions like how to represent data that can be captured from a real system and how to cope with inadequacies inherent to the data collection process. In [START_REF] Dotoli | Online identification of discrete event systems: a case study[END_REF] a case study shows that there is a considerable potential of identification methods to obtain meaningful DES models of physical systems. Since the identification data base in this work has been obtained by simulating a three tank system, important issues of working with data captured from a real system have not been addressed.

In [START_REF] Klein | Fault detection of discrete event systems using an identification approach[END_REF] an algorithm for the iden-tification of closed-loop DES is presented. The algorithm has been designed to work with data obtained from real systems and yields a monolithic automaton.

In this paper some implementation issues concerning the application of this algorithm to a real system are presented. In section 2 the class of closed-loop DES is presented and it is outlined that this system class is an appropriate modeling formalism for many industrial systems. Section 3 summarizes some practical implications of the data collection procedure and defines an appropriate data format for the identification algorithm. The identification algorithm is compactly presented in section 4. An important property of models identified with this algorithm is proofed in this section: Under some well-defined conditions concerning the observed system language, the identified model is able to simulate the complete original system language of arbitrary length 1 . In section 5 the data collection procedure and the identification algorithm are applied to a laboratory facility in order to show the relevance of the approach for real systems.

It is shown how it can be decided of if the preconditions presented in the former section hold only using measured system data.

CLOSED-LOOP DES

A typical configuration of industrial systems is a closed-loop of controller and plant. In the plant, a set of sensors measures certain process values and delivers them to the controller using the controller inputs. The controller executes a control algorithm and determines appropriate actuator settings for the plant.

Commands to actuators in the plant are transfered via controller output signals. Figure 1 shows this principle. The external behavior of such systems can be obtained by an analysis of the signals exchanged between controller and plant. In the considered class of systems these signals are binary. From an external point of view, a signal changes its value asyn-1 Language L A simulates language L B if L A ⊇ L B holds chronously which can be considered as the occurrence of an event. The closed-loop system can be characterized as non-deterministic since it consists of the combination of a deterministic subsystem (controller) and a non-deterministic subsystem (plant). Since the closed-loop system does not have any inputs, it must be considered as an event generator (note that the controller inputs also belong to the external behavior of the closed-loop DES). This system characteristic shows that the application of test functions for identification purposes like it is often done in continuous systems is not possible for industrial closed-loop DES. Only passive identification approaches working on observed system evolutions are suitable for the considered system class.

The aim of identification is to deliver a model to reproduce the external behavior of the closed-loop system. Hence, it is necessary to capture the signals exchanged between controller and plant in order to get samples of the external system behavior. In case of existing industrial facilities this process must be noninvasive to avoid disturbances of the process. In the next section, a method to capture these signals in an efficient way is presented.

DATA COLLECTION

Technical implementation

The implementation of a data collection procedure for closed-loop DES necessitates capturing the signals exchanged between plant and controller. The most accurate approach to get the according signal values is to connect the wires between sensors or actuators and the controller with a special data collection hardware like described in [START_REF] De Smet | Dispositif et procd d'analyse de performances et d'identification comportementale d'un systme industriel en tant qu'automate vnements discrets et finis[END_REF]. Although such an approach is possible within a laboratory environment, for existing industrial facilities the necessary cabling effort would be too important. Since one of the main reasons to use identification methods is to save costs, the effort to apply the method must not exceed the costs of manually model building. A slightly less accurate data collection approach that can be implemented with less effort is to collect the signals after they have been captured by the controller.

Figure 2 shows the functional principle of a programmable logic controller (PLC) which is a widely used class of controllers in industry. The controller cyclically performs the steps 'input reading' where it reads the signals from the sensors, 'program execution' to determine new output values for the actuators, and 'output writing' where the newly determined commands are sent to the plant actuators. Modern PLCs are equipped with a communication processor which makes it possible to send the values of the input and output signals to a standard PC where they can be stored in a data base. The implementation of such a connection is relatively easy (it is mainly a software problem) and does not require any special hardware. As implementation of the data link between controller and identification data base, a UDP (User Datagram Protocol) connection is used. At the end of the 'program execution' phase, the communication processor of the controller sends a UDP-datagram which is received by the PC with the identification data base. In order to validate that this connection is fast enough to be used for data collection, tests have been performed using a Siemens PLC (CPU 315-2 DP) equipped with a program leading to a PLC-cycle time of 25 to 30 ms. The PLC as a communication processor (CP 343-1 IT) which sends the data to a standard PC (identification data base). Figure 3 shows that the time between the reception of two packages alters between 25 ms and 30 ms according to the slightly varying PLC-cycle. It could also be observed that no data packets got lost during the transmission. This shows that the UDP connection is adapted for our purposes. In figure 5 a scenario with a controller input and a controller output is shown. In the example it is assumed that there is a logical condition in the control algorithm relating these two signals: if the input changes its value, the controller changes the value of the output as a consequence. It can be seen that the cause (change in value of the input) and the according effect (change in value of the output) are sent simultaneously to the data base. Hence, in the data base cause and effect cannot not directly be seen. Additionally, the figure shows that using the described data collection procedure it is possible to receive I/O vectors in the data base before the according output values are valid for the plant. The output values are sent to the plant during the step 'output writing' which takes place after the transfer of the I/O vector. The third scenario in figure 6 shows the case of an actuator influencing a sensor in the plant. When the according output is set in the controller it is transfered to the data base and with a short delay written to the the plant. The actuator controlled by the output can only then start influencing the sensor connected with input 1. Hence, in this case cause and effect cannot be captured simultaneously since the change in value of input 1 occurs some time after the vector with the change in value of output 1 has been sent to the identification data base. The delay of cause and effect is often not considered in manually built models like in [START_REF] Sampath | Failure diagnosis using discrete-event models[END_REF]. A second issue of the data collection process can also be seen in the figure: although input 1 and output 1 change their value relatively fast one after the other (faster than the duration of a PLC-cycle), it can take up to one PLC cycle until this change in value is sent to the identification data base.

The three scenarios show that the selected data collection procedure introduces some inadequacies that will also be part of the identified model. It is thus important to clearly indicate when the data has been captured in the PLC-cycle to precisely describe the data in the identification data base.

Definition of the observed language

For identification, the captured system data can be interpreted as the language of the considered closedloop DES. The identification is based on the observation of I/O vector sequences during l h different system evolutions: Definition 3 (I/O vector sequence). If during the h-th system evolution l h I/O vectors u h have been observed, the sequence is denoted as σ(h) = (u h (1), u h (2), . . . , u h (l h )).

The term 'system evolution' refers to a system run of a certain length. In manufacturing systems such an evolution can be a production cycle. Based on the I/O vector sequences it is possible to define the observed word set (I/O vector sequences of a given length) and the observed language: Definition 4 (Observed word set and language). The observed words of length q captured during p different system evolutions are denoted as

W q Obs = p i=1 ( l i -q+1 j=1 (u i ( j), u i ( j + 1), . . . , u i ( j + q -1))).
With the observed word set we can define the observed language of length n of the system starting from any reachable state as

L n Obs = n i=1 W i

Obs

In most practical applications the observed system language is only a subset of the possible system language L n Orig . The longer a closed loop system is observed, the more likely the cardinality of L n Obs converges to a certain value. If new system evolutions do not lead to new words in L n Obs , the system language L n Orig can reasonably be considered as completely observed (L n Obs ≈ L n Orig ). Figure 7 shows typical evolutions of the observed language in case of convergence and in case of continued growth. In practical application it is often the case that L n Obs converges for smaller values of n but still grows for larger values. As an example consider the case when each possible single system output has been observed (L 1 Obs converges) but there still occur new combinations (sequences) of already known single system outputs (L n>1

Obs continues to grow).

IDENTIFICATION

The aim of identification is to build a model that approximates the original system language L n Orig . In [START_REF] Klein | Identification of Discrete Event Systems for Fault Detection Purposes[END_REF] a non-deterministic autonomous automaton with output is chosen as an appropriate model to reproduce the observed language of closedloop discrete event systems:

Definition 5 (Non Deterministic Autonomous Automaton with Output). NDAAO = (X, Ω, r, λ, x 0 ) with X finite set of states, Ω output alphabet, r : X → 2 X non-deterministic transition relation, λ : X → Ω output function and x 0 the initial state.

If the output alphabet Ω consists of the captured I/O vectors it is possible to approximate the observed language L n Obs by performing state trajectories in the automaton:

Definition 6 (Words and Language of the NDAAO). The set of words of length n generated from a state x(i) is defined as:

W n=1 x(i) = {w ∈ Ω 1 : w = λ(x(i))} and W n>1 x(i) = {w ∈ Ω n : w = (λ(x(i)), λ(x(i + 1)), . . . , λ(x(i + n -1))) : x( j + 1) ∈ r(x( j)) ∀i ≤ j ≤ i + n -2}
The language of length n generated by the NDAAO is given by

L n Ident = n i=1 x∈X W i x
In [START_REF] Klein | Identification of Discrete Event Systems for Fault Detection Purposes[END_REF] an algorithm to identify an NDAAO based on an observed language is given. The algorithm delivers a model that is k + 1-complete which means that L k+1 Ident = L k+1 Obs (proof can be found in [START_REF] Klein | Identification of Discrete Event Systems for Fault Detection Purposes[END_REF]). This property excludes that the identified model contains any non-observed word of length k + 1. This makes the model suitable for fault detection purposes [START_REF] Roth | An FDI method for manufacturing systems based on an identified model[END_REF]. It is also the basis for the completeness of the model which will be shown at the end of the section. The algorithm uses words of the parametric length k to construct the NDAAO. The observed I/O vector sequences in the data base have to be modified according to the following equation. It duplicates the first vector of each sequence k -1 times:

σ k h (i) = σ h (1) for 1 ≤ i ≤ k σ h (i -k + 1) for k < i ≤ k + |σ h | -1
(1) On the basis of Σ k = {σ k 1 , . . . , σ k p } we determine the observed word sets of length k and k + 1 for the identification:

W k Obs,Σ k = σ k h ∈Σ k ( |σ k h |-k+1 i=1 (u h (i), u h (i+1), . . . , u h (i+k -1)))
(2)

W k+1 Obs,Σ k = σ k h ∈Σ k ( |σ k h |-k i=1 (u h (i), u h (i + 1), . . . , u h (i + k)))
The identification procedure is given in algorithm 1. It is a condensed version of the algorithm given in [START_REF] Klein | Identification of Discrete Event Systems for Fault Detection Purposes[END_REF]. For the algorithm, we define an operator w[a..b] to deliver the substring from position a to position b in word w. In the first step, for each word of length k a state is created. If two words of length k have been observed successively, they build a word of length k + 1. Hence, the states representing the two words of length k are connected in step 2 of the algorithm. In step 3, the output function of each state is redefined. The new state output is the I/O vector at the end of the word of length k representing the state output so far. In the last step, states with equal output and equal following states are merged. A detailed description of this procedure is given in [START_REF] Klein | Identification of Discrete Event Systems for Fault Detection Purposes[END_REF].

An interesting characteristic of a model identified with algorithm 1 is that under certain conditions the identified language does not only reproduce the system behavior observed so far (L n Ident ⊇ L n Obs ) but the complete original system language (L n Ident ⊇ L n Orig ). This property (which is not proved in [START_REF] Klein | Identification of Discrete Event Systems for Fault Detection Purposes[END_REF]) is very important for many model-based techniques relying on a complete system description. In the fol-

: X = {x|∀w ∈ W k Obs,Σ k : ∃!x|λ(x) := w, r(x) := {}} 2: ∀(x, x , w) ∈ X × X ×W k+1 Obs,Σ k |λ(x) = w[1, . . . , k]∧ λ(x ) = w[2, .., k + 1] : r(x) := r(x) ∪ x 3: x 0 = x ∈ X|λ(x) = w k and w k [i] = σ 1 (1)∀1 ≤ i ≤ k 4: ∀x ∈ X : λ(x) := λ(x)[|λ(x)|] 5: Merge x 1 , x 2 ∈ X with λ(x 1 ) = λ(x 2 ) and r(x 1 ) = r(x 2 )
lowing, the necessary conditions to proof the characteristic are given. The first step is to show that each state trajectory producing a word of length k ends in the same state. In the following, w k denotes a word of length k.

Lemma 1. In an NDAAO identified with parameter k each state trajectory λ(x(i), . . . ,

x(i + k -1)) = w k ∈ L k Ident |x( j + 1) ∈ r(x( j))∀i ≤ j < i + k -1 ends in the same state.
We define a function λ(x) delivering w k used in step 1 for each state of the algorithm. It represents the state output before it has been replaced by the I/O vector at the end of the word of length k representing the state output until step 3.

Proof of lemma 1. From equations 1 and 2 it follows that

∀w k ∈ L k Obs ∃v k 1 , . . . , v k k ∈ W k Obs,Σ k |v k 1 [k] = w k [1], v k 2 [k -1 . . . k] = w k [1 . . . 2], . . . , v k k [1 . . . k] = w k [1 . . . k].
From steps 1 and 2 of algorithm 1 it follows that states representing v k 1 , . . . ,

v k k are connected since ∀v k 1 , v k 2 ∃w k+1 ∈ W k+1 Obs,Σ k |w k+1 = v k 1 [1 . . . k]v k 2 [k]. Since step 1 assures that ∀w k ∈ L k Ident ∃!x| λ(x) = w k it follows that each state trajectory with λ(x(i), . . . , x(i + k -1)) = w k ∈ L k Ident |x( j + 1) ∈ r(x( j))∀i ≤ j < i + k -1 ends in the same state.
In the next theorem, it is stated that the identified language simulates the original system language of arbitrary length if L k+1 Orig = L k+1 Obs holds for a given value of the identification parameter k.

Theorem 1. If L k+1

Orig = L k+1 Obs , then L k+n Ident ⊇ L k+n Orig for an NDAAO identified with parameter k.

Proof of theorem 1. L k+1

Ident ⊇ L k+1 Orig since the identified NDAAO is k + 1 complete. For k + 2 it holds:

∀w k+2 ∈ L k+2 Orig ∃a k b 1 c 1 = d 1 e 1 f k = s 1 u k v 1 = w k+2 |a k b 1 , e 1 f k , u k v 1 ∈ L k+1 Orig = L k+1
Obs . Each state trajectory producing a k ends in the same state x 1 (lemma 1). In step 2 of the algorithm, this state is connected with x 2 | λ(x 2 ) = u k . Each state trajectory producing u k ends in the same state x 2 which gets connected to x 3 | λ(x 3 ) = f k . Since there is a trajectory leading to state x 1 and x 1 , x 2 and x 3 are in one trajectory, it follows that ∀w k+2 ∈ L k+2

Orig there exists a trajectory of states producing this word. For larger values than k + 2 ∀w k+n ∈ L k+n Orig there is always an appropriate decomposition into already observed substrings of L k+1 Orig = L k+1 Obs to find a trajectory of connected states like presented above. Hence, it follows that L k+n Ident ⊇ L k+n Orig if L k+1 Orig = L k+1 Obs holds.

Theorem 1 shows that it is crucial to state L k+1 Orig = L k+1

Obs for a precise k in order to deliver a model which is able to simulate the complete original system behavior. In section 3.2 it is shown how it can be decided if L k+1 Orig = L k+1 Obs holds for a given value of k.

APPLICATION

In order to show that the identification algorithm of section 4 is capable of delivering a model of existing systems that can be interpreted as closed-loop DES, one of the case studies we have treated will be presented in this section. The system depicted in figure 8 has 30 digital I/Os and is controlled by a Siemens PLC equipped with a communication processor. The system treats work pieces stored in the left most part of the facility. Each work piece is successively treated by the three tools. For identification a system evolution is defined as the run of two work pieces through the machine. Hence, there are at most two work pieces treated concurrently in the whole system.

Figure 8: Laboratory facility 50 system evolutions (treating 50 times two work pieces) have been performed and the according data has been collected using the procedure described in section 3. The observed word sets of different length are shown in figure 9. It can be seen that for small values of n like n = 2 or n = 3 the according observed word set and thus the observed language converges to a stable level which implies that the observed language converges to the original system language (L n=3 Obs ≈ L n=3 Orig ). Although for L 3 Obs there is a new word observed in one of the last evolutions, it can still reasonably be considered as completely observed. Hence, the precondition of theorem 1 is fulfilled. Since L n=3

Obs ≈ L n=3 Orig , it is possible to identify an NDAAO with k + 1 = n = 3 (→ k = 2) to simulate the original system behavior. For the identification of an NDAAO a software tool has been developed. Like depicted in figure 10, it takes the data base consisting of the observed system evolutions and the identification parameter k as input and applies algorithm 1. The software allows an analysis of the model structure (number of states, number of transitions etc.) and a behavioral analysis (see below). The identified model can be exported to an XML-file to use it in other tools such as diagnosis software [START_REF] Roth | An FDI method for manufacturing systems based on an identified model[END_REF]. To visualize the resulting automaton, an interface to GRAPHVIZ is provided. The identification of the NDAAO with k = 2 on the basis of 50 system evolutions took 170 ms on a standard PC with a 1.79 Ghz CPU and 1.96 GB RAM. The identified model has 121 states and 162 transitions. For the scenario with two controller inputs changing their value synchronously due to the data collection process (figure 4), the transition between states 93 and 54 is an example. Both inputs I2.2 and I3.2 change their value when taking this transition. The transition from state 48 to 49 is an example for the second sampling scenario (figure 5) where the change in value of an input triggers the change in value of an output. This transition represents the situation when the second work arrives at the entrance of the second station (position sensor connected to I2.4 changes its value) and the conveyor of this station is started (controller output O2.5 is set to 1). Both changes in value appear at one transition due to the data collection process as explained in section 3.1. An example for the third scenario form section 3.1 (figure 6) can be seen in the state trajectory x 48 → x 49 → x 50 . From state 48 to state 49 the conveyor is started (O2.5 1) to transport the work piece away from the entrance position (I2.5). Since it takes at least until the next PLC cycle to transport the work piece away from the sensor (I2.5 0 for the falling edge) cause and effect cannot be seen at once but at some successive transitions. The non-deterministic nature of the identified NDAAO can also be seen in figure 11: there are several ways to go from state 50 to state 55. Being in state 50 the choice of the trajectory is not determined but taken at random like in the closed-loop DES where unpredictable physical conditions in the plant lead to non-deterministic behavior. One of the important characteristics of the identified model is its capability to simulate the complete original system language (theorem 1). Even if only a subset of possible I/O vector sequences connecting the closed-loop system states represented by NDAAO states 50 and 55 has been observed, the model contains each possible trajectory that can occur when going from one state to the other as long as no new word of length k + 1 is produced. If L k+1 Orig = L k+1 Obs , the model is capable of exhibiting words of length k + n although these words have not been seen before. This capability comes at cost of also exhibiting words that have not and probably will not be observed (w k+n / ∈ L k+n Orig ). To get some information of the amount of words which are created without having been observed, the coefficient

C n B = |L n Ident | |L n
Obs | is a useful indicator. The presentation of the coefficient in figure 12 describes the relation between the identified and the observed language of an automaton identified with k = 2. For = k + 1, the model strictly creates the observed language L Obs . It can be seen that for larger values of n the automaton generates a larger language than L n Obs . A certain part of the additionally created words is probably not part of the original system language which may lead to a need for specific precautions in some model based techniques like diagnosis. However, from theorem 1 it is clear that each word with length n ≥ k + 1 of the original language not observed so far is part of the identified language. In the case of model based diagnosis for example, this allows stating that there will be no false alerts using the identified automaton as fault-free reference model [START_REF] Roth | An FDI method for manufacturing systems based on an identified model[END_REF].

CONCLUSION

In this paper practical implications of identification of closed-loop discrete event systems have been addressed. It has been shown how the necessary data can be obtained in the case of industrial closed-loop systems. For many model-based techniques it is crucial to have a model of the complete system behavior. For the identification algorithm of [START_REF] Klein | Identification of Discrete Event Systems for Fault Detection Purposes[END_REF] it has been proved that the identified automaton is simulates the original system language of arbitrary length if some conditions concerning the observed system language hold.

Figure 1 :

 1 Figure 1: Closed-loop Discrete Event system

Figure 2 :

 2 Figure 2: PLC cycle and data collection

Figure 3 :

 3 Figure 3: Validation of the UDP connection

Figure 4 :

 4 Figure 4: Sampling scenario 1

Figure 5 :

 5 Figure 5: Sampling scenario 2

Figure 6 :

 6 Figure 6: Sampling scenario 3

Figure 7 :

 7 Figure 7: Principle of a converging language

Algorithm 1

 1 Identification algorithmRequire: Parameter k, observed word sets W

Figure 9 :

 9 Figure 9: Observed word set for the laboratory system

Figure 10 :

 10 Figure 10: Features of the implemented software

Figure 11 :

 11 Figure 11: Part of the identified NDAAO

Figure 12 :

 12 Figure 12: Coefficient of identified and observed language

* This works was partially supported by a grant from Région Île-de-France


Alain Barrat
email: alain.barrat@cpt.univ-mrs.fr

Ciro Cattuto
email: ciro.cattuto@isi.it

Martin Szomszor

Wouter Van Den Broeck
email: wouter.vandenbroeck@isi.it

Harith Alani
email: h.alani@open.ac.uk

Social dynamics in conferences: analyses of data from the Live Social Semantics application

Popularity and spread of online social networking in recent years has given a great momentum to the study of dynamics and patterns of social interactions. However, these studies have often been confined to the online world, neglecting its interdependencies with the offline world. This is mainly due to the lack of real data that spans across this divide. The Live Social Semantics application is a novel platform that dissolves this divide, by collecting and integrating data about people from (a) their online social networks and tagging activities from popular social networking sites, (b) their publications and co-authorship networks from semantic repositories, and (c) their real-world face-to-face contacts with other attendees collected via a network of wearable active sensors. This paper investigates the data collected by this application during its deployment at three major conferences, where it was used by more than 400 people. Our analyses show the robustness of the patterns of contacts at various conferences, and the influence of various personal properties (e.g. seniority, conference attendance) on social networking patterns.

Introduction

Participation in online social networking has been growing at an unprecedented speed, with sites such as Facebook logging more than 400 million active users in only a few years since its birth. This new online phenomena is arming today's researchers in many disciplines with very rich and rapidly evolving social environment which is proving invaluable for the study and analyses of social dynamics, collective behaviour, community formation, etc.

Nevertheless, in spite of the surge in investigations of online social networks, these studies have largely overlooked the association of these networks with each other, and with the offline, real-world networks. Social networks, in all their shapes and forms, often reflect each other in a variety of ways. The lack of comparative analyses of such heterogenous networks is mainly due to the shortage of data that spans this onlineoffline divide. Additionally, to better inform the analyses of real-world face-to-face (F2F) contact networks, researchers need to take into account the already-existing social relationships between users. Existing relationships can have a high impact on the shape, dynamics, and strengths of interaction between the subjects. Such multi-relation analyses (called multiplexity in social networks [START_REF]To dwell among friends[END_REF][START_REF] Alani | Social Network Analysis: Methods and applications[END_REF]) remains underinvestigated [START_REF] Jm | Birds of a feather: Homophily in social networks[END_REF][START_REF] Trade | conflict and sentiments: multi-relational organization of largescale social networks[END_REF].

We have designed, developed, and deployed an application that bridges the divides between offline and online, and between real-time and historical social networks and relationships. This is achieved by integrating various heterogeneous and distributed networks. More specifically, Live Social Semantics (LSS) collects and integrates data about people from (a) their online social networks and tagging activities from popular social networking sites such as Facebook, Twitter, Flickr, and Last.fm (b) their publications and co-authorship networks from semantic repositories of publications, such as data.semanticweb.org and rkbexplorer.org, and (c) their real-world faceto-face (F2F) proximity, considered as a proxy for a social interaction, recorded with a network of wearable sensors (sociopatterns.org). To the best of our knowledge, this is the first time that an application is deployed that is capable of gathering and integrating this type of data.

Main contribution

The main contribution of this paper is the investigation of the data collected by the LSS application during its deployment at three major conferences (section 4), where it was used by more than 400 people. We analyse the data for contacts patterns and the impact of parameters such as seniority and role on these patterns. We also compare the networks from online social networking sites with those generated from real F2F contacts, as well as with co-authorship networks. More specifically, we investigate the following:

-Face-to-face interactions in scientific conferences (section 5.1): We start our analyses by looking for common statistical characteristics in the F2F interaction networks we collected from three scientific conferences. We focus our attention to F2F contacts frequency and duration and how they compare across all three conferences. -Networking behaviour of frequent users (sections 5.2). Here we focus our anaysis on users who participated in two LSS deployments (section 4). We measure the networking behaviour of these users quantitatively and qualitatively, and across conferences, in comparison to the behavior of other one-time users of LSS. -Scientific seniority of users (section 5.3). This analysis aims to study the impact of seniority on social activity. Seniority is approximated from (a) number or publications, (b) h-index, and (c) organisational roles at the conference where LSS was deployed. In this analysis we search for correlations between seniority of users and the seniority of their F2F contacts, as well as the general strength of their social network. We also compare scientific seniority of users to the number of their Twitter followers. -Comparison of F2F contact network with Twitter and Facebook (section 5.4):

We compare the size of F2F network of users to the size of their Facebook and/or Twitter social network. The idea is to see if there is a clear correlation between the two parameters; i.e whether people with strong online social presence are also very active in F2F networking and vice versa. -Social networking with online and offline friends (section 5.5): We analyse F2F contact networks while taking into account any co-authorship relationships between users, which we obtain from data.semanticweb.org, and any online social relationship, taken from Facebook or Twitter.

The purpose of our analyses is to provide novel insights into the comparability of online and offline networks, and to better understand the impact of specific drivers and parameters on the social contact behaviour of individuals and groups in scientific communities and gatherings. Such knowledge can feed into the design of better tools for supporting networking at conferences and at similar events. It can also be used for the identification of future scientific leaders and event organisers.

In the following section we describe some work related to monitoring live social interactions and to online network analysis. In section 3 we briefly describe the application and its main components, and then summarise the outcome of its deployments so far in section 4. Section 5 details the analyses we applied to our data collection and the main results obtained. Discussion and future work related to LSS and to our results is given in section 6, followed by conclusions in section 7.

Related Work

Using sensor devices for detecting contacts at conferences is not a novel idea by itself. IBM used RFIDs to track sessions and meal attendance at a conference [START_REF] Thibodeau | IBM uses RFID to track conference attendees[END_REF]. Bluetoothenabled mobiles were also used to track networking of conference attendees [START_REF] Hui | Pocket switched networks and human mobility in conference environments[END_REF] and for sensing organisational aspects [START_REF] Eagle | Reality mining: sensing complex social systems[END_REF]. Networks from blutoothed mobiles were also studied for characterising some statistical properties of human mobility and contact [START_REF] Scherrer | Description and simulation of dynamic mobility networks[END_REF]. Wu and colleagues used what they call "sociometric badges" to investigate impact of F2F interactions on productivity [START_REF] Wu | Mining face-to-face interaction networks using sociometric badges: Evidence predicting productivity in it configuration[END_REF]. These badges used radio frequency to detect physical proximity, infra red to detect F2F body alignments, and voice sensors to detect conversations. All these works focus on only one type of network which is based on proximity of users, irrespective of whether these users interacted with each other (e.g. had a F2F contact) or were already closely linked in other social contexts.

Recently, the SocioPatterns project (http://sociopatterns.org) developed an RFID platform that is scalable and attains reliable detection of F2F interactions [START_REF] Barrat | High resolution dynamical mapping of social interactions with active rfid[END_REF][START_REF] Cattuto | Dynamics of person-to-person interactions from distributed rfid sensor networks[END_REF]. They used this platform to investigate patterns of human contacts at various social gatherings [START_REF] Isella | What's in a crowd? analysis of face-to-face behavioral networks[END_REF]. The LSS application presented here leverage that platform to mine real-time social contacts. To the best of our knowledge, the Live Social Semantics application is the first where real-world F2F contacts are mashed up in real time with semantic data from on-line social networking systems.

Social scientists identify several parameters that influence and motivate social and communication networks, such as physical and digital proximity, social support and community belonging, and homophily; similarity of individuals [?]. Such parameters were the focus of many works on characterising social networks (e.g. [?,?,?]). However, such works are often limited to online social networks.

The novelty of the analyses we present in this paper resides in the integration of heterogeneous data sources for the analysis of social networks.

Live Social Semantics application

The Live Social Semantics (LSS) [START_REF] Alani | Live social semantics[END_REF][START_REF] Szomszor | Semantics, sensors, and the social web: The live social semantics experiments[END_REF] is an innovative application that tracks and supports social networking between conference attendees. The application integrates data and technologies from the Semantic Web, online social networks, and a F2F contact sensing platform. It helps researchers to find like-minded and influential researchers, to identify and meet people in their community of practice, and to capture and later retrace their real-world networking activities at conferences.

LSS integrates (a) the available wealth of linked semantic data, (b) the rich social data from existing major social networking systems, and (c) a physical-presence awareness infrastructure based on active radio-frequency identification (RFID).

Figure 1 shows the main components of LSS. At the center of this architecture is a 4Store5 triplestore for storing, integrating, and accessing the heterogenous data collected by LSS from various distributed resources. LSS gathers tagging and social networking information on registered users from selected sites (component 2 in Figure 1). This tagging data is then used by component 3 for building semantic user profiles, which applies a series of services (component 4) for filtering tags [START_REF] Szomszor | Correlating user profiles from multiple folksonomies[END_REF], disambiguating tags [START_REF] Garca-Silva | Preliminary results in tag disambiguation using dbpedia[END_REF], and associating them with semantics from DBpedia [START_REF] Szomszor | Semantics, sensors, and the social web: The live social semantics experiments[END_REF].

In [START_REF] Szomszor | Semantics, sensors, and the social web: The live social semantics experiments[END_REF], we focused on describing and evaluating the generation of semantic profiles of interest from the tags shared by LSS users on Delicious and Flickr. The evaluation demonstrated the relative high accuracy of 85% achieved by our fully automatic tag-to-URI association algorithm which maps every tag to a DBpedia URI.

Information on user's publications and co-authorship networks are collected from data.semanticweb.org and rkbexplorer.com. Co-authorship networks represent another type of social networking that LSS integrates with the networks it collects from online social networking sites and from F2F contact networks.

Real-world F2F interactions of conference attendees are mined using RFID hardware and software infrastructure developed by the SocioPatterns project [START_REF] Barrat | High resolution dynamical mapping of social interactions with active rfid[END_REF][START_REF] Cattuto | Dynamics of person-to-person interactions from distributed rfid sensor networks[END_REF]. The RFID platform is represented by component 5 in the architecture, and it is responsible for collecting and processing readings from active wearable RFIDs carried by the conference attendees who participated in using the LSS application. This information is periodically uploaded to the triple store via RDF/HTTP and integrated with the other data layers. Details of using RFID in LSS can be found in [START_REF] Broeck | The live social semantics application: a platform for integrating face-to-face proximity with on-line social networking[END_REF].

Data from LSS deployments

Live Social Semantics was deployed at three conferences. Below are some statistics on participation in each of these deployments.

Data Analyses and Results

Understanding the correlations between the characteristics of users who are linked in a social network is a long-standing problem in social sciences, ecology and epidemiology: a typical pattern, referred to as "assortative mixing", describes the tendency of nodes of a network (here, the users), to link to other nodes with similar properties.

In this section we describe a variety of analyses that we applied to the data we gathered from LSS deployments. In this analyses we take several parameters into account, such as degree and strength of F2F networks, size of online social networks, coauthorship relations, conference chairing roles, and scientific seniority of users. These analyses are aimed at identifying patterns, or testing and verifying various conceptions, on how people connect socially at conferences.

We start by showing the high similarity of the social networks we obtained from all three deployments. Therefore, to save space, we sometimes only report the results of applying our analysis to data from ESWC2010. However, the results for the other two conferences are quite similar.

Face-to-face interactions in scientific conferences

The aim of this analysis is to determine the statistical characteristics of F2F networks, and assess their uniformity across multiple conferences.

The Sociopatterns platform [START_REF] Cattuto | Dynamics of person-to-person interactions from distributed rfid sensor networks[END_REF] used by LSS enables the detection of F2F proximity of attendees wearing the RFID badges. The LSS architecture registers the contact events taking place within the range of our RFID readers, and stores this data in RDF in the LSS triplestore. The data is also stored as a network, allowing to build the aggregated contact network of the conference as follows: nodes represent individuals, and an edge is drawn between two nodes if at least one contact event took place between the corresponding attendees. Each edge is weighted by the number of contact events or the total duration spent in face to face proximity. For each node, the degree of a node (number of neighbours on the network) gives the number of different attendees with whom the user has been in contact, and the "strength" (sum of the weights of the links) is defined by the total time this person spent in F2F interaction with other attendees.

Tables 1 and2 give the main characteristics of the observed behavior of the participants in the three LSS deployments. The data show a very high level of uniformity across the three conferences, 2. Some characteristics of the aggregated network of contacts between participants. The degree of a user is the number of other users with whom s/he has had at least one contact. The weight of an edge between two users is given by the total time they have spent in F2F interaction.

More in detail, Table 1 shows that most contacts are very short, but that some very long contacts are also measured. In fact, the distributions of contact durations are broad, as also observed in other settings [START_REF] Cattuto | Dynamics of person-to-person interactions from distributed rfid sensor networks[END_REF][START_REF] Isella | What's in a crowd? analysis of face-to-face behavioral networks[END_REF]. Figure 2 shows that the distributions of total time spent in F2F interaction by two attendees, and of the number of contact events between two attendees, are also broad, and are very similar in all three conferences. Fig. 2. Probability distribution of (left) the total time spent in F2F interaction, and (right) the number of contact events, between two participants to the LSS deployments. The X-axis is the total time (left) and the number (right) of contact events, and the Y-axis gives the probability to observe such a value. Interestingly, the observed general behaviours across conferences are remarkably similar, both qualitatively and quantitatively, from the point of view of the contact durations and for what regards cumulated contacts between participants: The average contact durations and total time spent F2F by two individuals are very close, 6 and in fact, the whole statistical distributions can be superimposed, as shown in Figure 2.

Face-to-face networking behaviour of frequent attendees

The successive deployment of the LSS architecture at ESWC in 2009 and 2010 enables not only the comparison of the overall attendees behavior, as shown in the previous paragraphs, but also to focus on the persons who attended both deployments. These common participants turn out to be 33. It is thus interesting to investigate their characteristics, in order to understand if these participants are in some aspects different from the others.

Table 3 compares the main characteristics of the contacts between returning participants with the overall average characteristics. It highlights how the attendees who participated in LSS in both ESWC 2009 and ESWC 2010 conferences were much more active, in terms of F2F interactions, than those who used LSS only once.

We observe that the average number of distinct participants with whom returning attendees have interacted is larger. attendees (strength) is close to twice the interaction time averaged over all participants. This feature can be investigated in more details by measuring the average weight of a link between a returning attendee and any of his/her neighbours, or also between two returning attendees. We find that returning attendees have a larger average interaction time (212 seconds, against a global average of 141 seconds) and interact more frequently with their neighbours (4.3 contact event per edge, against 3.44 overall).

When focusing the analyses to only those interactions that took place between the returning attendees, Table 3 shows an even stronger effect, with an average total duration of interaction (link weight) of about 400 seconds. Interestingly, this strong difference in total interaction time comes mostly from a much larger number of contact events, while the average duration of a single contact event is only slightly larger for returning attendees. Overall, returning attendees interact more frequently and longer than average, especially among each other.

Stability of F2F interactions across conferences In section 5.1 we showed that the general statistical patterns of F2F networking are very similar across all three conferences where LSS was deployed. Then in section 5.2 we showed that frequent users have stronger F2F networks. Another interesting question is whether these common users show similar social-networking behaviour from one year to the next.

To this end, we study the correlation between the properties of individuals and of their links in the interaction network in 2009 and 2010. More precisely, we plot in Figure 3 for each individual the number of neighbours in 2010 versus the number of neighbours in 2009 (top). We also plot the total time spent in F2F interaction in 2010, versus the same quantity measured at ESWC2009 (middle plot). For the links observed in both 2009 and 2010, we also plot the weight in 2010 versus the weight in 2009 (bottom plot). The plots show a clear correlation pattern. More quantitatively, the Pearson correlation coefficients 7 are 0.37 for the degrees, 0.76 for the total time spent in interaction, and 0.75 for the link weights. What this implies is that although people interacted with a different set of people during these two conferences, the time they spent in these interactions was very similar. 7 The Pearson correlation coefficient between two variables is defined as the covariance of the two variables divided by the product of their standard deviations. It measures the correlation (linear dependence) between these two variables, and is comprised between -1 when the variables are perfectly anti-correlated and +1 when they are perfectly correlated. Since people's social behaviour seems to remain rather stable from one conference to the next, we can assume that they will show homogenous behaviour at other similar conferences, and that the typical changes in conference programs and events have little impact on the behaviour of attendees.

Scientific seniority and F2F network patterns

One interesting parameter to investigate in conference F2F networks is the scientific seniority of people. This section investigates this parameter and its influence on F2F networking dynamics.

We consider two different ways to quantify the scientific seniority se u of a user u: (i) the number of papers authored by an individual at semantic web related conferences, 8 and (ii) the h-index. 9 While the publication and citation patterns change from one community to the next, we are here dealing with scientists coming from the same community, so that these quantities are reasonable indicators of how senior a person is.

To quantitatively answer the question of whether people tend to only mix with their peers or not, we compute for each user u in the aggregated contact graph the average seniority of nearest neighbours

se u nn = 1 k u v∈V(u) se v (1)
where the sum is over the k u users with whom u has been in contact at the conference. We also compute the average seniority of the neighbours of users with seniority se se nn (se) = 1 |u/se u = se| u/seu=se se u nn .

(

) 2
The study of the F2F interaction patterns has however shown that not all contacts are equivalent. On the contrary, the amount of time spent by two users in F2F proximity is strongly heterogeneous (see Fig. 2). Since Eq. ( 1) performs an unweighted average of the seniority of all neighbours, we generalize it to take into account the contact diversity:

se u nn,w = 1 s u v∈V(u) w uv se v (3)
where w uv is the total time spent in F2F proximity by u and v, and s u = t∈V(u) w ut is the total time spent by u in F2F proximity with other users. We also consider for each user u the strongest link, and define se u nn,max as the seniority of the user v with whom the corresponding contacts took place.

Figure 4 displays the average seniority of the neighbours of users with seniority se, Eq. ( 2), as a function of the seniority se, measured as the number of papers authored by an individual. No clear pattern is observed if the unweighted average over all neighbours in the aggregated network, Eq. (1), is considered. The picture is different when the time spent in F2F interaction is considered in order to compute an average in which each neighbour is weighted by the time spent with him/her, as in Eq. ( 3). An assortative trend is then observed, which is even stronger if considering for each individual only the neighbour with whom the most time has been spent. Such procedures allow to filter out short encounters which are then given small importance, or completely ignored.

Our analyses unveils a clear assortative mixing behavior, in which people tend to mix with others with similar seniority levels. In other words, more senior individuals tend to spend more time with other senior individuals, and junior people are more likely to mix with their peers. Similar results are obtained when the h-index is considered as a measure of seniority. It is important to note that relying only on unweighted contacts, i.e., the only knowledge of who has met whom, would not have allowed to reveal this assortative mixing, and that information on the temporal aspects is crucial in this respect.

Conference chairing and F2F networks Another indicator of seniority is whether a person has taken a chairing role at the conference or not. Conference chairing and organisational roles were retrieved for all LSS users at ESWC2010 from data.semanticweb. org and used in this analysis. 2). Red squares show the weighted average Eq. ( 3), and green diamonds show the seniority of the neighbour with whom the strongest link is observed. 4. Some characteristics of the ESWC 2010 chairs, and of the links between chairs, compared with the overall averages. Table 4 explores this particular aspect of the relationship between "seniority" and social activity at the conference. Track chairs are indeed typically more senior. We observe that the chairs interact with more distinct people (larger average degree), and spend more time in F2F interaction (almost three times as much as a random participant). Moreover, the contact events between chairs tend to be longer, and edges between chairs in the aggregated network correspond to many contact events. The density of the subnetwork of chairs is also very large (80% of all possible encounters are observed, against 35% for the possible encounters between all participants). Scientific seniority and twitter followers A comparison between seniority and the number of followers on Twitter (i.e. number of Twitter users who follow the person in question) is given in Figure 5 for ESWC2010. It is interesting to see that of all LSS users, the most senior scientists are not the mostly followed on Twitter. Also, a number of less senior people in terms of h-index were followed by many Twitter users. It is worth noting that the first two peaks on the Twitter line in the figure belong to researchers with high visibility and who have taken on chairing responsibilities in other conferences conference events (sessions, tracks, workshops, etc.). The third peak belong to a developer in a semantic web company and not to a researcher (hence the zero h-index). In future work we will consider other parameters, such as user's Twitter activity levels and time since Twitter account was created. Comparison between people's scientific seniority and the number of people following them on Twitter. Y-axis is the h-index normalized by the maximum h-index among participants, or the number of Twitter followers, as well normalized by the maximum number of followers observed, and X-axis is the 55 people who gave LSS their Twitter accounts during ESWC2010, ranked in decreasing order of h-index.

Characteristics

What these results show is that the number of Twitter followers is not necessarily a good indication of pure seniority in the context of scientific communities, but rather it is a reflection of popularity of individuals and of the work they do (more in section 6).

Face-to-face interactions and size of online social networks

Figure 6 shows the average amount of F2F networking of participants during ESWC 2010, alongside the size of their online social networks from Facebook and/or Twitter (followers and followees). The figure does not show any strong correlation between these two parameters. In other words, people who were active in F2F contacts do not necessarily have the largest online social networks, and vice versa. Note that these online networks include people who were not present at the conference, or who were present but did not participate in LSS. These online networks also include people from outside the research community (e.g. family, friends, or even spam). The figure also shows a large discrepancy for some of those with low degree of F2F contacts. In a closer look at the data, we found that these readings belong to people who were not researchers in the semantic web field, but were nevertheless present at the conference. It is therefore reasonable to expect these people not to know many of the attendees, which limited their social interactions at the conference.

Social networking with online and offline "friends"

A social relationship between two individuals can be defined from different points of view. They can be friends, colleagues, co-workers, and the relationship can exist in real life and/or in online social networking sites. The concept of multiplexity refers to the extent to which multiple ties coexist between the same persons. The LSS platform offers an interesting way to crosslink data concerning on the one hand real life interactions taking place on short times and on the other hand professional or online social links.

We focus here on the ESWC 2010 deployment, although the other deployments give very similar results.

Among the participants to the ESWC 2010 deployment, 26 links of co-authorship are found, together with 194 links of Facebook friendship, and 112 pairs in which at least one individual follows the other on Twitter. Table 5 gives the average contact characteristics for pairs of LSS users who share a social relationship either at a professional level or online. The average duration of a contact is much larger than for a random pair of attendees, but remains of the same order of magnitude.

The total time spent in F2F interaction is instead much larger, due to the fact that individuals sharing an online or professional social link meet much more often than other individuals. Moreover, while the two different online social networks give very similar results, the average number of encounters -and total time spent in interaction-is highest for co-authors. 6 Discussion and Future Work

The analyses we report in this paper is based on data from three conferences. When we closely compared the list of users of HT2009 with those of ESWC2009 and ESWC2010, it was clear that there was negligible overlap between these users lists. For this reason, some of our analyses that required common users was limited to ESWC data only. However, in our analyses we showed that behaviour in F2F networking of groups and of individuals is very similarly from one conference to the other (sections 5.1 and 5.2).

Our data is naturally sparse, since not all conference attendees participated in LSS, and not all users of one LSS deployment attended, or participated in other LSS deployments. Also, for some deployments, many F2F contacts were taking place outside the perimeters of our RFID readers (e.g. at the bar, during meals), and therefore could not be logged by LSS. However, we believe that the patterns we identified were strong enough in spite of this data sparsity. To overcome this problem, SocioPatterns.org is currently developing RFID with on-board memory, thus enabling F2F contacts to be logged regardless of distance to RFID readers.

As we report in this paper, there are often many parameters and types of relationships that influence social networks and their analyses. In this paper we focused our analyses on a number of such parameters, and our results are based on the network data we gathered from LSS deployments. Such data however, might contain some bias, caused by that data's inherited limitation to only those users who registered to use LSS, and to only those conferences where LSS was deployed. Other parameters can be taken into account in future deployments and analyses, such as users' affiliations, and project membership (e.g. from rkbexplorer.org). Deploying LSS at non-computer science conferences will also help to widen the scope of our analyses.

Chronology of social relationships could be taken into account when analyzing social networks, to investigate the influence of existing relationships between users on the dynamics of their networks. Some temporal relationships can be obtained from further LSS deployments over longer periods of time, where F2F, and online social networks can be monitored more frequently, and compared with each other over time.

Additionally, we currently do not consider when an online social networking account was set up, or whether the owner is an active user of these accounts or not. Such information can strengthen the analyses of these networks. We are currently building models and tools for generating rich user profiles that can acquire and represent user's activities in various social networking systems. Such profiles can then be analysed to identify usage and social behaviour, influence, trends, and interests.

With respect to estimating scientific seniority of LSS users, we relied on the number of their papers, their h-index, and their chairing roles at the conferences where LSS was deployed (section 5.3). Other features could be taken into account, such as their chairing roles in other previous conferences, or their overall number of publications. However, based on our knowledge of who's who in the semantic web community, we find that the seniority results from our approaches were very realistic approximations.

Linked Data resources such as data.semanticweb.org and rkbexplorer. org proved invaluable for this work. We used these resources for obtaining information on publications, co-authorships, chairing roles at various conferences, etc. Such initiatives should be supported and extended further, emphasizing quality as well as quantity of the data they store.

Work on LSS so far has concentrated on building the platform and website. Future work will instead focus on providing users with added-value services that use the collected data and analyses results to, for example, recommend new contacts to add to online social networks, to meet or collaborate with certain users F2F, attend specific talks, etc.

Conclusions

Data from LSS gave us the opportunity to analyse and compare various types of online as well as offline social networks for conference attendees, and to better understand their characteristics, dynamics, and dependencies. Below we summarize the main finding from our analyses:

-Statistical properties of the F2F social contact patterns were very similar across all three conferences. (section 5.1). -Frequent conference attendees (i.e. used LSS in more than one conference) were more socially active in F2F networking than others, with %22 more F2F interactions and %50 more interaction time than other users (section 5.2). -Time spent on F2F networking by frequent conference attendees remained stable, even though the list of people they networked with change (section 5.2). -Conference attendees tend to networks with others of similar levels of scientific seniority. We also show that conference chairs meet more people and spend 3 times as much time in F2F networking than other users (section 5.3). -People who have the highest number of Twitter follower are not necessarily the most senior in terms of their h-index, although they have high visibility, popularity, and experience (section 5.3). -No visible correlation is found between size of online social networks of users in Facebook and Twitter and the number of people they met face to face (section 5.4). -People's F2F contacts with their Facebook friends and Twitter mutual followers were respectively %50 and %71 longer, and %286 and %315 more frequent than with others. They have also spent %79 more time in F2F contacts with the people they co-authored papers with, and they met them %1680 more times than they met non co-authors (section 5.5).

Fig. 1 .

 1 Fig. 1. General architecture of LSS application. A triple store is the central point of integration for all LSS components.

Fig. 3 .

 3 Fig.3. Correlation between the characteristics of a returning attendee in 2009 and 2010. The X-axis gives the value of the charateristics of an attendee measured in 2009, and the Y-axis gives the value of the same characteristics measured in 2010. Black circles: degree, giving the number of other participants with whom an attendee has interacted. Red squares: total time spent in interaction by an attendee. Green diamonds: total time spent in F2F interaction by a pair of returning attendees in 2010, versus the same quantity measured in 2009.

Fig. 4 .

 4 Fig.[START_REF] Barrat | High resolution dynamical mapping of social interactions with active rfid[END_REF]. Average seniority of the neighbours of a user, versus the user's own seniority. Black circles correspond to an unweighted average over all neighbours, Eqs. (1) and (2). Red squares show the weighted average Eq. (3), and green diamonds show the seniority of the neighbour with whom the strongest link is observed.

  Fig.5. Comparison between people's scientific seniority and the number of people following them on Twitter. Y-axis is the h-index normalized by the maximum h-index among participants, or the number of Twitter followers, as well normalized by the maximum number of followers observed, and X-axis is the 55 people who gave LSS their Twitter accounts during ESWC2010, ranked in decreasing order of h-index.

Fig. 6 .

 6 Fig.6. X-axis shows the LSS users who declared their Facebook and/or Twitter accounts during ESWC2010 deployment. The Y-axis shows the total size of their online social networks, normalized by the maximal size observed, and the degree in the F2F interaction network of ESWC2010, divided by the maximum degree. There is no strong correlation between the amount of F2F contact activity and the size of online social networks. In other words, it appears that people who have a large number of friends on Twitter and/or Facebook are not necessarily the most socially active in the offline world.

Table 1 .

 1 Some characteristics of the contact events between LSS participants during three conferences. The F2F contact pattern is very similar for all three conferences.

	Contact characteristics ESWC 2009 HT 2009 ESWC 2010
	Number of contact events	16258	9875	14671
	Average contact length (s)	46	42	42
	Fraction of contacts ≤ 1 mn	0.87	0.89	0.88
	Fraction of contacts ≤ 2 mn	0.94	0.96	0.95
	Fraction of contacts ≤ 5 mn	0.99	0.99	0.99
	Fraction of contacts ≤ 10 mn	0.998	0.998	0.998
	Network characteristics ESWC 2009 HT 2009 ESWC 2010
	Number of users	175	113	158
	Average degree	54	39	55
	Average strength (s)	8590	7374	7807
	Average edge weight (s)	159	189	141
	Fraction of weights ≤ 1 mn	0.7	0.67	0.74
	Fraction of weights ≤ 5 mn	0.9	0.89	0.93
	Fraction of weights ≤ 10 mn	0.95	0.94	0.96
	Table

Table 3 .

 3 The total time spent in F2F proximity with other Average characteristics in each year of the participants to both ESWC 2009 and ESWC 2010, and of the contact patterns between these returning participants, as compared to the average over all participants.

	Characteristics	all participants,	all participants,	common partici-	common partici-
		2009	2010	pants, 2009	pants, 2010
	Average degree	55	54	73	62
	Average strength	8590	7807	16426	13216
	Average weight	159	141	416	404
	Average contact dura-	46	42	52	57
	tion in seconds
	Average number of	3.44	3.37	8	7
	contact events per edge

Table 5 .

 5 F2F contact characteristics between (i) all LSS users, (ii) LSS users who are coauthors, (iii) LSS users who are friends on Facebook, and (iv) pairs of users who are linked on Twitter.

	Characteristics	all participants coauthors	FB	Twitter
	average contact duration (s) 42	75	63	72
	average edge weight (s)	141	4470	830	1010
	average number of events	3.37	60	13	14
	per edge

http://4store.org/

Note that since the distributions are broad, the precise value of the averages is rather sensitive to rare events in the distribution tail.

Number of papers is obtained from data.semanticweb.org and is therefore limited to the conferences metadata available in this repository. However, these numbers give a good approximation of seniority for the attendees of the conferences in question.

From scholarometer http://scholarometer.indiana.edu/