L Théolier

F Morancho

K Isoird

H Mahfoz-Kotb

H Tranduc

The DT-SJMOSFET: a new power MOSFET structure for highvoltage applications

Keywords: Power semiconductor devices, MOSFET, SuperJunction devices, Simulation

New hybrid vehicles will probably use high voltage batteries (150 to 200 Volts). For these future automotive applications, the development of 600 Volts power MOSFET switches exhibiting low onresistance is desired. The "Deep Trench SuperJunction" MOSFET (DT-SJMOSFET) is one of the new candidates. In this paper, a comparative theoretical study, using 2D simulations, shows that the DT-SJMOSFET should be a challenger to the conventional SJMOSFET in terms of "specific onresistance / breakdown voltage" trade-off. Simulations of the DT-SJMOSFET breakdown voltage versus the technological parameters exhibit the difficulties to fabricate the device. Finally, an original edge cell is proposed that contains the peripheral potential.

Introduction

New hybrid vehicles will probably use high voltage batteries (150 to 200 Volts). For these future automotive applications, the development of 600 Volts power MOSFET switches exhibiting low onresistance is desired. Although, power MOSFET is commonly used in this voltage ranges, unfortunately its on-resistance (R ON .S) increases drastically with its breakdown voltage (BV).In fact due to the limitation of the maximum electric field, a high breakdown voltage requires the drift region to be lightly doped and thick, which then causes R ON .S to be very high. The theoretical limit for the "R ON .S / BV" trade-off of conventional vertical power MOSFET is given by the relationship (1):

( )

( ) 5 . 2 9 2 10 3 . 8 . . BV cm S R ON × × = Ω - (1)
The aim of this work is to address the rising need of this class of MOSFETs in future automotive applications, in which development of 600 Volts power MOSFETs exhibiting low on-resistance is desired. Nowadays the Vertical Double diffused MOSFET structure -VDMOSFET -(Figure 1) is widely used as a power MOSFET. This structure is based upon the double diffusion of the P-body and N + source regions using the edge of the polysilicon as a masking boundary. The voltage handling capability of this structure is given by the breakdown voltage of the "P-body / N -epilayer" junction, that is strongly dependent on the thickness and the doping concentration of the lower doped region (i.e. the N - epilayer region in the case of N-channel VDMOS transistors) [START_REF] Baliga | modern Power Devices[END_REF]. Today, advances in process technology have improved transistor's packing density and consequently transistor's specific onresistance. However improvements in specific onresistance have been limited by material and breakdown voltage, which required a relative thick and low doped epitaxial layer. Recently, several MOSFET configurations have been proposed to reduce specific on-resistance while keeping a high breakdown voltage: the SuperJunction [START_REF] Lorenz | COOLMOS -A new Milestone in high voltage power MOS[END_REF], [START_REF] Fujihira | Theory of Semiconductor Superjunction devices[END_REF] and semi-superjunction [START_REF] Saito | 600V Semi-superjunction MOSFET[END_REF] devices. These devices recently attracted the attention of many researchers because they offer a good "specific onresistance / breakdown voltage" trade-off around 600 Volts breakdown voltage [START_REF] Saito | A 20mΩ.cm 2 600V-class Superjunction MOSFET[END_REF], [START_REF] Saito | A 15.5mΩcm 2 -680V Superjunction MOSFET Reduced On-Resistance by Lateral Pitch Narrowing[END_REF]. In this paper, a new 600 Volts vertical N-channel SuperJunction MOSFET called DT-SJMOSFT is proposed. These DT-SJMOSFET use a deep trench in the N -drift layer as a new approach to form the vertical N and P pillars as oppose to the most widely reported technological fabrication of SJMOSFET that involves the repeated use of epitaxies and implantations in order to form these zones [START_REF] Lorenz | COOLMOS -A new Milestone in high voltage power MOS[END_REF]. It will be shown that the DT-SJMOSFET exhibit an equivalent "R ON .S / BV" trade-off. Then an original edge cell will be proposed to contain the peripheral potential.

SuperJunction concept

Principle

Schematic cross-sections of the conventional Vertical DMOSFET (VDMOSFET), is shown in Figure 1. In the conventional structure, the N -drift region is required to be lightly doped so that the depletion region sufficiently develops in the N -drift region to sustain the blocking voltage. This lightly doped N -drift region results in a high drift resistivity. The SJ technology [START_REF] Fujihira | Theory of Semiconductor Superjunction devices[END_REF] is based on the charge compensation principle. The excess charge in the npillar is counterbalanced by the adjacent charges in the p-pillar (Figure 2). It allows the doping level of the n-pillars to be higher than that of the N -drift layer of the conventional MOSFET: then ultra low onresistance below the Si-limit can be realized.

Considering both the lowest on-resistance and the highest breakdown voltage, P -and N -columns width and doping concentration are optimized in the way that the lateral and the vertical peak electric field are approximately equal. The charge compensation principle, on the other hand, requires the precise control in the doping of P - and N -columns to realize low on-resistance and high breakdown voltage because a small impurity imbalance between highly doped P -and N -columns causes large change of the electric field in the drift region and results in lower breakdown voltages. The relation between the doping concentration unbalance and the breakdown voltage has been published [START_REF] Shenoy | Analysis of the effect of charge balance on the static and dynamic characteristics of the super junction MOSFET[END_REF] to define critical process window for the P -and N - columns.

The newly DT-SJMOSFET concept (Figure 3), based on the VTR-DMOSFET [START_REF] Glen | A novel Vertical Deep Trench RESURF DMOS (VTR-DMOS)[END_REF], is a charge compensation structure like the SJMOSFET. The main difference with a SJMOSFET is the introduction of a deep trench in the N -epitaxial layer in order to realize the P-pillars necessary for the charge balance. These Ppillars are made by boron diffusion of a P ++ heavily doped polysilicon across a thin oxide in order to control the diffused dose. From a technological point of view, DT-SJMOSFET has some advantages. On one hand, it includes only one epitaxial growth step, compared to SJMOSFET. On the other hand, the oxide thickness and the thermal process enable an accurate control of the boron dose, compared to VTR-DMOSFET. Moreover, this structure can exhibit the same conduction area, compared to a SJMOSFET, because the area required by the Ppillars and the trench oxide in the DT-SJMOSFET (W pox , Fig. 3) is approximately the same than the one required by the P-pillars in the SJMOSFET (W p , Fig. 2).

O x i d e W pox W p

Device parameters

Conventional VDMOSFET, SJMOSFET and DT-SJMOSFET have been studied: Table 1 gives some important device parameters of these devices. Because of the voltage handling capability requirements (BV = 680 Volts), the N -epitaxial layer doping concentration required is 3 x 10 14 cm -3 for conventional VDMOSFETs and 3.3 x 10 15 cm -3 for a 12 μm width SJMOSFET [START_REF] Saito | A 15.5mΩcm 2 -680V Superjunction MOSFET Reduced On-Resistance by Lateral Pitch Narrowing[END_REF]. The simulated DT-SJMOSFET parameters are a N -epitaxial layer with a doping concentration of 3 x 10 15 cm -3 and a gaussian P-pillar with a boron peak concentration of 6 x 10 16 cm -3 at the oxide/silicon interface. The total width of the trench is 4 µm for a depth of 50 µm. It is noteworthy that the boron peak concentration and the junction depth are chosen to fulfill the charge balance condition between the N and P-pillars.

Simulated static characteristics

This study concerns 600 Volts breakdown voltage DT-SJMOSFET device. In order to evaluate the structure, a simulated study was made on the central and edge cells on off-state and on-state.

Edge cell

A key issue in designing power devices is the breakdown termination (edge cell). An optimized and well-designed termination technique should shift the peak of the electric field from the surface to the bulk of the device. In the DT-SJMOSFET, the drawback of the increase in the N -epitaxial layer doping concentration is that the termination of the device has to be very efficient: actually, the higher doping concentration in DT-SJMOSFET implies that the conventional edge cell realized with planar guard rings or field plate are not sufficiently efficient and could induce a lower breakdown voltage. The proposed edge cell of the DT-SJMOSFET (Figure 5) includes a polysilicon field plate on top of an oxide trench (termination trench) that is larger than the one used in the central cell (8 µm). The principle of this termination is to contain all the potential in the last oxide trench without additional process steps for the realization of the edge cell. This prevents aligning defects between the edge cell and the central cells, which secure the charge balance condition for the last base cell.

ON-state behavior

Only the central cell of the DT-SJMOSFET is studied in the on-state because the edge cell does not take part in conduction.

The simulated breakdown voltage variations versus unbalanced diffused boron dose are presented in Figure 7. The simulations were made with a 16 μm width base cell and a 4 μm opening trench based on the laboratory possibilities in order to reach a better "specific on-resistance". In all cases, it can be observed that a light unbalanced boron dose would result in a dramatic decrease in the breakdown voltage. The higher the epitaxial doping concentration is, which is the most interesting case in the on-state (Figure 7) is, the lower the maximal breakdown voltage is. Because of this strong sensitivity to the boron dose, we will choose a weaker epitaxial doping concentration to fabricate DT-SJMOSFETs (3 x 10 15 cm -3 ) exhibiting the best trade-off between the breakdown voltage, the specific on-resistance, and facility of manufacture.

Parameters sensitivities

Some parameters sensitivity simulations will be discussed in order to evaluate the static performances evolution. At first we present the influence of parameters which affect the most the charge balance condition in central cell. These parameters will include the trench width (W T ), the diffused boron dose (D B ) and the trench verticality.

Other parameters have been studied like the gate shape, its position or the P-body dose. They are not presented in this paper because they have a little effect on the specific on-resistance or on the breakdown voltage. The edge cell is also presented. The field plate length variation (L

O x i d e N B FP
) and the last cell width (W A ) are simulated in order to evaluate the parameters sensitivities.

Trench profile sensitivity

Over-etching compensation

The simulations were made with a 16 μm width base cell, a 4 μm opening trench, an epitaxial layer doping concentration of 3 x 10 15 cm -3 and a constant boron diffusion length at 0.6 μm, in order to reach a better current density. The simulated breakdown voltage variations (BV) versus trench width (W T ) and diffused boron dose (D B ) are presented Figure 8. It can be observed that the breakdown voltage is sensitive to both parameters; this is mainly a charge unbalance issue. For example, for a fixed boron dose, a variation in the trench width (W B T ) will change the number of N carriers. Then it can induce an unbalanced charge in either side. In the same way, for a fixed value of W T , a variation of the diffused dose induces an unbalanced charge. In both cases, this charge unbalance will result in the variation of the breakdown voltage. However, the variations of the active area width can be corrected by adjusting the diffused boron dose so we get the best results on the line defining the charge balance. Boron dose and active area width have a poor influence on the "specific on-resistance".

Trench Verticality

The simulated breakdown voltage variations versus the trench slope defined by the difference (W BT -W TT ), where W BT and W TT are the width at the bottom and the top of the trench respectively (Figure 9), are presented in Figure 10.The chosen values for trench slope in these simulations are based on study results made in our team on realizing high aspect ratio deep trenches for integrated MIM capacitors applications [START_REF] Brunet | Development of fabrication techniques for highdensity integrated MIM capacitors in power conversion equipment[END_REF]. This study used a time multiplexed Inductively Coupled Plasma etcher and a Bosch etch-process where an etching gas (SF 6 ) and passivation gas (C 4 F 8 ) are used alternatively [10]. Results showed that deep trenches with an aspect-ratio of 12 can be realized with a slope of about ± 0.5 μm where the slope sign depends strongly on etching conditions (platen power, pressure, passivation / etching time ratio, …) [START_REF] Liu | Vertical profiles and CD loss control in deep RIE technology[END_REF][START_REF] Park | High aspect ratio via etching for deep trench of silicon[END_REF][START_REF] Ikehara | Fabrication of an accurately vertical sidewall for optical switch applications using deep RIE and photoresist spray coatings[END_REF]. Our simulation results show that verticality of the trench is a critical parameter, particularly the negative slope case. The asymmetry is not yet confirmed but we think that in the case of positive trench slope, the N-type carriers deficiency in the bottom of the N -epilayer is counterbalanced by the N carriers in the N + substrate. This enables a deeper depletion in the epilayer for small bias variation explaining the increase of the breakdown voltage. Consequently, the trench verticality is necessary to insure equivalent performance with the SJ-VDMOSFET. Our simulation results show that the breakdown voltage is not sensitive to the field plate width.

Nevertheless the electric field between the end of the field plate and the end of the trench increase with the field plate width. The simulations do not present an oxide breakdown, but the electric field is close to 10 7 V.cm -1 with the field plate wider than 7 μm. It is necessary to note that the edge cell sustains around 91% of the breakdown voltage of the central cell in the better conditions with a 1μm oxide field plate. In order to increase the breakdown voltage of the edge cell, it is necessary to increase the trench width. The problem comes from the filling of the trench. The wider the opening edge trench is, the more the filling time and the depth trench increase. Then, a 8 μm opening trench is a good trade-off between the manufacture and the breakdown voltage.

Last edge width

The simulated breakdown voltage variations versus edge cell width (W A , Figure 11) are presented in Figure 13. Simulation results show that the breakdown voltage is very sensitive to the edge cell width, particularly for the values below 9 μm. The floating P-pillar is polarized when the depletion layer reaches the Ppillar / N -epilayer junction. So, the wider the edge cell is, the more the P-pillar begins to create a depletion layer late. For width values lower than 9 μm, the two P-pillars are very close. The P-type excess carriers are not completely depleted by the N-type carriers in the substrate because the high doping level in the Ppillars (6 x 10 16 cm -3 ) is too important and the critical breakdown voltage value is rapidly reached.

In an optimal situation, the P-body and the left edge cell P-pillar continue to create a depletion layer until the floating P-pillar is reached. Then, the two P-pillars create a depletion layer until there is no P-type carrier.

In the case of W A values larger than 9 µm, on can expect an excess of N-type carriers in the epilayer. However, the effect of these excess carriers will be partially compensated by the heavily doped P-body.

To control this parameter (W A ), the edge trench and the central trenches are recommended to be made in one step which will avoid the unintentional variations in W A values due to the alignment errors. Even so, it is still important to consider the lateral trench overetching. In order to keep an edge cell width upper than 9 μm, the over-etch effect has to be considered during the masks conception.

Conclusion

In this paper, a new vertical N-channel Superjunction MOSFET called DT-SJMOSFET dedicated to hybrid vehicle applications has been proposed with an original edge cell containing the peripheral potential. These DT-SJMOSFETs use a deep trench in the N - drift layer in order to form vertical N and P pillars, whereas the most widely reported technological fabrication of SJMOSFET involves the repeated use of epitaxies and implantations. The study has shown that the electric performances are very sensitive to the charge unbalance, but the sensitivity can be reduced by decreasing the epilayer doping concentration at the expense of the specific onresistance. However to fabricate a DT-SJMOSFET exhibiting the highest breakdown voltage capacity, we must control accurately the trench shape (width, slope) to ensure the charge balance. The termination still needs to be controlled, notably the edge cell width in order to keep the charge balance.

The study needs to be completed with dynamic and thermal simulations. Moreover, the internal diode needs to be optimized in order to use it in switching mode. However, the realization of this structure remains difficult because the performances are very sensitive to the technological parameters' variations. The deep trench process, using boron diffusion across a thin oxide to realize P-pillars, is now in progress in order to validate the concept of the DT-SJMOSFET: we plan to fabricate 600 Volts Deep Trench diodes, to verify the edge cell, and DT-SJMOSFETs in the near future.

Figure 1 :

 1 Figure 1: Schematic cross-section of a half-cell of a conventional VDMOSFET.

Figure 2 :

 2 Figure 2: Schematic cross-section of a half-cell of a SJMOSFET.

Figure 3 :

 3 Figure 3: Schematic cross-section of a half-cell of a DT-SJMOSFET.

3. 1 .Figure 4 :

 14 Figure 4: 1D lateral Electric Field distribution at breakdown in the middle of the trench.

Figure 5 :

 5 Figure 5: Schematic cross-section of the proposed termination.The position of the edge trench needs to be optimized. The last central cell must polarize the floating P-pillars before reaching the critical electric field. The electrostatic potential distribution in the termination is presented in Figure6. The drawback of this termination is that all the potential is sustained over the distance between the end of the field plate and the edge of the trench. It is necessary to optimize this distance in order to sustain the 600 Volts with the minimal width. The higher oxide critical electric field allows containing 91% of the central cell breakdown voltage in an 8 μm width trench and 1 μm between the end of the field plate and the edge of the tank.

Figure 6 :

 6 Figure 6: Electrostatic potential distribution in the termination.

Figure 7 :

 7 Breakdown voltage variations vs diffused Ptype dose, for different epitaxial doping concentrations. Specific on-resistances are also given.Electrostatic Potential Narrowing

Figure 8 :

 8 Figure 8: Breakdown voltage (BV) variations vs diffused P-type dose (D B ) and deep trench width (W B

Figure 9 :

 9 Figure 9: Schematic cross-section of a half-cell of a DT-SJMOSFET with the simulated parameters.

Figure 10 :

 10 Figure 10: Simulated breakdown voltage (BV) variations versus trench slope.

4. 2 .

 2 Edge cellField plate lengthThe simulations were made with a 9 μm width edge cell (W A ), a 8 μm opening edge trench and 1μm oxide field plate thickness. The simulated breakdown voltage variations versus the field plate width (W FP defined on Figure11) are presented Figure12.

Figure 11 :

 11 Figure 11: Schematic cross-section of the edge cell with the simulated parameters.

Figure 12 :

 12 Figure 12: Simulated breakdown voltage (BV) variations versus field plate width (W FP ).

Figure 13 :

 13 Figure 13: Simulated breakdown voltage (BV) variations versus edge cell width (W A ).

Table 1 :

 1 Main device parameters of the conventional VDMOSFET, a SJMOSFET and the DT-SJMOSFET.

		Simulated Conventional	Realized	Simulated
		VDMOSFET	SJMOSFET [9]	DT-SJMOSFET
	N -epitaxial layer thickness (μm)	51	42	50
	N -epitaxial layer doping concentration (cm -3 )	3 x 10 14	3.3 x 10 15	3 x 10 15
	Central cell width (μm)	12	12	16
	Breakdown voltage (V)	680	680	710
	Specific on-resistance (mΩ.cm 2 )	56	15.5	15.3


Marcos-Cesar Cesar Bragagnolo

Irinel-Constantin Morarescu

Jamal Daafouz

Pierre Riedinger

Irinel-Constantin Morȃrescu

LMI sufficient conditions for the consensus of linear agents with nearly-periodic resets

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

Introduction

From biology, ecology and sociology to communication and power systems, diverse areas of science and engineering deal with complex interconnected systems called networks [START_REF] Reynolds | Boids (flocks, herds, and schools: a distributed behavioral model[END_REF][START_REF] Hegselmann | Opinion dynamics and bounded confidence models, analysis, and simulation[END_REF][START_REF] Lorenz | A stabilization theorem for dynamics of continuous opinions[END_REF][START_REF] Gfeller | Spectral coarse graining and synchronization in oscillator networks[END_REF][START_REF] Ratmann | From evidence to inference: Probing the evolution of protein interaction networks[END_REF][START_REF] Pavlopoulos | Using graph theory to analyze biological networks[END_REF]. Throughout this paper, whatever is the domain of application, the constitutive elements of the network will be called agents and their number will define the network dimension. In many fields of application, the encountered networks have often large dimension [START_REF] Boccaletti | Complex networks: Structure and dynamics[END_REF][START_REF] Blondel | Fast unfolding of communites in large networks[END_REF][START_REF] Hanski | Metapopulation dynamics[END_REF] and they are obtained interconnecting several networks of smaller dimension. In other words, inside large networks we can detect groups of agents called clusters or communities. The agents belonging to a community are better connected [START_REF] Newman | Finding and evaluating community structure in networks[END_REF][START_REF] Newman | Modularity and community structure in networks[END_REF][START_REF] Morȃrescu | Opinion dynamics with decaying confidence: Application to community detection in graphs[END_REF] and they agree/synchronize faster on some quantity of interest called state.

The networks are often represented by graphs in which the vertices are the agents and the links define the interconnections between agents. The problem of agreement of dynamic agents belonging to a network has been studied in many frameworks depending on the application. The variations include: whether the edge set of the graph remains fixed or changes over time; whether the graph is undirected or directed; whether the dynamics is continuous or discrete; whether the state of each agent is scalar or vectorial; whether the interconnections are affected by delays or not; and whether all nodes update their states in the same time or not [START_REF] Jadbabaie | Coordination of groups of mobile autonomous agents using nearest neighbor rules[END_REF][START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF][START_REF] Ren | Consensus seeking in multiagent systems under dynamically changing interaction topologies[END_REF][START_REF] Moreau | Stability of multiagent systems with time-dependent communication links[END_REF][START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF][START_REF] Morȃrescu | Consensus with constrained convergence rate and time-delays[END_REF]. The agreement speed in different frameworks has also been quantified (see for instance [START_REF] Xiao | Fast linear iterations for distributed averaging[END_REF][START_REF] Olshevsky | Convergence speed in distributed consensus and averaging[END_REF]). Some works have been oriented towards networks in which the global agreement cannot be reached and only local ones are obtained [START_REF] Morȃrescu | Opinion dynamics with decaying confidence: Application to community detection in graphs[END_REF][START_REF] Touri | On approximations and ergodicity classes in random chains[END_REF]. Some others studied the agreement in networks of agents with discrete dynamics in which any agent is linked with no more than one neighbor at each time [START_REF] Boyd | Randomized gossip algorithms[END_REF][START_REF] Aysal | Broadcast gossip algorithms for consensus[END_REF][START_REF] Liu | Analysis of accelerated gossip algorithms[END_REF][START_REF] Anderson | Convergence of periodic gossiping algorithms[END_REF].

In this work, motivated by some behaviors encountered in social networks we address a consensus problem involving a mix of continuous and discrete dynamics. The network consists of a large number of agents belonging to several clusters. Each cluster is represented by a fixed directed strongly connected graph and almost all the time there is no link between different clusters. In each cluster there exists a specific agent called leader. At specific instants, that will be defined in the next section, the leaders interact via a fixed directed strongly connected graph. We consider a model in which the agents have continuous dynamics but the states of the leaders are reseted at some specific instants corresponding to the moments when the leaders interact between them. This model can be interpreted in terms of opinion dynamics. Each agent has an opinion that continuously evolves towards a local agreement representing the opinion of the community in which it lies. At specific instants, the leaders of the communities interact and they reset their opinion taking into account the ones of other leaders. The new opinions of the leaders will reset the values of the local agreements in each community. Iterating this process all the opinions will tend to a common value that depends only on the initial conditions and the network topology.

The rest of the paper is organized as follows. In Section 2 we formulate the problem under consideration. The agreement behavior and the possible consensus value are studied in Section 3. Sufficient conditions for the global uniform exponential stability of the consensus are provided in Section 4. This condition is given in the form of a parametric LMI. In the next section we consider the problem of numerical implementation of the proposed conditions. Precisely we have shown that only a finite number of LMIs has to be solved. Section 6 is dedicated to numerical simulation which illustrate the results. Some conclusions and perspectives are presented at the end of the paper.

Notation. The following standard notation will be used throughout the paper. The sets of nonnegative integers, real and nonnegative real numbers are denoted by N, R and R + , respectively. For a vector x we denote by x its Euclidian norm. The transpose of a matrix A is denoted by A ⊤ . Given a symmetric matrix A ∈ R n×n , notation A > 0 (A ≥ 0) means that A is positive (semi-)definite. By I k we denote the k × k identity matrix. 1 k and 0 k are the column vectors of size k having all the components equal 1 and 0, respectively. We also use

x(t - k ) = lim t→t k ,t≤t k x(t).
We consider a network of n agents described by the digraph (i.e. directed graph) G = (V, E) where the vertex set V represents the set of agents and the edge set E ⊂ V × V represents the interactions.

Definition 1 A path in a given digraph G = (V, E) is a union of directed edges p k=1 (i k , j k ) such that i k+1 = j k , ∀k ∈ {1, .
. . , p -1}. Two nodes i, j are connected in a digraph G = (V, E) if there exists at least a path in G joining i and j (i.e. i 1 = i and j p = j). A strongly connected digraph is such that any two distinct nodes are connected. A strongly connected component of a digraph is a maximal subset such that any of its two distinct nodes are connected.

In the sequel, we consider that the agent set V is partitioned in m strongly connected clusters/communities C 1 , . . . , C m and no link between agents belonging to different communities exists. Each community possesses one particular agent called leader and denoted in the following by l i ∈ C i , ∀i ∈ {1, . . . , m}. The set of leaders will be referred to as L = {l 1 , . . . , l m }. At specific time instants t k , k ≥ 1, called reset times, the leaders interact between them following a predefined interaction map E l ⊂ L × L. We also suppose that G l = (L, E l ) is strongly connected. The rest of the agents will be called followers and denoted by f j . For the sake of clarity we consider that the leader is the first element of its community:

C i = {l i , f mi-1+2 , . . . , f mi }, ∀i ∈ {1, . . . , m} (1)
where m 0 = 0, m m = n and the cardinality of C i is given by

|C i | n i = m i -m i-1 , ∀i ≥ 1.
In order to keep the presentation simple and making an abuse of notation, each agent will have a scalar state denoted also by l i for the leader l i and f j for the follower f j . We also introduce the vectors x = (l 1 , f 2 , . . . , f m1 , . . . , l m , . . . , f mm ) ⊤ ∈ R n and x l = (l 1 , l 2 , . . . , l m ) ⊤ ∈ R m collecting all the states of the agents and all the leaders' states, respectively. We are ready now to introduce the linear reset system describing the overall network dynamics:

   ẋ(t) = -Lx(t), ∀t ∈ R + \ T x l (t k ) = P l x l (t - k ) ∀t k ∈ T x(0) = x 0 (2)
where

T = {t k ∈ R + | t k < t k+1 , ∀k ∈ N, t k reset time}, L ∈ R n×n
is a generalized Laplacian matrix associated to the graph G and P l ∈ R m×m is a Perron matrix associated to the graph G l = (L, E l ). Precisely, the entries of L and P l satisfies the following relations:

         L (i,j) = 0, if (i, j) / ∈ E L (i,j) < 0, if (i, j) ∈ E, i = j L (i,i) = - j =i L i,j , ∀i = 1, . . . , n , (3)
           P l(i,j) = 0, if (i, j) / ∈ E l P l(i,j) > 0, if (i, j) ∈ E l , i = j m j=1 P l(i,j) = 1, ∀i = 1, . . . , m . (4)
The values L (i,j) and P l(i,j) represent the weight of the state of the agent j in the updating process of the state of agent i when using the continuous and discrete dynamics, respectively. These values describe the level of "democracy" inside each community and in the leaders' network. In particular, L has the following block diagonal structure

L =    L 1 . . . L m    , L i ∈ R ni (5)
with L i 1 ni = 0 ni and P l 1 m = 1 m . Due to the strong connectivity of C i , i = 1, m and G l , 0 is simple eigenvalue of each L i and 1 is simple eigenvalue of P l . This model can be interpreted in terms of opinion dynamics or decision making process in social networks. The network is partitioned in a number of communities. The opinion of each agent continuously evolves taking into account the opinion of its neighbors. At the time t k the leaders interact in a dedicated network and reset their opinion. We show that, if no external perturbation occurs and the process continue for a long period of time, all the opinions will converge towards a common one. This global agreement opinion depends on the level of "democracy" inside each community and on the level of "democracy" in the leaders' network.

Agreement behavior

In this section we assume that system (2) achieves consensus and we characterize the possible values for it. Firstly, we show that each agent tracks a local agreement function which is piecewise constant. In the second subsection we prove that the vector of local agreements lies in a subspace defined by the system's dynamics and initial condition. Therefore, if the consensus is achieved and the corresponding consensus value is x * than x * 1 m belongs to the same subspace. Moreover, this value is determined only by the initial condition of the network and by the interconnection structure.

As we have noticed 1 ni is the right eigenvector of L i associated with the the eigenvalue 0 and 1 m is the right eigenvector of P l associated with the eigenvalue 1. In the sequel, we denote by w i the left eigenvector of L i associated with the the eigenvalue 0 such that w ⊤ i 1 ni = 1. Similarly, let v = (v 1 , . . . , v m ) ⊤ be the left eigenvector of P l associated with the eigenvalue 1 such that v ⊤ 1 m = 1. Due to the structure (1) of the communities, we emphasize that each vector w i can be decomposed in its first component w i,l and the rest of its components grouped in the vector w i,f .

Local agreements

Let us first recall a well known result concerning the consensus in networks of agents with continuous time dynamics (see [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF] for instance).

Lemma 2 Let G be a strongly connected digraph and L the corresponding Laplacian matrix. Consider a network of agents whose collective dynamics is described by ẋ(t) = -Lx(t). Let us also consider L1 = 0, u ⊤ L = 0 and u ⊤ 1 = 1. Then, the agents asymptotically reach a consensus and the consensus value is given by x * = u ⊤ x(0). Moreover, the vector u defines an invariant subspace for the collective dynamics: Lemma 2 implies that between two reset instants t k and t k+1 , the agents belonging to the same community converge to a local agreement defined by x * i (k) = w ⊤ i x Ci (t k ) where x Ci (•) is the vector collecting the states of the agents belonging to the cluster C i . Nevertheless, at the reset times the value of the local agreement can change. Thus,

u ⊤ x(t) = u ⊤ x(0), ∀t ≥ 0 Remark 1 When dynamics (2) is considered,
w ⊤ i x(t) = w ⊤ i x Ci (t k ), ∀t ∈ (t k , t k+1 ) and possibly w ⊤ i x Ci (t) = w ⊤ i x Ci (t k ), for t / ∈ (t k , t k+1 )
Therefore, the agents whose collective dynamics is described by the hybrid system (2), may reach a consensus only if the local agreements converge one to each other.

Consensus value

Before presenting our next result, let us introduce the following vectors:

x * (t) = (x * 1 (t), x * 2 (t), ..., x * m (t)) ⊤ ∈ R m u = (v 1 /w 1,l , v 2 /w 2,l , ..., v m /w m,l ) ⊤ ∈ R m (6) It is noteworthy that x * (t) is time-varying but piecewise constant: x * (t) = x * (k) ∀t ∈ (t k , t k+1 ).
Proposition 3 Consider the system (2) with L and P l defined by (3) and (4), respectively. Then,

u ⊤ x * (t) = u ⊤ x * (0), ∀t ∈ R + . (7)
Proof: Let us introduce the matrix of the left eigenvectors of the communities:

W =      w ⊤ 1 0 • • • 0 0 w ⊤ 2 • • • 0 . . . . . . . . . . . . 0 0 • • • w ⊤ m      ∈ R m×n . (8)
Then, the following relation holds:

x * (t) = W x(t) ∀t ∈ R + \ T (9)
Since w i = (w il , w if ), we define a permutation matrix T such that W T ⊤ = U = (U 1 , U 2 ). The matrix U 1 is a diagonal matrix corresponding to the leaders' components w i,l , while U 2 is a block diagonal matrix corresponding to the followers' components w i,f . In other terms

U 1 =      w 1,l 0 • • • 0 0 w 2,l • • • 0 . . . . . . . . . . . . 0 0 • • • w m,l      ∈ R m×m (10)
U 2 =      w 1,f 0 • • • 0 0 w 2,f • • • 0 . . . . . . . . . . . . 0 0 • • • w m,f      ∈ R m×(n-m) . (11)
Finally, we can rewrite equation ( 9) as:

x * (t) = W T ⊤ x(t) = U • (x l (t), x f (t)). (12)
Note that at the reset time t k the vector x f remains the same, i.e.

x f (t k ) = x f (t - k ) . This yields x * (t k ) -x * (t - k ) = U • (x l (t k ) -x l (t - k ), x f (t k ) -x f (t - k )) = U • (x l (t k ) -x l (t - k ), 0) = U 1 • (x l (t k ) -x l (t - k )) + U 2 • 0 = U 1 (x l (t k ) -x l (t - k )).
Thus,

x * (t k ) = x * (t - k ) + U 1 • (P l -I m )x l (t - k )). (13)
Multiplying equation ( 13) by u ⊤ and using

u ⊤ U 1 = v ⊤ one obtains u ⊤ x * (t + k ) = u ⊤ x * (t - k ) + u ⊤ U 1 (P l -I m )x l = u ⊤ x * (t - k ) + v ⊤ (P l -I m ) = u ⊤ x * (t - k ) + v ⊤ -v ⊤ = u ⊤ x * (t - k ) (14)
According to Remark 1, x * (t) remains constant for all t ∈ (t k , t k+1 ) leading to

u ⊤ x * (t) = u ⊤ x * (0) ∀t ∈ R + . ( 15
)
Corollary 1 Consider the system (2) with L and P l defined by (3) and (4), respectively. Assuming the agents of this system reach a consensus, the consensus value is

x * = u ⊤ W x(0) m i=1 u i . ( 16
)
Proof: Let x * be the consensus value reached by the system (2). It means that x(t) →

x * 1 n . Thus, when t goes to ∞ in (15) one obtains

u ⊤ x * 1 n = u ⊤ x * (0) = u ⊤ W x(0)
leading to [START_REF] Newman | Modularity and community structure in networks[END_REF].

In order to simplify the presentation and without loss of generality, in what follows, we consider that

m i=1 u i = 1.
Remark 2 It is important to note that the consensus value depends only on the system matrices L, P l and does not depend on the reset sequence T . This can be interpreted as: the consensus depends only on the weight of the agents inside communities and on the wight of leaders in the leaders' network. Thus the level of "democracy" inside communities and in the leaders' network are the only factors influencing the consensus value.

A trivial result which may be seen as a consequence of Corollary 1 is the following.

Corollary 2 If the matrices L, P l are symmetric (i.e. i th agent takes into account the state of j th agent as far as j th takes into account the i th one and they give the same importance one to another) the consensus value is the average of the initial states.

Proof: In this case w

i = 1 ni 1 ni and v = 1 m 1 m which leads to u = ( n1 m , n2 m , . . . , nm m
). The result follows from ( 16).

Stability analysis

The stability analysis of the equilibrium point x * will be given by means of some LMI conditions. Precisely, we recall and adapt some results presented in [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF]. Since the consensus value is computed in the previous section we can first define the disagreement vector y = x -x * 1 n . We also introduce an extended stochastic matrix P ex as follows:

P ex = T ⊤ P l 0 0 I n-m T ( 17
)
where T is the permutation matrix used in the proof of Proposition 3. It is noteworthy that L1 n = 0 n and P ex 1 n = 1 n . Thus, the disagreement dynamics is exactly the same as the system one:

   ẏ(t) = -Ly(t), ∀t ∈ R + \ T y(t k ) = P ex y(t - k ) ∀t k ∈ T y(0) = y 0 . ( 18
)
Now we have to analyze the stability of the equilibrium point y * = 0 n for the system [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF]. We note that Theorem 2 in [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF] cannot be directly applied due to the marginal stability of the matrices L and P ex .

The reset sequence is defined such that t k+1 -t k = δ + δ ′ where δ ∈ R + is fixed and δ ′ ∈ ∆ with ∆ ⊂ R + a compact set. Thus the set of reset times T belongs to the set of all admissible reset sequences associated with ∆:

Φ(∆) {t k } k∈N , t k+1 -t k = δ + δ ′ k , δ ′ k ∈ ∆, ∀k ∈ N (19)
where we always consider t 0 = 0. We recall that for any T ∈ Φ(∆) and any initial condition x 0 the system (2) has a unique solution denoted by ϕ T (t, x 0 ).

Definition 4

We say that the equilibrium y * = 0 n of the system [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF] is Globally Uniformly Exponentially Stable (GUES) with respect to the set of reset sequences Φ(∆) if there exist positive scalars c, λ such that for any T ∈ Φ(∆), any y 0 ∈ R n , and any t ≥ 0

ϕ(t, y 0 ) ≤ ce -λt y 0 (20)
The following theorem is instrumental:

Theorem 5 (Theorem 1 in [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF]) Consider the system [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF] with the set of reset times T ∈ Φ(∆). The equilibrium y * = 0 n is GUES if and only if there exists a positive function V : R n → R + strictly convex,

V (y) = y ⊤ S [y] y, homogeneous (of second order), S [•] : R n → R n×n , S [y] = S ⊤ [y] = S [ay] > 0, ∀x = 0, a ∈ R, a = 0, V (0) = 0, such that V (y(t k )) > V (y(t k+1
)) for all y(t k ) = 0, k ∈ N and any of the possible reset sequences T ∈ Φ(∆).

In the sequel, we define a quasi-quadratic Lyapunov function satisfying Theorem 5 by means of some LMI. Therefore, the following result gives sufficient conditions for the stability of the equilibrium point y * = 0 n for the system [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF] or equivalently of x * 1 n for the system (2).

Theorem 6 Consider the system (2) with T in the admissible reset sequences Φ(∆). If there exist matrices S(δ ′ ), S(•) : ∆ → R n×n continuous with respect to δ ′ , S(δ

′ ) = S ⊤ (δ ′ ) > 0, δ ′ ∈ ∆ such that the LMI I n -1 n u ⊤ W ⊤ S(δ a ) I n -1 n u ⊤ W - Y (δ a ) -1 n u ⊤ W ⊤ S(δ b ) Y (δ a ) -1 n u ⊤ W > 0, Y (δ a ) P ex e -L(δ+δa) (21)
is satisfied on span{1 n } ⊥ for all δ a , δ b ∈ ∆, then x * is globally uniformly exponentially stable for [START_REF] Aysal | Broadcast gossip algorithms for consensus[END_REF]. Moreover, the stability is characterized by the quasi-quadratic Lyapunov function

V (t) = max δ ′ ∈∆ (x(t)-x * 1 n ) ⊤ S(δ ′ )(x(t)-x * 1 n ) satisfying V (t k ) > V (t k+1 ).
Proof: Using the disagreement vector y(t) = x(t) -x * 1 n and supposing that there exist matrices S(δ ′ ) satisfying ( 21) for all δ a , δ b ∈ ∆ we define the Lyapunov matrix

S [y] = S(δ * (y)) with δ * (y) = arg max δ ′ ∈∆ y ⊤ S(δ ′ )y (22)
Following [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF] the Lyapunov function

V (y) = y ⊤ S [y] y = max δ ′ ∈∆ y ⊤ S(δ ′ )y,
is convex and homogeneous of the second order. Let us show now that S(•) solution of [START_REF] Pavlopoulos | Using graph theory to analyze biological networks[END_REF] ensures that V (•) defined above satisfies Theorem 5. We note first that any x(t k ) ∈ R n can be decomposed as x(t k ) = x(t k ) + x(t k ) with x(t k ) ∈ span{1 n } ⊥ and x(t k ) ∈ span{1 n }. Moreover,

I n -1 n u ⊤ W x(t k ) = 0, Y (δ a ) -1 n u ⊤ W x(t k ) = 0 hence I n -1 n u ⊤ W x(t k ) = I n -1 n u ⊤ W x(t k ), Y (δ a ) -1 n u ⊤ W x(t k ) = Y (δ a ) -1 n u ⊤ W x(t k )
Thus, the LMI (21) yields

x(t k ) ⊤ I n -1 n u ⊤ W ⊤ S(δ a ) I n -1 n u ⊤ W x(t k ) > x(t k ) ⊤ Y (δ a ) -1 n u ⊤ W ⊤ S(δ b ) Y (δ a ) -1 n u ⊤ W x(t k ), ∀δ a , δ b ∈ ∆ Consequently, using u ⊤ W x(t k ) = x * one gets x(t k ) -1 n x * ⊤ S(δ a ) x(t k ) -1 n x * > Y (δ a )x(t k ) -1 n x * ⊤ S(δ b ) Y (δ a )x(t k ) -1 n x * , ∀δ a , δ b ∈ ∆, x(t k ) ∈ R n (23)
For any

{t k } k∈N ∈ Φ(∆) we have x(t k+1 ) = Y (δ ′ k )x(t k ) with some δ ′ k ∈ ∆.
Thus, for δ a = δ ′ k , (23) rewrites as:

x(t k ) -x * 1 n ⊤ S(δ ′ k ) x(t k ) -x * 1 n > x(t k+1 ) -x * 1 n ⊤ S(δ b ) x(t k+1 ) -x * 1 n ∀δ ′ k , δ b ∈ ∆, x(t k ) ∈ R n or equivalently y(t k ) ⊤ S(δ ′ k )y(t k ) > y(t k+1 ) ⊤ S(δ b )y(t k+1 ) ∀δ ′ k , δ b ∈ ∆
Taking δ b = δ * (y(t k+1 )), defined by ( 22) one obtains

V (y(t k )) > y(t k ) ⊤ S(δ ′ k )y(t k ) > V (y(t k+1 ))
for all y(t k ), which ends the proof.

Numerical implementation

In order to render this paper self-contained, in this section we consider the problem of approximation of the parametric LMI ( 21) by a finite number of conditions using polytopic embeddings.

Periodic resets

If ∆ = {0} i.e. the resets take place periodically with the period δ, Theorem 6 is rephrased as follows.

Corollary 3 If there exists a positive definite matrix S such that the LMI

I n -1 n u ⊤ W ⊤ S I n -1 n u ⊤ W - Y (δ) -1 n u ⊤ W ⊤ S Y (δ) -1 n u ⊤ W > 0, Y (δ) P ex e -L(δ) (24)
is satisfied on span{1 n } ⊥ , then x * is globally uniformly exponentially stable for (2). Moreover, the stability is characterized by the quadratic Lyapunov function

V (t) = (x(t) -x * 1 n ) ⊤ S(x(t) -x * 1 n ) satisfying V (t k ) > V (t k+1 ).
In this case the parametric LMI ( 21) is simply replaced by the LMI [START_REF] Reynolds | Boids (flocks, herds, and schools: a distributed behavioral model[END_REF] and no numerical difficulties arise.

Nearly-periodic resets

In this case, to replace the parametric LMI ( 21) by a finite number of LMIs we have to deal with the parametric uncertainty δ ′ k in the definition [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF] of the admissible reset sequence. As in [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF] the matrix exponential e -Lδa is approximated by its horder Taylor expansion h i=0 (-L) i i! δ i a . Thus the set {X ∈ R n×n | X = e -Lδa , δ a ∈ ∆} can be embedded into the polytopic set defined by the vertices Z 1 , . . . , Z h+1 where

Z 1 = I n Z i = i l=0 (-L) l l! δ l max , ∀i ∈ {1, . . . , h + 1} with δ max = max δ ′ ∈∆ δ ′ .
Then, Theorem 6 can be replaced by the following result.

Theorem 7 Consider the system (2) with T in the admissible reset sequences Φ(∆).

If there exist symmetric positive definite matrices S i , 0 ≤ i ≤ h + 1 such that the LMI

I n -1 n u ⊤ W ⊤ S i I n -1 n u ⊤ W - Y (δ)Z i -1 n u ⊤ W ⊤ S j Y (δ)Z i -1 n u ⊤ W > 0, Y (δ) P ex e -L(δ) (25)
is satisfied on span{1 n } ⊥ for all i, j ∈ {0, . . . , h + 1}, then x * is globally uniformly exponentially stable for [START_REF] Aysal | Broadcast gossip algorithms for consensus[END_REF].

Proof: Assume that the set of LMIs ( 25) is satisfied for a set of matrices S i , 0 ≤ i ≤ h + 1. Thus,

I n -1 n u ⊤ W ⊤ h+1 i=1 µ i S i I n -1 n u ⊤ W - Y (δ) h+1 i=1 µ i Z i -1 n u ⊤ W ⊤ h+1 i=1 µ j S j × Y (δ) h+1 i=1 µ i Z i -1 n u ⊤ W > 0,
is satisfied for all µ i , µ j ∈ [0, 1], i, j ∈ {1, . . . , h + 1} such that , P l = 0.4500 0.5500 0.2500 0.7500 [START_REF] Xiao | Fast linear iterations for distributed averaging[END_REF] and the reset sequence given by δ = 0.5 and δ ′ k randomly chosen in ∆ = [0, 0.2]. The initial condition of the system is x(0) = (1, 4, 9, 2, 5) and the corresponding consensus value computed by ( 16) is x * = 4.1587. The convergence of the 5 agents towards x * is illustrated in Figure 1 emphasizing that the leaders trajectories are non-smooth while the followers trajectories are. The jumps, convexity and decreasing of the Lyapunov function defined by Theorem 6 are pointed out in Figure 2. Larger networks have also been numerically analyzed but due to the space limitation we do not provide the simulations here.

1 .µ i Z i and h+1 i=1 µ i = 1 .

 11 It is noteworthy that the polytopic embedding provided above implies that for all δ a ∈ [0, δ max ] there exists the set of scalars µ i ∈ [0, 1] such that e -Lδa = h+1 i=1 In other words, Theorem 6 holds with S(δ ′ ) = h+1 i=1 µ i (δ ′ )S i .6 Illustrative ExampleAn academic example consisting in a network of 5 agents partitioned in 2 clusters (n 1 = 3, n 2 = 2) is used in the sequel to illustrate the theoretical results. We consider the dynamics (2) with

Figure 1 :

 1 Figure 1: The state-trajectories of the agents converging to the calculated consensus value.

Conclusions and perspectives

In this paper we have considered the problem of consensus for linear reset systems. The contribution of the paper is twofold: firstly, we define the consensus value for the systems under consideration and secondly, we provide their stability analysis using the Lyapunov framework. The results are easy to implement since the sufficient conditions for stability are given in LMI form and the corresponding Lyapunov function is defined by the solutions of these LMIs. An interesting issue that will be considered in future works is the design of the reset mapping that allows to reach a prescribed consensus value. Figure 2: The behavior of the Lyapunov function given by Theorem 6.


Marcos-Cesar Bragagnolo

Irinel-Constantin Morȃrescu

Jamal Daafouz

Pierre Riedinger

Design of reset strategy for consensus in networks with cluster pattern

This work focuses on the problem of consensus in network of agents with linear reset dynamics. This continues a preliminary work in which we have characterized the consensus value and its stability for networks of linear reset systems. The contributions of this work are the characterization of the convergence speed and the design of the interactions allowing to reach a prescribed consensus value. One numerical example illustrates the results.

Introduction

The problem of agreement of dynamic agents belonging to a network has been studied in many frameworks depending on the application (see [START_REF] Ren | A survey of consensus problems in multi-agent coordination[END_REF] and the references therein). All existing works agree that the connectivity of the network is a main ingredient for consensus of agents with linear [START_REF] Jadbabaie | Coordination of groups of mobile autonomous agents using nearest neighbor rules[END_REF][START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF][START_REF] Ren | Consensus seeking in multiagent systems under dynamically changing interaction topologies[END_REF][START_REF] Moreau | Stability of multiagent systems with time-dependent communication links[END_REF] or nonlinear dynamics [START_REF] Mei | Distributed coordinated tracking with a dynamic leader for multiple Euler-Lagrange systems[END_REF][START_REF] Buşoniu | Consensus for black-box nonlinear agents using optimistic optimization[END_REF]. Therefore, some works have been oriented toward decentralized control design able to preserve the network connectivity [START_REF] Zavlanos | Distributed connectivity control of mobile networks[END_REF][START_REF] Fiacchini | Convex conditions on decentralized control for graph topology preservation[END_REF]. Whenever the connectivity is lost, clustering behavior was emphasized [START_REF] Morȃrescu | Opinion dynamics with decaying confidence: Application to community detection in graphs[END_REF][START_REF] Touri | On approximations and ergodicity classes in random chains[END_REF].

In [START_REF] Bragagnolo | Lmi sufficient conditions for the consensus of linear agents with nearlyperiodic resets[END_REF] we considered networks that are partitioned in several clusters. The agents are able to continuously interact only with neighbors belonging to the same cluster. Moreover, each cluster contains an agent with powerful communication capacity called leader. Each leader can interact with some other leaders via a network with communication constraints. Thus, the leaders will interact only at specific isolated instants that will be defined in the next section as a nearly periodic sequence.

This model can be interpreted in terms of opinion dynamics -decision making process in social networks. The network is partitioned in a number of communities. The opinion of each agent continuously evolves taking into account the opinion of its neighbors. At some discrete times the leaders interact in a dedicated network and reset their opinion. We show that, if no external perturbation occurs and the process continues for a long period of time, all the opinions approach a common one. This global agreement opinion depends on the centrality ( [START_REF] Bonacich | Eigenvector-like measures of centrality for asymmetric relations[END_REF]) of each node inside each community and in the leaders' network. Roughly speaking the centrality of an agent expresses the importance of its opinion in the network. Thus, it characterizes somehow the level of "democracy" inside the network.

All the clusters as well as the network of leaders are represented by fixed, strongly connected directed graphs. The agents have a continuous dynamics but the leaders reset their state when they are communicating between them. In other words, we address the problem of consensus for agents subject to both continuous and discrete dynamics. Precisely, we are focusing on agreement in networks of reset systems, which are a particular class of hybrid systems (see [START_REF] Beker | Plant with an integrator: an example of reset control overcoming limitations of linear feedback[END_REF][START_REF] Nesić | Stability properties of reset systems[END_REF]). The existing literature on reset systems treats mostly linear dynamics.

In [START_REF] Bragagnolo | Lmi sufficient conditions for the consensus of linear agents with nearlyperiodic resets[END_REF] we evaluated and studied the stability of the consensus value when the leaders interact and reset their state in a near-periodic manner. We shown that the consensus value depends only on the initial conditions and the topologies of the involved networks (i.e the networks associated with the clusters and that associated with the leaders). It is noteworthy that the consensus value does not depend on the reset period used for the leaders' opinions. A first objective of this paper is to study the convergence speed of the algorithm proposed in [START_REF] Bragagnolo | Lmi sufficient conditions for the consensus of linear agents with nearlyperiodic resets[END_REF]. A second objective is the design of the network of leaders allowing to reach an a priori specified consensus value. In order to reach this goal, we consider that each cluster has a fixed and known interconnection topology. Therefore, we modify the consensus value of the whole network by changing the weights in the network of leaders. The set of consensus values that can be reached is contained in the convex hull of the initial local agreement values, which, for scalar states, is just the interval defined by the minimum and maximum initial local agreements.

Notation. The following standard notation will be used throughout the paper. The sets of nonnegative integers, real and nonnegative real numbers are denoted by N, R and R + , respectively. For a vector x we denote by x its Euclidian norm. The transpose of a matrix A is denoted by A ⊤ . Given a symmetric matrix A ∈ R n×n , notation A > 0 (A ≥ 0) means that A is positive (semi-)definite. By I k we denote the k × k identity matrix. ✶ k and 0 k are the column vectors of size k having all the components equal 1 and 0, respectively. We also use

x(t - k ) = lim t→t k ,t≤t k x(t).

Problem formulation

We consider a network of n agents described by the digraph (i.e. directed graph) G = (V, E) where the vertex set V represents the set of agents and the edge set E ⊂ V × V represents the interactions.

In the sequel, we consider that the agent set V is partitioned in m strongly connected clusters/communities C 1 , . . . , C m . The state of each agent continuously evolves by taking into account the states of its neighbors belonging to the same community. On top of that, each community possesses one particular agent called leader and denoted in the following by l i ∈ C i , ∀i ∈ {1, . . . , m}. The set of leaders will be referred to as L = {l 1 , . . . , l m }. At specific time instants t k , k ≥ 1, called reset times, the leaders interact between them following a predefined interaction map E l ⊂ L × L. We also suppose that G l = (L, E l ) is strongly connected. The rest of the agents will be called followers and denoted by f j . For the sake of clarity we consider that the leader is the first element of its community:

C i = {l i , f m i-1 +2 , . . . , f m i }, ∀i ∈ {1, . . . , m} (1)
where m 0 = 0, m m = n and the cardinality of C i is given by

|C i | n i = m i - m i-1 , ∀i ≥ 1.
In order to keep the presentation simple, each agent will have a scalar state denoted also by l i for the leader l i and f j for the follower f j . We also introduce the vectors x = (l 1 , f 2 , . . . , f m 1 , . . . , l m , . . . , f mm ) ⊤ ∈ R n and x l = (l 1 , l 2 , . . . , l m ) ⊤ ∈ R m collecting all the states of the agents and all the leaders' states, respectively. We are ready now to introduce the linear reset system describing the overall network dynamics:

   ẋ(t) = -Lx(t), ∀t ∈ R + \ T x l (t k ) = P l x l (t - k ) ∀t k ∈ T x(0) = x 0 (2) where T = {t k ∈ R + | t k < t k+1 , ∀k ∈ N, t k reset time}, L ∈ R n×n
is a generalized Laplacian matrix associated to the graph G and P l ∈ R m×m is a Perron matrix associated to the graph G l = (L, E l ). The components L (i,j) and P l(i,j) of L and P , represent the weight of the state of the agent j in the updating process of the state of agent i when using the continuous and discrete dynamics, respectively. In particular, L has the following block

diagonal structure L = diag(L 1 , . . . , L m ), L i ∈ R n i with L i ✶ n i = 0 n i and P l ✶ m = ✶ m . Due to strong connectivity of C i , i = 1, m and G l , 0 is a simple eigenvalue of each L i and 1 is a simple eigenvalue of P l .
In the sequel, we denote by w i the left eigenvector of L i associated with the the eigenvalue 0 such that

w ⊤ i ✶ n i = 1. Similarly, let v = (v 1 , . . . , v m ) ⊤
be the left eigenvector of P l associated with the eigenvalue 1 such that v ⊤ ✶ m = 1. Due to the structure (1) of the communities, we emphasize that each vector w i can be decomposed in its first component w i,l and the rest of its components grouped in the vector w i,f . Let us introduce the matrix of the left eigenvectors of the communities:

W =      w ⊤ 1 0 • • • 0 0 w ⊤ 2 • • • 0 . . . . . . . . . . . . 0 0 • • • w ⊤ m      ∈ R m×n . (3)
We also introduce the following vectors:

x * (t) = (x * 1 (t), x * 2 (t), ..., x * m (t)) ⊤ ∈ R m , u = (v 1 /w 1,l , v 2 /w 2,l , ..., v m /w m,l ) ⊤ ∈ R m (4
) where x * i (t) is the local agreement value of the cluster i at time t. It is noteworthy that x * (t) is time-varying but piecewise constant:

x * (t) = x * (k) ∀t ∈ (t k , t k+1 ).

Consensus value and its stability analysis

In this section we briefly recall the results that we obtained in [START_REF] Bragagnolo | Lmi sufficient conditions for the consensus of linear agents with nearlyperiodic resets[END_REF]. The reset sequence is defined such that t k+1 -t k = δ + δ ′ where δ ∈ R + is fixed and δ ′ ∈ ∆ with ∆ ⊂ R + a compact set. Thus the set of reset times T belongs to the set Φ(∆)

{t k } k∈N , t k+1 -t k = δ + δ ′ k , δ ′ k ∈ ∆, ∀k ∈ N of
all admissible reset sequences associated with ∆.

Proposition 1 When the collective state x(•) follows the dynamics (2), one has u ⊤ x * (t) = u ⊤ x * (0), ∀t ∈ R + . Moreover, assuming the agents of this system reach a consensus, the consensus value is

x * = u ⊤ W x(0) m i=1 u i . ( 5
)
Let us define the disagreement vector y = x -x * ✶ n . We also introduce an extended stochastic matrix

P ex = T ⊤ P l 0 0 I n-m
T where T is a permutation matrix allowing to recover the cluster structure of L.

In the sequel, we define a quasi-quadratic Lyapunov function satisfying Theorem 1 in [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF] by means of LMI conditions.. Therefore, the following result gives sufficient conditions for the stability of the equilibrium point of x * ✶ n for the system (2).

Theorem 2 Consider the system (2) with T in the admissible reset sequences Φ(∆). If there exist matrices S(δ ′ ), S(•)

: ∆ → R n×n continuous with respect to δ ′ , S(δ ′ ) = S ⊤ (δ ′ ) > 0, δ ′ ∈ ∆ such that the LMI I n -✶ n u ⊤ W ⊤ S(δ a ) I n -✶ n u ⊤ W -Y (δ a ) -✶ n u ⊤ W ⊤ S(δ b ) Y (δ a ) -✶ n u ⊤ W > 0, Y (δ a ) P ex e -L(δ+δa) (6)
is satisfied on span{✶ n } ⊥ for all δ a , δ b ∈ ∆, then x * is globally uniformly exponentially stable for [START_REF] Bonacich | Eigenvector-like measures of centrality for asymmetric relations[END_REF]. Moreover, the stability is characterized by the quasi-quadratic Lyapunov function

V (t) = V (x(t)) max δ ′ ∈∆ (x(t)-x * ✶ n ) ⊤ S(δ ′ )(x(t)- x * ✶ n ) satisfying V (t k ) > V (t k+1 ).
Due to the space limitations we do not provide the proofs of the results above. However, we point out that Theorem 2 requires to solve a parametric LMI which can be approximated by a finite number of LMIs using polytopic embeddings. The set {X ∈ R n×n | X = e -Lδa , δ a ∈ ∆} can be embedded into the polytopic set defined by the vertices Z 1 , . . . , Z h+1 where

Z 1 = I n , Z i = i-1 l=0 (-L) l l! δ l max , ∀i ∈ {2, . . . , h + 1} with δ max = max δ ′ ∈∆
δ ′ , (-L) 0 = I n and 0! = 1. Then, Theorem 2 can be replaced by the following result.

Theorem 3 Consider the system (2) with T in the admissible reset sequences Φ(∆). If there exist symmetric positive definite matrices S i , 1 ≤ i ≤ h + 1 such that the LMI

I n -✶ n u ⊤ W ⊤ S i I n -✶ n u ⊤ W - Y (δ)Z i -✶ n u ⊤ W ⊤ S j Y (δ)Z i -✶ n u ⊤ W > 0, Y (δ) P ex e -L(δ) (7)
is satisfied on span{✶ n } ⊥ for all i, j ∈ {1, . . . , h + 1}, then x * is globally uniformly exponentially stable for (2).

4 Main results

Decay rate analysis

Once the global uniform exponential stability of x * ensured by Theorem 2 we can compute the convergence speed of system [START_REF] Bonacich | Eigenvector-like measures of centrality for asymmetric relations[END_REF]. Denoting it by λ, one has λ = ln λ d δ + δ max (see [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF] for details) where δ max = max δ ′ ∈∆ δ ′ and λ d is the decay rate of the linear difference inclusion (LDI)

x(t k+1 ) ∈ F(x(t k )), k ∈ N (8)
where F(x) = P ex e -L(δ+δ ′ ) , δ ′ ∈ ∆ .

Precisely, for the LDI (8) there exist M > 0 and ξ ∈ [0, 1] such that

x(t k ) -x * ✶ n ≤ M ξ k x(0) -x * ✶ n , ∀k ∈ N (9)
and λ d is defined as the smaller ξ satisfying (9). Thus, in order to quantify the convergence speed of system (2), we only have to evaluate λ d . Let us denote again y = x-x * ✶ n and note that V (y) defined by Theorem 2 is a norm. That implies there exist α, β > 0 such that

α y 2 ≤ V (y) ≤ β y 2 .
Consequently, one obtains that the decay rate λ d coincides with the decay rate of V . Thus, the following result can be derived directly from Theorem 2.

Proposition 4 Assume there exist α > 0, β > 0, ξ ∈ (0, 1] and the matrices S(δ ′ ), S•) : ∆ → R n×n continuous with respect to δ ′ , S(δ ′ ) = S ⊤ (δ ′ ) > 0, δ ′ ∈ ∆ fulfilling the following constraints

                 αI n ≤ S(δ ′ ) ≤ βI n , ∀δ ′ ∈ ∆ ξ 2 I n -✶ n u ⊤ W ⊤ S(δ a ) I n -✶ n u ⊤ W - Y (δ a ) -✶ n u ⊤ W ⊤ S(δ b ) Y (δ a ) -✶ n u ⊤ W > 0, Y (δ a ) P ex e -L(δ+δa) ( 10
)
on span{✶ n } ⊥ for all δ a , δ b ∈ ∆. Then, the decay rate is defined as

λ d = min ξ satisfies (10) ξ and x(t k ) -x * ✶ n ≤ β α (λ d ) k x(0) -x * ✶ n , ∀k ∈ N. Remark 1 It is noteworthy that 0 < λ d ≤ 1

and for a priori fixed values of α, β we can use the bisection algorithm to approach as close as we want the value of λ d .

Remark 2 To complete the decay rate analysis, we can consider that P ex , L and λ d are fixed and perform a line search to find the nominal reset period δ that ensures the convergence speed constraint. In other words, we check if [START_REF] Moreau | Stability of multiagent systems with time-dependent communication links[END_REF] has solutions for ξ = λ d and δ heuristically sweeping the positive real axis. Moreover, we can progressively decrease λ d and re-iterate the line search in order to find the smaller reachable decay rate.

Convergence toward a prescribed value

In what follows we assume that the value x * is a priori fixed and at least a vector u satisfying (5) exists. Under this assumption we are wondering if there exists a matrix P l that allows system (2) to reach the consensus value x * . It is worth noting that the network topology is still considered fixed and known for each cluster. Under these assumptions, a consensus value is imposed by a certain choice of v such that v ⊤ ✶ m = 1 and v left eigenvector of P l associated with the eigenvalue 1. In other words we arrive to a joint design of P l and the Lyapunov function V guaranteeing that the trajectory of (2) ends up on x * .

Theorem 5 Let us consider the system (2) with T in the admissible reset sequences Φ(∆) and let x * be a priori fixed by a certain choice of v. If there exist matrices

R(δ ′ ), R(•) : ∆ → R n×n continuous with respect to δ ′ , R(δ ′ ) = R ⊤ (δ ′ ) > 0, δ ′ ∈ ∆ and P l ∈ R m×m such that the LMI   Z(δ a ) Y (δ a ) -✶ n u ⊤ W ⊤ Y (δ a ) -✶ n u ⊤ W R(δ b )   > 0, Y (δ a ) P ex e -L(δ+δa) Z(δ a ) I n -✶ n u ⊤ W ⊤ + I n -✶ n u ⊤ W -R(δ a ) (11)
with the constraints

v ⊤ P l = v ⊤ , P l ✶ m = ✶ m , P l(i,j) ≥ 0 is satisfied on span{✶ n } ⊥ for all δ a , δ b ∈ ∆, then x * is GUES for (2). More-
the stability is characterized by the quasi-quadratic Lyapunov function

V (t) = max δ ′ ∈∆ (x(t) -x * ✶ n ) ⊤ R(δ ′ ) -1 (x(t) -x * ✶ n ) satisfying V (t k ) > V (t k+1 ). Proof: First notice that (I n -✶ n u ⊤ W ) ⊤ S(δ a ) -I n S(δ a ) -1 × S(δ a )(I n -✶ n u ⊤ W ) -I n ≥ 0 leads to (I n -✶ n u ⊤ W ) ⊤ S(δ a )(I n -✶ n u ⊤ W ) ≥ (I n -✶ n u ⊤ W ) ⊤ + (I n -✶ n u ⊤ W ) -S(δ a ) -1
Thus, once the solution to the LMI problem ( 11) is obtained we can define

S(δ a ) = R(δ a ) -1 and S(δ b ) = R(δ b ) -1 . Then:   Z(δ a ) Y (δ a ) -✶ n u ⊤ W ⊤ Y (δ a ) -✶ n u ⊤ W S(δ b ) -1   > 0 where Z(δ a ) = (I n -✶ n u ⊤ W ) ⊤ + (I n -✶ n u ⊤ W ) -S(δ a ) -1 and hence   Z(δ a ) Y (δ a ) -✶ n u ⊤ W ⊤ Y (δ a ) -✶ n u ⊤ W S(δ b ) -1   > 0 where Z(δ a ) = (I n -✶ n u ⊤ W ) ⊤ S(δ a )(I n -✶ n u ⊤ W ).
By Schur complement, the last LMI is nothing than (6) in Theorem 2.

Moreover, the constraints v ⊤ P l = v ⊤ , P l ✶ m = ✶ m and the coefficients of P l positive ensure the matrix P l is row stochastic and the consensus value is exactly x * .

5 Illustrative examples

Academic example

An academic example consisting in a network of 5 agents partitioned in 2 clusters (n 1 = 3, n 2 = 2) is used in the sequel to illustrate the theoretical results. We consider the dynamics (2) with

L =       4 -2 -2 0 0 -1 1 0 0 0 0 -2 2 0 0 0 0 0 3 -3 0 0 0 -1 1      
, P l = 0.45 0.55 0.25 0.75 [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF] and the reset sequence given by δ = 0.5 and δ ′ k randomly chosen in ∆ = [0, 0.2]. The initial condition of the system is x(0) = (8, 7, 9, 2, 3) and the corresponding consensus value computed by ( 5) is x * = 4.6757. The convergence of the 5 agents towards x * is illustrated in Figure 1 emphasizing that the leaders trajectories are non-smooth while the followers trajectories are.

The table below collects the first 10 time intervals between consecutive reset instants. As expected, these time intervals have random lengths within [0.5, 0.7] and no monotony occurs. The jumps and decreasing of the Lyapunov function defined by Theorem 2 are pointed out in Figure 2. In Figure 4 the consensus value was fixed as x * = 3.5. The obtained P l matrix was P l = 0.3010 0.6990 0.0874 0.9126 .

Figure 4: The states of a system (x * = 3.5).

Larger network analysis

In order to prove that the algorithms are implementable in real networks we consider in the following a larger system. Precisely, we present an example consisting of a network of 100 agents partitioned in 3 clusters. The size of the clusters as well as the connections between agents are randomized, resulting in non-symmetric matrices L and P l . The random initialization leads at n 1 = 59, n 2 = 20, n 3 = 21 and

P l =   0.
The initial condition is also randomized but, in order to guarantee a relatively large interval for the possible consensus value, for the first cluster the initial states of the agents are randomly chosen within [0, 3], for the second one within [START_REF] Bragagnolo | Lmi sufficient conditions for the consensus of linear agents with nearlyperiodic resets[END_REF][START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF] and for the third one within [START_REF] Hetel | Stabilization of linear impulsive systems through a nearly-periodic reset[END_REF][START_REF] Moreau | Stability of multiagent systems with time-dependent communication links[END_REF]. The corresponding initial local agreement values are 1.2970, 5.2578 and 8.7556, respectively. We illustrate the theoretical results by using the dynamics (2) with the reset sequence given by δ = 0.5. The corresponding consensus value computed by ( 5) is x * = 4.2562. The convergence of the 100 agents towards x * is shown in Figure 5.

Conclusions and perspectives

In this work we have considered networks of linear agents partitioned in several clusters disconnected one of each other. Each cluster has a linear impulsive leader that resets its state nearly periodically by taking into account the state of some neighboring leaders. In [START_REF] Bragagnolo | Lmi sufficient conditions for the consensus of linear agents with nearlyperiodic resets[END_REF] we have characterized the consensus value for this type of networks and we have performed its stability analysis. In this work we provided the convergence speed towards consensus and we designed the interconnection network between the leaders allowing to reach a prescribed consensus value.

Figure 1 :

 1 Figure 1: The state-trajectories of the agents converging to the calculated consensus value.

Figure 2 :

 2 Figure 2: The behavior of the Lyapunov function given by Theorem 2.

Figure 3 :

 3 Figure 3: The states of a system (x * = 6.5).

Figure 5 :

 5 Figure 5: The state-trajectories of the agents converging to the calculated consensus value.To find the decay rate λ d we use the bisection algorithm as stated in Remark 1. In Figure6we demonstrate that the initial conditions of Lyapunov

Figure 6 :

 6 Figure 6: Lyapunov function for different conditioningsThe consensus value is always a convex combination of the initial agreement values of the clusters. Therefore, for the initialization above, any consensus value can be imposed between 1.2970 and 8.7556. In Figure7the consensus value was fixed at x * = 6.5 and one obtained P l matrix is

Figure 7 :

 7 Figure 7: The states of a system (x * = 6.5).

t 1

 1 -t 0 0.6189 s t 6 -t 5 0.5979 s t 2 -t 1 0.6131 s t 7 -t 6 0.5372 s t 3 -t 2 0.6433 s t 8 -t 7 0.6401 s t 4 -t 3 0.6023 s t 9 -t 8 0.6965 s t 5 -t 4 0.6553 s t 10 -t 9 0.6613 s


I Dudek

J Y Blaise

Visualising time with multiple granularities: a generic framework

When investigating the evolution of historic architecture, and putting together various pieces of information (each with its specific characteristics in terms of precision, scope and reliability), time points and intervals the analyst will identify are often inconsistent in terms of granularity. Our contribution introduces graphic solutions that combine multiple aspects of the parameter time, and particularly multiple granularities. As a first step, we initially propose a visual comparison of 25 alternative calendars, covering a wide range of historic periods and cultures or civilisations.This first result is then extended to propose a more generic framework for visualising time with multiple granularities. It is applied on two very different test cases. The contribution will present the concepts and ideas behind this research, as well as their practical applications on the tests cases and accordingly it possible benefits for researchers and practitioners in historic sciences.

Introduction

Investigating the evolution of historic artefacts most often starts with the cumbersome task of putting together various pieces of information, each with its specific characteristics in terms of precision, scope and reliability. Naturally, time slots are among the main clues analysts expect to spot when filtering and cross-examining these pieces of information. In order to proceed to any type of reasoning (teleological or causal) one has to place all the data and pieces of information. But due to the very nature of historic data sets -heterogeneity, uncertainty, missing data, uneven distribution in time (etc.) -time points and intervals the analyst will identify are often inconsistent in terms of granularity. Time intervals, typically the overall lifetime of an artefact, its periods of construction or modification, may be described by expressions like "between the last quarter of the XIIIth c. and the middle of the XIVth c.", whereas some punctual events may be recorded more precisely, in cases like "the fire that occurred at night on Nov 29 th 1554" or "the town's siege between March 1445 and November 1445". In parallel, describing an artefact's life evolution often implies taking into consideration pieces of information that correspond to regular or cyclic events, with here also inconsistent granularities. Typically, when analysing an isolated chapel at high altitude, the analyst will need to cope with a fuzzy cyclic behaviour -the chapel is inaccessible due to snow for a certain number of weeks during the year -as well as with a well-defined cyclic behaviour -a pilgrimage is organised on the saint's day every year. In other words, may it be because of the nature of historic data sets, or may it be because of the heterogeneity of the events we need to report, there are very few solutions analysts can count on if they need to visualise in a consistent, insight-gaining manner the time slots they have spotted. In historic sciences it appears clearly that the handling of multiple time granularities is one of the major bottlenecks in the analyst's visualisation effort. Naturally, conveying properly doubts is an even harder challenge -with numerous overlapping issues, as will be shown. Our research aims at giving analysts means to combine in a single visualisation multiple aspects of the parameter time, and particularly multiple granularities. As a first exploratory step, we initially focused on a visual comparison of 25 alternative calendars covering a wide range of historic periods and cultures or civilisations (Julian and Gregorian calendars of course , but also Babylon, ancient Egypt, China and Japan, Incas, Inuits, Burma and Bali, etc.). The visualisation sums up in a synthetic way key aspects of calendars (cycles, divisions, period of validity, area of validity, the intercalation -i.e. correction mechanisms, etc.) corresponding to alternative time granularities. The visualisation helps underlining legacies in between periods and areas, alternative visions of time as linear or cyclic, common or opposing choices like solar/lunar/lunisolar, alternative divisions of the year, mechanisms to cope with intercalations, etc.. A prominent service offered by this visualisation is that it enabling comparisons at various time granularities, "within the eyespan", to quote E.R Tufte. This first result has been extended to propose a more generic framework for visualising time with multiple granularities. It is applied on two test cases representing different scales and territories. The contribution will present the concepts and ideas behind this research, as well as their practical applications on the tests cases and accordingly it possible benefits for researchers and practitioners in historic sciences.

Research context

Reasoning on the historic artefacts requires a deeper understanding of the time parameter than what we understand of it in everyday life. And if in addition we want to use visualisations to inquire into what is behind our time-oriented data, we need even more extensive understanding, analysis and control over the time parameter. In parallel, Information Visualisation and Visual Analytics are multidisciplinary fields that are increasingly applied as a critical component in scientific research where visual reasoning is a relevant method (i.e. analytical method that employs human perception in order to inform, reveal unknowns or as a part of the thinking process itself (MacEachren et al.2005,139-160)). In other words visualisation is about : … pictures of numbers … pictures of nouns … pictures of verbs, the representation of mechanism and motion, of process of dynamics, of causes end effects, of explanation and narrative… (Tufte1997, 126). This is probably the reason why the time parameter has been carefully studied and structured notably in and around the above fields -see for example (Tufte 1990, 151), [START_REF] Chardonnel | Time-Geography: individuals in time and space[END_REF] (Knight 1993, 401-419), (Perlata 2004, 241-248), (Matoušek 2007, 239-254), (Allen 1984, 124-154) -although it doesn't mean that we at this stage fully understand its nature. As demonstrated in (Aigner et al. 2008, 47-60) multiple aspects of time can be taken into account : time progression (linear time vs. cyclic time), time structure (ordered time, branching time, time with multiple perspectives), temporal entities and their relations (time points, time intervals), temporal scale (ordinal time, discrete time, continuous time, discontinuous time), time granularity, uncertainty of temporal position of temporal entities, etc.. However as sagely remarked "In theory, there is no difference between theory and practice. But in practice, there is. (…) Theory and practice both have limitations. Sometimes, practice proves the value of a good theory …" (West 2010).

Theory vs. practice

Theoretical approaches are crucial in understanding the time parameter, still they are not the only solution to the problem. Another approach can be observing facts: here, historic calendars. Calendars are basically an effort to position oneself in time, by observing and measuring objectively one or several phenomena that occur repeatedly, on a regular basis -may it be the course of planets, hunting seasons, market days in the neighbouring cities. In other words, understanding calendars means understanding how time is seen by a society, in a given space. This way calendars tell us something about societies, but in addition they also demonstrate the complexity of the time parameter, with several repetitive cycles to combine in a way that has to be understood by everyone (night & day, seasons & years, cultural events, etc.). Finally, calendars are used not only to position oneself in absolute time, but also to position oneself with regards to other specific temporal slot, may they be "how many months since my last check-up at the dentist" or less depressing "how many grand-fathers since Copernic's discovery"? (account in grandfathers, as a tribute to T. Pratchett). Naturally this applies both to past and to future events. Accordingly calendars are de-facto examples of (at least) three key issues when talking about time:

• positioning a time slot inside a continuum, • handling alternative cycles, granularities, rhythms, • ordering, comparing, analysing time slots and the way they are depicted here and there, and trying to make sense out of it.

In this contribution, we will focus on historic calendars, i.e. calendars that have been introduced at sometime in the past, have evolved (Julian to Gregorian for instance), ceased to be used (Coligny Gaulish for instance), or remained unchanged (Chinese calendar for instance). The word "historic" might be here a bit confusing, however we have chosen it in order to insist on two aspects that are of importance:

• Handling calendars that are not used any more implies to some extent handling something known to us through testimonies, (i.e. questionable data sets, and accordingly implies confidence assessments).

•

Handling calendars that have succeeded to one another -may we know of it or not -implies highlighting parenthoods on one hand (Babylonian -Greek; Egyptian -French Republican)

and on the other hand calls attention to the consistency of dating (shift of the new year in the Roman calendars).

Let us illustrate a classic implication of this last point with some well-known example:

To honour the date of death of Cervantes, Shakespeare and De la Vega, who supposedly died on the same day, April 23, 1616, UNESCO established April 23rd as the International Day of the Book (UNESCO 2011). But Shakespeare died on a different day than Cervantes and de la Vega -the date of his death (April 23, 1616) is given according to the Julian calendar, and not in the Gregorian calendar, already adopted by Spain but not by England in 1616. Since at that time the Gregorian calendar was ten days ahead of the Julian, the Spanish authors actually died ten days earlier than Shakespeare, whose date of death according to the Gregorian calendar was May 3, 1616. In other words, we are officially asked to remember a fact -three main authors dying the very same day -that never occurred, because of a ten days shift in calendars.

From calendars to architectural changes?

Calendars are an interesting topic by themselves, but what is the connection with architectural changes? Why should we "start from the globe" -time in calendars -when what we are interested in is analysing the evolution of pieces of architecture?

The first reason is a very simple one: there is a clear relation of calendars to architecture. A well known example is the iterative reconstruction of the Temple in Ise (Japan), every 20 years -and 20 years is precisely the Japanese calendar's main cycle (along with eras, connected with the country's rulers). Another simple example is the orientation of Christian churches and chapels in the medieval period. These edifices are usually dedicated to a given saint, and when possible oriented with the apse towards the East at sunrise on the Saint's day, a clear dependence of architecture to the Christian calendar.

The second reason why we chose to "start from the globe" results from an analysis of our previous chronology assessment contributions (Dudek and Blaise 2008, 349-357), (Dudek and Blaise 2011, 632-641), (Blaise and Dudek 2010, 91-100). We have introduced in the past years a number of visualisations aimed at facilitating analytical reasoning. Yet these visualisations rely on a single and common modelling choice, namely -using Aigner's terminology -a one-year chronon time granularity.

And, although we did investigate ordinal time rather than discrete time (Dudek and Blaise 2011, 632-641), branching time rather than ordered time (Blaise and Dudek 2011, 8) we are far from having investigated in a thorough way the temporal info we have about architectural changes. And this relative thinness is neither a choice nor an accident. It is the direct consequence of how time is viewed in the context of historical data sets where it is basically seen as a dating issue. Once you have said "circa 1 st half of the XIVth century" you're done with the temporal aspect. And so we believe that, if we are to further investigate the time parameter we need to handle historic data sets that go beyond dating -and calendars are well suited to that need. We expect that developing better tools to model and visualise temporal aspects of historic calendars will help us to re-read our data sets and, for instance, to uncover similarities and differences, constructive innovations, etc..

Issue and content

What does it take to analyse similarities and differences between calendars? It naturally requires a modelling effort, through which common features can be pointed out. Poincaré wrote … it is in the relations alone that objectivity must be sought, it would be vain to seek it in beings considered as isolated from one another… [START_REF] Poincaré | Conversion of Hijri A[END_REF] In a way this contribution's main issue could be seen as finding a mean to compare in an insight gaining manner historic calendars. Because calendars were designed that way, modelling will be done by extension -with a subset of 25 calendars chosen (Section 3.1). Furthermore, we will need to integrate confidence assessments in cases where the data is questionable. Given a predefined set of descriptors for each calendar, we will need to develop visualisations in order to sum-up visually a specific calendar's descriptors, or to compare it to others (Section 3.2). Finally, we will need to check out whether or not the proposed framework helps uncovering parenthoods (preferably unexpectedotherwise the whole effort might have been vain).

An exploratory transfer of the calendar framework to the handling of multiple time granularities on architectural cases will be proposed in section 4. Remaining implementation challenges and perspectives of this research will be discussed in section 5.

One point has to be made clear here: this research is not about the parameter time in general, but about how time is handled inside calendars -i.e discrete time, with a one-day chronon. Result expected is a set of visualisations helping us to analyse where and when historic calendars have been used, in what they compare to one another. Finally, computational platforms helping users to translate 21st April 2023 (Gregorian calendar) into Chinese, Muslim, Hebrew or other calendars already exist, this aspect will therefore not be mentioned (see for example (Cultural-China 2010), (Philosophia Islamica 2009), (Hebcal Jewish Calendar 2012)) .

Modelling and visualising historic calendars

As a first step, we initially focused on visual comparison of 25 alternative calendars covering a wide range of historic periods and cultures or civilisations.

(Japanese (Taiintaiyoreki), Tibetan, Babylonian, Burmese, Chinese, Hebrew, Pre-Islamic (DŜahilijja), Symmetry454, Incas (solar), French republican, Egyptian, Soviet, Coptic, Julian, Gregorian, Byzantine, Roman (republican), Inuit, Continental Celtic (Coligny), Muslim calendar (Hijri), Attic state calendar, Maya and Aztec calendars (Xiuhpohualli, Tonalpohualli), Badí', Incas (lunar), and Balinese Pawukon calendars)

Modelling

At first glance a calendar is made of common notions (day, season, year for instance) that need to be adjusted depending on the culture (day finishes with the sunset in the Jewish calendar, there are nine seasons in the Inuit Calendar, year started in November in Gaulish Coligny calendar).

In fact there also are less obvious features that need to be taken into consideration if we are to crossexamine calendars:

• What is the repetitive phenomenon the calendar bases on (sun / moon / seasons, etc.)? In the following section we present how these notions are actually transferred into graphics (visual cues used), and evaluated on real cases. It has to be made clear that initially we focused on the graphics -we needed to check out whether the whole idea of starting from the globe could make sense. So the implementation we propose is dynamic but poorly structured -script interpretation. Among perspectives of this research is to develop a robust OO-based structure to represent the notions we have identified here above.

Visualising

The first visualisation we propose sums up in a synthetic way fifteen key descriptors of calendars (Fig. 1) distributed inside six visual components (Fig. 2). The most widespread calendar system today is the Gregorian calendar (solar) introduced in by Pope

Gregory XIII in a papal bull signed on 24 February 1582. It was adopted in turn by different countries. Gregorian calendar modified the Julian calendar's regular cycle of leap years (leap years are exactly divisible by four except for years that are exactly divisible by 100, but the centurial years that are exactly divisible by 400 are still leap years). A Week is the smallest granule (7 days). Each year counts 12 months (365 days in common years, 366 days in leap years). Beginning of a year was maintained on 1st January.

Until the adoption of a resolution of the International Meridian Conference, each town used its own local time. Lengths of each day-time hour and night-time hour were unequal and depended on the geographical latitude and varied according to the seasons -what is more a day could begin at noon, sunrise or sunset, reflecting the wide diversity of customs for defining and counting the hours across the European continent (Fig. 3).

Fig. 3 Visual comparison of the Julian and Gregorian calendars

Influence of a culture and climate is plainly visible in Inuit calendar. The absence of a notion of day or week in Inuit's culture, as well as surprising number of seasons (related to the cycles of nature). On the other hand the French republican calendar has a clear "goddess reason" decimal structure (Fig. 4).

Fig. 4 Visual comparison of the Inuit and French republican calendars

In order to foster comparison of the whole collection (Fig. 5), we developed a second visualisation underlining:

• legacies in between periods and areas (e.g. The Coptic Year is the extension of the ancient Egyptian civil year retaining its subdivision into the three seasons.), • presence of cycles, alternative divisions of the year (e.g. Agriculture related calendars -Balinese Pawukon calendar or Incas agricultural calendar -seem quite weird compared to a calendars based on a sidereal year.), • mechanisms to cope with intercalations, etc.

Fig. 5 A visual comparison of 25 calendars

This comparison allowed us to ascertain similar mechanisms of time discretisation -day plays role of chronon in an overwhelming majority of cases and it is aggregated into widely used, standard granules (i.e. week, month, season, year, century) or some less employed ones (e.g. days outside a year). However the exact number of days in a given granule substantially differs (e.g. 12 months in a common year is not a rule but only a dominant trend). Moreover beginning of time countdown and originating position of temporal scale strongly varies. These parameters as well as intercalation mechanisms, beginning of a year or a day are culture dependent -showing us more about societies and their way of life than about the time.

A very common and instructive parameter is periodicity of calendars -presence of natural or calendar based cycles. Once again, cultural based cycles (e.g. ruler's lifetime, market day's cycle, unlucky day's cycle, intervals associated with different groups of deities, …) throws light on humans and societies, zones of influences helping us in teleological reasoning, etc... Natural cycles (climate or astronomical related) although profoundly built in calendar structure are independent from the calendar structure -even in most precise calendars they move slightly inside a sequence of a year. This relative freedom of natural cycles is reinforced by a recurrent phenomenon: a discontinuity of time in calendars due to human manipulation -time in calendars is stretched or shortened from time to time (e.g. 80 additional days in year 46th BC, 11 days less in 1582 AD a.s. in Madrid and Cordoba, but not in Stratford-upon-Avon or in Southampton). This first result has been extended to propose a more generic framework for visualising time with multiple granularities. It is applied on two different test cases: chapel of St Anne in Southern Alps (France) and the belfry of Cracow's former town hall in (Poland).

Visualising time-oriented historical data

Naturally the visualisation of time-oriented data poses various types of difficulties, with a number of them generating diverse types of uncertainties:

• modelling choices of temporal variables,

• data credibility (i.e. heuristic accuracy and bias of analyst),

• inconsistency of data -that implies possibility of various scenarios,

• incompleteness of data,

• subjectivity of choices (amount of interpretation or personal judgment included),

• approximations and imprecision in data description (e.g. How to interpret expressions like probably in 1567?), • temporal resolution of data -that relates to temporal granularity, • etc.

All these elements should be integrated into any visualisations to improve the cognitive task of spatiotemporal understanding. In this paper we will limit our discussion to the last point that relates to time granularity. We will start with a brief introduction into problems posed by visualisation of datasets characterised by varying temporal granularity. In a following section we will present a proposal framework of a method of visualising time with multiple granularities.

Visualisation of datasets characterised by varying temporal granularity

Historical data sets are not consistent in terms of temporal granularity. In other words the individual temporal resolution of pieces data of may vary. Let's take as an example three different pieces of information concerning the same object:

A fire in the town hall's tower took place in summer 1543.

A modification of a tower started on 15th August 1543. A big quantity of bricks have been bought in August 1543.

Each piece of information has its own temporal granularity. If the chronon of our visualisation (the smallest unit) is one civil year (date format YYYY), information about the events that occurred in the same year can be represented only as a group of events that took place in 1543. What is more other hints about temporal relations between these events (i.e." in summer" contains "in August" contains "15th August") will disappear.

If our choice for the chronon is one day (date format DD MM YYYY), granularity of the visualisation will exceed the natural temporal granularity of the underlying information. In such situations the description and visualisation of events compels to introduce approximated, interpretation-derived values, thereby reinforcing the global uncertainty on temporal aspects (i.e."in summer" does no mean each and every summer day). In other words, whatever chronon we choose, and represent, there will be pieces of information that just don't fit -either they are too "thin" and the foot moves in the shoe, or too big and the foot is shrunk to fit in the shoe. Accordingly, and taking advantage of what we had observed on the variable granularity of calendars and on the importance of fuzzy periodic comportment of seasons, we have tried to support timeoriented reasoning tasks with mechanisms that would display in a unique visual layout several granularities at a glance. The visual formalism, first experimented on calendars and seasons, provides a simple solution to handle both a day granularity and more fuzzy intervals within a cyclic-time enhancing visualisation (Fig 6).

It is in fact a rather generic formalism (it could be applied to year and centuries, or to any other combination) that bases on two principles:

• concentricity on one hand -mechanism to segregate granularities,

• sector vs. point on the other hand -mechanism to allow switches from chronon to granules, including fuzzy granules. This type of visualisations may be reorganised according to additional criterion (e.g. by events type) in order to help in reasoning. It is also possible to produce them for a selected time span (e.g. two decades, a century or a whole life of an artefact (Fig 8).

Fig 8 Visualisation produced for a whole life of the artefact. Note that all the events related to the chapel took place in summer (i.e. before st Anne's day) except of a collect of the money and avalanche -a fact very easy to consider as obvious (altitude 2400m) once the visualisation did the job for us…

Linear and cyclic visualisation modes underline different particularities of the data sets: it should be stated clearly that their combination notably reinforces their power of assistance in reasoning. What this simple experiment shows is not that one is better than the other -the basic linear timeline is for instance very useful in underlining temporal densities -but digging into that temporal aspects requires to think outside the square in terms of visualisation.

The second case study is the belfry of Cracow's former town hall, and more precisely its fires. Although we managed to visualise all dates of known fires of the artefact with their specific temporal resolution, it is hard to find any regularity basing our reasoning on four cases only. One could be tempted to say that : the oldest historical sources are less precise in terms of dating. We have therefore verified this hypothesis on the ensemble of buildings that furnished the entire Main Market Square in Cracow (Fig 10) and it turned out to be false. Unsurprisingly, we notice no regularity, no cyclic comportment inside these datasets.

Conclusions

This contribution presents bases of a method we have tried to develop in order to visualise time with multiple granularities, in order to support reasoning on various aspects of temporal relations (cyclic or fuzzy periodic comportments) in the context of heterogeneous temporal data sets. In short, this experience was primarily about "shaking the tree" of possibilities when one needs to handle multiple granularity.

At the current stage of development we wish to restrict our conclusions to the following remarks:

• properly designed visualisation helps in reasoning (visual comparisons, visual thinking)

• study of cyclic and fuzzy periodic behaviour may help in better understanding data sets we handle in the context of historic sciences, • periodic behaviour analysis requires specific visual tools (beyond basic linear timelines),

• differently localised artefacts may necessitate different visual instruments -'tailoring' to the local conditions (in particular to the succession of calendars with various -sometimes localtime discontinuities, cycles of seasons, time granulation, etc.), • if we deal with the notion of time in our research, it is worth to take some time to think about "time" for itself, and not about time as a date stamp we need to put on a given piece of data.

It has to be said clearly that further work, especially in terms of implementation, is necessary if we wish to further investigate potential benefits and drawbacks of this approach. Yet there is one lesson that probably deserves to be drawn in conclusion: although most often a risky bet, starting from the globe -what we did by starting from calendars in order to depict temporal aspects of architectural changes -may be a fruitful attitude sometimes; in particular when talking about things we think we

Fig. 1

 1 Fig. 1 Visual encoding of the key descriptors taken into consideration in the comparison of calendars.

Fig. 6

 6 Fig. 6 Cyclic time visualisation mode exploits a 'clock' metaphor -one o'clock stands for beginning of January. Beginning of astronomical seasons is marked by colour dots and meteorological seasons are represented by coloured sectors ('rose of seasons') -they may not coincide (b) 4.2 Impact on representing architecture changes

Fig. 7

 7 Fig.7 St Anne chapel a) cyclic time visualisation mode; b) timeline -Different colours mark different types of events. The overall evolution of the chapel is marked with the brownish line. All known transformations were described according Gregorian calendar.

  Fig 9 The belfry of Cracow's former town hall. The classic timeline indicates intervals of transformations (green colour) and fires of the artefact (orange colour). a) average meteorological seasons do not coincide with the astronomical seasons, summer is the longest season in Cracow, no cyclic event for this artefact has been found

Fig

  Fig 10 a timeline listing all known fires of the ensemble of buildings that furnished the entire Main market Square in Cracow -a fire in town is a punctual phenomenon.