Paolo Frasca
email: paolo.frasca@gipsa-lab.fr

Sophie Tarbouriech

Luca Zaccarian
email: zaccarian@laas.fr

Hybrid Models of Opinion Dynamics with Opinion-dependent Connectivity

Keywords: Hybrid dynamical systems, opinion dynamics, Lyapunov analysis

Hybrid models of opinion dynamics with opinion-dependent connectivity

Introduction

Prior expertise in consensus and consensus-seeking dynamics is leading control scientists to study the evolution of opinions in social networks, which can be described by similar dynamics. An abundance of mathematical models has been proposed and studied in social sciences, economics, physics, and applied mathematics: [START_REF] Friedkin | The problem of social control and coordination of complex systems in sociology: A look at the community cleavage problem[END_REF][START_REF] Proskurnikov | A tutorial on modeling and analysis of dynamic social networks[END_REF] provide recent surveys that are oriented to the control community. Indeed, the topic of opinion dynamics has become a popular and distinct topic in control research, as evidenced by papers like [START_REF] Acemoglu | Opinion fluctuations and disagreement in social networks[END_REF][START_REF] Altafini | Consensus problems on networks with antagonistic interactions[END_REF][START_REF] Frasca | Distributed randomized algorithms for opinion formation, centrality computation and power systems estimation[END_REF][START_REF] Parsegov | Novel multidimensional models of opinion dynamics in social networks[END_REF].

Models of opinion dynamics need to explain both agreement and disagreement as potential outcomes of the dynamical evolution. In some models, this feature is allowed by including opinion-dependent limitations in the relative influence between individuals, that is, in the connectivity of the social network. Generally speaking, ⋆ The research of P. Frasca has been partly supported by Université de Toulouse III and by Institut National des Sciences Appliquées, Toulouse, France. A preliminary and incomplete account of our results has been presented in [START_REF] Frasca | A hybrid model of opinion dynamics with limited confidence[END_REF]. these limitations postulate that individuals do not influence each other if their opinions are too far apart. The simplest form of limitation -referred to as "bounded confidence"-is based on a fixed threshold: individuals interact if and only if their opinions are closer than the threshold. The resulting nonlinear dynamics has been popularized in the control community by [START_REF] Blondel | On Krause's multi-agent consensus model with state-dependent connectivity[END_REF], who analyzed the seminal discrete-time model by [START_REF] Hegselmann | Opinion dynamics and bounded confidence: models, analysis and simulation[END_REF]. Afterwards, many variations of this model have been studied, including continuous-time dynamics [START_REF] Blondel | Continuous-time average-preserving opin-ion dynamics with opinion-dependent communications[END_REF][START_REF] Yang | Opinion consensus of modified Hegselmann-Krause models[END_REF][START_REF] Jabin | Clustering and asymptotic behavior in opinion formation[END_REF][START_REF] Martin | Continuoustime consensus under non-instantaneous reciprocity[END_REF], heterogeneous thresholds [START_REF] Mirtabatabaei | Opinion dynamics in heterogeneous networks: Convergence conjectures and theorems[END_REF], continuous distributions of opinions [START_REF] Roozbehani | Lyapunov analysis of quadratically symmetric neighborhood consensus algorithms[END_REF][START_REF] Canuto | An Eulerian approach to the analysis of Krause's consensus models[END_REF], and multidimensional opinions [START_REF] Nedic | Multi-dimensional Hegselmann-Krause dynamics[END_REF][START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF][START_REF] Etesami | Game-theoretic analysis of the Hegselmann-Krause model for opinion dynamics in finite dimensions[END_REF][START_REF] Wang | Noisy Hegselmann-Krause systems: Phase transition and the 2r-conjecture[END_REF]. These dynamics typically induce the clusterization of the opinions, that is, the population splits into separate groups of individuals having a common opinion.

In this paper, we study opinion dynamics with opiniondependent connectivity that are defined by hybrid dynamical systems. According to the hybrid framework, our dynamics are represented by the combination of continuous flow dynamics and discrete jump dynamics. The flow embodies the attractive forces between the agents: it is defined by an ordinary differential equation whose right-hand side is a scaled Laplacian. At the same time, the jumps describe the activation or deactivation of the pairwise interactions between agents. Actually, in this paper we study two different jump rules. The first rule is based on fixed thresholds that distinguish between the interactions being present or not. As such, it defines a dynamics that is a hybrid system version of the continuous-time dynamics studied in [START_REF] Blondel | Continuous-time average-preserving opin-ion dynamics with opinion-dependent communications[END_REF] as a variation of the discrete-time Hegselmann-Krause (HK) model [START_REF] Hegselmann | Opinion dynamics and bounded confidence: models, analysis and simulation[END_REF]. The original HK model is not symmetric in the weights of the interactions, leading to some additional difficulties in the analysis: this fact has led researchers to propose symmetrized versions of the HK model that are amenable to finer study and keep a close similarity with the HK model: this was done in [START_REF] Blondel | Continuous-time average-preserving opin-ion dynamics with opinion-dependent communications[END_REF] and followed up in [START_REF] Ceragioli | Continuous and discontinuous opinion dynamics with bounded confidence[END_REF][START_REF] Yang | Opinion consensus of modified Hegselmann-Krause models[END_REF][START_REF] Wang | Noisy Hegselmann-Krause systems: Phase transition and the 2r-conjecture[END_REF]. We study the asymptotic properties of the novel hybrid model, showing (as expected) convergence to clustered opinions. The second rule, instead, features adaptive scale-invariant thresholds that activate the interactions depending only on the relative distances between the opinions. We also study the asymptotic properties of this dynamics, showing not only convergence to clustered opinions, but also stability of the set of equilibria. This stability property actually implies that clusterization is uniform in the initial condition: such uniformity is missing if fixed thresholds are used.

Our dynamics are defined within the hybrid systems framework, which brings two important advantages. Firstly, we are able to build upon the well-established and comprehensive theory presented in [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF]. This theory is useful to guarantee existence and completeness of solutions, which are tricky for some non-hybrid models: see [START_REF] Blondel | Continuous-time average-preserving opin-ion dynamics with opinion-dependent communications[END_REF][START_REF] Ceragioli | Continuous and discontinuous opinion dynamics with bounded confidence[END_REF][START_REF] Ceragioli | Consensus and disagreement: The role of quantized behaviors in opinion dynamics[END_REF] for detailed examples. At the same time, it allows us to prove stability and attractivity of the equilibria via a transparent Lyapunov argument. Secondly, the hybrid framework allows for considering the network topology as an independent (discrete) variable that interacts with the (continuous) opinion variable. To the best of our knowledge, previous works simply assume the topology to be a function of the current opinion, thus not allowing for memory or hysteresis effects. On the contrary, their inclusion is natural in the hybrid framework, which thus opens the way to wider opportunities for modeling opinion dynamics and similar consensus-seeking systems. As a matter of fact, some other researchers are starting to apply the hybrid framework [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF] to other issues in multi-agent systems: for instance, consensus problems have been addressed in [START_REF] Albea | Activation and consensus control of a three-node server network cluster via hybrid approach[END_REF][START_REF] Phillips | A hybrid consensus protocol for pointwise exponential stability with intermittent information[END_REF][START_REF] De Persis | A Lyapunov redesign of coordination algorithms for cyber-physical systems[END_REF].

Outline. Section 2 describes our hybrid dynamic model, including the undirected interaction graph and the corresponding Laplacians that define it. Next, Sections 3 and 4 study the dynamics resulting from, respectively, fixed and adaptive jump rules. Within both sections, we first present all relevant results and then provide their detailed proofs. Illustrative simulations are given in Section 4.3, before some final comments in Section 5.

Hybrid dynamics and Laplacians

Consider n agents indexed in a set i ∈ I = {1, . . . , n}, each of them holding a time-dependent opinion y i : R ≥0 → R. Consider also a time-varying interaction pattern where for any pair (h, k) ∈ I × I, such that h = k, agents h and k interact if a hk = a kh ∈ {0, 1} is set to 1. We call the binary values a hk edges, and they are defined for all indices (h, k) taking values in the index set:

E := {(i, j) : i ∈ I, j ∈ I \ {i}}.
Since we are considering symmetric interaction dynamics, namely a hk = a kh for all (h, k) ∈ E, set E above is redundant and it is convenient to introduce the reduced set E + := {(i, j) : i, j ∈ I, j > i}. Based on the above reduced index set, we can define vector a ∈ {0, 1} Then, all possible pairwise interactions among the n agents are described by the elements of a. In the sequel, we will refer to elements of a interchangeably using the two notations a hk = a kh whose meaning is not ambiguous as long as h = k. Based on the time-varying edges represented in a, each agent may have a variable number of active connections with other agents. This number is usually referred to as the degree of the agent. Actually, in what follows it will be convenient to count the node itself among its neighbors, and denote this (augmented) degree of agent i, for each i ∈ I, as

d i := 1 + j =i a ij , (1)
consistently with the approach in [18, eq. (2.3)]. Note that with this convention one gets d i ≥ 1.

The model proposed in this paper aims at regulating both the continuous evolution of the agents' opinions (described by suitable variations of state y), and the discrete variations in the interaction pattern (described by instantaneous jumps of state a). Since the proposed model involves both continuous variations and instantaneous jumps of the state, we will adopt a hybrid framework for its description and analysis. More precisely, the overall state x is such that

x := (y, a) ∈ X := R n × {0, 1} n(n-1) 2
.

(2)

Following [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF], solutions are understood as hybrid arcs: besides the physical time t also the logical time (or jump counter)  is taken into account. Consequently, solutions are locally absolutely continuous maps R ≥0 × Z ≥0 ∋ (t, ) → (y, a) ∈ X.

Regarding the dynamics of the overall model, we will consider the following flow equation for the overall state variable (y, a):

   ẏi = j∈I\{i} ψ ij (a)(y j -y i ) for all i ∈ I ȧij = 0 for all (i, j) ∈ E + , (3)
where ψ ij (a) are suitable functions of the discrete state a such that ψ ij (a) ≥ 0 for all a and ψ ij (a) > 0 only if a ij = 1. These features are motivated by the fact that interactions only occur between pairs (i, j) of agents having an active link (a ij = 1).

Following classical approaches in consensus of multiagent systems, the flow dynamics (3) can be conveniently written in terms of the following (state-dependent) Laplacian matrix L(a) ∈ R n×n :

L(a) := {ℓ ij (a)} (i,j)∈I×I , where ℓ ij (a) := -ψ ij (a), if i = j, -j∈I\{i} ℓ ij (a), if i = j.
In this paper, we shall consider two choices for the Laplacian, namely, the standard Laplacian

ψ ij (a) = a ij , (4)
which has been used, e.g., in [START_REF] Blondel | Continuous-time average-preserving opin-ion dynamics with opinion-dependent communications[END_REF], and the normalized Laplacian

ψ ij (a) = a ij d i d j (5)
where d i is defined in [START_REF] Acemoglu | Opinion fluctuations and disagreement in social networks[END_REF]. In the latter model, the interaction is relatively stronger if the two agents have a small number of active links (small values of d i and d j ) encompassing the intuition that a smaller number of peers leads to a more frequent, therefore stronger, interaction.

Note that according to (3), the undirected interconnection graph remains constant ( ȧij = 0) during flowing of the hybrid solutions. Indeed, the change of topology of the interconnection graph is captured by a jump of the hybrid solution that leaves the opinions y unchanged and only affects the elements a ij of a by the following set of jump rules that must be applied to each (h, k) ∈ E + :

   y + i = y i for all i ∈ I a + hk = 1 -a hk a + ij = a ij for all (i, j) ∈ E + \ {(h, k)} (y, a) ∈ D hk . (6)
According to the above equation, a jump (toggle between 0 and 1) of edge a hk is enabled when the state (y, a) belongs to the set

D hk := D on hk ∪ D off hk , for all (h, k) ∈ E + . (7)
In what follows we shall consider different definitions of the jump sets D on hk and D off hk . Jump equations ( 6) should be understood in the sense that hybrid solutions only experience the change of one edge (h, k) ∈ E + across one jump. This does not prevent multiple edges to be activated or deactivated at the same (physical) time, however such a simultaneous activation/deactivation is conveniently represented by multiple jumps of the hybrid solution. This suggestive description enables studying the qualitative behavior of solutions by analyzing the change of a Lyapunov function across each single jump, namely across the change of only one edge a hk under the condition that (y, a) belongs to D hk .

The jump dynamics is then conveniently written by compactly representing (6) by the update laws:

y + a + = g hk (y, a), (y, a) ∈ D hk , ∀(h, k) ∈ E + , (8)
which can be grouped together into a set-valued map enabling any of the allowable jumps:

y + a + ∈ G(
where flow set C :=

(h,k)∈E +
X \ D hk is defined as the closed complement of the jump set D with respect to the overall state space X introduced in (2). Note that this selection of C ensures that solutions to the overall dynamics ( 9), ( 10) cannot flow if the state belongs to the interior of any of the sets introduced in (7). However solutions may flow or jump if the state belongs to the boundary of some of these sets (and not to the interior of any other, of course).

According to [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF], the hybrid dynamics under consideration is well-posed if the data of the hybrid system satisfy the so-called "hybrid basic conditions" [17, Ass.

6.5]. The well posedness property enables a large number of relevant fundamental tools (such as the hybrid invariance principle and intrinsic robustness properties of asymptotic stability) that we exploit in our proofs.

To ensure the fact that dynamics ( 9)-( 10) with Laplacian (4) or ( 5) satisfies these hybrid basic conditions, it is enough to select the jump sets D on hk and D off hk in (6) as closed subsets of the state space, as clarified at the beginning of Section 3.2.

Our convergence results rely on the stability theory for hybrid systems reported in [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF]. In particular, they focus on the stability properties of the following closed but not necessarily bounded set:

A := {(y, a) : a ij (y i -y j ) 2 = 0, ∀(i, j) ∈ E + }. (11)
This set contains points of the state space with the following property: if two nodes interact, then they agree with each other, or equivalently, if two nodes disagree, then they do not interact. The results that we present in the next sections focus on the following stability and convergence properties. 10) if all complete solutions x to ( 9)-( 10) satisfy lim t+→∞ |x(t, )| A = 0. Set A is uniformly globally asymptotically stable (UGAS) for ( 9)-( 10) if it is:

Definition 1 Given the closed set A ⊂ X, define as |x| A = |(y, a)| A := inf (z,a)∈A |y -z| the distance of point x from set A. Set A is globally attractive for (9)-(
• (LyapS). Lyapunov stable, that is, for each ǫ > 0 there exists δ > 0 such that all solutions x to ( 9)-( 10), satisfy

|x(0, 0)| A ≤ δ ⇒ |x(t, )| A ≤ ǫ, ∀(t, ) ∈ dom x; (12
) • (LagS). Lagrange Stable, that is, for each δ > 0 there exists ǫ > 0 such that all solutions x to ( 9)- [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF], satisfy [START_REF] Etesami | Game-theoretic analysis of the Hegselmann-Krause model for opinion dynamics in finite dimensions[END_REF]; and • (UGA). Uniformly Globally Attractive, that is, for each pair (r, ǫ) there exists T such that, for all solutions x to ( 9)- [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF],

|x(0, 0)| A ≤ r implies |x(t, )| A ≤ ǫ for all (t, ) ∈ dom x such that t +  ≥ T .
3 Fixed thresholds

Proposed model and its properties

The first definition of jump sets that we consider is

D on hk :={a hk = 0} ∩ {(y h -y k ) 2 ≤ R 2 -ε} (13a) D off hk :={a hk = 1} ∩ {(y h -y k ) 2 ≥ R 2 + ε}, (13b)
where R and ε are positive scalars and ε is (much) smaller than R. In combination with the jumps induced by these jump sets we consider the flow induced by the standard Laplacian (4). This definition returns us the opinion dynamics model studied in [START_REF] Blondel | Continuous-time average-preserving opin-ion dynamics with opinion-dependent communications[END_REF], modified by the addition of a hysteresis slack regulated by the parameter ε.

The convergence properties of these dynamics are summarized in the following statement, dealing with global attractivity of A, namely the property that all complete solutions converge to A.

Theorem 1 Set A in (11) is globally attractive for dynamics ( 9)- [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF] with Laplacian (4) or (5) and jump sets [START_REF] Fagnani | Introduction to Averaging Dynamics over Networks[END_REF]. Moreover, all solutions perform at most a finite number of jumps and converge to a point (y * , a * ) ∈ A such that

y * i = y * j if a * ij = 1 and |y * i -y * j | 2 ≥ R 2 -ε if a * ij = 0.
This result proves convergence to an opinion profile where any two individuals agree if they communicate with each other. Consequently, opinions asymptotically cluster at a certain number of stable values, which depend in a complex way on the initial conditions. Such a clustering is a typical outcome of opinion models with bounded confidence. In order to prove this result, we proceed in two main steps. First, we establish that solutions are well behaved in a suitable sense, and then perform a Lyapunov convergence analysis. The proposition given below ensures that these solutions are well behaved in terms of providing an evolution that is persistent in the ordinary time direction t, namely, solutions will be defined for arbitrarily large ordinary times. Such properties are important for hybrid models where solutions may prematurely terminate due to the impossibility to flow or jump. This situation does not occur in our model for any initial condition starting in X, as established below.

Proposition 2 Dynamics ( 9)- [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF] The Lyapunov analysis will be based on the following function

V 1 (y, a) := 1 2 y ⊤ y, (14)
which enjoys the useful properties established in the next lemma (whose proof is immediate). [START_REF] Frasca | Distributed randomized algorithms for opinion formation, centrality computation and power systems estimation[END_REF] and dynamics ( 9)- [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF] with Laplacian (4) or (5) and jump set [START_REF] Fagnani | Introduction to Averaging Dynamics over Networks[END_REF].

Lemma 3 Consider function V 1 in
The following hold:

∇V 1 (x), f (x) = -y ⊤ L(a)y ≤ 0, ∀x ∈ C, (15) V 1 (g) -V 1 (x) = 0 ∀x ∈ D, ∀g ∈ G(x) (16)
and inequality (15) is strict outside set A.

The relevance of the properties in Lemma 3 is that function V 1 can never grow along the solutions, indeed the first equation ( 15) characterizes its derivative along the continuous motion, while equation ( 16) characterizes its behavior across links activation/deactivation. Function V 1 will be useful to establish convergence properties of solutions but cannot be used to establish stability.

Remark 1 (Instability of A) Even though Theorem 1 establishes global convergence to set A, we must observe that such a convergence is not uniform. Indeed, the set A, although attractive, is not strongly forward invariant 1 and therefore is unstable. Instability is evident if one takes an initial condition (y, a) ∈ A such that a ij = 0 and (y i -y j ) 2 = R 2 -ε for some (i, j). From this point there is a solution that never jumps and remains constant (in A) for all (t, ) ∈ R ≥0 × {0}. There are however infinitely many other solutions that coincide with this one for an arbitrarily long time T and then jump to a ij (T, 1) = 1, which is outside A because a ij (T, 1)(y i (T, 1) -y j (T, 1)) 2 = R 2 -ε, thereby proving instability. Note that these solutions approach A asymptotically after having jumped, because of the global convergence established in Theorem 1. Nevertheless, this convergence is non-uniform because time T can be arbitrarily large.

Proofs

For the proof of Proposition 2 we exploit below the fact that the dynamics satisfies the hybrid basic assumptions of [17, Ass. 6.5], which, among other things, has useful ramifications in terms of sequential compactness of solutions.These basic assumptions hold because map f in [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF] page 124] applies because C ∪ D covers the whole space and the boundary of C belongs to set D, so that any point in C \ D belongs to the interior of C, where the tangent cone is the whole space (so that the intersection in [17, Prop. 6.10, condition (VC)] is certainly non-empty). Since (VC) holds, then all solutions satisfy either condition (a), (b) or (c) of [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF]Prop. 6.10]. Condition (c) never happens because G(D) ⊂ C ∪ D. Condition (b) never happens because solutions remain bounded. The only possibility is then condition (a), establishing completeness of maximal solutions. From now on, when referring to solutions, we shall in general intend maximal solutions.

Proof of item (ii). We will show that the boundedness of solutions and finiteness of ε imply that the same edge cannot switch too often. Indeed, assume that a hk = 0 and a + hk = 1 at a certain time (t hk 0 ,  hk 0 ). Then, at that time (y h (t hk 0 ,  hk 0 )-y k (t hk 0 ,  hk 0 )) 2 = R 2 -ε. Furthermore, in order to switch back to zero, it must be at a later time (t hk 1 ,  hk 1 ) true that (y

h (t hk 1 ,  hk 1 ) -y k (t hk 1 ,  hk 1 )) 2 = R 2 + ε = (y h (t hk 0 ,  hk 0 ) -y k (t hk 0 ,  hk 0 )) 2 + 2ε.
Since solutions are bounded, then the flow is such that, when using (4), we have that

| ẏi | ≤ j∈I\{i} a ij (y j -y i ) ≤ max j∈I |y i -y j | max j∈I d j
is bounded by a constant K > 0 that depends on the initial condition only (namely on the size of set K), while when using (5) a parallel straightforward bound can be derived. Hence, also using the fact that y is constant across jumps, t hk 1 -t hk 0 ≥ T d := ε/(2K 2 ). Since the number of edges in E + are N d := n(n-1)

2

, then the thesis follows from suitably concatenating the bounds above. ♦

The proof of Theorem 1 involves two main steps. First, we apply an Invariance Principle to conclude that solutions converge to the set A. Later, an ad hoc argument is used to verify that solutions stop switching after a certain time: this fact then implies the desired convergence.

δ := 1 2 √ R 2 -ε, there exists T > 0 such that for all (t, ) ∈ E with t+  > T , |(y(t, ), a(t, ))| ∞,A < δ.
We claim that the solution can not jump for all such (t, ) in its domain. If, by contradiction, edge a hk is added, then immediately before the jump one would need to have |y h -y k | ≥ √ R 2 -ε, which implies that immediately after the jump (when a + hk = 1) it would be |(y

+ , a + )| ∞,A ≥ √ R 2 -ε > δ
, leading to a contradiction. Similarly, if an edge a hk is removed, this would mean that at the jump (and then immediately before the jump), one would have

|y h -y k | ≥ √ R 2 + ε and a hk = 1, which implies |(y, a)| ∞,A ≥ √ R 2 + ε > δ
, leading to a contradiction again. Hence, solutions stop jumping after a finite (hybrid) time. From item (ii) of Proposition 2, only a finite number of jumps may occur. After this finite time, standard arguments (along the lines of [8, Theorem 4], for instance) show that the pure flow dynamics, which evolves according to a fixed graph, asymptotically converges to a point that exhibits consensus between every pair of agents that are connected. Instead, two agents i, j that are disconnected (a ij = 0) must be at least R 2 -ε apart (namely, |y i -y j | ≥ R 2 -ε), for otherwise the dynamics would force them to jump to a ij = 1. ♦ 4 Adaptive thresholds

Proposed model and its properties

The definition of jump set ( 13) is based on a fixed threshold R. In this section, we want to modify this definition and replace the fixed threshold with adaptive thresholds that depend on the relative distances between the nodes. To this goal, we propose the following definition.

D on hk := {a hk = 0} ∩ 1 + η 2 d h d k (y h -y k ) 2 ≤ -ε + ℓ =k,h d + k a hℓ d h d ℓ (y h -y ℓ ) 2 + d + h a kℓ d k d ℓ (y k -y ℓ ) 2 ,
where

d + h = d h + 1, d + k = d k + 1 (17a) D off hk := {a hk = 1} ∩ 1 - η 2 d h d k (y h -y k ) 2 ≥ ε + ℓ =k,h d k a hℓ d + h d ℓ (y h -y ℓ ) 2 + d h a kℓ d + k d ℓ (y k -y ℓ ) 2 , where d + h = d h -1, d + k = d k -1 . (17b)
The rationale for this apparently involved definition is the following. In both sets the quantities d + k and d + h represent the degrees that one would see if jump (h, k) were to take place. Then, a new connection between h and k is established when the distance |y h -y k | is small compared to a weighted average of the distances between h (or k) and their current neighbors. On the contrary, a connection is dropped when the two individuals are too far apart, compared with their distance to their other neighbors. Note that the forms (17) require agents h and k to be aware of the degrees of their neighbors. Comparing sets [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF] with sets [START_REF] Fagnani | Introduction to Averaging Dynamics over Networks[END_REF] of the classical HK model, one clearly sees that the homogeneous (of degree 2) terms on the second line of each definition essentially replace the fixed threshold R appearing in ( 13) by an alternative formulation that does not depend on scaling. On the other hand, due to the absence of the tuning knob given by R in (13), we reinsert here the design parameter η ≥ 0 that influences the connectivity: larger values of η inhibit both the creating and the breaking of the edges, in a weighted fashion that accounts for the degrees of the nodes. Due to this fact, the average degree of the nodes at the steady state is typically not far from the value of η (see the trends reported in Figure 3). The (small) positive parameter ε has the same role as in [START_REF] Fagnani | Introduction to Averaging Dynamics over Networks[END_REF]. We observe that, should ε be set to zero, the dynamics would be invariant to translation and scaling of the initial condition: more precisely, scaling by a non-zero factor K merely multiplies the Laplacian (3) by K. Since instead ε is positive but small, we may say that adaptive jumps [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF] render the dynamics approximately scaling invariant. Choosing ε = 0 would make the dynamics scaling invariant but would lead to Zeno behavior.

Let us now consider the dynamics that combines the jumps induced by jump map [START_REF] Ceragioli | Consensus and disagreement: The role of quantized behaviors in opinion dynamics[END_REF], jump sets [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF] with the flow dynamics [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF] induced by the normalized Laplacian [START_REF] Blondel | Continuous-time average-preserving opin-ion dynamics with opinion-dependent communications[END_REF], and provide the following convergence result.

Theorem 4 All solutions to ( 9)- [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF] with Laplacian (5) and jump sets (17) perform a finite number of jumps and then converge to a constant state (y * , a * ) such that

y * i = y * j if a * ij = 1.
Similarly to the previous section, we first establish that solutions are well behaved and then perform our stability analysis. To these goals, consider the Lyapunov-like function

V 2 (y, a) := 1 2 y ⊤ L(a)y = - 1 4 (i,j)∈E ℓ ij (y i -y j ) 2 (18) = 1 4 (i,j)∈E a ij d i d j (y i -y j ) 2 .
Given our definition of Laplacian, function V 2 is the counterpart of the classical disagreement function i,j a ij (y i -y j ) 2 , also known as Dirichlet form [13, Prop. 1.9] and [START_REF] Levin | Markov Chains and Mixing Times[END_REF]Lemma 13.11]. Observe that the quadratic form V 2 is always nonnegative. Moreover, using the second line of the expression in [START_REF] Hegselmann | Opinion dynamics and bounded confidence: models, analysis and simulation[END_REF] and the strict positivity of d i in [START_REF] Acemoglu | Opinion fluctuations and disagreement in social networks[END_REF], it is apparent that the set where V 2 is equal to zero coincides with the set A defined in [START_REF] Col | Equivalent conditions for synchronization of identical linear systems and application to quality-fair video delivery[END_REF], namely, {(y, a) : V 2 (y, a) = 0} = A. In particular, following up to the discussion of the properties of set A at the end of Section 2, V 2 is strictly positive as long as any two interacting agents have different opinions. The next lemma establishes useful properties of function V 2 .

Lemma 5 Consider function V 2 in (18) and dynamics ( 9)- [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF] with Laplacian (5) and jump set [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF]. There exist positive scalars c 1 , c 2 , c F , c J such that the following hold:

c 1 |x| 2 A ≤ V 2 (x) ≤ c 2 |x| 2 A , ∀x ∈ C ∪ D, ( 19
) ∇V 2 (x), f (x) ≤ -c F V 2 (x), ∀x ∈ C, ( 20
) V 2 (g) -V 2 (x) ≤ -c J ε, ∀x ∈ D, ∀g ∈ G(x). (21)
Relation ( 21) entails that any switching will reduce the Lyapunov function by a constant amount. The combination of ( 20) and ( 21) together with (uniform) positive definiteness of V 2 imply that V 2 is a strict Lyapunov function for A. This also implies the existence of a class KL bound for the solutions, which may be used to establish bounds on the speed of convergence. Such a bound can be obtained by first integrating and summing [START_REF] Jabin | Clustering and asymptotic behavior in opinion formation[END_REF] and ( 21) to obtain V (x(t, )) ≤ V (x(0, 0)) along any solution x, and then using [START_REF] Hendrickx | Convergence of type-symmetric and cut-balanced consensus seeking systems[END_REF], [START_REF] Levin | Markov Chains and Mixing Times[END_REF] and the previous bound to get, for any x(0, 0) / ∈ A,

V 2 (x(t,  + 1)) ≤ V (x(t, )) -c J ε |x(0, 0)| A |x(0, 0)| A ≤ V (x(t, )) - c J ε |x(0, 0)| A V (x(0, 0)) c 2 (22) ≤ 1 - c J ε c 2 |x(0, 0)| A V (x(t, )),
which clearly shows that solutions can never jump if |x(0, 0)| A ≤ cJ ε c2 , otherwise V 2 would become negative. Using [START_REF] Jabin | Clustering and asymptotic behavior in opinion formation[END_REF] and [START_REF] Martin | Continuoustime consensus under non-instantaneous reciprocity[END_REF] we may then integrate and sum V along solutions to get V (x(t, )) ≤

e cF t 1 -min 1, c J ε c 2 |x(0, 0)| A 
V (x(0, 0)), and then from [START_REF] Hendrickx | Convergence of type-symmetric and cut-balanced consensus seeking systems[END_REF] we obtain the following KLL bound [START_REF] Cai | Smooth Lyapunov functions for hybrid systems-Part I: Existence is equivalent to robustness[END_REF]:

|x(t, )| A ≤ β(|x(0, 0)| A , t, ) (23)
:= c 2 c 1 e -c F 2 t 1 -min 1, c J ε c 2 |x(0, 0)| A  2 |x(0, 0)| A .
A class KL bound β satisfying |x(t, )| A ≤ β(|x(0, 0)| A , t+ ) can also be obtained using β(r, s) := sup t+=s β(r, t, ). Bound [START_REF] Mirtabatabaei | Opinion dynamics in heterogeneous networks: Convergence conjectures and theorems[END_REF] depends on c 1 , c 2 , c F and c J and these quantities unfortunately depend on global quantities related to the (time-varying) connectivity graph, which are hardly known explicitly. With the help of Lemma 5, we can establish the following result on the long-time behavior of solutions. Proposition 6 For system ( 9)- [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF] with Laplacian (5) and jump sets [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF], the following hold:

(i) all maximal solutions are complete;

(ii) all maximal solutions perform a finite number of jumps (possibly none) and then flow forever.

Note that a consequence of item (ii) is that matrix L(a) converges in finite time to a constant value, representing an asymptotic clustering of the set of agents.

We may then state the following result that is a straightforward consequence of [17, Thm 3.18] and Lemma 5.

Theorem 7

The closed set A in ( 11) is uniformly globally asymptotically stable for dynamics ( 9)- [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF] with Laplacian (5) and jump sets [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF].

Note that Theorem 7 not only establishes attractivity of A, which is required for proving Theorem 4, but also establishes its stability. That appears to be an interesting property pertaining the proposed model. This contrasts the lack of stability of A when the jump set is [START_REF] Fagnani | Introduction to Averaging Dynamics over Networks[END_REF], as discussed in Section 3 (see Remark 1).

Proofs

Similar to the discussion at the beginning of Section 3.2, we exploit below the fact that the dynamics satisfies the hybrid basic assumptions of [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF]Ass. 6.5]. This fact once again follows from the properties of sets D on hk and D off hk in [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF], which are closed subsets of the state space.

Proof of Proposition 6 Proof of item (i). First note that basic existence of solutions applies to system (9), [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF] due to the statement of [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF]Prop. 6.10]. In particular, we first note that the viability condition (VC) reported in [17, page 124] applies because C ∪D covers the whole space and the boundary of C belongs to set D, so that any point in C \ D belongs to the interior of C, where the tangent cone is the whole space (so that the intersection in [17, Prop. 6.10, condition (VC)] is certainly non-empty). Since (VC) holds, then all solutions satisfy either condition (a), (b) or (c) of [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF]Prop. 6.10].

Condition (c) never happens because G(D) ⊂ C ∪ D. Condition (b) never happens because solutions remain bounded: indeed, the largest (smallest) component of y is non-increasing (non-decreasing) during dynamics (3). The only possibility is then condition (a), establishing completeness of maximal solutions.

Proof of item (ii). This item trivially follows from Lemma 5 and the fact that there is a constant decrease of function V 2 across each jump. Since V 2 never increases along solutions and is a positive function, then the initial value of V 2 (clearly dependent on the initial condition) imposes a hard bound on the maximum number of jumps that the issuing solutions can perform. ♦

Proof of Lemma 5 Consider function V 2 defined in [START_REF] Hegselmann | Opinion dynamics and bounded confidence: models, analysis and simulation[END_REF] and perform the eigenvalue decomposition of the normalized Laplacian L(a) = U T (a)∆(a)U (a), where U (a) is an orthogonal matrix and the positive semidefinite matrix ∆(a) has an upper left diagonal positive definite matrix and the rest of it is zero. Due to the specific pattern of matrix ∆(a) and the shape of set A in [START_REF] Col | Equivalent conditions for synchronization of identical linear systems and application to quality-fair video delivery[END_REF], one obtains (this can be proven, e.g., following the proof technique in [11, Lemma 1]) that for each possible selection of a ∈ {0, 1} has a finite number of elements, we obtain [START_REF] Hendrickx | Convergence of type-symmetric and cut-balanced consensus seeking systems[END_REF] with

c 1 := min ā∈{0,1} n(n-1) 2 c1 (ā) and c 2 := max ā∈{0,1} n(n-1) 2 c2 (ā),
which are positive because they arise from a minimum/maximum of positive functions over a finite set.

Let us now prove inequality [START_REF] Jabin | Clustering and asymptotic behavior in opinion formation[END_REF]. To this end, consider again the eigenvalue decomposition L(a) = U (a) T ∆(a)U (a) and denote by δ i (a) ≥ 0, i = 1, . . . , n the non-negative diagonal entries of ∆(a). Consider the following candidate selection of c F in (20):

c F := min a∈{0,1} n(n-1) 2 min {i:δi(a)>0} δ i (a), (24)
which is clearly positive because it is the minimum over a finite set of positive numbers, and satisfies 2 ∆ 2 (a) = diag{δ 2 i (a)} ≥ c F diag{δ i (a)} (which is trivially true where δ i (a) = 0 and follows from [START_REF] Nedic | Multi-dimensional Hegselmann-Krause dynamics[END_REF] where δ i (a) > 0). Using relation [START_REF] Parsegov | Novel multidimensional models of opinion dynamics in social networks[END_REF], we may now prove [START_REF] Jabin | Clustering and asymptotic behavior in opinion formation[END_REF] by exploiting the fact that a remains constant along flow and equation [START_REF] Chazelle | Inertial Hegselmann-Krause systems[END_REF], to get

∇V 2 (x), f (x) = -y T L(a)L(a)y ≤ -c F V 2 (x). ( 26
)
Let us now prove the jump inequality [START_REF] Levin | Markov Chains and Mixing Times[END_REF] and, to this end, we consider the alternative expression for V 2 in [START_REF] Hegselmann | Opinion dynamics and bounded confidence: models, analysis and simulation[END_REF] and the fact that across jump dynamics [START_REF] Ceragioli | Consensus and disagreement: The role of quantized behaviors in opinion dynamics[END_REF], only one of the functions g hk (y, a) is evaluated, thereby corresponding to y + = y (no change) of y and a + ij = a ij for all (i, j) ∈ E + \ {(h, k)}. Then only two cases need to be addressed: the case where a hk = 0 and (y, a) ∈ D on hk (called case "on" below) and the case where a hk = 1 and (y, a) ∈ D off hk (called case "off" below). We address those two cases separately.

Case "on". By definition (17a), since (y, a) ∈ D on hk , we have that a hk = a kh = 0, a + hk = a + kh = 1, d + h = d h + 1, and d + k = d k + 1, while all other state variables and scalars d i , i / ∈ {h, k} remain unchanged. Then, using the last expression in [START_REF] Hegselmann | Opinion dynamics and bounded confidence: models, analysis and simulation[END_REF], we get

4V 2 (g) -4V 2 (x) = = (i,j)∈E a + ij d + i d + j (y i -y j ) 2 - (i,j)∈E a ij d i d j (y i -y j ) 2 = (i,j)∈E a + ij d + i d + j - a ij d i d j (y i -y j ) 2 = 2 =1 a + hk d + h d + k - =0 a hk d h d k (y h -y k ) 2 + 2 ℓ =k,h a ℓh d + h d ℓ - a ℓh d h d ℓ (y h -y ℓ ) 2 + 2 ℓ =h,k a ℓk d + k d ℓ - a ℓk d k d ℓ (y k -y ℓ ) 2 = 2 d + h d + k (y h -y k ) 2 + 2 ℓ =k,h d h -(d h + 1) (d h + 1)d h a ℓh d ℓ (y h -y ℓ ) 2 + 2 ℓ =h,k d k -(d k + 1) (d k + 1)d k a ℓk d ℓ (y k -y ℓ ) 2 = 2 d + h d + k (y h -y k ) 2 - d + k d h ℓ =k,h a ℓh d ℓ (y h -y ℓ ) 2 - d + h d k ℓ =h,k a ℓk d ℓ (y k -y ℓ ) 2 ≤ - 2 d + h d + k ε + η 2 d h d k (y h -y k ) 2 ≤ -4c J ε,
where in the next to last line we used the inequality in (17a) and in the last line we used the selection c J := (2n 2 ) -1 , together with d i ≤ n for all i. The above inequality clearly proves [START_REF] Levin | Markov Chains and Mixing Times[END_REF] for case "on".

Case "off ". By definition (17b), since (y, a) ∈ D off hk , we have that a hk = a kh = 1, a + hk = a + kh = 0, d + h = d h -1, and d + k = d k -1, while all other state variables and scalars d i , i / ∈ {h, k} remain unchanged. Then, using the last expression in [START_REF] Hegselmann | Opinion dynamics and bounded confidence: models, analysis and simulation[END_REF], we get similar derivations to the previous case:

4V 2 (g) -4V 2 (x) = (i,j)∈E a + ij d + i d + j - a ij d i d j (y i -y j ) 2 = 2 =0 a + hk d + h d + k - =1 a hk d h d k (y h -y k ) 2 + 2 ℓ =k,h a ℓh d + h d ℓ - a ℓh d h d ℓ (y h -y ℓ ) 2 + 2 ℓ =h,k a ℓk d + k d ℓ - a ℓk d k d ℓ (y k -y ℓ ) 2 = - 2 d h d k (y h -y k ) 2 + 2 ℓ =k,h d h -(d h -1) (d h -1)d h a ℓh d ℓ (y h -y ℓ ) 2 + 2 ℓ =h,k d k -(d k -1) (d k -1)d k a ℓk d ℓ (y k -y ℓ ) 2 = - 2 d h d k (y h -y k ) 2 - d + k d h ℓ =k,h a ℓh d ℓ (y h -y ℓ ) 2 - d + h d k ℓ =h,k a ℓk d ℓ (y k -y ℓ ) 2 ≤ - 2 d h d k ε + η 2 d h d k (y h -y k ) 2 ≤ -4c J ε,
where in the next to last line we used the inequality in (17b) and in the last line we used the selection c J := (2n 2 ) -1 .The above inequality clearly proves [START_REF] Levin | Markov Chains and Mixing Times[END_REF] for case "off" and completes the proof. ♦

We are now ready to prove Theorem 4 using these results.

Proof of Theorem 4

The fact that all solutions perform a finite number of jumps and then flow forever has been established in Proposition 6. As a consequence, substate a (which only changes across jumps) converges in finite time to a value a * . Moreover, Theorem 7 establishes UGAS, which involves uniform convergence to the set A. It remains to show that each solution actually converges to a point (y * , a * ) ∈ A. After convergence to a * , the flow reads ẏ = -L(a * )y. If two nodes h, k are connected in the graph associated to L(a * ), that is, if they belong to the same "cluster", then |y h -y k | converges to zero. Equivalently, we may say that every y h and the average of its cluster converge to each other. At the same time, the flow preserves the average of y within each cluster, implying that y converges asymptotically to a constant value y * , as to be proven. ♦

Remark 2

The symmetry a ij = a ji brings the opportunity to exploit the results by Hendrickx and Tsitsiklis [START_REF] Hendrickx | Convergence of type-symmetric and cut-balanced consensus seeking systems[END_REF] for Laplacian-based consensus-seeking systems that satisfy an assumption of symmetry (or, more generally, of cut-balance) in the interactions. Nevertheless, here we have preferred to prove convergence directly from an explicit Lyapunov argument. This choice has several reasons. Firstly, before being able to exploit cut-balance, one needs to verify by other means the basic properties of the solutions such as existence and completeness. Secondly, we prefer to provide a more self-contained and thus more transparent analysis, which has the advantage of guaranteeing additional natural properties of the system, for instance on the stability of the equilibria.

Simulations

We have used the Matlab/Simulink Hybrid Equations Toolbox by [START_REF] Sanfelice | A toolbox for simulation of hybrid systems in Matlab/Simulink: Hybrid Equations (HyEQ) Toolbox[END_REF] to simulate dynamics ( 9)-( 10) with adaptive jump sets [START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF] in order to illustrate our main results and provide some empirical observations about the role of the parameters. The definition of our system naturally involves as parameters the connectivity parameter η and the hysteresis parameter ε. Furthermore, each solution depends on the associated initial conditions. In the simulations that we present here, the initial conditions are randomly generated in the following way: the components of y are independent uniform random variables in the interval [0, 1] and the initial topology is an Erdős-Rényi random graph where each pair of nodes is connected by an edge with probability p.

Simulations corroborate our convergence result, showing that opinions separate into distinct clusters that asymptotically converge to consensus. The number and location of the clusters depend on the parameters and on the initial condition in a complex way. The initial topology plays the important role of "seeding" the interactions: if the initial topology is empty (p = 0), then the topology stays empty and the opinions y do not evolve. Besides this extreme case, lower values of p induce more fragmented limit opinions, whereas if the initial topology is well connected (p is large), then the evolution typically leads to a smaller number of clusters. Figure 1 gives an example of the complex relation between initial and final conditions. The initial topology has four connected components, namely one "giant component" and three isolated nodes. During the evolution, the large connected component splits into different clusters. Note that isolated nearby nodes may fail to get connected and that the final set of edges is not a subset of the initial one.

The parameter ε determines an hysteresis zone around the (adaptive) radius: consequently, a larger value makes the topology evolution more conservative and increases the relevance of the initial conditions. However, in our perspective ε essentially constitutes a technical regularization term: for this reason we have set it to a very small value (0.01 or 0.001) in most of our trials. This choice is consistent with the spirit of having a dynamics that is invariant to scaling: indeed, in the simulations that we present here, η is chosen to be strictly positive. The invariance property is confirmed by simulations: as expected from the scaling-invariance pointed out just before Theorem 4, when the initial conditions have been multiplied by factors 10, 100 and 1000, the responses experienced with these scaled initial conditions are indistinguishable from the ones reported in Figure 1. Only when η = 0, then ε has a more prominent role of design parameter that controls the sensitivity of the link activation and deactivation mechanisms. A more extended discussion on this special case is given in our preliminary paper [START_REF] Frasca | A hybrid model of opinion dynamics with limited confidence[END_REF].

The most important parameter for the qualitative properties of the limit configuration is η: if η is small, say smaller than or close to 2, clusterization is very limited, whereas larger values of η produce more intense clusterization (that is, fewer and larger cluster). Some examples are given in Figure 2. More precisely, the parameter η seems to influence the degree of the nodes in the final graph: in our simulations, the average degree grows approximately linearly in η. This relation is shown in Figure 3 and may lead to interesting use of the proposed techniques for automatic clusterization of data, where the scale invariance of our model may turn out to be useful whenever the scaling of the data is difficult to be determined a priori.

Conclusion

This paper has looked at Laplacian-based opinion dynamics with opinion-dependent connectivity from the perspective of hybrid systems. We have first reformulated the classical Hegselmann-Krause model and then defined a novel scale-invariant model. The latter model allows for an intuitive Lyapunov analysis and enjoys strong stability properties that are not available for the former one. While the specific form of interactions that we have defined might not be of immediate relevance in social sciences, we believe that describing opinion dynamics by hybrid systems opens wide and potentially fruitful perspectives. Firstly, it permits to undergo precise analyses of stability and convergence of the dynamics. Secondly, it has the potential to model a variety of interaction phenomena, possibly featuring historydependent interaction patterns that involve delays, hysteresis, decision variables, and asymmetric interactions. Future studies will involve developing theorems on properties of models with empirical evidence that may emerge from intuitive definitions of jump/flow sets along the lines of the results reported here.

  y, a) := (h,k): (y,a)∈D hk g hk (y, a), (y, a) ∈ D, (9) where D := (h,k)∈E + D hk is the (overall) jump set of the hybrid dynamics. With this definition, it is readily seen that dynamics (3) can be compactly written as the flow equation: ẏ ȧ = f (y, a) := -L(a)y 0 , (y, a) ∈ C,

Proof of Theorem 1

 1 We apply[START_REF] Goebel | Hybrid dynamical systems: modeling, stability, and robustness[END_REF] Corollary 8.7(b)] with the Lyapunov function V 1 . First, observe that since solutions are bounded and complete, they are also precompact. By Lemma 3, the growth of V 1 is bounded by the nonnegative functions u c (y, a) := -y ⊤ L(a)y and u d = 0, respectively in C and in D. By Proposition 2, jumps are well-spaced and we can thus apply [17, Corollary 8.7(b)] and conclude that for each solution there exists a constant r such that the solution converges to the largest weakly invariant subset of V -1 1 (r)∩u -1 (0) ⊂ u -1 (0) = A (indeed, the set u -1 (0) is defined as the set where u c (y, a) := -y ⊤ L(a)y is equal to zero, and this clearly coincides with A), which proves global attractivity.Let us now prove the second part of the theorem. Let us consider a solution (y, a) with components y and a, defined on a domain E := dom y = dom a. If we denote the infinity-norm distance of the continuous component y from the attractor by |(y, a)| ∞,A := inf{|y -z| ∞ for some (z, a) ∈ A}, then the convergence to A established above entails that selecting

-1) 2 there

 2 exist positive scalars c1 (a) and c2 (a) such that c1 (a)|x| 2 A ≤ y T U T (a)∆(a)U (a)y ≤ c2 (a)|x| 2 A , where |x| A = |(y, a)| A = inf (z,a)∈A |y -z| denotes the distance of x from A as introduced in Definition 1. Since the set {0, 1} n(n-1) 2

2

  By writing A ≤ B when A and B are symmetric matrices we mean that B -A is positive semidefinite.

For

  this choice of c F we have the following useful property (where we used U (a)U T (a) = I): L(a) 2 = U T (a)∆ 2 (a)U (a) (25) ≥ U T (a)c F ∆(a)U (a) = c F L(a).

Fig. 1 .

 1 Fig. 1. Simulated evolution of the state y (left) and initial/final topologies (right) with n = 25, η = 3, ε = 0.01, and p = 0.1.For the sake of visualization, nodes are sorted from bottom to top in the left plot and clockwise in the right plot: this choice makes clusters apparent in the final topology.

Fig. 2 .

 2 Fig. 2. Simulated evolutions of the state y with n = 25 and ε = 0.001, starting from a randomly generated initial condition with 3 connected components. The parameters η are chosen in {1, 3, 6} and the resulting dynamics respectively lead to 11, 7 and 2 connected components in the final graph.

Fig. 3 .

 3 Fig. 3. Five examples of the growth of the average node degree as a function of η, with n = 20 and ε = 0.001. For each curve, the initial conditions are kept the same across all values of η.

  on hk and D off hk in (13) are closed, and map G in (9) has a graph corresponding to the union of the (closed) graphs of functions g hk . Strong forward invariance of A means that all solutions starting in A remain in A for all times.

	Proof of Proposition 2 Proof of item (i). Bound-
	edness is guaranteed because the largest (respectively,
	lowest) component in y is monotonically non-increasing
	(non-decreasing) during flows. Completeness follows
	from applying [17, Prop. 6.10]. In particular, we first
	note that the viability condition (VC) reported in [17,

is a continuous function (therefore it is trivially locally bounded, convex and outer semi-continuous), the flow and jump sets C and D are closed subsets of the state-space because D 1