Mathieu Génois

Christian L Vestergaard

Ciro Cattuto

Alain Barrat

Compensating for population sampling in simulations of epidemic spread on temporal contact networks

Data describing human interactions often suffer from incomplete sampling of the underlying population. As a consequence, the study of contagion processes using data-driven models can lead to a severe underestimation of the epidemic risk. Here we present a systematic method to correct this bias and obtain an accurate estimation of the risk in the context of epidemic models informed by high-resolution time-resolved contact data. We consider several such data sets collected in various contexts and perform controlled resampling experiments. We show that the statistical information contained in the resampled data allows us to build surrogate versions of the unknown contacts and that simulations of epidemic processes using these surrogate data sets yield good estimates of the outcome of simulations performed using the complete data set. We discuss limitations and potential improvements of our method.

Human interactions play an important role in determining the potential transmission routes of infectious diseases and other contagion phenomena [START_REF] Barrat | Dynamical processes on complex networks[END_REF]. Their measure and characterisation thus represent an invaluable contribution notably to the study of transmissible diseases [START_REF] Read | Close encounters of the infectious kind: methods to measure social mixing behaviour[END_REF]. In this context, the use of surveys and diaries in which volunteer participants record their encounters [START_REF] Edmunds | Who mixes with whom? a method to determine the contact patterns of adults that may lead to the spread of airborne infections[END_REF][START_REF] Read | Dynamic social networks and the implications for the spread of infectious disease[END_REF][START_REF] Mossong | Social contacts and mixing patterns relevant to the spread of infectious diseases[END_REF][START_REF] Mikolajczyk | Social contacts of school children and the transmission of respiratory-spread pathogens[END_REF][START_REF] Danon | Social encounter networks: collective properties and disease transmission[END_REF][START_REF] Danon | Social encounter networks: characterizing great britain[END_REF] have provided crucial insight, despite the memory biases inherent in self-reporting procedures [START_REF] Read | Dynamic social networks and the implications for the spread of infectious disease[END_REF][START_REF] Smieszek | Collecting close-contact social mixing data with contact diaries: reporting errors and biases[END_REF][START_REF] Smieszek | How should social mixing be measured: comparing web-based survey and sensor-based methods[END_REF]. Moreover, new approaches have emerged to measure contact patterns between individuals, using wearable sensors that can detect the proximity of other similar devices [START_REF] Hui | Pocket switched networks and human mobility in conference environments[END_REF][START_REF] O'neill | Instrumenting the city: Developing methods for observing and understanding the digital cityscape[END_REF][START_REF] Eagle | Inferring friendship network structure by using mobile phone data[END_REF][START_REF] Vu | Joint bluetooth/wifi scanning framework for characterizing and leveraging people movement in university campus[END_REF][START_REF] Salathé | A high-resolution human contact network for infectious disease transmission[END_REF][START_REF] Hashemian | Flunet: Automated tracking of contacts during flu season[END_REF][17][START_REF] Cattuto | Dynamics of person-to-person interactions from distributed RFID sensor networks[END_REF][START_REF] Hornbeck | Using sensor networks to study the effect of peripatetic healthcare workers on the spread of hospital-associated infections[END_REF][START_REF] Stopczynski | Measuring large-scale social networks with high resolution[END_REF]. Data gathering efforts have produced data sets describing the contact patterns between individuals in various contexts in the form of temporal networks [START_REF] Salathé | A high-resolution human contact network for infectious disease transmission[END_REF]17,[START_REF] Isella | What's in a crowd? Analysis of face-toface behavioral networks[END_REF][START_REF] Stehlé | Simulation of an SEIR infectious disease model on the dynamic contact network of conference attendees[END_REF][START_REF] Stehlé | High-resolution measurements of face-toface contact patterns in a primary school[END_REF][START_REF] Fournet | Contact patterns among high school students[END_REF]: nodes represent individuals and, at each time step, a link is drawn between pairs of individuals who are in contact [START_REF] Holme | Temporal networks[END_REF]. Such data can inform models of epidemic spreading phenomena to evaluate epidemic risks and mitigation strategies [START_REF] Salathé | A high-resolution human contact network for infectious disease transmission[END_REF][START_REF] Stehlé | Simulation of an SEIR infectious disease model on the dynamic contact network of conference attendees[END_REF][START_REF] Lee | Exploiting temporal network structures of human interaction to effectively immunize populations[END_REF][START_REF] Machens | An infectious disease model on empirical networks of human contact: bridging the gap between dynamic network data and contact matrices[END_REF][START_REF] Starnini | Immunization strategies for epidemic processes in time-varying contact networks[END_REF][START_REF] Smieszek | A low-cost method to assess the epidemiological importance of individuals in controlling infectious disease outbreaks[END_REF][START_REF] Masuda | Predicting and controlling infectious disease epidemics using temporal networks[END_REF][START_REF] Gemmetto | Mitigation of infectious disease at school: targeted class closure vs school closure[END_REF].

However, most data sets suffer from population sampling: despite efforts to maximise participation, for instance through scientific engagement of participants [START_REF] Fournet | Contact patterns among high school students[END_REF][START_REF] Conlan | Measuring social networks in british primary schools through scientific engagement[END_REF], not all individuals accept to participate. Hence, the collected data only contains information on contacts occurring among a fraction of the population under study.

Population sampling is known to affect the properties of static networks [START_REF] Granovetter | Network sampling: Some first steps[END_REF][START_REF] Frank | Sampling and estimation in large social networks[END_REF]: Various statistical properties of a sampled network may differ from those of the complete system under scrutiny [START_REF] Kossinets | Effects of missing data in social networks[END_REF], and several works have focused on inferring network statistics from the knowledge of incomplete, sampled network data [START_REF] Viger | What is the real size of a sampled network? the case of the Internet[END_REF][START_REF] Bliss | Estimation of global network statistics from incomplete data[END_REF][START_REF] Zhang | Estimating Network Degree Distributions Under Sampling: An Inverse Problem, with Applications to Monitoring Social Media Networks[END_REF][START_REF] Cimini | Systemic risk analysis in reconstructed economic and financial networks[END_REF]. Both structural and temporal properties of time-varying networks are as well affected by sampling effects.

In addition, a crucial though poorly studied consequence of population sampling is that simulations of dynamical processes in data-driven models can be affected. For instance, in simulations of epidemic spreading, ex-cluded nodes are by definition unreachable and thus equivalent to immunised nodes. Due to herd vaccination effects, the outcome of simulations of epidemic models on sampled networks is thus underestimated. How to estimate the outcome of dynamical processes on contact networks using incomplete data remains an open question.

Here we tackle this issue for incompletely sampled data describing networks of human face-to-face interactions. We do not aim at inferring the true sequence of missing contacts but at estimating the outcome of simulations of models of epidemic spread in the whole population. To this effect, we resample available data sets by excluding at random a fraction of the individuals (nodes of the contact network), measure how resampling affects relevant network statistics and show that some crucial properties are stable under resampling. We exploit this stability to present a systematic method to construct surrogate contact sequences for the excluded nodes, using only information available in the resampled data. We show that the outcome of simulations performed on the reconstructed data sets, obtained by the union of the resampled and surrogate contacts, reproduces results obtained on the complete data set, while using only the resampled data severely underestimates the epidemic risk. We show the efficiency of our procedure for data collected in three widely different contexts: a conference, a high school and a workplace.

RESULTS

Data & Methodology

We consider data sets describing contacts between individuals, collected by the SocioPatterns collaboration [17] in three different settings: an office building ("InVS") [START_REF] Génois | Data on face-to-face contacts in an office building suggests a low-cost vaccination strategy based on community linkers[END_REF], a high school ("Thiers13") [START_REF] Fournet | Contact patterns among high school students[END_REF] and a scientific con-ference ("SFHH") [START_REF] Isella | What's in a crowd? Analysis of face-toface behavioral networks[END_REF][START_REF] Stehlé | Simulation of an SEIR infectious disease model on the dynamic contact network of conference attendees[END_REF]. These data correspond to the close face-to-face proximity of individuals equipped with wearable sensors, at a temporal resolution of 20 seconds [17,[START_REF] Cattuto | Dynamics of person-to-person interactions from distributed RFID sensor networks[END_REF]. Table I summarises the characteristics of each data set. The contact data are represented by temporal networks, in which nodes represent the participating individuals and a link between two nodes i and j at time t indicates that the two corresponding persons were in contact at that time. Moreover, the InVS and Thiers13 populations were structured in departments and classes, respectively (see Methods).

To understand how sampling affects the properties of the temporal networks, the outcome of simulations of dynamical processes, and, ultimately, how to compensate for these effects, we consider as ground truth the available data 1 and perform population resampling experiments by removing a fraction f of the nodes uniformly at random. We explore how several characteristics of the temporal networks depend on f and how the outcome of numerical simulations of epidemic spread is biased by such resampling. We then present a method for constructing surrogate data using only information contained in the resampled data and show that it allows us to obtain a good estimate of the outcome of processes simulated on the complete data set.

Specifically, we consider the Susceptible-Infectious-Recovered (SIR) and the Susceptible-Infectious-Susceptible (SIS) models of epidemic propagation. In these models, a susceptible (S) node becomes infectious (I) at rate β when in contact with an infectious node. Infectious nodes recover spontaneously at rate µ. In the SIR model, nodes then enter an immune recovered (R) state, while in the SIS model, nodes become susceptible again and can thus be reinfected.

The quantities of interest are for the SIR model the distribution of epidemic sizes, defined as the final fraction of recovered nodes, and for the SIS model the average fraction of infectious nodes i ∞ in the stationary state. We also calculate for the SIR model the fraction of epidemics that infect more than 20% of the population and the average size of these epidemics. For the SIS model, we determine the epidemic threshold β c for different values of µ: it corresponds to the value of β that separates an epidemic-free state (i ∞ = 0) for β < β c from an endemic state (i ∞ > 0) for β > β c , and is thus an important indicator of the epidemic risk. We refer to the Methods section for further details on models and simulations.

To validate our method, we compare for each data set the outcomes of simulations performed (i) on the whole data set, (ii) on resampled data sets with a varying fraction of nodes removed, f , and (iii) on reconstructed data sets built to compensate for sampling effects.

Resampled contact networks

Sampling affects the various properties of contact networks in different ways. The number of neighbours of a node decreases as the fraction f of removed nodes increases (Supplementary Fig. S1) since removing nodes also removes links to these nodes. On the contrary, the density of the resampled aggregated network, defined as the number of links divided by the total number of possible links between the nodes, remains stable (Supplementary Fig. S2).

We moreover show in Supplementary Figs. S2-S4 that the group structure of a population, as summarised by contact matrices, is well preserved under resampling. Contact matrices give a measure of the interaction between groups (here classes or departments). Here we consider the link density matrix, where the element (i, j) is given by the number of links between individuals of groups i and j in the aggregated contact network, normalised by the total number of possible links between these two groups2 . Table II and Supplementary Fig. S2 show that the similarities between the original and sampled matrices are high for all data sets (see Supplementary Figs. S3-S4 for the contact matrices themselves).

Finally, the temporal statistics of the contact network are not affected by population sampling, as already noted in [START_REF] Cattuto | Dynamics of person-to-person interactions from distributed RFID sensor networks[END_REF] for other data sets: the distributions of contact durations, of inter-contact durations, of number of contacts per link and of cumulated contact durations (i.e., of the link weights in the aggregated network) do not change when the network is sampled (Supplementary Fig. S1).

Despite the robustness of these properties under sampling, the outcome of simulations of epidemic spread is strongly affected by the resampling (Figs. 1 and2). In particular, for large values of f , the probability of large outbreaks in the SIR model vanishes (Fig. 1). As mentioned above, the reason is that the removed nodes act as if they were immunised: sampling hinders the propagation by removing transmission routes between the remaining nodes. As a result, the prevalence and the final size of the outbreaks are systematically underestimated by simulations of the SIR model on the resampled network with respect to simulations on the whole data set (Fig. 1), and the epidemic threshold of the SIS model is overestimated (Fig. 2): resampling leads to a systematic underestimation of the epidemic risk.

Estimation of epidemic sizes through simulations on reconstructed temporal networks

We now develop a method able to compensate for the bias due to population sampling in the simulations of epidemic spread. To this aim, we use only information measured in the resampled network that has been shown above to be robust under resampling, namely the density of the aggregated contact network, the contact matrices of link density and the distributions of number of contacts per link and of contact and inter-contact durations. We assume that the number of missing nodes in each group is known, as well as the timelines of scheduled activity (nights and weekends, during which no contact occurs).

For each data set, considered as ground truth, we create resampled data sets by removing at random a fraction f of the N nodes. We measure on each resampled data set the contact network density, the contact matrix of link densities between groups (for the structured population cases) as well as the distributions mentioned above. We then construct stochastic, surrogate versions of the missing part of the network, as described in detail in the Methods section: We create for each missing node a surrogate instance of its links, in a way to keep the density of the network and the density of links between groups of nodes fixed (equal to the value measured in the resampled data); we then create a synthetic timeline of contacts on each surrogate link, extracted at random from the measured distributions. The statistical properties of the resulting reconstructed (surrogate) networks, obtained by the union of the resampled data and of the surrogate links, are similar to the ones of the original data (Table II and Supplementary Figs. S5-S10). In particular, the method conserves the distribution of link weights (W), the group structure (S), and the temporal (T) characteristics of individual links; we thus refer to it in the following as the WST method. We emphasise that our aim is not to infer the true missing contacts, and we do not compare the detailed structures of the surrogate and original contact networks. Instead, we simply aim at obtaining a surrogate version of these contacts, such that the resulting simulations of epidemic spread yield outcomes close to the ones obtained when the whole data set is used.

Figure 1 shows that the distribution of final epidemic sizes for the SIR model on surrogate networks is much closer to those obtained by simulating on the whole data set than for the simulations performed on the resampled networks. Instead of a severe underestimation of epidemic sizes, we obtain a slight overestimation. We quantify this result in Fig. 3 where we display the fraction of outbreaks that reach at least 20 % of the population and the average epidemic size for these outbreaks, for simulations performed on either resampled or surrogate networks. In the case of resampled data, we rapidly lose information about the size and even the existence of large outbreaks, whereas this crucial information is well recovered when using surrogate networks, even when a large fraction of nodes are removed. We show in the Supplementary Information that similar results are obtained for different values of the spreading parameters. Moreover, as shown in Fig. 2 and Supplementary Figs. S11-S12, the phase diagram obtained for the SIS model when us-ing reconstructed networks is much closer to the original than for resampled networks, in particular concerning the value of the epidemic threshold. Overall, simulations using the reconstructed network yield a much better estimation of the epidemic risk than simulations using resampled network data, for both SIS and SIR models.

When the fraction f of nodes excluded by the resampling procedure becomes large, the properties of the resampled data may start to differ substantially from those of the whole data set (Figs. S1 &S2). As a result, the distributions of epidemic sizes of SIR simulations deviate from those obtained on the whole data set (Fig. 4), even if the epidemic risk evaluation is still better than for simulations on the resampled networks. Most importantly however, the information remaining in the resampled data at large f can be insufficient to construct surrogate contacts. This happens in particular if an entire class or department is absent from the resampled data or if all the resampled nodes of a class/department are disconnected (see Supplementary Information for details). We investigate this limitation in the bottom plots of Fig. 3 by showing the failure rate, i.e., the fraction of cases in which we are not able to construct surrogate networks from the resampled data. The failure rate increases gradually with f for the InVS data since the groups (departments) are of different sizes. For the Thiers13 data, all classes are of similar sizes so that the failure rate reaches abruptly a large value at a given value of f . For the SFHH data, we can always construct surrogate networks as the population is not structured.

Reconstruction methods using partial information

A natural question concerns how much information is needed to build the surrogate networks. The WST method uses the contact matrix of link densities and the distributions of contact durations, inter-contact durations and numbers of contacts per link. We investigate here three alternative procedures that use less information, still only computed from the resampled data:

• W: we construct surrogate networks that conserve the overall link density and the distribution of weights found in the resampled data. The group structure (S) and temporal characteristics (T) of contacts are not conserved.

• WS: in addition to the W construction, we here use the contact matrix of link densities to conserve the group structure (S) of the network.

• WT: we construct the surrogate links as in the W method, without taking into account the link density contact matrix (S), but with contact timelines on each surrogate link that conserve the temporal characteristics (T) of the individual links.

Details of these methods are given in the Supplementary Information.

The results of SIR simulations performed on the resulting surrogate networks are shown in Fig. 3. All three methods using partial information lead to a larger overestimation of the epidemic risk than the WST method. The W method consistently gives the worst results, as infections spread easier on random homogeneous graphs than on structured graphs [START_REF] Onnela | Structure and tie strengths in mobile communication networks[END_REF][START_REF] Karsai | Small but slow world: How network topology and burstiness slow down spreading[END_REF]. Taking into account the population structure yields slightly better results (WS case), while using realistic contact sequences (i.e., taking into account the heterogeneity of contact numbers and durations and the burstiness of contacts) has an even stronger effect (WT). Overall, surrogate networks that respect all these constraints (WST) yield the best results.

DISCUSSION

The understanding of epidemic spreading phenomena have been vastly improved thanks to the use of datadriven models. In the case of contact data, population sampling represents however a serious issue: individuals absent from a data set have the same role as immunised individuals when epidemic processes are simulated. Feeding sampled data into data-driven models can therefore lead to severe underestimations of the epidemic risk and might even a priori affect the evaluation of mitigation strategies.

Here we have put forward a systematic method to compensate for such underestimation in simulations performed using sampled contact data and to obtain a good estimate of the epidemic risk in the entire population, as measured by the distribution of outbreak sizes and by the epidemic threshold. To this aim, we have shown how it is possible, starting from a data set describing the contacts of only a fraction of the population of interest, to construct a surrogate data set that uses only accessible information, i.e., quantities measured in the sampled data: the contact network density, the densities of links between groups in a structured population, and the distributions of numbers and durations of contacts and of inter-contact durations. Simulations of epidemic spreading on such surrogate data yield results similar to those obtained on the complete data set, albeit with a small overestimation of the risk (which, from a public health point of view, is much better than a large underestimation).

Strikingly, the method presented here yields good results even when a substantial part of the population is excluded, in particular in estimating the probability of large outbreaks. It has however two limitations when the fraction f of excluded individuals is too large. First, the construction of the surrogate contacts relies on the stability of a set of quantities with respect to resampling, but the measured quantities start to deviate from the original ones at large f . The shape of the distribution of epidemic sizes may then deviate substantially from the original one. Second, large values of f might even render the construction of the surrogate data impossible due to the loss of information on whole categories of nodes.

Another important point concerns the issue of how much information should be included when constructing the surrogate data. It is linked to the general issue of how much information is needed to get an accurate picture of spreading processes on temporal networks [START_REF] Stehlé | Simulation of an SEIR infectious disease model on the dynamic contact network of conference attendees[END_REF][START_REF] Machens | An infectious disease model on empirical networks of human contact: bridging the gap between dynamic network data and contact matrices[END_REF][START_REF] Smieszek | A low-cost method to assess the epidemiological importance of individuals in controlling infectious disease outbreaks[END_REF][START_REF] Blower | The importance of including dynamic social networks when modeling epidemics of airborne infections: does increasing complexity increase accuracy?[END_REF][START_REF] Pfitzner | Betweenness preference: Quantifying correlations in the topological dynamics of temporal networks[END_REF]. On the one hand, we have shown that using less information to build the surrogate data yields worse results. On the other hand, the surrogate contacts do not take into account any correlations between structure and activity in the temporal contact network, which are known to influence spreading processes [START_REF] Isella | What's in a crowd? Analysis of face-toface behavioral networks[END_REF][START_REF] Karsai | Small but slow world: How network topology and burstiness slow down spreading[END_REF][START_REF] Pfitzner | Betweenness preference: Quantifying correlations in the topological dynamics of temporal networks[END_REF][START_REF] Gauvin | Activity clocks: spreading dynamics on temporal networks of human contact[END_REF][START_REF] Scholtes | Causality-driven slow-down and speedup of diffusion in non-markovian temporal networks[END_REF][START_REF] Gauvin | Revealing latent factors of temporal networks for mesoscale intervention in epidemic spread[END_REF]. This might be the cause of the systematic overestimation of the epidemic sizes in simulations using reconstructed data (Figs. 1 and3). From this point of view, our method could be improved by integrating into the surrogate data complex correlation patterns measured in the sampled data. It might for instance be possible to use the temporal network decomposition technique put forward in [START_REF] Gauvin | Revealing latent factors of temporal networks for mesoscale intervention in epidemic spread[END_REF][START_REF] Gauvin | Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach[END_REF] on the sampled data, in order to extract mesostructures such as temporally-localized mixing patterns. The surrogate contacts could then be built in a way to preserve such patterns.

Finally, we have considered uniform sampling of nodes, corresponding to data collection in a population with a participation rate smaller than 100%. It would be interesting to consider as well other types of data losses, due for instance to a partial coverage of the premises of interest by the measuring infrastructure [17]. Moreover, the population under study is (usually) not isolated from the external world, and it would be important to devise ways to include contacts with outsiders in the data and simulations, for instance by using other data sources such as surveys. processed the data. M.G., C.L.V. and A.B. analyzed the data, carried out computer simulations and prepared the figures. M.G., C.L.V., A.B., and C.C. wrote the manuscript.

METHODS

Data

Two of the data sets used in our study -the high school (Thiers13) and the office building (InVS) -are structured in groups corresponding respectively to classes and departments. For the conference data (SFHH), we instead do not have metadata on the participants, and it has been shown in [START_REF] Stehlé | Simulation of an SEIR infectious disease model on the dynamic contact network of conference attendees[END_REF] that the aggregated network structure was homogeneous.

The high school is structured in 9 classes, which form three subgroups of three classes corresponding to their specialisation in Mathematics-Physics (MP, MP *

SIR simulations

In the SIR model, all nodes are initially susceptible, except one infectious node, the seed of the epidemic. A susceptible node in contact with an infectious node becomes infectious at rate β. Infectious nodes enter the recovered state at rate µ.

Spreading simulations are performed using the temporal networks of contacts (original, resampled or reconstructed). We run each simulation until no infectious individual remains (nodes are thus either still susceptible or have been infected and then recovered). If needed, the sequence of contacts is repeated in the simulation [START_REF] Stehlé | Simulation of an SEIR infectious disease model on the dynamic contact network of conference attendees[END_REF]. We consider values of β and µ yielding a non-negligible epidemic risk, i.e., such that a rather large fraction of simulations lead to a final size larger than 20% of the population (see Fig. 1): β = 4 × 10 -4 s -1 , µ = 4 × 10 -7 s -1 (InVS) or 4 × 10 -6 s -1 (SFHH and Thiers13). Other parameter values are explored in the Supplementary Information. For each set of parameters, the distribution of epidemic sizes is obtained by performing 1, 000 simulations.

SIS phase diagram

In the SIS model infectious nodes become susceptible again at rate µ. Depending on the values of β and µ, the outbreak can either die out or reach a stationary state. For each value of µ, there is a critical threshold value for β where the system goes continuously from a stationary state with no infectious nodes, to a stationary state with a finite fraction of infectious nodes. In order to determine this threshold, we follow [START_REF] Valdano | Analytical computation of the epidemic threshold on temporal networks[END_REF] and write the Markov chain equation for the probability p (t) i for a node to be infectious at time t:

p (t) i = 1-1-(1-µ)p (t-1) i j 1-βA (t-1) ji p (t-1) j . (1)
Here A (t) is the adjacency matrix of the network at the time t (A

(t) ij = 1 if
there is a link between nodes i and j at time t, and A (t) ij = 0 otherwise). For each data set of finite length T , we assume periodic boundary conditions with A

(t+T ) ij = A (t)
ij . This equation corresponds to the extension of the individual-based mean field approach 3 [START_REF] Pastor-Satorras | Epidemic processes in complex networks[END_REF] to SIS processes on temporal networks. The equation is iterated until a stationary state is reached, and we then compute the average fraction of infectious nodes as

i ∞ = i,t p (t) i T N , (2)
where T is the duration of the data set and N the number of nodes.

Reconstruction algorithm

We consider a population P of N individuals (the nodes of the contact network), potentially organised in groups. We assume that all the contacts taking place among a subpopulation P of these individuals, of size Ñ = (1 -f )N , are known. This constitutes our resampled data from which we need to construct a surrogate set of contacts concerning the remaining n = N -Ñ = f N individuals for which no contact information is available: these contacts can occur among these individuals and between them and the members of P. We assume that we know the group to which each member of P\ P belongs, as well as the overall activity timeline, i.e. the intervals during which contacts take place, separated by nights and weekends. We construct the surrogate contacts as follows:

1. we measure in the sampled data: 3 It does not take into account the dynamical correlations created by the spreading process between the states of neighboring nodes.

• the density ρ of links in the time-aggregated network;

• a row-normalised contact matrix C, in which the element C AB gives the probability for a node in group A to have a link to a node of group B;

• the list {τ c } of contact durations;

• the list {τ ic } of inter-contact durations;

• the list {p} of numbers of contacts per link;

2. we compute the number e of additional links needed to keep the network density constant when we add the n excluded nodes.

3. we construct each link according to the following procedure:

• a node i is randomly chosen from the set P\ P of excluded nodes;

• knowing the group A that i belongs to, we extract at random a target group B with probability given by C AB ;

• we draw a target node j at random from B (if B = A, we take care that i = j) such that i and j are not linked;

• from {p}, we draw the number of contact events p taking place over the link ij;

• the starting time t 0 of the first ij contact is drawn uniformly in the first activity interval of the global activity timeline;

• we then sequentially draw the duration of a contact from {τ c } and the inter-contact duration until the next contact from {τ ic }, and repeat until we have built p contacts;

• finally, we insert breaks defined by the activity timeline.

When the fraction f of excluded nodes is large, the method may be unable to construct the surrogate links (see Supplementary Information). 3. Outcome of SIR epidemic simulations performed on resampled contact networks and on networks reconstructed using different methods. We compare in each case, and as a function of f , the fraction of outbreaks that lead to a final fraction of recovered individuals r∞ larger than 20 % of the population (top plots), and the average size of these large outbreaks (middle plots). The dashed lines give the corresponding values for simulations performed on the complete data sets. The different methods are (see text): reconstruction conserving only the link density and the distribution of weights of the resampled data (W); reconstruction preserving, in addition to the W method, the group structure of the resampled data (WS); reconstruction conserving link density, distribution of weights and distributions of contact times, of inter-contact times and of numbers of contacts per link measured in the resampled data (WT); full method conserving all these properties (WST).

We also plot as a function of f the failure rate of the WST algorithm, i.e. the percentage of failed reconstructions (bottom plots); in the SFHH case reconstruction is always possible as the population is not structured into groups. The SIR parameters are β = 0.0004 and β/µ = 1000 (InVS) or β/µ = 100 (Thiers13 and SFHH) and each point is averaged over 1, 000 independent simulations.

PDF

InVS

Thiers13 SFHH FIG. 4. Outcome of simulations of SIR processes unfolding on reconstructed contact networks for large values of the fraction f of removed nodes. Distributions of epidemic sizes for simulations of SIR processes on reconstructed networks and on the whole data set (case f = 0), similarly to Fig. 1, but for large values of the fraction f of removed nodes.

Here β = 0.0004 and β/µ = 1000 (InVS) or β/µ = 100 (Thiers13 and SFHH) and 1, 000 simulations were performed for each value of f . The distributions of epidemic sizes for simulations performed on resampled data sets are not shown since at these high values of f , almost no epidemics occur.

As described in the main text, we consider temporally resolved networks of contacts T in a population P of N individuals and we perform a resampling experiment by selecting a subpopulation P of these individuals, of size Ñ = (1 -f )N . We assume that only the contacts occurring among the subpopulation P are known and we compare the properties of the corresponding resampled subnetwork T with those of the original network.

Figure S1 shows how population sampling affects several statistical properties of the contact networks. On the one hand, the degree distribution of the aggregated network of contacts systematically shifts towards smaller degree value. This is expected as each remaining node has in the resampled network a degree which is at most its degree in the original network, and is strictly smaller if some of its neighbours are not part of the resampled population. On the other hand, the statistical distributions of several quantities of interest are not affected by sampling: This is the case of the quantities attached either to single contacts or to single links, namely contact and inter-contact durations, number of contacts per link and link weights (the weight of a link is given by the total duration of the contacts between the two corresponding nodes).

Moreover, as shown in Fig. S2, the density of the aggregated network, i.e. the ratio between the number of links and the number of possible links, is on average conserved by the random resampling procedure. It varies however for different realisations of the resampling, and the corresponding variance increases with the fraction f of excluded nodes.

In the case of structured populations, Figures S3 & S4 show that the stability of the resampled network's density holds at the more detailed level of the contact matrices of link densities. In such matrices, the element (i, j) is given by the number of links between individuals of groups i and j, normalised by the total number of possible links between these two groups (if n i denotes the number of individuals in group i, the number of possible links is equal to n i n j /2 for i = j and to n i (n i -1)/2 for i = j). These figures clearly illustrate how the diagonal and block-diagonal structures are preserved, and Fig. S2 gives a quantitative assessment of this stability by showing that the cosine similarity between contact matrices between the resampled and original aggregated contact networks remains high even for when a large fraction of the nodes are excluded.

Properties of the reconstructed contact networks

As described in the main text and in particular in the Methods section, we construct a surrogate set of con-tacts concerning the f N individuals excluded by the resampling. We compare here the properties of the resulting contact networks (obtained by merging the resampled contact network T and the surrogate set of contacts) and of the original contact network. T .

Figure S5 shows that the degree distribution, which is not constrained by the reconstruction procedure, deviates from the original distribution. On the other hand, the distributions of contact durations, inter-contact durations, number of contacts per link and link weights are preserved. Moreover, the link density contact matrices of the reconstructed networks (Fig. S6 & S7) share a high similarity with the original contact matrices, even for high fractions of nodes excluded (Fig. S10).

For completeness, we also compute the contact matrices in contact time density (CMT), in which each element (i, j) is given by the total time in contact between individuals of groups i and j, normalised by the total number of possible links between these two groups: it gives the average time spent in contact by two random individuals of groups i and j. Figures S8, S9 and S10 show that the structure of these matrices is well recovered by the reconstruction method, with high similarity with the original matrices.

Phase diagram of the SIS model for the conference and office building data sets

We observe for the workplace and the conference the same effect on the phase diagram of the SIS model as in the high school: sampling leads to a shift of the epidemic threshold to higher values and thus to an underestimation of the epidemic risk. The phase diagram and the epidemic threshold are estimated more accurately by using reconstructed networks, thus giving a better evaluation of the epidemic risk (Fig. s S11 &S12).

Sensitivity analysis

In the main text, we have considered values of the SIR model parameters leading to a non-negligible epidemic risk and a value of β corresponding to slow processes. We consider here several other values of the parameters, corresponding either to smaller epidemic risk (Fig. S13) or to faster processes (Figs. S14 -S16). In all cases, simulations performed on the resampled contact networks lead to a strong underestimation of the epidemic sizes, with distributions shifting to smaller values as f increases, while the use of reconstructed data sets leads to a better estimation and generally speaking a slight overestimation of the epidemic risk. The estimation of the distribution of epidemic sizes becomes worse when the processes become faster, which might be due to the fact that temporal correlations, which are present in the original data but not in the surrogate contacts, play then a more important role in the outcome of the spreading processes.

Detailed alternative reconstruction methods

We give here details on the alternative reconstruction methods mentioned in the main text, which use less information than the WST method. In each case we consider the same setup as the complete method: a population P of N individuals (the nodes of the contact network), potentially organised in groups, for which we know all the contacts taking place among a subpopulation P of size Ñ = (1 -f )N . For the remaining n = N -Ñ = f N individuals, no contact information is available, but we know to which group they belong. We also have access to the overall activity timeline, i.e. to the successive intervals during which contacts can happen (daytimes), and are excluded (nights and weekends). The alternative reconstruction methods are the following: W: We perform the reconstruction using only the network density and the distribution of link weights, both measured in the resampled network T . The algorithm goes as follows:

1. we measure in the resampled data:

• the density ρ of links in the timeaggregated network; • the list {w} of link weights (the weight of a link is defined as the total contact time between the two linked nodes);

2. we compute the number of links e that must be added to keep the network density constant when we add the n excluded nodes;

3. we construct e links according to the following procedure:

• a node i is randomly chosen from the set P\ P of excluded nodes; • a node j is randomly chosen from the set P\{i} of all other nodes; • from {w}, we draw the weight w of the link ij; • we compute n ij = w/∆t, where ∆t = 20s is the temporal resolution of the data set, and we randomly choose n ij time windows of length ∆t within the activity windows defined by the activity timeline as contact events between i and j.

WS:

We perform the reconstruction using the network density, the distribution of link weights and the structure of the aggregated network given by the link density contact matrix, all measured in the resampled network T . The algorithm goes as follows:

1. we measure in the resampled data:

• the density ρ of links in the timeaggregated network; • a row-normalised contact matrix C, in which the element C AB gives the probability for a node in group A to have a link to a node of group B; • the list {w} of link weights; 2. we compute the number of links e that must be added to keep the network density constant when we add the n excluded nodes;

3. we construct e links according to the following procedure:

• a node i is randomly chosen from the set P\ P of excluded nodes; • knowing the group A that i belongs to, we extract at random a target group B with probability given by C AB ; • we draw a target node j at random from B (if B = A, we check that j = i); • from {w}, we draw the weight w of the link ij; • as for the W method, we extract at random w/∆t contact events of length ∆t = 20s within the activity timeline.

WT: We perform the reconstruction using the network density, the distribution of link weights and the temporal structure of the contacts given by the distributions of contact durations, inter-contact durations and number of contacts per link, all measured in the resampled network T . The algorithm goes as follows:

1. we measure in the resampled data:

• the density ρ of links in the timeaggregated network; • the list {τ c } of contact durations;

• the list {τ ic } of inter-contact durations;

• the list {p} of numbers of contacts per link;

2. we compute the number of links e that must be added to keep the network density constant when we add the n excluded nodes;

3. we construct e links according to the following procedure:

• a node i is randomly chosen from the set P\ P of excluded nodes; • a node j is randomly chosen from the set P\{i} of all other nodes; • from {p}, we draw the number of contact events p taking place over the link ij; • the starting time t 0 of the first contact between i and j is drawn uniformly in the first activity interval of the global activity timeline;

• we then sequentially draw the duration of a contact from {τ c } and the inter-contact duration until the next contact from {τ ic }, and repeat until we have built p contacts; • finally, we insert breaks defined by the activity timeline.

Possible failure of the reconstruction method at large f

The construction of the surrogate version of the missing links uses as an input the group structure of the subgraph that remains after sampling, as given by the contact matrix of the link densities between the different groups of nodes that are present in P. Depending on the characteristics of P and of the corresponding contacts, the construction method can fail in several cases: (i) if an entire group (class/department) of nodes in the population is absent from P;

(ii) if the remaining nodes of a specific group (class/department) are all isolated in P's contact network;

(iii) if, during the algorithm, a node of P\ P is selected but cannot create any more links because it already has links to all nodes in the groups B such that C AB = 0.

Cases (i) and (ii) correspond to a complete loss of information about the connectivity of a group (class/department) of the population, due to sampling. It is then impossible to reconstruct a sensible connectivity pattern for these nodes. Case (iii) is more subtle and occurs in situations of very low connectivity between groups. For instance, within the contact network of P, a group A has links only with another specific group B, and both A and B are small; it is then possible that the nodes of (P\ P) ∩ A quickly exhaust the set of possible links to nodes of B during the reconstruction algorithm. If a node of (P\ P) ∩ A is again chosen to create a link, such a creation is not possible and the construction fails.

FIG. 1 .- 2 FIG. 2 .

 122 FIG. 1.Comparison of the outcome of SIR epidemic simulations performed on resampled and reconstructed contact networks. Distribution of epidemic sizes (fraction of recovered individuals) at the end of SIR processes simulated on top of either resampled (left column) or reconstructed (right) contact networks, for different values of the fraction f of nodes removed. The parameters of the SIR models are β = 0.0004 and β/µ = 1000 (InVS) or β/µ = 100 (Thiers13 and SFHH). The case f = 0 corresponds to simulations using the whole data set, i.e., the reference case. For each value of f , 1, 000 independent simulations were performed.

FIG- 3 FIG. S11 .

 3S11 FIG.S1. Effect of sampling on contact network properties. Comparison of the distributions of structural (node degrees and link weights in the aggregated network of contacts) and temporal (contact durations, inter-contact times, number of contacts per link) properties of the contact networks, for different fractions f of removed nodes. For each value of f , the distributions are computed on a single realisation of the resampling.

  FIG. S14.Outcome of SIR epidemic simulations on reconstructed networks for different parameter values. Same as Fig.S13for β = 0.004, β/µ = 1000 (InVS) or β/µ = 100 (Thiers13 and SFHH). Each distribution is computed on 1, 000 simulations of the SIR process.

  1, MP * 2 with respectively 31, 29 and 38 students), Physics (PC, PC * , PSI with respectively 44, 39 and 34 students), or Biology (2BIO1, 2BIO2, 2BIO3 with respectively 37, 35 and 39 students).

	The office building is structured in 5 departments:
	DISQ (Scientific Direction, 15 persons), DMCT (Depart-
	ment of Chronic Diseases and Traumatisms, 26 persons),
	DSE (Department of Health and Environment, 34 per-
	sons), SRH (Human Resources, 13 persons) and SFLE
	(Logistics, 4 persons).

TABLE I .

 I Data sets considered. For each data set we specify the type of social situation, the number N of individuals whose contacts were measured, the corresponding participation rate r, the duration T and the dates of the data collection.

		TABLES & FIGURES
	Data set	Type	N	r	T	Dates
	InVS Office building 92 63 % 2 weeks June 24th -July 5th 2013
	Thiers13 High school 326 86 % 1 week December 2nd -7th 2013
	SFHH	Conference 403 34 % 2 days	June 3rd -4th 2009
		f		InVS CML	Thiers13 CML
		10 % 0.996 [0.937, 0.999] 0.999 [0.998, 0.999]
	Resampled 20 % 0.980 [0.889, 0.994] 0.996 [0.995, 0.997]
		40 % 0.925 [0.872, 0.983] 0.988 [0.983, 0.990]
		10 % 0.976 [0.846, 0.995] 0.998 [0.994, 0.999]
	Reconstructed 20 % 0.942 [0.844, 0.984] 0.993 [0.985, 0.995]
		40 % 0.890 [0.652, 0.953] 0.977 [0.938, 0.987]

TABLE II .

 II Similarities between the original contact matrices and the contact matrices of the resampled networks (top) and of the reconstructed networks (bottom). Median and 90% confidence interval for the cosine similarity between link density contact matrices (CML) for different values of f , the fraction of nodes removed from the original data. Values were obtained from 100 independent realisations of the resampling and reconstruction procedures.

Note that the full data sets are also samples of all the contacts that occurred in the populations, as the participation rate was lower than 100% in each case.

If n i denotes the number of individuals in group i, the number of possible links is equal to n i n j /2 for i = j and to n i (n i -1)/2 for i = j.

ACKNOWLEDGEMENTS The present work is partially supported by the French ANR project HarMS-flu (ANR-12-MONU-0018) to M.G. and A.B, by the EU FET project Multiplex 317532 to A.B., C.C. and C.L.V., by the A*MIDEX project (ANR-11-IDEX-0001-02) funded by the "Investissements d'Avenir" French Government program, managed by the French National Research Agency (ANR) to A.B., by the Lagrange Project of the ISI Foundation funded by the CRT Foundation to C.C., and by the Q-ARACNE project funded by the Fondazione Compagnia di San Paolo to C.C. We warmly thank André Panisson for providing the algorithm used in the numerical simulations of the SIS process.


Bernardo Severo
email: bernardo.severo@acad.pucrs.br

Cassia Trojahn
email: cassia.trojahn@irit.fr

Renata Vieira
email: renata.vieira@pucrs.br

VOAR: A Visual and Integrated Ontology Alignment Environment

Keywords: Ontology Alignment, Ontology Matching, Ontology Visualization

Ontology alignment is a key process for enabling interoperability between ontology-based systems in the Linked Open Data age. From two input ontologies, this process generates an alignment (set of correspondences) between them. In this paper we present VOAR, a new web-based environment for ontology alignment visualization and manipulation. Within this graphical environment, users can manually create/edit correspondences and apply a set of operations on alignments (filtering, merge, difference, etc.). VOAR allows invoking external ontology matching systems that implement a specific alignment interface, so that the generated alignments can be manipulated within the environment. Evaluating multiple alignments together against a reference one can also be carried out, using classical evaluation metrics (precision, recall and f-measure). The status of each correspondence with respect to its presence or absence in reference alignment is visually represented. Overall, the main new aspect of VOAR is the visualization and manipulation of alignments at schema level, in an integrated, visual and web-based environment.

Introduction

The Linked Open Data and Semantic Web efforts have been promoting the publishing of interlinked collections of data, in which the vocabulary is defined with the help of ontologies. In order to allow the interoperability between these different data sources, one has to be able to find semantically related entities in these sources. The task of finding semantically related entities (concepts, properties, instances) between two ontologies is known as ontology matching [START_REF] Euzenat | Ontology matching[END_REF]. Ontology matching is a key challenge and there are many academic efforts proposing different ways to perform this task, which are evaluated in the context of evaluation campaigns, like the ones organized by the Ontology Alignment Evaluation Initiative (OAEI) 1 . Even with a variety of matching systems and a strong community working in this problem, the area still lacks webbased, visual and integrated environments in which ontology alignments can be easily manipulated and compared. Different matching systems propose ways for visualizing their generated alignments, like YAM++ (Ngo and Bellahsene, 2012a), HOMER [START_REF] Udrea | Homer: Ontology visualization and analysis[END_REF] and Agreement-Maker [START_REF] Cruz | Agreementmaker: efficient matching for large real-world schemas and ontologies[END_REF]. Others environments provide an interface for manipulating alignments through a set of operations, like the Alignment Server [START_REF] David | The Alignment API 4.0[END_REF], while few systems make available web-based interfaces for invoking their matching algorithms, like LogMap [START_REF] Jiménez-Ruiz | Logmap: Logic-based and scalable ontology matching[END_REF]. Another resource largely used in the ontology matching community is the Alignment API [START_REF] David | The Alignment API 4.0[END_REF], that provides the basis for developing matching systems and means for alignment manipulation and evaluation that can be reused by other applications. In this paper we present a comparison of such tools/environments and VOAR. The main motivation behind VOAR (Visual Ontology Alignment EnviRonment) 2 is to assist end users in the series of tasks for alignment manipulation, evaluation and visualization as a single integrated resource. VOAR provides an environment in which alignments can be shown and manipulated in different ways (combining with other alignments, editing correspondences, graphically displaying ontology entities and correspondences between them), as well as evaluated (graphically displaying evaluation outputs) and generated (using external matching systems). We believe that VOAR offers an alternative visual environment to the community interested in ontologies and ontology alignment. The remainder of this paper is organized as follows. In 2. we provide the basic definitions of ontology alignment. Then, in §3. we detail the architecture of VOAR, describing the tool and its modules. The main related work are discussed in §4. where we present a comparative overview of the different matching tools and environments and VOAR. Finally, we conclude the paper and present future work §5..

Background

The value of ontologies for a range of applications has long been recognized. In Computer Science, the most common definition of an ontology comes from Gruber in [START_REF] Gruber | Toward principles for the design of ontologies used for knowledge sharing[END_REF] "an explicit, formal specification of a shared conceptualization of a domain of interest". Following this definition, an ontology should be machine-readable, agreed (shared) by a community or group, and restricted to a specific domain of interest. Ontologies provide a model of the concepts of a domain and how these concepts are related to each other. While these different ontologies may be similar, they may differ in granularity or detail, use different representations, or model the concepts, properties and axioms in different ways.

The process of finding correspondences between ontology entities is known as ontology matching [START_REF] Euzenat | Ontology matching[END_REF]. It takes as input two ontologies o and o and an (possibly empty) alignment A to be completed, and determines as output an alignment A , i.e., a set of correspondence. A simple correspondence can be defined as follows: [Correspondence [START_REF] Euzenat | Ontology matching[END_REF]] A correspondence can be defined as <e,e ,r,n>, such that: e and e are entities (e.g., elements, properties, classes, instances) of o and o , respectively; r is a relation holding between two entities e and e , (for instance, equivalence (≡), more general ( ), disjointness (⊥), overlapping ( )); and n is a confidence measure number in the [0;1] range. The confidence assigns a degree of trust on the correspondence from the matcher. Different matching approaches have emerged from the literature. A review on these approaches can be found in [START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF][START_REF] Kalfoglou | Ontology mapping: the state of the art[END_REF][START_REF] Euzenat | Ontology matching[END_REF]. The main distinction between each is due to the type of knowledge encoded within each ontology, and the way it is utilized when identifying correspondences between features or structures within the ontologies. While terminological methods lexically compare strings (tokens or n-grams) used in naming entities (or in the labels and comments concerning entities), semantic methods utilize model-theoretic semantics to determine whether or not a correspondence exists between two entities. Approaches may consider the internal ontological structure, such as the range of their properties (attributes and relations), their cardinality, and the transitivity and/or symmetry of their properties, or alternatively the external ontological structure, such as the position of the two entities within the ontological hierarchy. The instances (or extensions) of classes could also be compared using extensionbased approaches. In addition, ontology matching systems rely not on a single approach. In order to help users evaluating the suitability of proposed matching approaches to their needs and help developers of matching systems to improve their systems, evaluation of the generated alignments is an important task (Euzenat et al., 2011). With this aim, OAEI organizes ontology matching evaluation campaigns yearly since 2004 [START_REF] Euzenat | Ontology alignment evaluation initiative: Six years of experience[END_REF]. The most common way for evaluating matching systems is to compare their generated alignments (A ) with a reference alignment R, usually manually created by a domain expert. Typically, classical measures as precision (P ), recall (Re) and f-measure (F ) are used to compare alignments:

P = |R ∩ A | |A | (1) Re = |R ∩ A | |R| (2) F = 2 * P * Re P + Re (3)
Ontology alignments are important resources for the exploitation of ontologies and visual tools are important for the tasks of alignment manipulation and visualization, therefore we developed VOAR, described in the next section.

VOAR: Visual Ontology Alignment Environment

VOAR was built based on the PLATAL tool [START_REF] Severo | PLATAL -a tool for web hierarchies extraction and alignment[END_REF], originally designed to support the tasks of extraction of lightweight ontologies from web pages, alignment of these ontologies using basic matching strategies, and evaluation against reference alignments (which could be manually created). This improved version of PLATAL integrates a web-based visual environment and improves some of its functionalities, making it more manipulation driven.

VOAR is an environment organized in five modular operation modes, working independent of each other, namely: In order to promote interoperability and reuse, VOAR is developed on the top of established technologies in the field of ontology matching, such as the Alignment API (version 4.5) and OWL API [START_REF] Horridge | The OWL API: A Java API for OWL ontologies[END_REF].

The OWL API is a Java library that offers a reference implementation to work with OWL ontologies, mainly OWL parsing, while the Alignment API provides a set of functions that are used as basis in the Alignment Manipulation and Evaluation modules. Furthermore, the Alignment API format3 , the most common alignment representation format adopted in the ontology matching community, is used to export and import alignments in VOAR. With respect to the development of the web-based interface, VOAR was built with JavaServer Faces (JSF) technology, compatible with most current browsers.

For the ontology matching task itself, VOAR does not implement any specific matching approach, once it does not pretend to be a matching system. Instead, VOAR offers the possibility of invoking external matching systems. In order to do so, we chose to use a well-known interface that has been proposed in the context of the SEALS project4 . This interface has been adopted since 2011 in the OAEI campaigns, where for some tracks, participating systems have to implement it in order to be automatically invoked with the evaluation platform5 . Therefore, VOAR is able to invoke any matching system implementing the SEALS interface. Furthermore, VOAR works with the concept of a 'working alignment', an in-memory alignment that can be built (creating a new/blank, uploading an existing one in the Alignment API format, generating one from running matchers, etc.) and changed along the use of each module (editing correspondences, performing set operations with other alignments, etc.). The working alignment is what the user will visualize along each module. Users can as well export this generated/modified alignment for later use.

In the following, each VOAR module is presented.

Correspondences Edition

Following the definition of alignment in §2., VOAR was designed to allow users to load two ontologies o and o and an alignment A , which can be edited. Figure 1 presents a screenshot of the VOAR correspondences edition module, where trees representing each ontology are shown, and between them, a table of correspondences of the working alignment for a given ontology entity. The 'Modules' option in the top of the Figure 1 allows for switch between the modules. The ontologies used in the examples come from the test 304 of the OAEI 2012 benchmark 6 . Correspondences in the alignment can be visualized, for a selected entity (on the tree representation), then its relation and confidence modified (in the table itself) or deleted. One can use the focus operation in each correspondence line of the table to jump to the entities in the tree visualization. A new correspondence may be created by selecting entities in both source and target ontologies, and it is displayed along with the existing ones. Finally, in each tree visualization, users can also filter out the entities whose naming (URI, label, comments) corresponds to a search criteria, what is especially useful when dealing with large ontologies. In this current version, VOAR is limited to the visualization and manipulation of correspondences involving ontology classes.

Alignment Manipulation

VOAR also provides ways to manipulate an alignment as an object, mostly by interacting with other alignments. The Figure 2 shows a screenshot of this module. The current set of available operations are: union (resulting in the merge of alignments), intersection (where only correspondences occurring in all input alignments are kept), difference (complement, where a sub-set of correspondences are removed from a given alignment). There are also other auxiliary operations, like the possibility to trim correspondences under a given threshold and invert the ontologies order. These op-erations are available in the Alignment API and Alignment Server for a pair of alignments, in their native versions, and we reuse that implementation through the Alignment API.

In VOAR users can select multiple alignments at once and apply these operations (for instance, making the union of multiple alignments together), by using the API as base and composing its results. All resulting changes are incorporated to the working alignment.

Figure 2: VOAR alignment manipulation module.

Ontology Matching

As stated in §3., VOAR does not pretend to be a matching system. Instead, VOAR allows for invoking external matching systems. In order to do so, these systems have The proposed alignment contains incorrect correspondences for this entity when compared to the reference alignment (true negative) Missing correspondences

The proposed alignment is missing correspondences for this entity when compared to the reference alignment (false negative) Correct correspondences

The proposed alignment contains all possible correspondences for this entity when compared to the reference alignment (true positive) No correspondences

Neither the proposed alignment nor the reference alignment contains correspondences for this entity (true negative)

to implement the well-known SEALS Ontology Matching Interface. We choose to follow this interface because it has been largely adopted in the context of the OAEI evaluation campaigns. Therefore, using this common interface promotes the interoperability in the ontology community.

Basically, the SEALS format requires to bundle the matcher in a certain folder structure, and create a "bridge" implementing the SEALS Ontology Matching Interface. As most state-of-the-art matching systems participate in OAEI campaigns and have to implement the SEALS interface in order to participate in some tracks, using this interface allows users to upload most matchers (publicly) available from the OAEI campaigns (like YAM++, LogMap, etc.). One can also follow this format for generating a bundle from their own matghing system in order to run it in VOAR. In VOAR, one can upload a matcher bundle (available only for the current session), what facilitates the user task when running matchers, once some matchers usually have to be run in a console prompt. Users are able to select which available matchers will be run for the uploaded ontologies (those that belong to the working alignment). Each selected matcher will run one after the other, sequentially. If any error occurs during execution, VOAR displays an appropriate error message and starts the execution of the the next matcher (no interaction is needed). When the executions are finished, the resulting alignments can be loaded as working alignment, once they are temporarily stored during the current session and can be edited, evaluated and visualized. VOAR is not yet able to manage systems requiring long execution times along with other modules execution, and the user has to wait until the alignment processes are completed. Hence, the alignment resulting from the execution of each matcher can be then loaded and downloaded (for other uses or later loading in VOAR).

Alignment Evaluation

With VOAR, one can compare multiples alignments (working alignment and/or others that can be uploaded) with respect to a reference alignment. Measures of precision, recall, and F-measure can be visualized for each evaluated alignment. We have used the implementations available in the Alignment API for generating these evaluation metrics. VOAR allows the visualization of the results according to each correspondence. Figure 3 shows a screenshot of VOAR where evaluation results are presented (table of results for all submitted alignments and tree representations with status by entity for a selected alignment).

The status of specific entities with regard to the reference alignment is shown on each ontology tree representation, according to four possible status (represented by icons on each entity), as presented in Table 1. These icons are shown respecting the order of precedence of values in Table 1. For example, if a given ontology entity has one or more incor- rect correspondences, it will be shown the associated icon of incorrect correspondences, even if there are other correspondences correct or missing for the same entity.

Alignment Visualization

An important feature for a visual alignment tool is the visualization of an alignment in a graphical form, aiming at facilitating the interpretation and analysis of the generated correspondences. A global view, as the one available in VOAR, provides assistance in the interpretation of the alignment as a whole, showing aspects such as density. Areas of alignments concentration or lack of alignments can also be observed.

Another important aspect of the representation is related to the colors used to each ontology entity and correspondences. When a great number of correspondences are displayed on screen, is hard to see which entities and connections are the ones one want to focus on. So the visualization strategy in this module assigns a common color for entities with a correspondence, as well as their connection line (Figure 4), making easier to track the links.

During the visualization of the alignment, one can set the focus on a given correspondence to make it being shown highlight with their attributes. Selecting entities in the ontologies trees allows the user to navigate to the application module that provides ways to manipulate that specific data (also accessible in the 'Modules' option in the top of the Figure 4).

Related Work

Different tools have been proposed for assisting the user in the task of matching ontologies, in which we found similar operations and visual representations as the ones provided by VOAR. COMA++ [START_REF] Aumueller | Schema and ontology matching with coma++[END_REF] was designed for aligning XML schemas and offers a library of matchers. Users can define their own correspondences and provide feedback on automatically generated ones. Visualization of alignments is done by lines drawn between the trees of entities. HOMER [START_REF] Udrea | Homer: Ontology visualization and analysis[END_REF] makes available a radial-graph display GUI for alignment visualization that allows the user to navigate to any match decisions and to compare multiple alignments in parallel (i.e., displaying common/differences between the alignments). PROMPT [START_REF] Noy | Prompt: Algorithm and tool for automated ontology merging and alignment[END_REF] is a Protégé plugin for ontology merging and alignment that makes suggestions and, for each of its suggestions, presents a series of explanations. A series of other Protégé plug-ins are also available for similar tasks [START_REF] Lanzenberger | Alviz -a tool for visual ontology alignment[END_REF]) [START_REF] Kolli | Optima: Tool for ontology alignment with application to semantic reconciliation of sensor metadata for publication in sensormap[END_REF].

The YAM++ (Ngo and Bellahsene, 2012a)(Ngo and Bellahsene, 2012b) matcher, which discovers correspondences between two ontologies by using machine learning approach, offers a graphical way for visualizing the generated alignments just like COMA++. Other examples of matching systems implementing some GUI mechanism are AgreementMaker [START_REF] Cruz | Agreementmaker: efficient matching for large real-world schemas and ontologies[END_REF], that presents information in a tree diagram, provides more information than others tools at the level of the correspondence (colors for each connected entities and confidence of the relation) and allows to focus on individuals; and TaxoMap (Hamdi et al., 2010) 7 , where the interface is oriented to the system parameterization. Taxomap does not show the ontologies or its alignment in a graphical form. LogMap8 , a matching systems based on applying reasoning and repair capabilities, provides a simple web interface that allows users to browse the input ontologies and invoke the LogMap system. An environment for manipulating alignments is OLA (OWL Lite Alignment) [START_REF] Euzenat | Ontology alignment with OLA[END_REF]. It supports parsing and visualization of ontologies, automated generation of correspondences between entities, based on a set of predefined matching strategies, manual construction of alignments, and visualization of alignments. A graph-based approach is used to represent ontologies in order to make the comparisons between them and their alignments easier. This structure makes the links between classes more explicit, through the links established from their object properties, while the alignment visualization is made by loading the graph structures for both ontologies. Another similar system is the SILK workbench [START_REF] Volz | Silk -a link discovery framework for the web of data[END_REF], focused on the linked data, that provides means to interactively create configuration files enabling to manage different sets of data sources and linking tasks, allowing to visualize the links found and to correct them. The Alignment Server 9 , available with the Alignment API, provides a set of alignment operations (alignment using basic matching strategies, alignment manipulations and alignment evaluation) in a web-based interface, with the advantage of storing and retrieving alignments, enabling users to search for already generated alignments for a given pair of ontologies. However, the visualizations is raw text based and users cannot edit particular correspondences in the system. Furthermore, the manipulations of alignments are limited to pairs of alignments.

In Table 2 a comparison of the environment type and the operations available for each related tool is presented. The first point to be observed is the number of tools that are standalone (usually Java-based programs), while VOAR is a web-based application (not a plugin or a standalone application), like the Alignment Server, SILK and LogMap. This is an important aspect in the development of applications nowadays, improving compatibility with different OS, browsers, devices and making easier their access and management of versions (users dealing with tools upgrades).

For most of the evaluated tools with the functionality of editing the correspondences manually, the available actions are similar for most tools and environments: adding/removing and changing the relation type or confidence. The same scenario was found for the capability of alignment manipulation, where the only two tools with this functionality (Alignment Server and VOAR) present 9 http://alignapi.gforge.inria.fr/aserv.html the available operations of the Alignment API.

Analyzing the matching functionality, all tools provide a way for running matchers. Some in particular allow to run existing matchers (Alignment Server -which invokes basic matchers, VOAR -which invokes systems implementing the SEALS Ontology Matching Interface), instead of implementing specific algorithms itself. The other tools usually provide customizations to their methods through their interface, like setting up thresholds and other parameterization of matchers (since their purpose is to be more matching-driven). With respect to evaluation, the most common evaluation, for those with this option, is basically the calculation of precision, recall and f-measure. A differential aspect is that some tools allow the user to manually set for each correspondence its correct status (true positive, true negative, etc.), like in YAM++ and AgreementMaker.

Regarding those tools and environments implementing visualization strategies, while matchers like COMA++ and YAM++ draw lines between the two ontology hierarchies, sometimes making difficult to distinguish relationships for large amount of alignments, VOAR proposes some simple but remarkable improvements in this type of presentation. Once a correspondence is selected, their properties and visualization gain a different appearance, making easier to evaluate them, like displaying the relation and the confidence value (similar to what is done in AgreementMaker). VOAR also determines a color, that is common for the entities on both ontologies which share a correspondence, making their correspondences more visual-driven, even if more than one line is connected to an entity. Other tools present visualizations with a focus on the evaluation of specific attributes (like in OLA), what is not yet done in VOAR, or simple interfaces for helping the user in the configuration and execution of matchers (mostly without graphical representation of alignments), like Alignment Server, LogMap and SILK. To the best of our knowledge, VOAR is the one of the first web-based integrated environment that includes a visual (graphical) representation of ontologies and their alignments, ways for manipulating multiple alignments and invoking external matching systems.

Conclusions and Future Work

This paper has presented the first release (1.0.0) of VOAR, a web-based and visual environment built to assist users in the main tasks involving ontology alignments. VOAR provides an integrated environment for manipulating, matching, evaluating, and visualizing alignments at schema level. Hence, making VOAR publicly available as a community resource offers an alternative way for manipulating alignments, what can be especially useful for end users.

As future work, many directions to improving and extending VOAR are envisaged. First of all, this initial release of VOAR will be submitted to evaluation by experts and non-experts of the ontology matching area. We plan also to add the possibility of visualizing and manipulating ontology alignments at the instance-level (a must in the context of Linked Open Data) -as well as visualizing data and object properties of ontologies. Third, we intend to provide a way for parameterizing matchers through the interface (in the current version, matchers run with their default configuration). Fourth, we plan to allow user to persist their data and configuration (storing ontologies, their alignments and matcher configurations). Furthermore, dealing with large ontologies and large sets of data instances may require providing alternative ways for visualizing the alignments between then. Finally, we intend to provide a way for collaborative ontology matching where multiple users can work collaboratively for generating and manipulating alignments.

  (a) Correspondences Edition Module, (b) Alignment Manipulation Module, (c) Matching Module, (d) Evaluation Module and (e) Visualization Module.

Figure 1 :

 1 Figure 1: VOAR correspondences edition module.

Figure 3 :

 3 Figure 3: VOAR evaluation module.

Figure 4 :

 4 Figure 4: VOAR visualization module.

Table 1 :

 1 Correspondence evaluation statuses

	Icon Status	Description
	Incorrect correspondences

Table 2 :

 2 Alignment tools comparison

	Tool	Environment Correspondences	Alignment	External	Evaluation Alignment
			Edition	Manipulation	Matching		Visualization
	PROMPT	Plugin	-	-	-	-	yes
	YAM++	Standalone	yes	-	-	yes	yes
	COMA++	Standalone	yes	-	-	yes	yes
	HOMER	Standalone	-	-	-	yes	yes
	AgreementMaker Standalone	yes	-	-	yes	yes
	TaxoMap	Standalone	-	-	-	-	-
	OLA	Standalone	-	-	-	-	yes
	SILK workbench Web	yes	-	-	-	yes
	Alignment Server Web	-	yes	-	yes	yes
	LogMap	Web	-	-	-	-	-
	VOAR	Web	yes	yes	yes	yes	yes

http://alignapi.gforge.inria.fr/format.html

http://www.seals-project.eu/

http://oaei.ontologymatching.org/2011.5/seals-eval.html

http://oaei.ontologymatching.org/2012/benchmarks

https://www.lri.fr/ hamdi/TaxoMap/TaxoMap.html

http://csu6325.cs.ox.ac.uk/