Julien Roux
email: jroux@laas.fr

Christophe Escriba
email: cescriba@laas.fr

Jean-Yves Fourniols
email: fourniol@laas.fr

M Contardo
email: m.contardo@tcsd.fr

Pascal Acco

Georges Soto-Romero

Toward soil smart sensing in v3.0 agriculture: a new original single-shape design for a capacitive moisture and salinity sensor

Keywords: smart sensing, connected agriculture, capacitive bi-sensor, soil moisture and salinity

To rationalise the amount of water needed to irrigate cultivated fields, modern agriculture imposes the need for better knowledge of the soil moisture content. In this context, since current technological solutions do not correspond to criteria of cost or use, this paper presents a design for a new original capacitive bi-functional sensor to measure soil moisture and salinity. In this paper, we outline all the stages of the design, from simulation to finished elements of the optimal design to deployment in the fields, taking into consideration the constraints of mechanical integration necessary for its industrialisation. Measurement electronics have been developed on the basis of an electric model of the sensor in order to obtain double measurement. Then, an on-site (field lot) measurement program was carried out to validate the good performance of the system in real time.

Finally, this performance was matched with that of leading industrial sensors on the market. This work clearly demonstrates that, after deployment of the sensors, the overall system makes it possible to obtain a precise image of the hydric condition of cultivated soil, with the best response time.

Introduction

In modern and ecological agriculture, knowledge of the hydric condition of the soil has become an economic factor of major importance for the supply of water to crops. Accordingly, knowledge of moisture content and salinity is essential to the development of new irrigation systems. To meet this need, one of the most widely employed methods of measurement is the use of tensiometers [START_REF] Faybishenko | Tensiometer for shallow and deep measurements of water pressure in vadose zone and groundwater[END_REF].

Yet, this type of sensor has two main drawbacks: a response time of several hours, during which water is being supplied [START_REF] Hayashi | Use of tensiometer response time to determine the hydraulic conductivity of unsaturated soil[END_REF], as well as a phenomenon known as uncoupling [START_REF] Trotter | Errors in reading tensiometer vacua with pressure transducers[END_REF]. These failings make it problematic to check the quantity of water supplied naturally (rain) or artificially (irrigation). Not only is it impossible to check the soil in real time, but, while these sensors are very sensitive, they often cease to work when the soil is too wet or too dry. In the latter event, it becomes necessary to reinstall sensors, which can be prejudicial to large farm operations.

Consequently, new capacitive measuring technology has been developed to modernise future agricultural installations. It is this capacitive measuring principle that we have selected to measure the level of moisture in the soil [START_REF] Gao | Design and Test of a Soil Profile Moisture Sensor Based on Sensitive Soil Layers[END_REF][START_REF] Dean | Soil moisture measurement by an improved capacitance technique, Part I. Sensor design and performance[END_REF][START_REF] Buckman | The Nature and Properties of Soils[END_REF]. The main advantage of this type of sensor is that it possesses a response time of less than a minute, which gives it the ability to monitor the hydric condition of the soil in close to real time 7. Existing solutions [START_REF] Chakraborty | PMMA-Coated Capacitive Type Soil Moisture Sensor: Design, Fabrication, and Testing[END_REF][START_REF] Kalita | Graphene quantum dot soil moisture sensor[END_REF][START_REF] Palaparthy | Graphene oxide based soil moisture microsensor for in situ agriculture applications[END_REF] include sensors based on a small-sized (<1 mm) detection cell), which limits the volume of soil that can be tested. On the other hand, their complex structures [START_REF] Boudaden | Polyimide-Based Capacitive Humidity Sensor[END_REF][START_REF] Xiao | Integrated soil moisture and water depth sensor for paddy fields[END_REF][START_REF] Dias | Autonomous soil moisture sensor based on nanostructured thermosensitive resistors powered by an integrated thermoelectric generator[END_REF] do not make them easy to use and require some time, several months, to restructure the soil, which can be damaging to farmers.

Since alternative technologies to measure moisture do exist, let us examine the radiofrequency method [START_REF] Pichorim | Two Solutions of Soil Moisture Sensing with RFID for Landslide Monitoring[END_REF][START_REF] Rezaei | A new 1.4-GHz soil moisture sensor[END_REF]. This approach does not allow for a double measurement to evaluate soil salinity at the same time. To respond to this need, our solution exploits the capacitive properties of a sensor structure because it makes it possible to measure salinity as well as moisture [START_REF] Aljoumani | Transfer Function and Time Series Outlier Analysis: Modelling Soil Salinity in Loamy Sand Soil by Including the Influences of Irrigation Management and Soil Temperature: Modelling soil salinity in loamy sand soil[END_REF][START_REF] Singh | Performance assessment of factory and field calibrations for electromagnetic sensors in a loam soil[END_REF]. Indeed, subject to a certain range of frequencies, soil capacity depends not only on moisture but also on its ionic composition [START_REF] Visacro | The Response of Grounding Electrodes to Lightning Currents: The Effect of Frequency-Dependent Soil Resistivity and Permittivity[END_REF]. Thus, by taking one moisture measurement followed by a measurement of moisture/salinity combined, the same sensor can obtain the two parameters.

To allow measurement on the scale of a large agricultural operation, multiplication of measurement points makes it possible to reach areas that are sufficiently representative of the soil's hydric condition. Several systems already have been created, but either their cost largely limits their deployment [START_REF] Boada | Battery-Less Soil Moisture Measurement System Based on a NFC Device With Energy Harvesting Capability[END_REF] or the existing system is technologically limited for large-scale use [START_REF] Da Costa | A Self-Powered and Autonomous Fringing Field Capacitive Sensor Integrated into a Micro Sprinkler Spinner to Measure Soil Water Content[END_REF].

So, in response to these technological barriers, our innovation is based on the design of a new generation of affordable capacitive sensors that are compatible with the demands of deployment on a large scale. Section 2 presents an elementary design of the sensor and its optimization. Section 3 presents a modification of the shape factor of the electrodes to optimise measurement parameters.

Section 4 describes the electric model of the sensor, while section 5 presents the design of on-board electronics for the associated measurement. Finally, section 6 outlines results of on-site performance tests on actual agricultural operations.

First approach and optimization

Initially, design of the transducer is based on the same principle as a condenser. The structure rests on two electrodes separated by a dielectric image of the soil. A cylindrical shape is preferred for this type of transducer to facilitate insertion into the soil. Copper electrodes are fixed to the cylinder as shown in Figure 1. Since the thickness of the electrodes is less than 1/10 mm, inter electrode Celectrodes capacity is negligible.

Figure 1. Sensor shape, first design

For practical reasons and for reasons of mechanical solidity, a 40mm diameter is selected to demonstrate the feasibility of the initial transducer. Advantages are:

• ease of insertion into the soil. An auger with a standard diameter is used to make a prehole.

• soil is minimally de-structured around the sensor to avoid skewing measurements.

Electrodes and inter-electrodes must be large enough to ensure connectivity and minimise parasitic capacity between electrodes. To permit soil moisture detection of 10% with a planar surface capacity of 25pF, analytical calculations point to 40 mm electrodes spaced 10 mm apart.

First, the electrodes surface must be limited to lower the cost of fabrication. The objective is to reduce the diameter of the transducer while preserving the dimensions' homothetic relationship in order to minimally affect the ultimate capacity of the transducer. Work to re-dimension the transducer makes it possible to obtain a 20mm diameter on electrodes with a width of 30mm, spaced 8mm apart. Figure 2 shows the evolution of capacities as a function of mass soil moisture for a diameter of 20mm as opposed to a diameter of 40mm.

Figure 2. Cylindrical sensor capacity as a function of soil moisture

Curves show that the 20mm transducer has the same characteristics as the transducer with a 40mm diameter, with a sensitivity of 0.26pF.% -1 , a variation of 12.6pF subsequent to a 48% change in moisture.

Beyond the sensitivity of the sensor, it is necessary to estimate the volume of soil probed. In order to conduct this study, COMSOL modelling of the final elements was carried out. The volume of soil probed is quantified on the basis of the density of the electric field generated (Figure 3). (centred between (-20 ; 0) and (20 ; 0)) make it possible to observe a 50mm radius with an electric field density higher than 50V/m, which means that soil volume of about 1.32 litres, with a sensitivity of (0.26pF.% -1 ) is needed in order to electronically probe a sufficient volume of soil. Yet the copper surface needed is relatively significant (15080 mm²), which raises the cost of the sensor. To optimise the dimensions of the transducer and thereby reduce the surface of the electrodes, Table 1 Analysis of these results allows us to exploit them according to the "rules of electrode design":

• If we reduce inter-electrode space, capacity is higher but sensitivity is reduced by 11%, from an initial 0.265pF.% -1 to 0.235pF.% -1 . This dimensional variation, therefore, is not viable.

• If we increase this space, capacity is too reduced and becomes impossible to exploit. It is preferable, therefore, to preserve a 10mm space between electrodes.

• If we increase electrode width, we increase capacity as well as the sensitivity of the sensitive element. In fact, we go from 0.265pF.% -1 to 0.367pF.% -1 , an increase of 38%. However, we also increase electrode surface by 67% which raises their cost. The increase in sensitivity is not significant enough to justify the resulting cost increase.

• If we reduce the width of the electrodes, we reduce sensitivity but we gain on the cost.

At the end of this optimization work, Figure 5 presents the final shape of the sensor equipped with cylindrical electrodes. Even if the geometric dimensions are now optimized, we want to evaluate the influence of materials that are less costly than copper but preserve the same electric characteristics as copper.

Identified materials are zinc, bronze, tin or their alloys. To conduct this study, partnership with the company Gilbert SA made it possible to produce several prototypes that we evaluated with an impedance analyser. It should be noted that, in the absence of the exact composition of alloys (for reasons of confidentiality), we have not carried out simulations with the final elements. Figure 6 shows measurement results obtained.

Figure 6. Capacity of different materials as a function of moisture

In Figure 6, we can see that copper, zinc and zinc-bronze-tin are suitable for the fabrication of electrodes. Nevertheless, in view of the steam fabrication process, copper, in spite of its higher cost, is the easiest to work with. It turns out, also, that the deposit process is more reliable for the fabrication of the electrodes. This explains why the metal electrodes of the transducer will be made of copper.

Toward new shapes with higher performance

With the cylindrical shape having been optimized from a geometric as well as a technological point of view, we now focus on a more complete optimization of the sensitivity and/or the volume of the probed soil. To do so, we propose to optimize the electrodes' shape factor.

New sensor shapes

The first parameter to optimise is sensitivity. Knowing that this parameter depends on the contact surface between the soil and the electrodes, it would seem to make sense to increase the contact surface. But in order to stay within initial cost limitations, the useful surface of the electrodes cannot be augmented. It must be distributed differently along the full length of the sensor. The conceptual idea that we defend consists of spreading the electrodes longitudinally around the cylinder by shaping them into a double helix (Figure 7). This approach is directly inspired by the strands of DNA. The second parameter to optimise is the volume of soil probed. Knowing that this parameter depends on the paths of the transducer's field lines, optimization depends on augmenting these paths. In practice (Figure 8), we distribute the electrodes in the shape of branches on the periphery of the cylinder, placing them diametrically opposite each other. The sensor with vertical ribbons (Figure 8) is equipped with two electrodes broken down into three ribbons, a main one in the centre and two 110mm lateral ones, for a total copper surface of 2670mm².

Determination of volume of soil probed

Simulation results confirm that the field created by the helicoidal sensor (Figure 7) is more uniform than that generated by the cylindrical shape. Assuming that the soil probed is traversed by an electric field of at least 50V/m, the helicoidal transducer probes a volume of 0.277L as opposed to 1.13L for the cylindrical shape. This decrease is subsequent to the division of the contact surface with a consequent reduction in the paths of these electric fields. As for the sensor with branches (Figure 8), its range of action is greater compared to the preceding shape. The volume of soil probed reached 1,737L, or six times more than with the helicoidal framework, as well as 1.5 times more than the initial structure (cf. §2). This, therefore, is the new shape factor that permits soil testing on a larger scale.

To best illustrate the evolution in terms of electrical sensitivity, Figure 9 presents simulation results for the different sensors: cylindrical, double helix and with branches. Sensitivity of the double helix shape is 67% higher, with a sensitivity of 0.4417pF.% -1 compared with 0.265pF.% -1 for the cylindrical sensor. Moreover, response linearity is much better. The transducer obtained is, therefore, more sensitive for an equivalent cost. For the sensor with branches, sensitivity also is improved --by 0.7188pF.% -1 or 171%. Nevertheless, the response obtained is not linear throughout the entire measurement. The graphic (Figure 9) shows two linear zones before and after 27% moisture in the soil. Electronic treatment will require two reading equations.

Choice of final shape

Table 2 reflects the characteristics of the three sensors studied. The overall performance of the sensor with branches stands out.

Table 2. Summary of sensor shape characteristics

The sensor with branches is not only more sensitive, it also registers better soil volume. Clearly, its response is not linear, but this can be easily corrected with suitable measurement electronics.

This shape is, therefore, the most suitable for our study. Nevertheless, in terms of industrialisation, this shape also is the costliest due to the discontinuous character of the electrodes. Manufacturers agree that the cost of fabrication is two times higher, compared to cylindrical or helicoidal shapes.

Economic considerations therefore prevailed over performance in the choice of a helicoidal shape for the sensor. Given the sensor's macroscopic capacitive behaviour as a function of moisture in the soil, this analysis (Figure 10) is necessary to identify the useful measurement frequency ranges.

Modelling the helicoidal-shaped sensor

Figure 10. Sensor capacity as a function of the frequency

Figure 10 shows that:

• Capacity variations are inversely proportionate to moisture in the soil, which confirms theoretical functioning.

• As expected, capacity platforms at about 15MHz.

• Beyond this frequency, the inductive parasitic effect is no longer negligible. This demonstrates that beyond 15MHz, it becomes difficult to devise an exploitable electronic conditioner. Measurements are carried out below this frequency.

Since the greatest variances in capacity as a function of moisture fall between 1MHz and 15MHz, a working frequency close to 8MHz was chosen for the electronic conditioner.

Would it now be possible to endow the sensor with a second aptitude, so that it could measure salinity in the soil, depending on the possibility of finding a second frequency interval that would be sensitive to variations in soil salinity? To this end, we now install a measurement protocol analogous to the moisture measurement. Capacity is measured on a frequency ranging from kilohertz to around ten megahertz (Figure 11).

Figure 11. Sensor capacity as a function of the frequency for different levels of salinity

We observe that for frequencies higher than 4MHz, salinity has no influence on the capacity of the sensor. This means that the moisture measurement of the sensor is not influenced by the salinity of the soil, which makes the measurement independent. But below 4MHz, capacity increases with salinity. Yet, capacity does not depend on the measurement frequency as it does for the moisture

Integration effect

For reasons of mechanical protection, we have studied the effect of plastic coating on the sensor.

Figure 13 provides a zoomed view of a cross-section of the sensor. This cross-section localises the coupling capacity between electrodes, coating and soil.

Figure 13. Effect of plastic protection on the sensor

Two supplementary pathways generated by the moulding can be observed:

• First, field lines close to the sensor only traverse the plastic and not the soil. This creates parasitic capacity where the dielectric is the plastic coating. Since this plastic is hermetic, its parameters are independent of moisture.

• Second, far-off field lines traverse the soil but also must traverse a layer of plastic coating which produces a series of parasitic capacity in addition to soil measurement capacity.

The transducer system may then be modelled as coated, according to the equivalent electrical diagram presented in Figure 14. • Parallel Cplastic capacity that adds to the Chumidity measurement capacity.

• A Chumidity measurement capacity that is altered by two parasitic capacities Cparasite. that end up in serial association with capacity Cparasite/2. This new measurement capacity turns out to be inferior to that of a non-integrated sensor.

Figure 15 shows the influence of the moulding on the sensitivity of the sensor. • The curve of the moulded transducer is superior in every way. It reflects the increase in C'hum0, estimated at 14.7pF.

• Sensitivity is reduced by 12% with an estimated value of 0.3875pF.% -1 , a value always measurable by our system for a relative variation of 1% in moisture.

It should be remembered that the salinity measurement is affected on the same precise order of grandeur as that of moisture. As of an impedance of 2.3kΩ at a frequency of f=35kHz, the curves are almost the same, then, as of f=400kHz, the curves are absolutely the same. Since useful frequency ranges are well above f=35kHz, the electric model for the sensor can be considered validated.

Equivalent electric models for sensors

Measurement electronics

Architecture

The architecture that we have developed breaks down into two distinct parts (Figure 20). The first part is the front end. It permits the conversion of the sensor's capacity variations into one electric variation that is exploitable. Bearing in mind the frequency of readings and the low cost of the final system, the sensor is placed in a Colpitts oscillator to allow a capacity conversion frequency that depends on moisture or salinity. Since sensor must be able to perform two measurements, we decided to use two different oscillators set at fosc= 8MHz for moisture and at fosc=500kHz for salinity.

The back end, or second part of the architecture, delivers readings of the variations. To this end, the back end is structured around one microcontroller embedded with a frequency metre algorithm dedicated to double measurement of a frequency. To minimise the effect of temperature on the measurement, the microcontroller is equipped with a TCXO-type precision clock. To reduce the cost of the system, this microcontroller's frequency performances are voluntarily limited, which explains why the frequency is divided. Once this electronic treatment is accomplished, the back end proposes two types of complementary outlets, an analogue outlet that makes it possible to deliver voltage proportionate to moisture or to salinity with the aid of a CAN and a digital outlet that can be configured to establish a communications link with a standardised protocol (slave SPI).

Material integration

In the process of industrial production of the sensor, the sensor tube will be manufactured according to an industrial procedure. The first stage consists of devising a cylindrical support tube.

Then, the electrodes are produced according to photolithography and by electrochemical deposit of copper on a surface that has been made functional by a laser. Finally, a nickel/gold layer is deposited to protect the copper from oxidation. Figure 21 presents the finished sensor produced by this process.

Figure 21. Shape of the industrially produced sensor

To control the thickness of the metallic deposit, measurement by optical profilometer is carried out.

Readings of these measurements are presented in Figure 24. • On the left of the graphic we can see the plastic tubing. It serves as reference to measure the height of the electrodes;

• On the right, there is the measurement of the average height of the metallic deposit: 24µm (20µm Cu, 4µm NiAu).

Since the sensor is to be inserted in the soil, it needs to be mechanically solid so that it is not damaged during its installation. As for the electronic board (Figure 25 • Data then goes through the other network nodes that could be concentrators used in repeating mode or weather data collection points that also could serve as the bridge.

• Data finally arrive at a base station connected to the Internet, where information is stored on an on-line server. From then on, the user can consult the data by means of a web interface or mobile application.

Longitudinal moisture measurements

After the system is installed and deployed in cultivated and irrigated fields, moisture monitoring performance is compared to that of two major players in the market: Decagon and Sentek Technologies. As this work continues, the sensor that we have developed is called IRRIS for IRRIgation Ingénierie Systèmes. The greater sensitivity of the IRRIS sensor is noticeable. As soon as the presence of water is detected by the IRRIS sensor, the moisture measurement increases, while the Decagon sensor does not detect this presence of water until after a few hours (red arrows). Detection, therefore, is better with the IRRIS sensor. The rising dynamic (+20%) and the descending dynamic (-2% per day) are identical for the two sensors, which validates the good performance of our sensor on this piece of agricultural land.

The second study addresses the surveillance of a corn field. Measurement readings reflect several days of continuous surveillance because of an installation made at the end of a cultivation cycle before the lot is harvested. Figure 28 presents results obtained. The last test is conducted with a Sentek sensor in another corn field. Figure 31 presents the results.

Figure 29.

Sensor results compared with the Sentek sensor in a corn field IRRIS sensor dynamics resemble those of the Sentek sensor. A measured rise in moisture after a supply of water followed by a slow descent on the scale may be clearly observed. What's more, this graphic shows the evapotranspiration effect. In fact, during a day/night cycle, it possible to observe a characteristic oscillation that displays this phenomenon. The IRRIS sensor also measures the phenomenon, which validates its performance.

To conclude on these tests, comparative response curves for the IRRIS sensors and the industrialised sensors attest to the superior performance of the IRRIS sensor. In this paper, we have shown that it is possible to detect small amounts of water more rapidly. This work clearly demonstrates the possibility of following these dynamic variations of moisture in the soil, when water is being supplied, as well as when the soil is drying out due to lack of water.

Conclusion

The sensor therefore is capable of measuring moisture and salinity in the soil for different types of crops. Thanks to its cylindrical shape, the sensor may be installed easily in the soil, and its different outlets (analogous wire, digital with or without wire) allow for a direct connection on most existing systems. Moreover, with a cost of fabrication estimated at less than 50€ per unit, its price makes it possible to multiply measuring points to better chart the hydric state of cultivated soil.

Figure 3 .

 3 Figure 3. Density of electric field around cylindrical sensor

Figure 4

 4 Figure 4 present results obtained:

Figure 4 .

 4 Figure 4. Capacity of different-sized electrodes as a function of moisture

Figure 5 .

 5 Figure 5. Optimized shape of first design

Figure 5 . 6 .

 56 Figure 5. Sensor in the shape of a helicoid Figure 6. Sensor shape with "vertical ribbons"

Figure 7 .Figure 8 .

 78 Figure 7. Electric field density around helicoidal sensor Figure 8. Electric field density around sensor with branches

Figure 9 .

 9 Figure 9. Capacity of different electrode shapes as a function of sensitivity to moisture

Figure 14 .

 14 Figure 14. Model of the integration effect on the sensor

Figure 15 .

 15 Figure 15. Moulded and unmoulded sensor sensitivity as a function of humidity

  Since sensor capacity is not perfect, we want to quantify the ESR, ESL and Celectrodes imperfections of the equivalent model. The Equivalent Series Resistor (ESR) is the resistance that materialises contact between the two electrodes, with a measured value of ESR = 105mΩ. Equivalent Series Inductance (ESI) consists of the connecting wires that induce the inductive behaviour beyond 40MHz. Measurements show that ESL = 60µH. Finally, inter-electrode capacity is equal to Celectrodes = 5.18fF. Figure 16 reflects this model.

Figure 16 .Figure 17 .Figure 18 .

 161718 Figure 16. Electric model of the sensor

Figure 19 .

 19 Figure 19. Validation of the sensor model by electric simulation

Figure 20 .

 20 Figure 20. Functional diagram of measurement electronics

Figure 22 .

 22 Figure 22. Electrode deposit profile

  Figure 23. (a) Photo of the measurement electronic board; (b) Photo of the connection between the board and the sensor tube

Figure 24 .

 24 Figure 24. Photo of the industrially moulded sensor

Figure 25 .

 25 Figure 25. Architecture of sensor network

Figure 26 .

 26 Figure 26. Photo of the electronic board produced

Figure 27

 27 Figure27presents measurement readings in an orchard that is cultivated all year round. Data from the IRRIS sensor shown on the graphic reflect three weeks of surveillance and are compared with that of the Decagon sensor.

Figure 27 .

 27 Figure 27. Results of a sensor in an orchard

Figure 28 .

 28 Figure 28. Sensor results in a corn field

  and

	pF
	Capacity,
							Ø 40mm
							Ø 20mm
	0%	10%	20%	30%	40%	50%	60%	70%
				Soil moisture, %

Table 1 .

 1 New electrode dimensions

Acknowledgments

This work was done within the framework of the IRRIS project which is funded by the French Midi Pyrenees council and the French Ministry of Agriculture. Many thanks are due to TCSD (TelecommuniCation Service & Distribution) who lead the project and helped us to deploy our system into actual agricultural exploitation. We would thank Gilbert SA for their industrial support and their advices for the mechanical integration.

Acknowledgments:

We thank all the technical team of the LAAS-CNRS for all their support.

Conflicts of Interest:

The authors declare no conflict of interest.

Author Contributions: C.E., J.Y.F and J.R. conceived, designed and performed the experiments; C.E. and J.R. analyzed the data; J.Y.F administrated the project; C.E. and J.R wrote the paper.


Marwan Ghanem

Clémence Magnien

Fabien Tarissan

Cl Émence Magnien

Centrality metrics in dynamic networks: a comparison study

Keywords: centrality, network dynamics, temporal paths, node importance !

HAL is

INTRODUCTION

Scientists studying complex networks have been interested for a long time in the question of evaluating the importance of a node. This has led to the introduction of several measures of importance, such as for instance degree, closeness or betweenness centrality, Eigenvector centrality or Katz centrality, or PageRank.

Many centrality measures are based on the study of paths in the network. In this approach, a node will be important if the paths from it to other nodes are short in average, or if it lies on the shortest paths between several pairs of nodes. One motivation is that links can act as a dissemination medium for an information spreading on the network. For instance, individuals can exchange information when they communicate, or a message can be forwarded from computer to computer until it reaches its destination.

Researchers started to focus on static networks first as they represent many real-world situations, such as protein interaction networks or food chain networks, among others. However, other cases of interest include temporal aspects, such as email exchanges between individuals occurring at different points in time. Such networks were first analyzed and modeled statically for the sake of simplicity but this representation induces a strong loss of information. Indeed, in the case of path based centralities, the order of links is completely lost and paths that do not respect time exist in the time-aggregated version of a dataset. To observe this, consider the toy example of Figure 1. This small network composed of five nodes evolves during four distinct time steps. By discarding the temporal aspect and aggregating all links into a single network, we can observe that a path from a to e exists although no transmission between a and e is possible in the temporal network.

This has led to a stream of works aiming at understanding and modeling these dynamics. In particular, in the case of centrality, some works have been concerned with efficiently updating the centrality values of the nodes when a change occurs in the network. In many cases however, the time scale at which the network evolves is the same as the one at which a dissemination phenomena may occur on the network. This is the case for instance when a disease propagates among individuals when they are in contact, or when information is disseminated by emails.

One very important point concerning centrality in dynamic networks is that while paths change during the network time span so does the importance of nodes. Consider again the toy example of Figure 1. One can see that, intuitively, the importance of node b is stronger at time t = 1 than at time t = 3. Indeed, at time t = 1 it forms a bridge between node a and nodes c and d, thanks to the link that exist at t = 2. This is in contrast with its situation at time t = 3 where it cannot be used as a relay anymore.

Several works have introduced extensions of centrality notions for the case of dynamic networks. In this paper, we study four such extensions proposed in the literature. We compare these extensions on several datasets from which we conclude that:

1) perception of the importance of a node strongly depends on the centrality metric used, raising the question of the desired characteristics of a dynamic centrality metric; 2) the dynamic of the network might be such that it is meaningless to identify nodes which are more important than others; 3) metrics react differently to the different natures of datasets; 4) a node can be inactive (i.e. not have any links) at a given time, yet be highly important as it may serve as a relay for future communications.

This work is organized as follows. First we present in Section 2 the existing work related to the notion of centrality in static and dynamic networks. We present in details the four methods we study here in Section 3, before providing our methodology of comparison in Section 4. We present the datasets we use for the comparison in Section 5 and the results we obtained in Section 6 before concluding the paper in Section 7.

RELATED WORK

Many papers have studied the importance of nodes in static networks, i.e. networks that don't evolve with time. Among the metrics that have been introduced, one may cite the degree centrality, closeness centrality [START_REF] Bavelas | Communication patterns in task-oriented groups[END_REF], betweenness centrality [START_REF] Linton C Freeman | A set of measures of centrality based on betweenness[END_REF] and the Katz [START_REF] Katz | A new status index derived from sociometric analysis[END_REF] and eigenvector centralities [START_REF] Bonacich | Power and centrality: A family of measures[END_REF], [START_REF] Newman | Networks: an introduction[END_REF]. Closeness and betweenness centralities are based on shortest paths, while the Katz centrality takes into account paths of all lengths between two nodes. Some papers which have studied dynamic networks have been concerned with efficiently computing the static centrality at all times. For instance, Kas et al. [START_REF] Kas | Incremental closeness centrality for dynamically changing social networks[END_REF] propose an algorithm that, given distances between all pairs of nodes and given a network change (edge appearance of disappearance), computes the new centrality measure by updating the distance values rather than computing them all from scratch again. This is relevant, e.g. in contexts where the network evolves at a much slower scale than the one on which a dissemination takes place.

One of the first methods attempting to account for the evolution of temporal networks is the snapshot method. In this approach, the network timeline is divided into several periods, and all nodes and links that exist in this period are aggregated into a snapshot network; each snapshot is then analyzed separately using a static metric. Uddin et al. [START_REF] Uddin | Topological analysis of longitudinal networks[END_REF] propose a framework that, given a static centrality measure, computes it for each period. This method proves to be better than a static analysis. Another approach [START_REF] Shahadat Uddin | A set of measures to quantify the dynamicity of longitudinal social networks[END_REF] studies the dynamicity of nodes. The authors introduce two metrics which quantify the change in importance and presence of a node in a dynamic network. This approach is subtly but really different from a study of the time evolution of a node's importance. Braha et al. [START_REF] Braha | Time-dependent complex networks: dynamic centrality, dynamic motifs, and cycles of social interaction[END_REF] also use the snapshot approach. However, in addition to detecting important nodes, they detect cycles as well. Similarly Tang et al. [START_REF] Tang | Analysing information flows and key mediators through temporal centrality metrics[END_REF] consider the same aggregation while keeping the edge order in each snapshot. They are thus more accurate as they only take into account paths that are temporally possible. All in all, the inconvenience of these aggregation variants remain: each centrality value represents the centrality for a period rather than an exact instant, leading to information loss.

In many contexts, the dissemination phenomenon in the network happens on the same time scale as the network evolution. It then becomes necessary to consider temporal paths [START_REF] Bui-Xuan | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF], [START_REF] Kumar | Path lengths, correlations, and centrality in temporal networks[END_REF], i.e. link sequences that are time-respecting. For instance, in the dynamic network of Figure 1, there is a temporal path from node a to node c going through the link (a, b) at t = 1 and the link (b, c) at time t = 2.

Several definitions of temporal paths have been studied in the literature. Some of them can be computed more easily than others. Whitbeck et al. [START_REF] Whitbeck | Temporal reachability graphs[END_REF] propose an efficient algorithm to approximate the existence of paths in the most difficult case and show that the notion of reachability (i.e. which nodes can be reached from which nodes, and at which times in the network's time span) provides enlightening insight on the network's dynamics.

Notions of centrality taking into account temporal paths have also been introduced. Nicosia et al. [START_REF] Nicosia | Graph metrics for temporal networks[END_REF] introduce the notions of temporal closeness and betweenness centralities. However, their definition of a shortest path considers only paths whose starting point is at the beginning of a dataset's time span.

Scholtes et al. [START_REF] Scholtes | Higher-order aggregate networks in the analysis of temporal networks: path structures and centralities[END_REF], [START_REF] Scholtes | Causality-driven slow-down and speed-up of diffusion in non-markovian temporal networks[END_REF] introduced another approach to take into account all temporal paths. They introduced a higher order aggregation where each node represents a possible temporal path. In addition, they introduce several temporal centrality definitions, including a temporal centrality that represents a node's importance at each instant, which is, however, too costly to compute except for small examples.

Another approach consists in depicting the dynamic network as a static network [START_REF] Takaguchi | Coverage centralities for temporal networks[END_REF], [START_REF] Ser-Giacomi | Most probable paths in temporal weighted networks: An application to ocean transport[END_REF], by creating one copy of each node for every instant, and linking two consecutive copies of the same node by a (directed) link. This representation allows to consider temporal paths while using classical centrality metrics. However, using this representation is computationally expensive and remains unfeasible particularly for highly active datasets.

Various other propositions acknowledge that the distances between nodes, and therefore, nodes' importance, vary with time [START_REF] Braha | Time-dependent complex networks: dynamic centrality, dynamic motifs, and cycles of social interaction[END_REF], [START_REF] Kumar | Path lengths, correlations, and centrality in temporal networks[END_REF], [START_REF] Shamma | Tweet the debates: Understanding community annotation of uncollected sources[END_REF], [START_REF] Kim | Temporal node centrality in complex networks[END_REF], [START_REF] Alsayed | Betweenness in time dependent networks[END_REF], [START_REF] Matthew | Spatio-temporal networks: reachability, centrality and robustness[END_REF]. However, in practice, they still represent the varying importance of a node by a single value that is supposed to represent its overall importance throughout the network global time span.

Several papers introduce and study variants of the Katz or eigenvector centralities [START_REF] Laflin | Discovering and validating influence in a dynamic online social network[END_REF], [START_REF] Praprotnik | Spectral centrality measures in temporal networks[END_REF]. Among those, Lerman et al. [START_REF] Lerman | Centrality metric for dynamic networks[END_REF] acknowledge the fact that a node's importance may evolve with time, but no systematic study is conducted. Moreover, their variant relies on parameters defining what is to be considered as relevant path lengths and path duration, which complicates the analysis. Fenu et al. [START_REF] Fenu | Block matrix formulations for evolving networks[END_REF] explore the different methods for representing a dynamic network as a block matrix where each column/row corresponds to a pair composed of a node and a time instant. They propose a method to construct such a block matrix that allows to compute dynamic centrality metrics in an efficient way. Taylor et al. [START_REF] Taylor | Eigenvector-based centrality measures for temporal networks[END_REF] introduce such a block matrix (that they call supra-centrality matrix) and study the corresponding eigenvector centrality.

Finally, Costa et al. [START_REF] Costa | Time centrality in dynamic complex networks[END_REF] notice that not all time instants are equivalent in a dynamic network, and introduce the notion of time centrality. This measures how fast a dissemination process can reach a significant portion of the nodes at a given time t. However, this notion is global and does not describe the importance of individual nodes in the dissemination process.

All in all, several papers acknowledge the fact that the temporal evolution of networks impact the value of centrality measures and propose variations of standard metrics to account for the dynamics. However, and to the best of our knowledge, very few analysis of the difference between these methods have been performed. This paper intends precisely to contribute in this direction, by comparing four different methods that evaluate the importance of a node based on different criteria.

TEMPORAL CENTRALITY DEFINITIONS

In this section we present the four methods that we will compare in the rest of the paper.

Temporal Closeness

The first method was previously presented in [START_REF] Magnien | Time evolution of the importance of nodes in dynamic networks[END_REF]. A dynamic network G = (V, E) consists of a set V of nodes 1 and a set E of timed links of the form (u, v, t) where u, v ∈ V and t is a timestamp. Throughout the paper we consider networks as undirected, i.e. a link (u, v, t) is equivalent to a link (v, u, t).

A temporal path in a dynamic network consists of:

• a starting time t s , and

• a sequence of links (v 0 , v 1 , t 0 ), (v 1 , v 2 , t 1 ), . . . , (v k , v k+1 , t k )
such that:

1) for all i, i = 0..k -1, t i < t i+1 , 2) t 0 > t s .

We say that such a path is a path from v 0 to v k+1 starting at time t s . Its duration is equal to t k -t s . We say that a path from u to v starting at time t s is a shortest path if it has the least duration among all paths from u to v starting at time 1. We assume that the set of nodes does not evolve with time.

t s . We define the (temporal) distance from u to v at time t s to be the duration of a shortest path from u to v starting at t s , and we denote it by d ts (u, v). If there is no path from u to v starting at time t s , we consider that d ts (u, v) = ∞.

Note that a path starting at time t s might imply waiting times at all nodes, including the first one, in the same way that a person starting a train trip with connections at a given time must wait for the train in the first station, and then at each connecting station.

If we consider the dynamic network of Figure 1, there is a temporal path from b to d starting at time t = 1. The path consists of the links (b, c, 2) and (c, d, 4) and its duration is 3. The temporal distance from b to d at time 1 is therefore d 1 (b, d) = 3 (there is no path that starts at time 1 and arrives earlier).

We recall that the closeness of a node u in a non-evolving network is defined as [START_REF] Bavelas | Communication patterns in task-oriented groups[END_REF]:

v =u 1 d(u, v) ,
where d(u, v) is the classical graph distance.

Similarly, we define the temporal closeness of a node u at time t as:

C t (u) = v =u 1 d t (u, v) .
Note that the strict definition of C t (u) requires to compute the value for each time instant t. For obvious computational reasons (one of the dataset we use in this study is a record spanning 3 years), we only compute the temporal closeness for each node every I seconds. The value of I is equal to the median of inter-link duration (i.e. the time separating two consecutive links) 2 . We argue that this fixed frequency is precise enough to get an accurate information when compared to computing the temporal closeness at every second.

Closeness Snapshot

The second method was proposed by Uddin et al. [START_REF] Uddin | Topological analysis of longitudinal networks[END_REF]. In this framework, a temporal network G t is represented as a sequence of static networks (snapshots), each to be analyzed separately. Each static network is the aggregation of all the links in a given period and all the snapshots represent periods of equal duration. Given a static centrality measure for each snapshot (such as the classical definition of closeness), the framework computes this centrality for all nodes.

Note that for the comparison with the temporal closeness presented above, we consider the closeness value of a node is the same every I seconds in a given snapshot. We denote this method by SnapshotCl.

Temporal Eigenvector

The third method was presented by Taylor et al. [START_REF] Taylor | Eigenvector-based centrality measures for temporal networks[END_REF]. They represent temporal networks as a supra-centrality matrix of size N T × N T , where N is the number of nodes and T is the number of considered time periods. This matrix contains one static centrality matrix (for example an ordinary 2. The program we used to compute the metrics is publicly available [START_REF]Source code for the temporal centrality metrics[END_REF]. adjacency matrix for the eigenvector centrality) for each time period. These matrices are placed on the diagonal of the supra-centrality matrix. Other links are added to couple these centrality matrices with each other. The dominant vector of this supra-centrality matrix would give the centrality for each node i at each time t.

A > B = C = D = E > F centrality Relation
In the following, we call this method Temporal Eigenvector. We will consider that each period has a duration of I seconds.

Coverage Centrality

The fourth method was presented by Takaguchi et al. [START_REF] Takaguchi | Coverage centralities for temporal networks[END_REF]. It represents a temporal network as a static network where each temporal node consists of a pair composed of a node (of the original network) and a time instant. Consecutive pairs of the form (u, t 1 ) and (u, t 2 ) sharing a same node u are linked, and temporal links between nodes u and v at time t are represented by two links: one from (u, t) to (v, t + 1), and the symmetric link. This allows to represent temporal networks statically while keeping the temporal order between the links. Building on this representation, the authors introduce two centrality notions. First, temporal coverage centrality represents the importance of a temporal node (u, t) by the fraction of pairs of nodes for which a shortest path passes through the node (u, t). A variant, called temporal boundary coverage centrality, has been defined. In this study, we only consider the temporal coverage centrality. Preliminary results, however, revealed that both centralities behave quite similarly on our datasets.

COMPARISON

The four approaches described in the previous section propose very different ways to quantify the importance of a node in a dynamic network, thus making it difficult to directly compare the raw values. In the rest of the paper we will therefore rely on the following additional steps to compare the methods.

Ranking

Evaluating the importance of a node with respect to the others by considering only its centrality value is difficult. Therefore, in order to obtain an intuition on the node's relative importance, we rank them at each time step with respect to their centrality values. We chose the inverse competition ranking method. In this ranking, the ranking 0 is attributed to the least central nodes, and the ranking of every node is equal to the number of less central nodes. Consider the example in Figure 2, which consists of 6 nodes with their centrality relationship in addition to their attributed ranks. The ranking 0 is attributed to F which is the least central node, while nodes B, C, D and E share the same ranking 1 as they are all equally important. Finally, A is ranked 5.

We will use this ranking approach to compare properly the results of the different methods.

First, given two rankings obtained by two different methods for the same network at the same time step, we can compute their correlation as defined by the Kendall-Tau coefficient. This coefficient has a value in [-1, 1] that represents the level of concordance between the two ranking lists. 1 stands for a perfect correlation while -1 stands for a perfect negative correlation. More precisely, we compute the difference between the number of concordant and discordant pair of nodes between the two lists, a concordant pair of nodes being a pair for which the two nodes have the same relationship in both ranking lists. So a pair (u, v) is said to be concordant if either u is ranked higher than v in both ranking lists, or u is lower than v in both ranking lists, or u has the same ranking as v in both ranking lists. We then normalize this value by the number of pairs in order to obtain a final value between -1 and 1. We compute this correlation at each instant to study its evolution over time.

Second, while it is interesting to know how much the rankings obtained by different methods differ globally, this does not provide any intuition on the difference of importance attributed to any given node in particular. In order to deepen our understanding, we will therefore also compute for every node the difference between the two ranks. A high difference thus indicates that the two rankings have a strong divergence regarding the importance of the considered node, while a value close to 0 indicates that they both agree on its relative importance in the network. We will study the distribution of the rank difference over all pairs consisting of a node and a time instant.

Global importance

In order to provide a more comprehensive and global perspective of the importance of all nodes at each time instant, we will study the number of times any given node is attributed a high (or low rank). The idea is that a node that is consistently assigned a high rank is evaluated as globally important. More formally, we define two regions, which we call top and bottom, representing respectively the top 25% ranks and the bottom 25% ranks. Considering a network of n nodes, a node with a ranking higher than n * 0.75 is therefore considered to be in the top region while a node with a ranking lower than n * 0.25 is considered to be in the bottom region. This allows to detect immediately which are the nodes of high or low global importance in a network 3 .

Finally, we compute for each node the total duration spent in each region and we denote it by Dur top (resp. Dur bot ). To compute these durations, we consider that a node is present in the top or bottom region from the instant where we compute the centrality to the next computing instant: given a node u ∈ V , if R(u) = (r i ) i=1...k is the sequence of ranks (computed at instants i = 1..k) for u, we define Dur top (u) and Dur bot (u) as :

Dur top (u) = I • |{i ≤ k -1, r i ≥ n * 0.75 }| , Dur bot (u) = I • |{i ≤ k -1, r i ≤ n * 0.25 }| .
3. it is worth noticing that, because the inverse competition ranking may assign the same ranking to several nodes, these regions may contain more than or less than 25% of the nodes.

DATA SETS

In order to compare and understand the differences between the different methods, we study several datasets coming from different contexts and presenting different characteristics:

• Enron [START_REF] Shetty | Discovering important nodes through graph entropy the case of Enron email database[END_REF]: this dataset contains the 47 088 emails that 151 Enron employees exchanged during approximately three years. It records information on the senders, receivers, and the moment they were sent.

• Radoslaw [START_REF] Michalski | Matching organizational structure and social network extracted from email communication[END_REF]: this dataset contains 82 876 emails exchanged by 168 employees of a mid-sized company during a period of nine months in 2010. It records information on the senders, receivers, and the moment they were sent.

• Rollernet [START_REF] Ugo Tournoux | The Accordion Phenomenon: Analysis, Characterization, and Impact on DTN Routing[END_REF]: this dataset was collected during a rollerblading tour in Paris in August 2006. The tour is a weekly event and gathers approximately 2 500 participants. Among these, 62 were equipped with wireless sensors recording when they were at a communication distance from one another. The total dataset duration is approximately 2 hours and 45 minutes (note that there is a break of approximately 30 minutes during the tour).

• Twitter (HashTags): A 22 day long twitter dataset generated by twitter accounts known to be associated with terrorist groups. Each node represents a hashtag, while each link represents a tweet that contained the two hashtags. Thus, a tweet with several hashtags generates several links. The dataset contains 3 048 hashtags and 100 429 links.

• Twitter (Retweets): From the same twitter dataset, we extracted a subset of 27 919 re-tweets generated by the 10 484 twitter accounts. Each link (u, v, t) represents a user v re-tweeting a tweet of user u at time t.

• Facebook [START_REF] Viswanath | On the evolution of user interaction in facebook[END_REF]: this dataset is a 1 year long record of the activity of Facebook users between 31st of December 2015 and 31st of December 2016. The dataset contains 8 977 Facebook users and their 66 153 posts to each other's wall on Facebook. The nodes of the network are users, and each link represents a user writing on another user's wall.

In all cases, we consider that links are undirected. In order to apply the snapshotCl method on these networks, we need to choose a snapshot duration. Choosing the appropriate value is in general a difficult question as this impacts the obtained results [START_REF] Sulo | Meaningful selection of temporal resolution for dynamic networks[END_REF], [START_REF] Uddin | The optimal window size for analysing longitudinal networks[END_REF], [START_REF] Léo | Non-altering time scales for aggregation of dynamic networks into series of graphs[END_REF]. We chose the value that gave a good compromise between a low loss of temporal information (i.e., a low aggregation and hence a small snapshot duration) and a sufficiently high number of active nodes, so each snapshot contains relevant information. We show that the choice of the snapshot duration has little impact on our observations in Section 7 and in the supplementary material.

The main global characteristics of these datasets, including the chosen snapshot duration, are presented in Table 1. In the rest of the paper, for the sake of brevity and because the observations on some datasets are similar, we will only present the results on three of the datasets: Enron, RollerNet, and Twitter (HashTags). Before comparing the methods, it is enlightening to make some global observation related to the dynamic of the three networks.

For each dataset, we computed the proportion of active nodes in a snapshot (i.e. the fraction of nodes having at least one link during the corresponding period). Figure 3 shows the time evolution of this value for the three datasets. In the Enron case, the proportion increases slowly to a maximum of 80% before dropping drastically at the very end. In the RollerNet case, the proportion of active nodes increases rapidly and remains very close to 1 until the end. Finally, in the Twitter dataset, we can see that the activity is extremely low compared to the two other datasets, with only very few nodes active in each snapshot. Thus, those three cases present very different characteristics in terms of activity. We conjecture that this has a strong impact on the way node's importance is perceived by the different methods. We will investigate this question in the next section.

RESULTS

In this section, we compare how the different methods presented in Section 3 quantify the importance of nodes in a dynamic network. We start by analyzing the global difference between the methods (Section 6.1) before evaluating how this difference impacts the relative importance of individual nodes (Section 6.2). Finally, we compare which nodes are identified by the methods as globally important over the whole period of time (Section 6.3).

Note that temporal closeness, snapshotCl and temporal eigenvector have been computed for all datasets but the coverage centrality was too computationally expensive to be used on another dataset than Enron.

Global observations

We start by comparing temporal closeness with snapshotCl. Figure 4 presents the evolution of the Kendall-tau correlation between the rankings provided by the two methods for the three datasets. For Enron (Figure 4, top), the correlation is low at first and then increases over time. At the beginning, a large number of nodes are inactive and snapshotCl attributes the lowest rank (0) to all of them. However, temporal paths involving links that appear later in the dataset exist from most of these nodes. Therefore, a non-zero value (and hence a non-zero rank) is attributed by the temporal closeness to these nodes. Naturally, as the network evolves, more nodes become active and are then taken into account by snapshotCl, which increases the correlation between the two methods 4 . The effect of inactive nodes spotted above is not restricted to the beginning of the evolution. One might notice for instance that the correlation drops suddenly at certain instants, even close to the end of the trace. Manual investigation revealed that this corresponds to moments where a significant number of nodes are temporarily inactive. This generates a strong difference between temporal closeness and snapshotCl for the same reason than above. We later on refer to such instants as temporary inactive moments.

Datasets

Finally, at the end of the evolution, the correlation reaches very high values; this is due to a large number of nodes inactive and ranked 0 by both methods, which makes it hard to have a high difference in the global rankings.

In contrast with the Enron dataset, if we now consider the RollerNet dataset (Figure 4, middle), we can see that the Kendall-tau correlation 1) fluctuates highly, 2) is globally lower, and 3) can even be negative at some instants. This observation is clearly related to the high activity of the nodes (see Fig. 3). This activity leads the networks of each snapshot to be much denser than in Enron. As we highlighted in Section 2, this makes snapshotCl more likely to consider paths that are temporally impossible, thus leading to divergence with temporal closeness.

Finally, we focus on the Twitter dataset (Figure 4, bottom). Since the dataset is the least active and contains mostly temporary inactive moments, the correlation is pretty low. At the beginning most nodes are inactive; the number of active nodes becomes significant only after the 14-th day. This is why the correlation starts to increase at that time. Finally, one can identify several periods of high correlation which are strongly related to periods with a high number of active nodes (see Figure 3).

We now turn to the comparison with temporal eigenvector. Figure 5 shows the evolution of the correlation between temporal closeness and temporal eigenvector for the three datasets. For Enron (Figure 5, top), the correlation fluctuates and globally increases with time, before dropping as the total activity drops (around the 1000-th day). This shows that both methods are only correlated when there is a relatively high activity. Interestingly, though we would expect the correlation to increase at the very end, as previously seen with snapshotCl, it actually decreases. If we now consider the Rollernet dataset (Figure 5, middle), we can see how the correlation fluctuates as seen previously. We notice that the correlation is quite low. This further indicates that both methods do not have the same notion of importance. Finally, for the Twitter dataset (Figure 5, bottom), we can see how the correlation is quite low and constant, with two peaks that correspond to a clear increase of the activity. This further shows that both methods produce different results when the activity is low. This is probably due to the observation made by Fenu et al. [START_REF] Fenu | Block matrix formulations for evolving networks[END_REF] that Temporal Eigenvector considers paths that do not respect time and can therefore go backwards in time. This explains why nodes that are permanently inactive at the end of the dataset can have a non-zero rank. We now turn to the coverage method. Figure 6 shows the evolution of the correlation between temporal closeness and coverage over time on Enron. One can easily notice that, except at the very end, the correlation is rather low during all the evolution of the network. Since coverage and temporal closeness both consider only time respecting paths, the divergence between the two rankings indicates that coverage captures another notion of importance in the dynamics, which we will discuss later. However, there is a noticeable increase at the end due to the very small number of nodes that are active at that time. This compensates for the difference in the definition of importance, as being active becomes enough to be considered important by both methods.

From this first analysis, we can conclude that the correlation between snapshotCl and temporal closeness is strongly related to the proportion of active nodes in the network. However, we provided evidence that snapshotCl has two strong limitations: when the nodes are inactive, it is unable to detect the importance that future connections give them; conversely, when many nodes are active, it considers many temporally impossible paths and therefore cannot quantify accurately the importance of the nodes. Though the temporal eigenvector and coverage methods do not have the same limitations, we have seen that they both detect different types of temporal importance compared to temporal closeness. We will investigate this further but it is worth noting that temporal eigenvector considers paths that may go backwards as well as forward in time.

Impact on individual nodes.

The previous section revealed that the four approaches generate significantly different rankings for the importance of nodes. This does not necessarily mean that the rank attributed to a given node is very different for two different methods. In order to study this aspect, this section analyses the difference in the ranks provided by the four methods for each node. More precisely, for each time instant and for each node, we compute the difference between the rank granted by temporal closeness and the one provided by either snap-shotCl, temporal eigenvector or coverage centrality. We then study the distribution of obtained values. We start by comparing the difference between temporal closeness and snapshotCl. Figure 7 (top) presents the inverse cumulative distribution of the difference of the ranks for each node at every instant, for the three datasets. For Enron and Twitter, the temporal closeness attributes a higher rank than snapshotCl in more than 70% of the cases. This is in agreement with the conclusions drawn in the previous section, and is mostly due to temporary inactive moments during which snapshotCl attributes a rank 0 to a node, while the temporal closeness ranks it higher. In contrast, for Rollernet which is a highly active network, the numbers of negative and positive values are more balanced. This is in contrast to what we observe when we compare temporal closeness and temporal eigenvector (Figure 7, bottom left).

Except a few values in Rollernet, both methods never attribute the same rank.

Finally, we consider the difference between temporal closeness and coverage centrality (Figure 7, bottom right). Interestingly, similarly to the comparison to the snapshotCl, temporal closeness tends to attribute higher ranks than coverage centrality (around 70% of the values). Since coverage centrality is not affected by temporary inactive moments, this indicates that the coverage method measures the importance differently.

In order to illustrate the differences between the four methods, figure 8 presents the evolution of the rank for a given node of Enron, for the four methods. We can observe that this node has many temporary inactive moments, corresponding to periods during which it snapshotCl rank is equal to 0. In contrast, temporal closeness takes into account future communications and therefore attributes a rank higher than 0 at those times. This is particularly remarkable between days 100 and 400. The links occurring around day 400 give it a high temporal closeness and hence a high rank not only at that time, but also influence previous times: even though the closeness at time, e.g., 300 is lower than at time 400, it is still high enough to warrant a significant rank for this node. This is again in sharp contrast with snapshotCl which perceives the node as unimportant for the whole period and clearly detects the role of the node only by peaks of activity. Manual investigation revealed that this phenomenon can be frequent: the fraction of time instants where temporarily inactive nodes have a high rank (≥ 0.75% of the nodes) represents 10% and 20% of the total in the Enron and Twitter cases respectively. As expected, this proportion drops to 1% in the case of RollerNet.

In the case of temporal eigenvector, although it can detect the importance of inactive moments, the ranks fluctuate extremely for no apparent reason. Quite interestingly, we observe in particular that, after the 1000-th day, although this node is no longer active, its rank still fluctuates and reaches at some points very high values. This confirms what we mentioned at the end of Section 6.1: the temporal eigenvector method considers paths that go backwards in time (otherwise it would give a rank 0 to this node). Even more strikingly, we see that the importance of this node evolves in a non monotonic way even though it doesn't have any activity. This indicates that this methods attributes centrality values in a non-intuitive way.

In regards to the coverage centrality, although it is difficult to conclude on its relevance, the rank evolution confirms that it captures a different notion of importance during temporarily inactive moments. One can see in particular that between days 400 and 500 the temporal closeness and coverage centrality evolve in opposite directions: the temporal closeness rank increases as the future links get closer, while the coverage rank decreases and drops to 0 after the links have occurred.

The observations presented above confirm and refine the conclusions drawn in the previous section: not only do the four methods give different global rankings, but they also have strong differences for individual nodes. Fig. 8: Time-evolution of the rank of a node in Enron.

Identifying globally important nodes

Although the results presented in the previous sections suggest that networks are highly dynamic and that nodes' importance varies over time, this does not mean that there are no nodes (or groups of nodes) that are globally important. Indeed, some nodes could stay important during a large period of the dataset. In this section we investigate how long each node is considered important (Dur top ) and unimportant (Dur bot ) by each method. Dur T otal ). This indicates that ranks in the middle region ( N * 0.25 < R < N * 0.75 ) are rarely attributed to nodes, which is well exemplified by the case presented in Figure 8. The behaviour is clearly different for temporal closeness that can attribute a wider range of values for the nodes. We also observe that, for temporal eigenvector, Dur top and Dur bot do not reach values as high as for the other methods. This can be an indication that the fluctuation seen in Figure 8 is a general phenomenon. Manual investigation showed that all nodes fluctuates in the same manner. Despite these differences, one can see on Figure 10 that the four methods tend to perceive similarly the global importance of nodes; the difference between the four approaches therefore lies mainly in how they evaluate unimportant nodes, as well as the nodes of average importance. Interestingly, these observations are completely different for RollerNet. In this dataset, one can see in Figure 11 that no node spends time in the top (or bottom) region more than half of the total duration, whatever the method used (except for one node that is almost always in the bottom region). Besides, when comparing the global importance attributed to nodes by different methods (evaluated by Dur T op , Figure 12), one can see that the correlation between temporal closeness and the other methods is not very strong and is even anti correlated with temporal eigenvector. All these observations are consistent with the fact that, in this dataset, there is no meaningful notion of global importance. We claim that this is due to the very dense (both temporally and structurally) nature of this dataset.

The Twitter dataset is also interesting as it combines the behaviours previously seen in Enron for the four methods.

Figure 13 shows that the comparison between Dur top and Dur bot is similar to what we observed on Enron, and even more extreme: for snapshotCl, points are all situated on the line y = T -x (where T stands for the total duration), meaning that at all times, any node is either in the top or the bottom region, but never in-between. Behaviours are more nuanced for the temporal closeness and, for temporal eigenvector, all the nodes have very similar values. This is similar to what we observed for Enron, but far more extreme. However, in contrast with Enron, the global importance (i.e. the Dur top value) attributed by temporal closeness is not at all correlated to the one attributed by the other methods (see Figure 14 5 ).

Finally, we study the results obtained for coverage centrality for the Enron dataset. We observe that coverage is close to snapshotCl in the sense that all nodes are always either in the top or in the bottom region (Figure 9, bottom right). However, as pointed out before, coverage does not capture the same notion of importance as temporal closeness, which can be seen by comparing the correlation between the Dur T op values (Figure 10 bottom). The elements provided in this study do not allow to conclude on the reasons of this divergence and we leave this question for further studies.

DISCUSSION

In this paper, we considered four centrality methods that quantify the time-evolution of nodes' importance. For the comparison of these methods, we performed several steps. This included ranking the nodes with respect to their centrality values, as well as computing a global duration that represents a node's global importance. Some papers [START_REF] Kim | Temporal node centrality in complex networks[END_REF] propose the study of the average over time of centrality rather than its evolution. They consider that this single value is representative of the node's complete evolution during a dataset.

To assess this claim, we propose to analyze the correlation between Dur top and the average temporal closeness. Figure 15 presents such a correlation for the three datasets. In the case of Enron and RollerNet, these values seem correlated (particularly for RollerNet). However, the correlation is very low for Twitter: some nodes have a high average temporal closeness yet a low Dur top , and conversely. We argue that the average temporal closeness is not representative as it does not give each instant an equal amount of importance. As we saw, a node can have an extremely high temporal closeness at a single instant (and therefore a high average temporal closeness) even though it may have a very low activity (and hence, a very low closeness) in the rest of the dataset. However, the Dur top value considers that all instants have an equal importance.

To study the snapshotCl method, we had to choose a value for the snapshot duration. As explained in Section 5, we chose the value that gave a good compromise between a low loss of temporal information and a sufficiently high 5. we only present the correlation between temporal closeness and snaphsotCl as the plot obtained for temporal eigenvector is very similar. number of active nodes in each snapshot, so that it contains enough information. In order to check whether this has an impact on our observations, we present in Figure 16 the correlation between the Dur top values of temporal closeness and the one of snapshotCl for different snapshot durations and for the three datasets we studied.

We observe few differences. The main difference is that for Enron, a snapshot duration significantly shorter than the one we studied in the rest of the paper (1 day) leads to a somewhat smaller Dur top value for all nodes. This is consistent with the fact that the snapshotCl method tends to detect the times at which the nodes are active: by reducing the snapshot duration, the relative number of snapshots at which any given node is active diminishes, hence a decrease in the Dur top value and a corresponding increase in the Dur bot value. Note that this does not affect the general shape of the plot, and that the Dur top values attributed by temporal closenes and snapshotCl are still correlated.

We study more in depth the impact of the snapshot duration in the supplementary material, and confirm that the observations made here are general and do not depend on the chosen snapshot duration.

We proposed in this paper a methodology to compare the four methods and better understand the difference between each method on different datasets of different nature.

Our observations can be summarized as follows:

1) different centralities have different results; a node can be perceived as important by the temporal closeness and irrelevant by the coverage centrality; 2) different datasets have different properties regarding nodes' importance; for one dataset, the importance of all nodes fluctuates extremely rapidly between high and low values; it is meaningless in this case to state that one node is more important than others, except for a very limited time span; in other datasets however, we find that some nodes are consistently important for the whole network time span; 3) a node can be inactive (i.e. not have any links) yet be highly important since it can be a waiting point in an important temporal path between two nodes; 4) nodes can be globally important while having a low global average centrality; average centrality gives a high significance to periods with very high temporal closeness (which correspond in general to highly active periods for the considered node).

Following those observations, we can draw a couple of conclusions regarding how to compare the different metrics. In particular, observation 3 above leads to the conclusion that snaphsotCl is unable to relate a temporary inactive node to its future connections. Therefore, it does a poor job in quantifying the importance of a node as a relay for future communication. Another conclusion drawn from the present study is that, although interesting, temporal eigenvector is less accurate than temporal closeness and coverage centrality to measure the importance of a node, as it considers path that can go backwards in time.

Our work opens the way to several interesting perspectives. First, the choice of several datasets stemming from very different contexts strengthens the conclusions drawn from this study. We would like to apply our approach to more datasets. For the time being, we were only able to apply the coverage centrality method to one dataset due to computational reasons. Thus, we are unable to understand completely the difference between the temporal closeness and the coverage centrality. Finding a way to speed up the coverage centrality computation, or approximate the results, would therefore allow a better understanding of this method.

Another way to address this question consists in obtaining datasets in which the ground truth about nodes' importance is known, or where it can be measured using an orthogonal approach. To that regards, one interesting approach could be to relate the findings provided in the present study to a practical investigation of the importance of the nodes in the network. To do so, one could for instance remove (a set of) nodes detected as important for the network by the different metrics and analyze how it impacts the properties of the structure in terms of information diffusion. Although very interesting, we claim that such an investigation deserves a complete and independent study that we leave for future work.

Our study of the temporal closeness centrality relies on a parameter I. Indeed, for computation reasons, instead of computing the temporal closeness for every time instant, we compute it only every I seconds. Though the values obtained in this way are exact, this may induce small inaccuracies, mainly on the obtained values for Dur top and Dur bot : indeed, the ranking of nodes is (exactly) known for points spaced I seconds from each other, and each point at which the rank is in the top or bottom region contributes I seconds to Dur top or Dur bot . This is an approximation of the ideal case in which I is equal to the lowest time resolution in the dataset. The value we selected for I in the study corresponds to the median of inter-link duration (i.e. the time separating two consecutive links) for each dataset. Although we are confident that the choice of this value has little impact on the conclusions drawn in the present study, a more in-depth study of the impact of I would surely be interesting. In particular, the value of I has a strong impact on the running time of the temporal closeness computation. Being able to identify low values of I that still give relevant information would allow to run the computations much faster, and hence tackle much larger datasets.

In this paper we studied the time evolution of the importance of nodes. This topic is closely linked to the question of detecting important changes, either in the network as a whole or in the behavior of specific nodes. Some papers [START_REF] Shahadat Uddin | A set of measures to quantify the dynamicity of longitudinal social networks[END_REF], [START_REF] Costa | Time centrality in dynamic complex networks[END_REF] study the importance of specific time instants and/or quantify the change in nodes' importance. An indepth study of the link between these two questions would lead to very interesting insights, for instance on questions such as: are the changes in the importance of time instants reflected in the importance of nodes at these instants? if so, do these changes correspond to a global increase/decrease of node importance, or are they triggered by a sudden increase/decrease of the importance of one (or a few) major nodes?

Finally, another interesting direction would be to design or use models for temporal networks that generate artificial temporal networks in which nodes' importance is controlled. Figure 1 shows the time evolution of the Kendall-tau correlation between the rankings produced by snapshotCl and temporal closeness, for the three datasets.

We observe the same global behaviors for all snapshot durations. In particular, we still observe a global increase of the correlation for the Enron dataset, coming from the fact that, as less nodes are active at the end of the dataset, both methods tend to agree more on which nodes are important; we still observe very important fluctuations for the Roller-Net dataset, consistent with the fact that this dataset is very dense and importance fluctuates widely from one instant to the next; and we still observe a consistently low correlation for the Twitter dataset, except at the times at which a larger fraction of nodes are active.

We now study the difference in the ranks attributed by snapshotCl and temporal closeness to each node. Figure 2 presents the inverse cumulative distribution of the difference of the ranks for each node at every instant, for the three datasets.

For Rollernet and Twitter, we observe no significant differences for the different snapshot durations. For Enron, we observe that, the higher the snapshot duration, the lower the fraction of (instant, node) pairs for which temporal closeness attributes a higher rank than snapshotCl. This is consistent with our earlier observations: snapshotCl attributes a rank of 0 during temporary inactive moments to the corresponding nodes, while temporal closeness ranks them higher. Since increasing the snapshot duration reduces the fraction of snapshots during which any given node is inactive, this induces a smaller fraction of positive rank differences.

Finally, Figure 3 presents the correlations between Dur top and Dur bot values for snapshotCl, for the three datasets. Again, for Rollernet and Twitter, we observe no significant difference: for Rollernet, we see that the values become more scattered when the snapshot duration increases; for Twitter however, the values are still concentrated in a single line, meaning that snapshotCl always considers a node as important or unimportant, but never places it in the middle region.

For Enron, we observe that the values become significantly more scattered as the snapshot duration increases. This comes from the fact that, as the snapshot duration increases, a larger fraction of nodes become active in each snapshot, and hence not all active nodes are placed in the top region by snapshotCl. However, we still clearly observe the tendency to seldom place nodes in the middle region, characterized by a globally linear shape of the plot, even for large snapshot durations: a one month snapshot leads to approximately 36 snapshots for the whole dataset, which induces a very important loss of temporal information.

Finally, as we observed in the main text of this paper, the snapshot duration has little impact on the correlations between the Dur top values of snapshotCl and temporal closeness.

Fig. 1 :

 1 Fig.1:A small example of a dynamic network. The links existing at time t = 1 are shown on the top left corner, the ones existing at t = 2 in the top right corner, and so on, and the aggregated network is shown last.

Fig. 2 :

 2 Fig. 2: An example of inverse competition ranking.

Fig. 3 :

 3 Fig. 3: Time-evolution of the proportion of active nodes.

Fig. 4 :

 4 Fig. 4: Time-evolution of the Kendall-Tau correlation between temporal closeness and snapshotCl. Top: Enron; Middle: Rollernet; Bottom: Twitter.

Fig. 5 :Fig. 6 :

 56 Fig. 5: Time-evolution of the Kendall-Tau correlation between temporal closeness and temporal eigenvector. Top: Enron; Middle: Rollernet; Bottom: Twitter.

Fig. 7 :

 7 Fig. 7: Inverse cumulative distribution of rank difference between Temporal Closeness and other methods: top: snapshotCl; bottom Left: temporal eigenvector; bottom Right: coverage centrality.

Fig. 9 :

 9 Fig. 9: Dur T op v.s. Dur Bot . For the Enron dataset.

Figure 9

 9 Figure 9 presents the correlations between Dur top and Dur bot for each of the four methods, for the Enron dataset. It is striking to observe that most of the nodes are almost always considered by snapshotCl as either highly important or unimportant (Dur top + Dur botDur T otal ). This indicates that ranks in the middle region ( N * 0.25 < R < N * 0.75 ) are rarely attributed to nodes, which is well exemplified by the case presented in Figure8. The behaviour is clearly different for temporal closeness that can attribute a wider range of values for the nodes. We also observe that, for temporal eigenvector, Dur top and Dur bot do not reach values as high as for the other methods. This can be an indication that the fluctuation seen in Figure8is a general

Fig. 10 :

 10 Fig. 10: Temporal closeness v.s. other methods. For Enron dataset.

Fig. 11 :

 11 Fig. 11: Dur T op v.s. Dur Bot . For RollerNet dataset.

Fig. 12 :Fig. 13 :Fig. 14 :

 121314 Fig. 12: Temporal closeness v.s. other methods. For the RollerNet dataset.

Fig. 15 :

 15 Fig. 15: Dur top v.s. average temporal closeness.

Fig. 16 :

 16 Fig. 16: Dur top for snapshotCl v.s. Dur top for temporal closeness for different snapshot sizes. Top: Enron; Middle: Rollernet; Bottom: Twitter.

Fig. 1 :

 1 Fig. 1: Time-evolution of the Kendall-Tau correlation between temporal closeness and snapshotCl for different snapshot sizes. Top: Enron; Middle: Rollernet; Bottom: Twitter.

Fig. 2 :Fig. 3 :

 23 Fig. 2: Inverse cumulative distribution of rank difference between Temporal Closeness and snapshotCl fir different snapshot sizes. Top: Enron; Middle: Rollernet; Bottom: Twitter.

TABLE 1 :

 1 number of nodes |V |, number of links |E|, dataset duration, median of inter-link duration (I) and snapshot duration for each dataset.

		|V |	|E|	Duration	I (Seconds)	Snapshot duration
	Enron	151	47 088	3 years	960	1 week
	Radoslaw	168	82 876	9 months	53	1 week
	RollerNet	62	403 834	3 hours	4	1 minute
	Twitter (HashTags)	3 048	100 429	22 days	16	3 hours
	Twitter (Retweets)	10 484	27 919	20 days	18	1 hours
	Facebook	8 977	66 153	1 year	278	1 week

note that nodes that were active in the past but do not have any future links are attributed a rank of 0 by both methods.

ACKNOWLEDGEMENTS

This work is funded in part by the European Commission H2020 FETPROACT 2016-2017 program under grant 732942 (ODYCCEUS), by the ANR (French National Agency of Research) under grant ANR-15-CE38-0001 (AlgoDiv), by the Ile-de-France Region and its program FUI21 under grant 16010629 (iTRAC).

Her research area is the study of large graphs occurring in practice, both in computer science but but also coming from other contexts, like social or biological networks.

Fabien Tarissan is a permanent researcher at CNRS and member of the laboratory ISP at ENS Paris-Saclay. He was previously an associate professor at Sorbonne Universit é from 2009 to 2015. His work mainly concerns the analysis and modeling of large networks encountered in practice. His approach consists in proposing new theoretical tools in order to identify non-trivial properties of these networks and to define new models able to capture these properties.

Supplementary material

!

In this supplementary material we study more in depth the impact of the choice of the snapshot duration for the snapshotCl method.

For each of the datasets, we chose a range of values for the snapshot duration, some shorter and some larger than the one we have chosen for the main part of the paper. Then we make the same studies than in Section 6 of the main paper.