【19】Heterophilious dynamics enhances consensus

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. SIAM R EVIEW

c 2014Society for Industrial an

d Applied Mathematics Vol.56,No.4,pp.577–621Heterophilious Dynamics Enhances Consensus ?Sebastien Motsch ?Eitan T admor ?

Abstract.We review a general class of models for self-organized dynamics based on alignment.The dynamics of such systems is governed solely by interactions among inpiduals or “agents,”with the tendency to adjust to their “environmental averages.”This,in turn,leads to the

formation of clusters,e.g.,colonies of ants,?ocks of birds,parties of people,rendezvous

in mobile networks,etc.A natural question which arises in this context is to ask when and how clusters emerge through the self-alignment of agents,and what types of “rules

of engagement”in?uence the formation of such clusters.Of particular interest to us are cases in which the self-organized behavior tends to concentrate into one cluster,re?ecting a consensus of opinions,?ocking of birds,?sh,or cells,rendezvous of mobile agents,and,

in general,concentration of other traits intrinsic to the dynamics.

Many standard models for self-organized dynamics in social,biological,and physical

sciences assume that the intensity of alignment increases as agents get closer,re?ecting a common tendency to align with those who think or act alike.Moreover,“similarity breeds connection”re?ects our intuition that increasing the intensity of alignment as the di?erence of positions decreases is more likely to lead to a consensus.We argue here that the converse is true:when the dynamics is driven by local interactions,it is more likely to approach a consensus when the interactions among agents increase as a function of their di?erence in position.Heterophily ,the tendency to bond more with those who are di?erent rather than with those who are similar,plays a decisive role in the process of clustering.We point out that the number of clusters in heterophilious dynamics decreases as the heterophily dependence among agents increases.In particular,su?ciently strong heterophilious interactions enhance consensus.Key words.agent-based models,self-alignment,heterophilious dynamics,clusters,consensus,?ocking,

active sets,connectivity of graphs,mean-?eld limits,kinetic equations,hydrodynamics AMS subject classi?cations.92D25,74A25,76N10DOI.10.1137/120901866Contents 1Introduction 5781.1Examples of Opinion Dynamics and Flocking ..............5812Global Interactions and Unconditional Emergence of Consensus 582?Received by the editors December 10,2012;accepted for publication (in revised form)May 5,2014;published electronically November 6,2014.This work was supported by NSF grants DMS10-08397and RNMS11-07444(KI-Net)and ONR grant N00014-1210318.92a29b85e518964bce847c0c/journals/sirev/56-4/90186 ?School of Mathematical &Statistical Sciences,Arizona State University,Tempe,AZ 85287(Sebastien.Motsch@92a29b85e518964bce847c0c).The research of this author was supported by the Center for Scienti?c Computation and Mathematical Modeling (CSCAMM),where this research was performed.?Center for Scienti?c Computation and Mathematical Modeling (CSCAMM)and Department of Mathematics,Institute for Physical Science and Technology,University of Maryland,College Park,MD 20742(tadmor@92a29b85e518964bce847c0c).577D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. 578SEBASTIEN MOTSCH AND EITAN TADMOR 2.1An L ∞Approach:Contraction of Diameters (584)

2.2Spectral Analysis of Symmetric Models (588)

3Local Interactions and Clustering 590

3.1The Formation of Clusters .........................5903.2How Many Clusters?. (592)

3.3Numerical Simulations with Local Dynamics (593)

4K =1:Uniform Connectivity Implies Consensus 5954.1Consensus in Local Dynamics:Symmetric Models ...........5954.2Consensus in Local Nonsymmetric Opinion Dynamics .........5995Heterophilious Dynamics Enhances Consensus:Simulations 601

5.11D Simulations (602)

5.2Clusters and Branches ...........................6035.32D Simulations ...............................6046Heterophilious Dynamics with a Fixed Number of Neighbors 604

6.1A Fixed Number of Neighbors with Global In?uence Function .....6066.2Two-Neighbor Dynamics .. (607)

7Self-Alignment Dynamics with Discrete Time-Steps 6097.1Consensus with Global Interactions ....................6097.2Clustering with Local Interactions .. (610)

7.3Numerical Simulations of Discrete Dynamics (612)

8Mean-Field Limits:Self-Organized Hydrodynamics 613

8.1Opinion Hydrodynamics ..........................6138.2Flocking Hydrodynamics ..........................6159Further Reading on Self-Organized Dynamics 616

1.Introduction.Nature and human societies o?er many examples of self-organ-ized behavior.Ants form colonies to coordinate the construction of a new nest,birds form ?ocks which ?y in the same direction,mobile networks are sought to form a coordinated rendezvous,and human crowds form parties to reach a consensus

when choosing a leader.The self-organized aspect of such systems is their dynamics,governed solely by interactions among its inpiduals or “agents,”which tend to cluster

into colonies,?ocks,parties,etc.A natural question which arises in this context is to ask when and how clusters emerge through the self-interactions of agents,and what types of “rules of engagement”in?uence the formation of such clusters.Of particular interest to us are cases in which the self-organized behavior tends to concentrate

into one cluster,re?ecting a consensus of opinions,?ocking of birds,?sh,or cells,rendezvous of mobile networks,and,in general,concentration around other positions intrinsic to the self-organized dynamics.Generically,we will refer to this process as concentration around an emerging consensus.Many models have been introduced to appraise the emergence of consensus.Rep-resentative examples can be found in [12,34,36,49,63,88,107,112],and we refer the

reader to a more comprehensive list of references surveyed in section 9.The starting D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. HETEROPHILIOUS DYNAMICS ENHANCES CONSENSUS 579point for our discussion is a general framework which embeds several types of models describing self-organized dynamics.We consider the evolution of N agents,each of

which is identi?ed by its “position”p i (t )∈R d .The position p i (t )may account for opinion,velocity,or other attributes of agent “i ”at time t .Each agent adjusts its position according to the position of its neighbors:(1.1)d dt p i =α j =i a ij (p j ?p i ),a ij ≥0.This provides a rather general description for processes of alignment .Here,α>0is a scaling parameter and the coe?cients a ij quantify the strength of in?uence between agents i and j :the larger a ij is,the more weight is given to agent j to align itself with agent i ,based on the di?erence of their positions p i ?p j .The underlying fundamental assumption here is that agents react not to the positions of others,but

to their di?erences relative to other agents.In particular,the a ij ’s themselves are allowed to depend on the relative di?erences p i ?p j .Indeed,we consider nonlinear models (1.1)where a ij =a ij (P (t )),P (t ):={p k (t )}k .

We emphasize the nonlinear aspect of the alignment models (1.1):the intricate aspect of such models is the nonlinear dependence of the in?uence matrix on the dynamics,a ij =a ij (P (t )).We ignore two other important processes involved in self-organized dynamics as advocated in the pioneering work of Reynolds [93],namely,the short-range repulsion (or avoidance)and the long-range cohesion (or attraction),and we refer to recent works driven by the balance of these two processes such as [8,47,50,

79,84,104].Our purpose here is to shed light on the role of mid-range alignment,which covers the important zone “trapped”between the short-range attraction and long-range repulsion.We distinguish between two main classes of self-alignment models.In the global case,the rules of engagement are such that every agent is in?uenced by every other agent,a ij >η>0.The dynamics in this case is driven by global interactions.We have a fairly good understanding of the large time dynamics of such models;an incomplete list of recent works in this direction includes [11,17,36,44,60,61,63,69,75,88]and the references therein.Global interactions which are su?ciently strong lead to unconditional consensus in the sense that all initial con?gurations of agents concentrate around an emerging limit state,the “consensus”p ∞,p i (t )t →∞?→p ∞.Section 2contains an overview of the concentration dynamics in such global models from the perspective of the general framework of (1.1).In more realistic models,however,interactions between agents are limited to their local neighbors [1,4,35,71,93].The behavior of local models,where some of the a ij may vanish,requires a more intricate analysis.In the general scenario for such local

models,discussed in section 3,agents tend to concentrate into one or more separate clusters .The particular case in which agents concentrate into one cluster,that is,the emergence of a consensus or a ?ock,depends on the propagation of uniform connec-tivity of the underlying (weighted)graph associated with the adjacency matrix,{a ij }.This issue is explored in section 4,where we show that connectivity implies consen-

sus.Thus,the question of consensus for local models is turned into the question of D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. 580SEBASTIEN MOTSCH AND EITAN TADMOR persistence of connectivity over time.Note that even if the initial con?guration is

assumed connected,then there is still a possibility of losing connectivity as the a ij ’s

may vary in time together with the positions P (t ).The open question of tracing the propagation of connectivity in time for the general class of local models (1.1)plays an important role in many applications,beyond the implication of emerging consensus.As an example we mention engineering applications to sensor-based networks,from

automatic tra?c control and wireless communication to production systems and mo-

bile robot networks,as seen,e.g.,in [64,71,89,91,94,113,112]and the references therein.Many standard models for self-organized dynamics in social,biological,and phys-ical sciences assume that the dependence of a ij decreases as a function of |p i ?p j |,where |·|is a problem-dependent proper metric to measure a di?erence of posi-

tions,opinions,etc.The statement that “birds of a feather ?ock together”re?ects a common tendency to align with those who think or act alike [69,77,83].Moreover,“similarity breeds connection”re?ects the intuitive scenarios in which the in?uence coe?cients a ij increase as the di?erence of positions |p i ?p j |decreases:the more the a ij ’s increase,the more likely this will lead to a consensus.However,we argue here that the converse is true:for a self-organized dynamics driven by local interactions,it is more likely to approach a consensus when the interaction among agents increases as a function of their di?erence |p i ?p j |.Heterophily ,the tendency to bond,more with the di?erent rather than with those who are similar,plays a decisive role in the clustering of (1.1).The consensus in heterophilious dynamics is explored in the

second part of the paper in terms of local interactions of the form a ij =φ(|p i ?p j |),where φ(·)is a compactly supported in?uence function which is increasing over its support.In section 5we report on our extensive numerical simulations which con-?rm the counterintuitive phenomenon in which the number of clusters decreases as the heterophilious dependence increases;in particular,if φis increasing fast enough,then the corresponding dynamics concentrate into one cluster,that is,heterophilious dynamics enhances consensus.We mention in passing the scenario of “extreme het-erophily”advocated in [71,113,112],where distributed coordination is governed by a local in?uence function φ(·)which grows to in?nity as it approaches the right edge of its support,in order to create an energy barrier which enforces connectivity and hence consensus.We are not unaware that this phenomenon of enhanced consensus in the presence of heterophilious interactions may have intriguing consequences in areas other than social networks,e.g.,global bonding in atomic scales,avoiding materials’fractures in mesoscopic scales,or “cloud”formations in macroscopic scales.In the rest of the paper,we address a few important extensions of the self-alignment models outlined above.These extensions are still a work in progress and we

by no means try to be comprehensive.In section 6we turn our attention to nearest neighbor dynamics.Careful 3D observations made by the StarFlag project [26,25,24]showed that interactions of birds are driven by topological neighborhoods,involving a ?xed number of nearby birds,instead of geometric neighborhoods involving a ?xed radius of interaction.Here we prove that in the simplest case of two nearest neigh-bor dynamics,connectivity propagates in time and consensus follows for in?uence

functions which are nondecreasing on their compact support.In section 7we turn our attention to fully discrete models for self-alignment.The large time evolution in discrete time-steps,e.g.,the opinion of dynamics in [11,12,75],may depend on the time-step Δt .Here,we show that the semidiscrete framework for global and local self-alignment outlined in sections 2–5can be extended,mutatis mutandis,to the fully discrete case.In particular,we recover a decreasing Lyapunov functional,a D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. HETEROPHILIOUS DYNAMICS ENHANCES CONSENSUS 581fully discrete analogue of the semidiscrete clustering analysis in section 4.2.Finally,in section 8we discuss the passage from the agent-based description to mean-?eld limits as the number of agents,or “particles,”tends to be large enough.There is a growing literature on kinetic descriptions of such models;see [20,21,22,49,51,61]and the references therein.Here we focus our attention on the hydrodynamic de-scriptions of self-organized opinion dynamics and ?ocking.The closing section 9is devoted to a more detailed discussion on the broader subject of self-organized dy-

namics.Since a comprehensive review of this multidisciplinary subject is beyond the scope of this paper,in particular,we include a selection of references,classi?ed into several complementary categories of di?erent disciplines,models,scales,approaches,and patterns.1.1.Examples of Opinion Dynamics and Flocking.Models for self-organized dynamics (1.1)have appeared in a large variety of di?erent contexts,including load balancing in computer networks,evolution of languages,gossiping,algorithms for sen-

sor networks,emergence of ?ocks,herds,schools,and other biological “clustering,”pedestrian dynamics,ecological models,peridynamic elasticity,multiagent robots,models for opinion dynamics,economic networks,and more;a detailed list of refer-ences is surveyed in section 9.To demonstrate the general framework for self-alignment dynamics (1.1),we shall work with two main concrete examples.The ?rst models opinions dynamics .In these

models,N agents,each with a vector of opinions quanti?ed by p i x i ∈R d ,interact

with each other according to the ?rst-order system (1.2a)d dt x i =α j =i a ij (x j ?x i ),a ij =φ(|x j ?x i |)N .Here,0<φ<1is the scaled in?uence function which acts on the “di?erence of opinions”|x i ?x j |.The metric |·|needs to be properly interpreted,adapted to the speci?c context of the problem at hand.Another model for interaction of opinions is (1.2b)d dt x i =α j =i a ij (x j ?x i ),a ij =φij k φik ,φij :=φ(|x j ?x i |).The classical Krause model for opinion dynamics [75,12]is a time-discretization of (1.2b),which will be discussed in section 7.Observe that the adjacency matrix {a ij }in the ?rst model (1.2a)is symmetric,while in the second model (1.2b)it is not.Another branch of models has been proposed to describe ?ocking .These are second-order models where the observed property is the velocity of birds,p i →v i ∈R d ,which are coupled to their location x i ∈R d .The ?ocking model of Cucker and Smale (C-S)has received considerable attention in recent years [36,37,61,17,60],(1.3a)d dt v i =α j =i a ij (v j ?v i ),a ij =φ(|x j ?x i |)N ,where d dt x i =v i .In the C-S model,alignment is carried out by isotropic averaging.In [88]we advocated a more realistic alignment-based model for ?ocking,where alignment is based on the relative in?uence,similar to (1.2b),(1.3b)d dt v i =α j =i a ij (v j ?v i ),a ij =φij k φik ,with φij :=φ(|x j ?x i |).D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. 582SEBASTIEN MOTSCH AND EITAN TADMOR Again,the C-S model is based on a symmetric adjacency matrix,{a ij },while sym-metry is lost in (1.3b),i.e.,a ij =a ji .The models for opinion and ?ocking dynamics (1.2)and,respectively,(1.3)can be written in the uni?ed form (1.4)d dt p i =αN j =1a ij (p j ?p i ),a ij =1σi φ(|x i ?x j |).In the opinion dynamics,p →x ;in the ?ocking dynamics,p →˙x .The degree is σi =N in the symmetric models,or σi = j =i φ(|x i ?x j |)in the nonsymmetric models.The local versus global behavior of these models hinges on the behavior of the in?uence function,φ.If the support of φis large enough to cover the convex hull of P (0)={p k (0)}k ,then global interactions will yield unconditional consensus

or ?ocking.On the other hand,if φis locally supported,then the group dynamics in (1.4)depends on the connectivity of the underlying graph,{a ij }.In particular,if the overall connectivity is lost over time,then each connected component may lead to a separate cluster.Heterophilious self-organized dynamics is characterized by a locally supported in?uence function,φ,which is increasing as a function of the mutual di?erences,φij =φ(|x i ?x j |).The more heterophilious the dynamics is,in the sense that its in?uence function has a steeper increase over its compact support,the more it tends to concentrate in the sense of approaching a smaller number of clusters.In particular,heterophilious dynamics is more likely to lead to a consensus as demonstrated,for example,in Figure 1(and further documented in Figures 8and 13).Observe that the only di?erence between the two models depicted in Figure 1is that the in?uence in the immediate neighborhood (of radius r ≤1/√2)was decreased,from φ=1χ[0,1](at the top)into φ=0.1χ[0,1/√2]+χ[1/√2,1](at the bottom):this was su?cient to enhance the four-party clustering on the top to become a consensus shown on the bottom.2.Global Interactions and Unconditional Emergence of Consensus.In this section we derive explicit conditions for global self-organized dynamics (1.1)to con-centrate around an emerging consensus.Our starting point is a convexity argument

which is valid for any adjacency matrix A ={a ij },whether symmetric or not.We be-gin by noting that,without loss of generality,A may be assumed to be row-stochastic,(2.1) j a ij =1,i =1,...,N.Indeed,by rescaling αif necessary we have j =i a ij ≤1,and (2.1)holds when we set a ii :=1? j =i a ij ≥0.We rewrite (1.1)in the form (2.2)d dt p i =α(p i ?p i ),p i :=N j =1a ij p j .Thus,if we let Ω(t )denote the convex hull of the properties {p k }k ,then,according to (2.2),p i is relaxing to the average value p i ∈Ω(t ),while the boundary of Ωis a barrier for the dynamics,as shown in Figure 2.It follows that the positions in the general self-organized model (1.1)remain bounded.Proposition 2.1.The convex hull of p (t )is decreasing in time in the sense that the convex hull,Ω(t ):=Conv {p i (t )}i ∈[1,N ] ,satis?es (2.3)Ω(t 2)?Ω(t 1),t 2>t 1≥0.D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. HETEROPHILIOUS DYNAMICS ENHANCES CONSENSUS 583Fig.1Evolution in time of the consensus model for two di?erent in?uence functions φ(top:φ(r )=χ[0,1];bottom:φ(r )=.1χ[0,1/√2]+χ[1/√2,1]).By diminishing the in?uence of close neighbors (bottom),we enhance the emergence of a consensus.Simulations are started with the same initial condition (100agents uniformly distributed on [0,10]).p Fig.2The convex hull Ωof the positions p i .D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. 584SEBASTIEN MOTSCH AND EITAN TADMOR Moreover,we have (2.4)max i |p i (t )|≤max i |p i (0)|.Proof .We verify (2.4)for a general vector norm |·|which we characterize in terms of its dual |w |?=sup w =0 w ,z /|z |,so that |p |=sup p ,w /|w |?.Let w =w (t )denote the maximal dual vector of p i (t ),so that p i ,w =|p i |;then

˙p i ,w =α( p i ,w ? p i ,w )≤α(|p i |?|p i |).

Since p i ,˙w ≤0,we have d dt |p i (t )|= ˙p i ,w + p i ,˙w ≤α(|p i (t )|?|p i (t )|),and,?nally,|p i (t )|≤max i |p i (t )|yields (2.4).Remark 2.2.Since the models of opinion dynamics

and ?ocking dynamics (1.4)are translation invariant in the sense of admitting the

family of solutions {p i ?c },then,for any ?xed state c ,Proposition 2.1implies max i |p i (t )?c |≤max i |p i (0)?c |.Consensus and ?ocking are achieved when the decreasing Ω(t )shrinks to a limit point Ω(t )t →∞?→{p ∞},max i |p i (t )?p ∞|t →∞?→0.There are various approaches,not unrelated,to deriving conditions which ensure un-conditional consensus or ?ocking.We shall mention two:an L ∞contraction argument and an L 2energy method based on spectral analysis.2.1.An L ∞Approach:Contraction of Diameters.Proposition 2.1tells us that {p i (t )}i remain uniformly bounded and the diameter,max ij |p i (t )?p j (t )|,is nonincreasing in time.In order to have concentration,however,we need to verify that

the diameter of p (t )decays to zero.The next proposition quanti?es this decay rate.Theorem 2.3.Consider the self-organized model

(1.1)with a row-stochastic adjacency matrix A (2.1).Let [p]:=max ij |p i ?p j |denote the diameter of the position vector p .Then the diameter satis?es the concen-

tration estimate (2.5)d dt [p (t )]≤?αηA (P (t ))[p (t )],ηA :=min ij k min {a ik ,a jk }.In particular,if there is a slow decay of the concentration factor so that ∞ηA (P (s ))ds =∞,then the agents concentrate in the sense that (2.6a)Θ(t ):= t ηA (P (s ))ds t →∞?→∞ lim t →∞max i,j |p i (t )?p j (t )|=0.Moreover,if the decay of the concentration factor is slow enough in the sense that D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. HETEROPHILIOUS DYNAMICS ENHANCES CONSENSUS 585 ∞exp(?αΘ(s ))ds <∞,then there is an emerging consensus p ∞∈Ω(0),(2.6b) ∞e ?αΘ(t )dt <∞ |p i (t )?p ∞| e ?αΘ(t )[p (0)]

for all i =1,...,N.Remark 2.4.We note that Theorem 2.3applies to any vector norm |·|.

Proof .We begin with the following estimate,which quanti?es the contractivity of the row-stochastic A in the induced vector semi norm [·](since this bound is solely due to the convexity of the row-stochastic A ,we suppress the time-dependence of p and p =A p ),(2.7)[A p]≤(1?ηA )[p],[p]=max ij |p i ?p j |,1?ηA =12 k |a ik ?a jk |.The estimate (2.7)in its 1-dual form for column-stochastic matrices goes back to Dobrushin [46],and his so-called coe?cient of ergodicity,ηA ,was later used to quantify the relative entropy in discrete Markov processes [29,30]and the contractivity in

models of opinion dynamics [75].For completeness,we proceed with the proof for

general vector norms |·|.Fix any i and j ,which are to be chosen later,and set ηk :=min {a ik ,a jk }so that a ik ?ηk and a jk ?ηk are nonnegative.Then,for arbitrary w ∈R d ,we have p i ?p j ,w = k a ik p k ,w ? k a jk p k ,w = k (a ik ?ηk ) p k ,w ? k (a jk ?ηk ) p k ,w ≤ k (a ik ?ηk )max k p k ,w ? k (a jk ?ηk )min k p k ,w =(1?ηA ) max k p k ,w ?min k p k ,w

≤(1?ηA )max k p k ?p ,w ≤ 1?ηA max k, |p k ?p ||w |?.In the last step,we characterize the norm |·|by its dual |w |?=sup w =0 w ,z /|z |so that z ,w ≤|z ||w |?.Now,choose i and j as a maximal pair such that [p]=|p i ?p j |;we then have [A p]≡[p]=|p i ?p j |=sup w =0 p i ?p j ,w |w |?≤(1?ηA )max k, |p k ?p |,and (2.7)now follows.Next,we consider the discrete time-marching system associated with (1.1),

p (t +Δt )?p (t )Δt =α(A p (t )?p (t )).Using (2.7)we obtain [p (t +Δt )]=[(1?αΔt )p (t )+αΔt A p (t )]≤(1?αΔt )[p (t )]+αΔt (1?ηA )[p (t )],or,after rearrangement,[p (t +Δt )]?[p (t )]Δt ≤?αηA [p (t )],D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. 586SEBASTIEN MOTSCH AND EITAN TADMOR and the desired bound (2.5)follows by letting Δt →0.In particular,we have (2.8)max ij |p i (t )?p j (t )|≤exp ?α t 0ηA (P (s ))ds [p (0)]t →∞?→0,which proves (2.6a).Moreover,|p i (t 2)?p i (t 1)|= t 2τ=t 1˙p i (τ)dτ ≤αmax ij t 2τ=t 1|p i (τ)?p j (τ)|ds ≤α t 2τ=t 1exp (?αΘ(τ))dτ[p (0)],Θ(τ)= τ0ηA (P (s )ds,which tends to zero,|p i (t 2)?p i (t 1)|→0for t 2>t 1 1,thanks to our assumption (2.6b).It follows that the limit p i (t )t →∞?→p ∞i exists,and hence all agents concentrate

around the same limit position,an emerging consensus p ∞∈Ω(0).The concentration rate estimate (2.6b)follows from (2.8).

Theorem 2.3relates the emergence of consensus or ?ocking of ˙p =A p ?p to the behavior of t ηA (P (s ))ds ↑∞,and to this end we seek lower bounds on the

“concentration factor”ηA ,which are easily checkable in terms of the entries of A .

This brings us to the following de?nition.Definition 2.5(active sets [88]).Fix θ>0.The

active set,Λ(θ),is the set of agents which in?uence every other agent “more”than θ,(2.9)Λ(θ):={j a ij ≥θfor any i }.Observe that since a ij changes in time,a ij =a ij (P (t ))

,the number of agents in the active set Λ(θ)is a time-dependent quantity,denoted λ(θ)=λ(θ,t ):=|Λ(θ,t )|.The straightforward lower bound ηA ≥max θθ·λ(θ)yields the following corollary.Corollary 2.6.The diameter of the self-organized model (1.1)with a stochastic adjacency matrix A ,as in (2.1),satis?es the concentration estimate (2.10)d dt [p (t )]≤?α(max θθ·λ(θ,t ))[p (t )].In particular,the lower bound ηA ≥N min ij a ij ,corresponding to θ=min ij a ij with λ(θ,t )=N ,yields [61](2.11)|p (t )?p ∞| exp ?αN t 0m (s )ds [p (0)],m (s ):=min ij a ij (s ).Remark 2.7.The bound (2.10)is an improvement of the “?ocking”estimate [88,Lemma 3.1]d dt [p (t )]≤?α(max θθ·λ(θ,t ))2[p (t )].Corollary 2.6is a useful tool to verify consensus and ?ocking behavior for general adjacency matrices A ={a ij },whether symmetric or not.We demonstrate its appli-cation with the following su?cient condition for the emergence of a consensus in the opinion models (1.2).In either the symmetric or the nonsymmetric case,a ij =?????????φij N φij σi ?????????≥φ([x (t )])N ,σi = k φik ≤N.D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. HETEROPHILIOUS DYNAMICS ENHANCES CONSENSUS 587By Proposition 2.1,the diameter [x (t )]is nonincreasing,yielding the lower bound

Na ij (P (t ))=N σi φ(|x i (t )?x j (t )|)≥min r ≤[x (t )]φ(r )≥min r ≤[x (0)]φ(r ),which in turns implies the following exponentially fast convergence toward a consensus x ∞.Proposition 2.8(unconditional consensus ).Consider the models for opinion dynamics (1.2)with an in?uence function φ(r )≤1,and assume that (2.12)m :=min r ≤[x (0)]φ(r )>0.Then there is an exponentially fast convergence toward an emerging consensus x ∞,

(2.13)|x i (t )?x ∞| e ?αmt [x (0)].Similar arguments apply for the ?ocking models (1.3):since [v (t )]is nonincreas-ing,then [x (t )]≤[x (0)]+t [v (0)]and hence Na ij (P (t ))=N σi φ(|x i (t )?x j (t )|)≥min r ≤[x (t )]φ(r )≥min r ≤[x (0)]+t [v (0)]φ(r );if φ(·)is decreasing,then we can set m (t )=φ([x (0)]+t [v (0)])and unconditional ?ocking follows from for Corollary 2.6for su?ciently strong interaction such that ∞φ(s )ds =∞.In fact,a more precise statement of ?ocking is summarized in the following proposition.Proposition 2.9(unconditional ?ocking ).Consider the ?ocking dynamics (1.3)with a decreasing in?uence function φ(r )≤φ(0)≤1,and assume that (2.14) ∞φ(s )ds =∞.Then the diameter of positions remains uniformly bounded,[x (t )]≤D ∞<∞,and there is an exponentially fast concentration of velocities around a ?ocking state v ∞,(2.15)|v i (t )?v ∞| e ?αmt [v (0)],m =φ(D ∞).Proof .Unlike the ?rst-order models for consensus,the diameter in second-order ?ocking models,[x (t )],may increase over time.The bound D ∞stated in (2.15)places a uniform bound on the maximal active diameter.To derive such a bound,observe

that in the second-order ?ocking models,the evolution of the diameter of velocities satis?es d dt [v (t )]≤?αφ([x (t )])[v (t )],and is coupled with the evolution of positions [x (t )]:since ˙x =v ,we have d dt [x (t )]≤[v (t )].The last two inequalities imply that the energy functional introduced by Ha and Liu [60],E (t ):=[v (t )]+α [x (t )]0φ(s )ds,

D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. 588SEBASTIEN MOTSCH AND EITAN TADMOR is decreasing in time,(2.16)α [x (t )][x (0)]φ(s )ds ≤[v (0)]?[v (t )]≤[v (0)].This,together with our assumption (2.14),yields the existence of a ?nite D ∞>[x (0)]such that (2.17)α [x (t )][x (0)]φ(s )ds ≤[v (0)]≤α D ∞[x (0)]φ(s )ds.

Thus,the active diameter of positions does not exceed

[x (t )]≤D ∞,and since φis assumed decreasing,the minimal interaction is Na ij ≥φ([x (t )])≥φ(D ∞),which yields d dt [v (t )]≤?αφ(D ∞)[v (t )].This concludes the proof of (2.15).Remark 2.10(global interactions ).Proposition 2.8derives an unconditional consensus under the assumption of global interaction ,namely,according to (2.12)every agent interacts with every other agent as a ij ≥1N φ(|x i ?x j |)≥m N >0.Similarly,the unconditional ?ocking stated in Proposition 2.9requires global interac-tions,in the sense of having an in?uence function (2.14)which is supported over the entire ?ock.Indeed,if the in?uence function φis compactly supported,supp {φ}=[0,R ],then assumption (2.14)tells us that [v (0)]≤α R [x (0)]φ(s )ds ;however,according to (2.16),α [x (t )][x (0)]φ(s )ds ≤[v (0)]and hence the support of φremains larger than the diameter of positions,R ≥[x (t )].

Proposition 2.9recovers the unconditional ?ocking results for the C-S model,φ(r )∝(1+r )?2β,β>1/2,obtained elsewhere in using spectral analysis, 1-, 2-,and ∞-based estimates [36,61,17,60,21].The derivations are di?erent,yet they all require the symmetry of the C-S in?uence matrix,a ij =φij /N .Here,we unify and generalize the results,covering both the symmetric and nonsymmetric scenarios.In particular,we improve here the unconditional ?ocking result in the nonsymmetric

model obtained in [88,Theorem 4.1].Although the tools are di?erent,notably,lack of conservation of momentum 1N i v i (t )in the nonsymmetric case—we nevertheless end up with the same condition (2.14)for unconditional ?ocking.2.2.Spectral Analysis of Symmetric Models.A more precise description of the concentration phenomenon is available for models governed by symmetric in?uence matrices,a ij =a ji ,such as (1.2a)and (1.3a).Set q i =p i ? p ,where p :=1/N i p i is the average (total momentum),which thanks to symmetry is conserved in time,˙ p (t )∝ ij a ij (p i ?p j )=0,and hence the symmetric system (1.1)reads d dt q i (t )=αN j =1a ij (q j ?q i ),q i :=p i ? p .D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. HETEROPHILIOUS DYNAMICS ENHANCES CONSENSUS 589Let L A :=I ?A denote the Laplacian matrix associated with A ,with ordered eigen-

values 0=λ1(L A )≤λ2(L A )≤···λN (L A ).The following estimate is at the heart of the matter (here,|·|denotes the usual Euclidean norm on R d ):(2.18)12d dt i |q i (t )|2=α i,j a ij q j ?q i ,q i =?α2 ij a ij |q j ?q i |2≤?αλ2(L A ) i |q i (t )|2.The second equality is a straightforward consequence of A being symmetric;the follow-ing inequality follows from the Courant–Fischer characterization of the second eigen-value of L A in terms of vectors q orthogonal to the ?rst eigenvector 1=(1,1,...,1) ,(2.19)λ2(L A )=min q k =0 L A q ,q q ,q ≤(1/2) ij a ij |q i ?q j |2 i |q i |2.We end up with the following su?cient condition for the emergence of unconditional concentration.Theorem 2.11(unconditional concentration in the symmetric case ).Consider the self-organized model (1.1),(2.1)with a symmetric adjacency matrix A .Then the following concentration estimate holds:(2.20)∨p (t )≤exp ?α t λ2(L A (P (s )))ds ∨p (0),∨2p (t ):=1N i |p i (t )? p (0)|2.In particular,if the interactions remain “su?ciently strong”so that ∞λ2(L A (P (s )))ds =∞,then there is convergence toward consensus p i (t )→p ∞= p (0).To apply Theorem 2.11,we need to trace e?ective lower bounds on λ2(L A );there follow two examples which recover our previous results in section 2.1.

Example 1(revisiting Theorem 2.3).If r is the Fiedler eigenvector associated with λN ?1(A )with r ⊥1,then (2.7)implies λN ?1(A )=[A r][r]≤sup p ⊥1[A p][p]≤1?ηA .We end up with the following lower bound for the Fiedler number:λ2(L A )=1?λN ?1(A )≥1?(1?ηA )≥ηA .Thus,Theorem 2.3is recovered here as a special case of the sharp bound (2.20)in Theorem 2.11.The former has the advantage that it applies to nonsymmetric models,but,as remarked earlier,it is limited to models with global interactions;the latter can address the consensus of local,connected models;see section 6.

We remark in passing that while Theorem 2.3employs the ∞-based diameter,[p]=[p]∞=max ij |p i ?p j |,Theorem 2.11is in fact the corresponding 2-based diameter,[p]22:= ij |p i ?p j |2/(2N )=∨p .Example 2(revisiting Propositions 2.8and 2.9).A straightforward lower bound λ2(L A )≥N min a ij recovers Corollary 2.6:(2.21)∨p (t )≤exp ?α t m (s )ds ∨p (0),m (t ):=min ij φ(|x i (t )?x j (t )|).The characterization of concentration in Theorem 2.11is sharp in the sense that

the estimate (2.18)is sharp.Indeed,it is well known that positivity of the Fiedler D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. 590SEBASTIEN MOTSCH AND EITAN TADMOR number,λ2(L A )>0,characterizes the algebraic connectivity of the graph associated with the adjacency matrix A [53,87,28].Theorem 2.11places a minimal requirement

on the amount of connectivity as a necessary condition for consensus.1There are

many characterizations for the algebraic connectivity of static graphs [28,45,53,54,56,86,87,95].In the present context of self-organized dynamics (1.1),however,the dynamics of ˙p

=α(A p ?p )dictates the connectivity of A =A (P (t )),which in turn determines the clustering behavior of the dynamics due to the nonlinear dependence,

A =A (P (t )).Thus,the intricate aspect of the self-organized dynamics (1.1)lies in tracing its algebraic connectivity over time through the self-propelled mechanism in which the nonlinear dynamics and algebraic connectivity are tied together.This issue will be explored in the following sections dealing with clustering driven by local

interactions.3.Local Interactions and Clustering.In this section we consider the self-organ-ized dynamics (1.1)of a “crowd”of N agents,P ={p i }N i =1,which do not interact globally:entries in their adjacency matrix may vanish,a ij ≥0.The dynamics is dictated by local interactions and its large time behavior leads to the formation of one or more clusters .3.1.The Formation of Clusters.A cluster C is a connected subset of agents,{p i }i ∈C ,which is separated from all other agents outside C ,namely,#1.a ij =0for all i,j ∈C ;and #2.a ij =0whenever i ∈C and j /∈C .

The important feature of such clusters is their self-contained dynamics,in the sense that d dt p i =α j ∈C a ij (p j ?p i ), j ∈C a ij =1,i ∈C .The dynamics of such self-contained clusters is covered

by the concentration state-ments of global dynamics in section 2.In particular,if cluster C (t )remains connected and isolated for a su?ciently long time,then its agents will tend to concentrate around a local consensus,p i (t )t →∞?→p ∞C for all i ∈C .The intricate aspect,however,is the last if statement:the evolution of agents in a cluster C may become in?uenced by non-C agents,and,in particular,di?erent clusters may merge over time.In the following,we ?x our attention on the particular models for opinion and ?ocking dynamics expressed in the uni?ed framework (1.4):(3.1a)d dt p i =αN j =1a ij (p j ?p i ),a ij =a ij (x )=1σi φ(|x i ?x j |).Recall that p →x in opinion dynamics,p →˙x in ?ocking dynamics,and σi is the degree,(3.1b)???σi =N,symmetric model ,σi = j =i φ(|x i ?x j |),nonsymmetric model .1We ignore possible cases in which the self-organized dynamics may regain connectivity under “cluster dynamics,”namely,agents separated into disconnected clusters and merging into each other at a later stage.D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. HETEROPHILIOUS DYNAMICS ENHANCES CONSENSUS 591We assume that the in?uence function φis compactly supported,

(3.2)Supp {φ(·)}=[0,R ].A cluster C =C (t )?{1,2,...,N }is speci?ed by the ?nite diameter of the

in?uence function φsuch that the following two properties hold:#1.max i,j ∈C (t )|x i (t )?x j (t )|≤R ;and #2.min i ∈C (t ),j /∈C (t )|x i (t )?x j (t )|>R.When the dynamics is global,R [x (0)],then the whole crowd of agents can be considered as one connected cluster.Here we consider the local dynamics when R is small enough relative to the active diameter of the global dynamics:R <[x (0)]in the opinion dynamics (1.2),or R

???either |p i (t )?p j (t )|t →∞?→0if i,j ∈C k ?|x i (t )?x j (t )|≤R,

or |x i (t )?x j (t )|>R if i ∈C k ,j ∈C ,k = .In this context,we raise the following two fundamental questions.Question 1.Identify the class of initial con?gurations,P (0),which evolve into ?nitely many clusters,C k ,k =1,...,K .In particular,characterize the number of such clusters K for t 1.Question 2.Assume that the initial con?guration P (0))is connected.Character-

ize the initial con?guration P (0)which evolves into one

cluster,K (t )=1for t 1,namely,the question of the emergence of consensus in the local dynamics.A complete answer to each of these questions should provide an extremely inter-esting insight into local processes of self-organized dynamics,with many applications.In the next two sections we provide partial answers to these questions.We begin with

the ?rst result,which shows that if the solution of (3.1)has bounded time-variation,then it must be partitioned into a collection of clusters.

Proposition 3.1(formation of clusters ).Let P (t )={p k (t )}k be the solution of the opinion or ?ocking models (3.1)with compactly supported in?uence function Supp {φ(·)}=[0,R ),and assume it has a bounded time-variation (3.3) ∞|˙p i (s )|ds <∞.Then P (t )approaches a stationary state,p ∞,which is partitioned into K clusters,

{C k }K k =1,such that {1,2,...,N }=∪K k =1C k and (3.4)???either p i (t )?→p ∞C k as t →∞for all i ∈C k ,or |x i (t )?x j (t )|>R for t 1if i ∈C k ,j ∈C ,k = .Remark 3.2.Observe that if the solution decays fast enough—in particular,if p (t )decays exponentially fast,|p i (t )?p ∞i | e ?C (t ?t 0),t ≥t 0>0(as in the unconditional consensus and ?ocking of global interactions discussed in section 2),then it has a bounded time-variation.D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. 592SEBASTIEN MOTSCH AND EITAN TADMOR Proof .Assumption (3.3)implies |p i (t 2)?p i (t 1)|≤ t 2t 1|˙p i (s )|ds 1for t 2>t 1 1,hence each agent approaches its own stationary state,p i (t )t →∞?→p ∞i .We claim that

˙p i (t )t →∞?→0.To this end,we distinguish between the two cases of ?rst-order opinion dynamics and second-order ?ocking dynamics.In opinion dynamics,p →x :since the expression on the right of (3.1a),(3.5)˙p i (t )=ασi (t ) j φ(|x i (t )?x j (t )|)(p i (t )?p j (t )),σi (t )= j φ(|x i (t )?x j (t )|),has a limit (involving p ∞i =x ∞i ),it follows that lim t →∞˙p

i (t )exists and by (3.3)it must be zero,˙p

i (t )→0.In the case of ?ocking dynamics,p →˙x ,and there are two types of pairs of agents (i,j ):either they have the same limiting “velocity,”p ∞i ?p ∞j =0,and,since φis bounded,φ(|x i (t )?x j (t )|)(p i (t )?p j (t ))t →∞?→0;

or,if p ∞i ?p ∞j =0,then (3.6)|x ∞i ?x ∞j | |p ∞i ?p ∞j |t >R,t 1,and hence φ(|x i (t )?x j (t )|)(p i (t )?p j (t ))=0,

t 1.In either case,the expression on the right of (3.5)vanishes as t →∞.Now,take the scalar product of (3.5)against p i and sum:(3.7) i σi ˙p i ,p i =α ij φij p j ?p i ,p i ≡?α2 ij

φij |p j ?p i |2.Since p i ∈Ω(0),σi ≤N are uniformly bounded and ˙p i (t )→0on the left,it follows that the expression on the right tends to zero.In opinion dynamics (p →x ),we can

pass to the limit in the expression on the right,which yields (3.8)φ(|x ∞i ?x ∞j |)|p ∞i ?p ∞j |2=0for all i,j ≤N.Thus,if |x ∞i ?x ∞j |>R ,then agents i and j are in separate clusters.Otherwise,when they are in the same cluster,say,i,j ∈C k so that |x ∞i ?x ∞j |0,and by (3.8)they must share the same stationary state,p ∞i =p ∞j =:p ∞C k ,that is,(3.4)holds.In the case of ?ocking dynamics,p →˙x ,we either have one type of pairs,|p i (t )?p j (t )|t →∞?→0,or a second type of pairs,(3.6),namely,(3.4)holds.We now turn our attention to the number of clusters,K .3.2.How Many Clusters?.Note that if p ∞=(p ∞1,...,p ∞N ) is a stationary state

of (3.1),then p ∞is an eigenvector associated with the nonlinear eigenvalue problem,

A (x ∞)p ∞=p ∞,D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. HETEROPHILIOUS DYNAMICS ENHANCES CONSENSUS 593corresponding to the eigenvalue λN (A (x ∞))=1.In fact,the number of stationary

clusters can be directly computed from the multiplicity of leading spectral eigenvalues of λN (A (x ∞)).Proposition 3.3.Assume that the crowd of N agents {p i (t )}N i =1is partitioned into K clusters,{1,2,...,N }=∪K (t )k =1C k .Then the number of clusters,K =K (t ),equals the geometric multiplicity of λN (A (x (t ))=1,(3.9)K (t )={#λN (A (x (t ))|λN (A (x (t ))=1}.Proof .We include the rather standard argument for completeness.Suppose that the dynamics of (3.1)at time t consists of K =K (t )clusters,∪K (t )k =1C k .De?ne the vector r k =(r k 1,...,r k N ) such that r k j = 1if j ∈C k ,0otherwise .We obtain A r k i = j a ij r k j = j ∈C k a ij .

Using the facts that A is a stochastic matrix and that a ij =0if x i and x j are not in the same cluster,we deduce j ∈C k a ij = 1if i ∈C k 0otherwise =r k i ,and therefore A r k =r k .Thus,associated with each cluster C k there is an eigenvector

r k corresponding to λN (A )=1.To conclude the proof,we have to show that there are no other vectors r satisfying A r =r .Indeed,assume that A r =r , j a ij r j =r i for any i.

Fix a cluster C k .Then for any p ∈C k we have j ∈C k a pj r j =r p for any p ∈C k .

Denote by r q the maximal entry of r j ’s on the left,corresponding

to some q ∈C k :since j ∈C k a pj =1with a pj >0,we deduce that for any p ∈C k we have r p = a pj r j ≤ a pj r q =r q .Thus,the entries of r are constant on the cluster C k ,so that r ∝r k .3.3.Numerical Simulations with Local Dynamics.We illustrate the emergence of clusters with 1D and 2D simulations of the opinion dynamics model (1.2b),

(3.10)d dt x i = j φij k φik (x j ?x i ),x i (t )∈R d .The in?uence function,φ,is taken as the characteristic function of the interval [0,1]:φ(r )=χ[0,1],and we use the Runge–Kutta method of order 4with a time-step of

Δt =.05for the time-discretization of the system of ODEs (3.10).D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. 594SEBASTIEN MOTSCH AND EITAN TADMOR d e n s i t y x x i t =40Fig.3The opinion model (1.2b)with M =100agents and φ=χ[0,1](left)and the histogram of

the distribution of x i at t =40unit time (right).We observe the formation of 4clusters separated by a distance greater than 1.As a ?rst example,we run a simulation of the 1D opinion model,d =1,subject to an initial con?guration of N =100agents uniformly distributed on the interval [0,10].In Figure 3(left)we plot the evolution of the opinions x i (t )in time.We observe the formation of four clusters after 15unit time.The histogram of the distribution of agents at the ?nal time t =40(see Figure 3(right))shows that the distance between the clusters is greater than 1,as predicted by Proposition 3.1.We also observe that the number of opinions contained in each cluster di?ers (respectively,35,14,31,and 20agents).Indeed,the larger cluster at x ≈2with 35opinions is a merge between three branches (see Figure 3)with one branch in the middle connecting the two external branches.When the two external branches ?nally connect at t ≈8.5(their distance is less than 1),we observe an abrupt change in the dynamics followed by a merge of the three branches into a single cluster.To analyze the cluster formation,we also look at the evolution of the eigenvalues of the matrix of interaction A (x (t ))in (3.10),a ij =φij / k φik .In Figure 4,we represent the evolution of the ?rst eight eigenvalues of the matrix A .From t =0to

t ≈3.5,we observe that the ?rst four ?rst eigenvalues converge to 1,which accounts for the fact that only four clusters remain at this time.Then

the matrix A (x (t ))remains constant in time from t ≈3.5to t ≈8.5.At t ≈8.5,two branches (see Figure 3)reconnect,and the two eigenvalues λ5and λ6equal zero.This con?rms Proposition 3.3where the additional multiplicity of the spectral eigenvalue λN (A (x (t ))=1indicates the formation of a new cluster.Next we illustrate the dynamics of the 2D,d =2,

opinion model (1.2b).With this aim,we run the model starting with an initial condition of N =1000agents distributed uniformly on the square [0,10]×[0,10].We present,in Figure 5,several snapshots of the simulations at di?erent times (t =0,2,4,6,12,and 30unit time).As in the 1D case,we ?rst observe a fast transition to a cluster formation (from t =0to t =6).However,at time t =12,the dynamics has not yet converged to a stationary state,and we observe on the upper left that three branches are at a distance less than 1from each other.This scenario is similar to the one observed in Figure 3with the apparition of three branches .At t =30,the three clusters on the upper left have ?nally merged and the system has reached a stationary state:each cluster is at a distance greater than 1from all others.D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. HETEROPHILIOUS DYNAMICS ENHANCES CONSENSUS 59500.20.40.60.81

0510152025λi t λ1λ2λ3λ4λ5λ6λ7λ8||||||||||||||||||Fig.4Absolute values of the eigenvalues of the matrix A (3.10)during the simulation given in Figure 3.The number of eigenvalues equal to 1corresponds to the number of clusters.4.K =1:Uniform Connectivity Implies Consensus.The emergence of a con-sensus in the opinion or ?ocking models (1.4)implies that the underlying graph as-

sociated with the dynamics must remain connected,namely,|x i (t )?x i (t )| R at least for t 1.In this section we discuss the converse

statement,namely,that uni-form connectivity implies consensus.The implication of consensus in the symmetric case is based on a straightforward application of algebraic connectivity and is outlined in section 4.1.The corresponding question of consensus in nonsymmetric connected models is carried out in section 4.2using an energy method .We emphasize that

consensus in both cases depends on the time-dependent

behavior of intensity of con-nectivity,beyond the mere graph connectivity.Recall that the graph associated with (1.1),G A :=(P ,A (P )),is connected if every two agents p i (t )and p j (t )are connected through a path Γij :={k 1=i

connected if there exists μ(t )>0such that,for all paths Γij ,(4.1)min k ∈Γij a k ,k +1(P (t ))≥μ(t )>0for all i,j.In particular,if μ(t )≥μ>0,then we say that P (t )is uniformly connected.Alternatively,uniform connectivity of (1.1)requires the existence of μ=μA >0independent of time,such that A N (P (t )) ij ≥μN >0.4.1.Consensus in Local Dynamics:Symmetric Models.We consider the sym-

metric dynamics (1.1)with associated graph G A :=(P ,A (P )).Fix the positions of any two agents p i (t )and p j (t )and their (shortest)connecting path Γij of length r ij .Thus,r ij measures the degree of separation between agents (i,j ),and if we let the maximal degree of separation denote the diameter of the graph,diam (G A ):=max ij r ij ,then

|p i ?p j |2≤diam (G A ) k ∈Γij |p k +1?p k |2,diam (G A )≤N.D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. 596SEBASTIEN MOTSCH AND EITAN TADMOR Fig.5Simulation of the opinion model (1.2b)in 2D with M =1000agents and φ=χ[0,1].The dynamics converges to a cluster formation (17clusters),with each cluster separated by a distance greater than 1.D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

Copyright ? by SIAM. Unauthorized reproduction of this article is prohibited. HETEROPHILIOUS DYNAMICS ENHANCES CONSENSUS 597By uniform connectivity,μ≤a k +1,k along each path and hence

(4.2)μdiam (G A )|p i ?p j |2≤ k ∈Γij a k +1,k |p k +1?p k |2≤ ij a ij |p i ?p j |2,and summation over all pairs yields μdiam (G A ) ij |p i ?p j |2≤N 2 ij a ij |p i ?p j |2.Now we recall our notation q i :=p i ? p :invoking (2.19)we ?nd (4.3)λ2(L A )=min q k =0 L A q ,q q ,q =min p (1/2) ij a ij |p i ?p j |2(1/2N ) ij |p i ?p j |2≥μNdiam (G A ).Thus,the scaled connectivity factor μ/(Ndiam (G A ))≥μ/N 2serves as a lower bound

for the Fiedler number associated with the symmetric dynamics of (1.1)(counting the number of “maximal”edges,it yields the slightly sharper lower bound λ2≥4μ/N 2[87]).Using Theorem 2.11we conclude the following result.Theorem 4.2(connectivity implies consensus:the symmetric case ).Let P (t )={p k (t )}k be the solution of a symmetric self-organized dynamics

d dt p i (t )=α j =i a ij (P (t ))(p j (t )?p i (t )),a ij =a ji .If P (t )remains connected in tim

e with “su?ciently strong”connectivity μA (P (s ))>0,then it approaches the consensus p (0),namely,∨p (t ) exp ?αN 2 t 0μA (P (s ))ds ∨p (0),∨2p (t ):=1N

|p i (t )? p (0)|2.In particular,if P (t )remains uniformly connected in time (cf.(4.1)),then it ap-

proaches an emerging consensus,p i (t )→p ∞= p (0),with a convergence rate (4.4)∨p (t ) e ?αμN 2t ∨p (0).It is important to notice that Theorem 4.2requires the intensity of connectivity to be su?ciently strong:connectivity alone,with a rapidly decaying μ(t ),is not su?cient for consensus as illustrated by the following counterexample.Counterexample.Consider the symmetric dynamics (1.2a)with ?ve agents,x 1,...,x 5,subject to initial con?guration (4.5)x 1(0)=?x 5(0),x 2(0)=?x 4(0),x 3(0)=0,with (x 4(0),x 5(0))to be speci?ed below inside the box D :={12

[0,1];note that φ (0)=φ (1)=0.By symmetry,the initial ordering in (4.5)is preserved in time.In particular,x 3(t )≡0,and (x 4(t ),x 5(t ))→(x (t ),y (t ))preserve D o w n l o a d e d 04/04/15 t o 61.187.54.9. R e d i s t r i b u t i o n s u b j e c t t o S I A M l i c e n s e o r c o p y r i g h t ; s e e h t t p ://w w w .s i a m .o r g /j o u r n a l s /o j s a .p h p

本文来源：https://www.bwwdw.com/article/70eq.html