EXPANDER GRAPHS ARE GLOBALLY SYNCHRONIZING PEDRO ABDALLA AFONSO S. BANDEIRA MARTIN KASSABOV VICTOR SOUZA STEVEN H. STROGATZ AND ALEX TOWNSEND

2025-05-06 0 0 754.66KB 34 页 10玖币

侵权投诉

EXPANDER GRAPHS ARE GLOBALLY SYNCHRONIZING

PEDRO ABDALLA, AFONSO S. BANDEIRA, MARTIN KASSABOV, VICTOR SOUZA,

STEVEN H. STROGATZ, AND ALEX TOWNSEND

Abstract.

The Kuramoto model is fundamental to the study of synchronization. It

consists of a collection of oscillators with interactions given by a network, which we

identify respectively with vertices and edges of a graph. In this paper, we show that

a graph with suﬃcient expansion must be globally synchronizing, meaning that a

homogeneous Kuramoto model of identical oscillators on such a graph will converge to

the fully synchronized state with all the oscillators having the same phase, for every

initial state up to a set of measure zero. In particular, we show that for any

ε >

and

p⩾

(1 +

)(

log n

)

, the homogeneous Kuramoto model on the Erdős–Rényi

random graph

(

n, p

)is globally synchronizing with probability tending to one as

goes to inﬁnity. This improves on a previous result of Kassabov, Strogatz, and

Townsend and solves a conjecture of Ling, Xu, and Bandeira. We also show that the

model is globally synchronizing on any

-regular Ramanujan graph, and on typical

d-regular graphs, for large enough degree d.

1. Introduction

In 1665, Christiaan Huygens—the inventor of the pendulum clock—observed that

two pendulum clocks spontaneously synchronize when hung from the same board.

This is the ﬁrst recorded observation of synchronization of coupled oscillators. In the

centuries since then, synchronization has become a central subject of study in dynamical

systems, motivated both by its mathematical interest and its many applications

in classical mechanics, statistical physics, neuroscience, engineering, medicine, and

biology [3,5,8,16,38,39,42,44,45].

We are interested in understanding spontaneous synchronization of multiple coupled

oscillators whose pairwise connections are given by a graph

= (

V, E

). Following the

celebrated work of physicist Yoshiki Kuramoto in 1975 [25], we consider the following

system of ordinary diﬀerential equations:

dθx

dt=ωx−X

y∈V

Ax,y sin(θx−θy),for all x∈V, (1.1)

where each vertex

x∈V

has associated with it an oscillator

θx:R→S1

. Here

θx

(

)is

the phase of oscillator

θx

at time

ωx∈R

is the oscillator’s intrinsic frequency, and

is the adjacency matrix of G.

The Kuramoto model

(1.1)

is an

-dimensional nonlinear dynamical system, where

is the number of vertices in

. For simplicity, the early work on this model focused on the

case where all

oscillators interact with each other with equal strength, corresponding

to a complete graph on

vertices. To account for the diversity inherent in real biological

oscillators, the intrinsic frequencies

ωx

were typically assumed to vary at random across

the oscillator population according to a prescribed probability density

(

), taken to

be unimodal and symmetric about its mean. In the limit

n→ ∞

, Kuramoto [25,26]

arXiv:2210.12788v3 [math.CO] 10 Apr 2024

2 ABDALLA, BANDEIRA, KASSABOV, SOUZA, STROGATZ, AND TOWNSEND

showed that the model undergoes a phase transition (from a completely disordered

state to a partially synchronized state) if the oscillators are close enough to identical,

i.e., if the width of

(

)falls below a certain threshold. For reviews of the Kuramoto

model on a complete graph, see [3,8,38,44].

Recent work on the Kuramoto model has turned to the exploration of other interaction

graphs. The goal is to understand which networks foster synchronization. We focus

our analysis on the homogeneous case where all the oscillators have the same intrinsic

frequency

ωx

. The advantage of the homogeneous case is that the oscillators are

then guaranteed to settle down to phase-locked states; in other words, all the phase

diﬀerences

θx

(

)

−θy

(

)asymptotically approach constant values as

t→ ∞

. In contrast,

if the oscillators’ frequencies are non-identical, more complicated long-term behavior

such as chaos can occur [32].

For the homogeneous case, it proves convenient to recast the dynamics in a rotating

frame

(

)

←θ

(

)

−ωt

. Then

(1.1)

is given by the gradient ﬂow d

θ/

−∇EG

(

), in

which the oscillators can be viewed as attempting to minimize the energy

EG:

(

)

V→R

deﬁned by

EG(θ) = 1

x,y∈V

Ax,y 1−cos(θx−θy).(1.2)

The long-term dynamics can thus be described by the landscape of the energy function

. A state

is called an equilibrium state if d

θ/

= 0. In view of

(1.1)

, all the

oscillators in an equilibrium state move at the intrinsic frequency

in the original

reference frame, without changing their relative phase diﬀerences, whereas in the

rotating frame, all the oscillators would be motionless. As the dynamics follow a

gradient system, the equilibrium states are the critical points of the energy, namely,

states

such that

∇EG

(

) = 0. If, furthermore,

is a local minimum of

, we call

astable equilibrium state, or simply a stable state. These correspond precisely to

equilibrium states that are physically achievable, as most small perturbations return

the system back to

. Indeed, we have a stable equilibrium only when

is a local

minimum of EG.1

The energy

(

)is always non-negative and it is minimized when all the oscillators

have the same phase, that is,

θx

θy

for all

x, y ∈V

. These states are called the fully

synchronized states.

If other local minima of

exist, they are called spurious local

minima. The main goal of this paper is to understand, for which graphs

, the energy

landscape EGhas no spurious local minima.

Deﬁnition 1.1 (Globally synchronizing graph).Consider the Kuramoto model on a

graph

with an initial state

chosen uniformly at random from (

)

. We say that

is globally synchronizing if

converges to a fully synchronized state with probability

one.

has a spurious local minimum then there will be an open set of initial conﬁgu-

rations that would converge to said minimum, so

is not globally synchronizing. Even

has no spurious local minima,

may not be globally synchronizing as other types

of undesirable equilibrium points are possible. These can be, for instance, third-order

1This is a consequence of the fact that EGis analytic; see Absil and Kurdyka [2].

We consider two states

and

θ′

to be equivalent if they diﬀer by a global rotation, that is

θx−θ′

for all x∈V, for some c∈R.

EXPANDER GRAPHS ARE GLOBALLY SYNCHRONIZING 3

saddle points of EGwhere the Hessian ∇2EGis zero. However, each trajectory for our

system converges to a single critical point of

. No other form of long-term behavior

is possible, because the homogeneous Kuramoto model is an instance of a gradient ﬂow

of an analytic potential function on a compact analytic manifold, and the solutions of

such ﬂows are always convergent to single points, as a consequence of the Łojasiewicz

gradient inequality, see Lageman [27].

is analytic, the set of initial states from which the Kuramoto model would

converge to a strict saddle point of

(that is, states

such that the Hessian

∇2EG

(

)

has a strictly negative eigenvalue) has measure zero, see e.g. [20, Lemma B.1]. The

upshot is that to show that a graph

is globally synchronizing, it is enough to guarantee

that the only equilibrium states

with positive semideﬁnite Hessian

∇2EG

(

)are the

fully synchronized states.

An active line of work has focused on determining which graphs are globally syn-

chronizing. Random graph models are of particular importance, as they play the role

of proxies for realistic complex networks. The classical model for a random graph

is the Erdős–Rényi model: a graph

drawn from

(

n, p

)is a graph on

vertices

where each edge is present, independently, with probability

. Ling, Xu, and Bandeira

in [29] established a connection between

(

)and non-convex optimization landscapes

arising in algorithms for community detection and other statistical inference prob-

lems [6], which allowed them to show that an Erdős–Rényi graph with edge probability

= Ω(

n−1/3log n

)is globally synchronizing with high probability.

The result was

improved to

= Ω((

log n

)

2/n

)by Kassabov, Strogatz, and Townsend [24]. Ling, Xu,

and Bandeira in [29, Open Problem 3.4] formulated a conjecture that almost any graph

(

n, p

)is globally synchronizing, where

= (1 +

)(

log n

)

and

ε >

0. As this

corresponds to the connectivity threshold of

(

n, p

), this threshold is the best possible.

One of our main results is to prove this conjecture.

Theorem 1.2. A graph in

(

n, p

)is globally synchronizing with high probability

whenever

p⩾

(1+

)(

log n

)

and

ε >

0. In other words, if a graph

has

vertices and

each possible edge is independently included in

with probability

p⩾

(1 +

)(

log n

)

then the probability that Gis globally synchronizing tends to 1as ntends to inﬁnity.

We prove global synchronization of graphs drawn from

(

n, p

)by using their expan-

sion properties and proving that graphs that are suﬃciently good expanders necessarily

globally synchronize. From a bird’s-eye view, the reason is that spurious stable ﬁxed

points need to correspond, in a certain sense, to assignments from the vertices to phases

such that pairs of vertices corresponding to similar phases are connected signiﬁcantly

more often than pairs of vertices corresponding to disparate phases. However, expander

graphs are known to satisfy versions of expander mixing lemmas that force most pairs

of subsets of vertices to have a number of edges connecting them that is close to the

expected number of edges if the edges were placed randomly. This rules out stable

states formed of phases that are well spread on the circle, as properties of expander

graphs prevent the possibility of having pairs of similar phases be “over-connected,” as

compared to pairs of disparate phases. At the other extreme, nontrivial stable ﬁxed

points that are formed of phases only occupying less than half of the circle can be ruled

out by a standard result known as the half-circle lemma (Lemma 2.8).

3That is, with probability tending to one as ntends to inﬁnity.

4 ABDALLA, BANDEIRA, KASSABOV, SOUZA, STROGATZ, AND TOWNSEND

One core diﬃculty is that the two types of arguments are fundamentally diﬀerent:

the former, for well-spread phases, is based on second-order (stability) conditions while

the latter, for concentrated phases, is based on ﬁrst-order (stationary) conditions.

Kassabov, Strogatz, and Townsend [24] developed a so-called ampliﬁcation argument

that can handle candidate stable ﬁxed points in between these two regimes by simul-

taneously leveraging both strategies; this allowed them to show global synchrony for

= Ω((

log n

)

2/n

). Our approach builds on [24] and achieves the connectivity threshold

by developing an improved version of the ampliﬁcation argument that is based on a new

stability condition, and by also performing a more reﬁned analysis of the expansion

and spectral properties of the graph.

Our ampliﬁcation argument (Section 4) works the following way: Given a stable state

, we interpret each phase

θx

as a point mass at

eiθ

on the unit circle in the complex

plane and consider the half-circle

with the smallest mass. If the arc

is empty, then

is a fully synchronized state, by the half-circle lemma (Lemma 2.8). Otherwise, we

progressively enlarge the arc

to pick up more and more of the mass. The core of

the argument is the use of ampliﬁcation steps, where we exploit the properties of the

expander graph to show that the mass encompassed by the arc grows exponentially fast

without growing the arc itself too quickly. By repeatedly applying these ampliﬁcation

steps, we obtain a new arc with most of the mass. If done carefully, this argument

leads to a contradiction when the mass of the ﬁnal arc is put together with various

stability conditions of the Kuramoto model. In essence, if most of the mass is on the

ﬁnal arc, and the ﬁnal arc is not too far from the original half-circle, then the original

half-circle cannot have been the one with the smallest mass. The only possibility then

is that the half-circle was originally empty and θis fully synchronized.4

Among the new technical tools we developed to prove Theorem 1.2, we highlight:

(i)

A novel kernel stability condition (Lemma 2.7) for the Kuramoto model. This

was a crucial piece in obtaining diﬀerent ampliﬁcation steps (Lemma 4.3 and

Lemma 4.4) that provide a massive savings on the late stages of the argument.

Without this improvement, we would not be able to obtain our result with

p=C(log n)/n, even with an arbitrarily large constant C.

(ii)

A reﬁned two-sided notion of expansion, together with its associated spectral

graph theory machinery. When

(

log n

)

, not only do the degrees of the

Erdős–Rényi graph fail to concentrate, but the maximum and minimum degree

do not deviate symmetrically from the mean. We must pay special attention

to vertices of small degree as they can interfere with expansion on small sets.

With one-sided control of expansion, we would not be able to obtain our global

synchrony in G(n, p)result when p < 2.58(log n)/n.

(iii)

We also employ techniques from random matrix theory in order to obtain explicit

control on the eigenvalues of the adjacency matrix of

(

n, p

). This allows us,

for instance, to obtain an explicit bound on the probability that

(

n, p

)is not

globally synchronizing; see Theorem 6.2, as well as further details in Section 6.

This technique resembles the density increment argument in extremal and additive combinatorics

(see the blog of Tao [46] for several examples) and while it takes considerable input from the

Kuramoto model, it may be possible that it can be adapted to other models and phenomena beyond

synchronization.

EXPANDER GRAPHS ARE GLOBALLY SYNCHRONIZING 5

The only information from the underlying graph needed to implement our version

of the ampliﬁcation argument is a control of the spectrum of the adjacency and

Laplacian matrices. Indeed, our main contribution is to show that expander graphs,

with suﬃciently large expansion, are globally synchronizing. Expander graphs are a

central object of study in graph theory and theoretical computer science (see, e.g., [21])

as they are good sparse surrogates for complete graphs and have many pseudorandom

properties.

After introducing the relevant notation, we state all our results in Section 1.2 and

Section 1.3 below. In Section 1.4 we brieﬂy outline some related work on globally

synchronizing graphs.

1.1. Notation. A graph

= (

V, E

)with adjacency matrix

A∈ {

}n×n

is said to

-regular if all vertices have degree

. The eigenvalues of

are represented by

λ1

(

)

⩾··· ⩾λn

(

). We denote by

the all-ones vector, by

1 1⊤

the all-ones

matrix and by

the identity matrix, always taken with appropriate sizes. For symmetric

matrices

and

of same dimensions, the notation

A⪰B

means that

A−B

is a

positive semideﬁnite matrix, i.e., the symbol ⪰denotes the standard Loewner partial

order. The degree matrix

D∈Rn×n

is a diagonal matrix with

Dii

(

)and the

graph Laplacian is given by

D−A

. We deﬁne the centered adjacency matrix by

∆

A:=A−

)

, the centered diagonal degree matrix ∆

D:=D−

and the centered

Laplacian matrix ∆

L:=

∆

D−

∆

L−

+ (d

)

. Here, dis a parameter to be

chosen, which we always select as an “expected average degree” of

. For instance,

when

-regular, we take d=

, and for

(

n, p

), we take d=

. We write

∥H∥

for the operator norm of a matrix H, namely, ∥H∥= supf̸=0∥Hf∥/∥f∥.

1.2. Main results: regular graphs. For regular graphs, our main result is that

spectral expansion implies global synchrony.

Deﬁnition 1.3. We say that a graph

is an (

,α

)-expander if it has

vertices and



∆A

:=

A−(d/n)J

⩽αd.

If in addition the graph

is d-regular

, then the condition above is equivalent to

maxi̸=1λi(A)⩽αd.

For regular graphs, our main result is the following.

Theorem 1.4. All d-regular (

,α

)-expander graphs with

α⩽

0816 are globally

synchronizing.

Remark 1.5. The proof of Theorem 1.4 relies on some numerical computations

outlined in Section 5. Without such computation we can only prove a weaker version

for α⩽0.0031, which follows from Theorem 1.10.

An important class of expander graphs are the Ramanujan graphs. These are

regular (

n, d, α

)-expanders with

= 2(

√d−1

)

, which is asymptotically the smallest

possible value of

for a given

, due to a result of Alon and Bopanna [36]. In other

words,

-regular Ramanujan graphs are the best expanding graphs among the class of

d-regular graphs.

5In the literature, d-regular (n, d, λd)-expanders are commonly called (n, d, λ)-graphs.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

EXPANDERGRAPHSAREGLOBALLYSYNCHRONIZINGPEDROABDALLA,AFONSOS.BANDEIRA,MARTINKASSABOV,VICTORSOUZA,STEVENH.STROGATZ,ANDALEXTOWNSENDAbstract.TheKuramotomodelisfundamentaltothestudyofsynchronization.Itconsistsofacollectionofoscillatorswithinteractionsgivenbyanetwork,whichweidentifyrespectivelywithvertices...

展开>> 收起<<

EXPANDER GRAPHS ARE GLOBALLY SYNCHRONIZING PEDRO ABDALLA AFONSO S. BANDEIRA MARTIN KASSABOV VICTOR SOUZA STEVEN H. STROGATZ AND ALEX TOWNSEND.pdf

共34页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

EXPANDER GRAPHS ARE GLOBALLY SYNCHRONIZING PEDRO ABDALLA AFONSO S. BANDEIRA MARTIN KASSABOV VICTOR SOUZA STEVEN H. STROGATZ AND ALEX TOWNSEND

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: