Bifurcations of mutually coupled equations in random networks

Eduardo Garibaldi^{∗} UNICAMP – Department of Mathematics 13083-859 Campinas – SP, Brazil garibaldi@ime.unicamp.br

Tiago Pereira^{†} Department of Mathematics Imperial College London, South Kensington, London SW7 2BA tiago.pereira@imperial.ac.uk

Abstract

We study the behavior of solutions of mutually coupled equations in heterogeneous random graphs. Heterogeneity means that some equations receive many inputs whereas most of the equations are given only with a few connections. Starting from a situation where the isolated equations are unstable, we prove that a heterogeneous interaction structure leads to the appearance of stable subspaces of solutions. Moreover, we show that, for certain classes of heterogeneous networks, increasing the strength of interaction leads to a cascade of bifurcations in which the dimension of the stable subspace of solutions increases. We explicitly determine the bifurcation scenario in terms of the graph structure.

Keywords: bifurcation, coupled equations, dichotomies, random graphs

2010 Mathematics Subject Classification: 05C80, 34C15, 34F05, 34F10, 37C10, 60B20

1 Introduction

The last decade has witnessed rapidly growing interest in dynamics of coupled dynamical systems [1, 2, 3]. In most applications, the interaction structure among elements is intricate [4] and modeled by random graphs [5, 6]. Empirical studies indicate that this interaction structure can have dramatic influences on the dynamical properties and the functioning of such systems [7, 8].

∗Supported by BREUDS and FAPESP 2012/18780-0.

†Supported by FP7 Marie Currie Actions (Project 303180) and IRSES–DynEurBraz.

Recent studies show that disparate real-world networks display a heterogeneous connectivity – while some nodes, called hubs, receive many connections, most of the nodes are poorly connected [1, 7]. Such a connectivity structure leads to distinct dynamical behavior across the network. The understanding of the dynamics in heterogeneous networks is in its early stages [3, 9].

Mutually coupled equations. Our aim is to study the behavior of solutions of mutually coupled systems with interaction structure given by a heterogeneous random graph. Consider the set of n nonautonomous linear equations

ẋ_{i} = V_{i}(t)x_{i},  for i = 1, …, n,  (1)

where, for d ≥ 1, each V_{i} : ℝ × ℝ^{d} → ℝ^{d} is a continuous and bounded linear operator. We also assume that these equations are unstable, with nontrivial solutions diverging exponentially fast.

We are interested in the changes in dynamics once the equations are coupled. We consider the following one-parameter family of n coupled equations

ẋ_{i} = V_{i}(t)x_{i} + α ∑_{j=1}^{n} A_{ij}[H(x_{j}) − H(x_{i})],  (2)

where α is the overall coupling strength, H is a positive-definite matrix, and A = (A_{ij}) is the adjacency matrix describing graph connectivity, so that A_{ij} = 1 if i receives a connection from j and A_{ij} = 0 otherwise. The degree of the i^{th} node to be the number of connections it receives. We will focus on heterogeneous graphs. To be precise, if κ_{j} < κ_{i} denote node degrees in different subnetworks, then heterogeneity means that Γκ_{i}^{1−γ} ≥ κ_{j} for some 0 < γ < 1 and Γ > 0. These models have hierarchical organization with modular structures.

This modelization appears in studies of synchronization in mutually coupled equations [10, 11] and has applications in many areas such as neuroscience and engineering [12]. In this research branch, synchronization corresponds to the existence of an attracting synchronization manifold. Although in the aforementioned works the equations for the isolated nodes are nonlinear, we have chosen to start with the linear case because, if the vectors fields of the isolated equations are smooth enough, we can linearize the equations about the synchronization manifold and obtain a set of equations in the form (2), see [11]. In this regard, all the results we develop here in an abstract setting have a direct counterpart to the theory of synchronization in complex networks.

We aim at understanding the dynamics of almost every heterogeneous connection structure A. The combination of the probabilistic point of view in graphs with the theory of exponential dichotomies makes it possible to characterize the dynamics of a large set of networks. Our main results show that, for large random graphs, as α is increased, there is a bifurcation leading to the appearance of stable subspaces of solutions. Furthermore, the dimension of the stable subspace is determined by the graph structure. Loosely speaking, for a suitable range of coupling strength α, we have that

dimension of stable subspace = d × ℓ,

where d is the dimensional of the solution space of the isolated equation, and ℓ is the number of highly connected nodes in the graph. Moreover, if the highly connected nodes are in distinct connectivity regimes, then we prove that there is a cascade of bifurcations increasing the dimension of the stable subspace of solutions. The precise statements of our results can be found in theorem 1 and theorem 3.

2 Preliminaries

In this section, we provide the basic ingredients for the statement of our results.

2.1 Notation

We use the small “o” notation for the asymptotic behavior n → ∞. We write f(n) = o(1) if f(n) goes to zero as n tends to infinity.

We endow the vector space ℝ^{d} with the usual Euclidean inner product and the associated Euclidean norm. The space of linear operators is equipped with the induced operator norm. For a continuous family of bounded operators V : ℝ_{+} × ℝ^{d} → ℝ^{d}, we consider the uniform norm

∥V ∥ = sup_{t>0} ∥V (t)∥.

The identity is denoted by I_{d}.

2.2 Nonautonomous Linear Equations

We introduce now the concept of exponential dichotomy for a linear differential equation. We follow closely [13, 14].

Consider the nonautonomous linear equation

ẋ = V (t)x,  (3)

where V : ℝ × ℝ^{d} → ℝ^{d} is a continuous and bounded linear operator. We denote by T (t, s) the associated evolution operator, which describes how the solution evolves in time: x(t) = T (t, s)x(s). Clearly,

T (t, t) = I_{d}  and  T (t, s)T (s, r) = T (t, r), ∀ t, s, r ∈ ℝ

The following definition will be central for our study.

Definition 1 (Exponential Dichotomy). We say that the linear equation (3) admits an exponential dichotomy in the half line ℝ_{+} if there is a projector P : ℝ × ℝ^{d} → ℝ^{d}, with

P (t)T (t, s) = T (t, s)P (s) ∀ t ≥ s > 0,

for which one may find constants η > 0 and K > 0 such that, for all t ≥ s ≥ 0,

∥T (t, s)P (s)∥ ≤ Ke^{−η(t−s)} and ∥T^{−1}(t, s)(I_{d} − P)(t)∥ ≤ Ke^{−η(t−s)}.  (4)

The exponential dichotomy implies that there is a stable subspace of solutions tending to zero uniformly and exponentially as time goes to infinity. In the complementary subspace, solutions tend to infinity uniformly and exponentially as time goes to infinity.

2.3 Random Graphs

We will consider random graphs of n nodes modelled by a probability space consisting of the set of labelled undirected graphs of n nodes, endowed with the power-set sigmaalgebra, and a probability measure. We will use a random graph model and terminology from references [5, 6]. This model is an extension of the Erdös-Rényi model for random graphs with a general degree distribution. Concerning the terminology, we will adopt the term “ensemble” instead of the longer expression “probability space”.

The main point of the model consists in to prescribe the expected values of the node degrees. For convenience, any given sequence of expected degrees w_{n} = (w_{1}, w_{2}, ⋯, w_{n}) is supposed to verify

max_{1≤k≤n} w_{k} = w_{1} ≥ w_{2} ≥ ⋯ ≥ w_{n} > 0.

We consider thus an ensemble of random graphs G(w_{n}) in which an edge between nodes i and j is independently assigned with success probability

p_{ij} = \frac{w_{i}w_{j}}{∑_{k=1}^{n} w_{k}} .

In order to ensure that p_{ij} ≤ 1, we assume that w_{n} is chosen so that

( max_{1≤k≤n} w_{k})^{2} ≤ ∑_{k=1}^{n} w_{k}.  (5)

A realization of a graph in the ensemble G(w_{n}) is encoded in the adjacency matrix A = (A_{ij}) with (0, 1)-entries determining the connections among nodes of the graph. The degree κ_{i} of the i^{th} node is the number of connections that it receives:

κ_{i} = ∑_{j=1}^{n} A_{ij}.

Notice that κ_{i} is a random variable whose expected value is exactly the prescribed quantity w_{i}. In particular, w_{1} = max_{1≤i≤n} w_{i} is the largest expected value of a degree.

Network property. We say that a property 𝔓 holds almost surely if the probability that 𝔓 holds tends to 1 as n goes to infinity. The assertion almost every graph in G(w_{n}) has a property 𝔓 shall be understood as the proportion of all labelled graphs of order n that satisfy 𝔓 tends to 1 as n goes to infinity.

This asymptotic probabilistic viewpoint naturally motivates us to work with sequences of random graphs and thus with sequences of expected degrees. In a rigorous way, we should write w_{i}(n) to highlight the dependence in n of the expected degree of the i^{th} node. In order to avoid a heavy notation, we leave this dependence implicit. Hence, by imposing additional assumptions on the prescribed expected degrees, we focus our attention on the following suitable sequences of heterogeneous graphs.

Definition 2 (Strong Heterogeneity). For a non decreasing function ℓ : ℕ → ℕ and constants θ, γ ∈ (0, 1), we say that a sequence of ensembles {G(w_{n})}_{n≥1} is (ℓ, θ, γ)-strongly heterogeneous if the following hypotheses are satisfied.

[H0] Cardinality of hubs: there exists a universal constant Γ_{0} > 0 such that

ℓ(n) < Γ_{0}( max_{1≤k≤n} w_{k})^{θ}.

[H1] Massively connected hubs: there exists a constant c_{0} ∈ (0, 1/2] such that

lim inf_{n→∞} min_{1≤i≤ℓ(n)} \frac{w_{i}}{max_{1≤k≤n} w_{k}} = lim inf_{n→∞} \frac{w_{ℓ(n)}}{max_{1≤k≤n} w_{k}} = 2c_{0}.

[H2] Poorly connected nodes: there exist universal constants Γ_{1}, Γ_{2} > 0 and β > 0 such that, for every i ∈ {ℓ(n) + 1, …, n},

Γ_{1}( log n)^{1+β} < w_{i} < Γ_{2}( max_{1≤k≤n} w_{k})^{1−γ}.

Notice that ℓ(n) indicates the number of hubs of the graph, that is, of highly connected nodes. The parameter θ restricts thus their amount. Besides, thanks to the hypothesis [H2], the constant γ controls the scale separation between low degree nodes and hub nodes. By abuse of notation, we say that any element G(w_{n}) of such a sequence is (ℓ, θ, γ)-strongly heterogeneous. We denote this ensemble of heterogeneous random graphs by G_{ℓ,θ,γ}(w_{n}). A relevant subclass of heterogeneous graphs is introduced below.

Definition 3 (Hubs in Distinct Regimes). We say that an (ℓ, θ, γ)-strongly heterogeneous sequence of ensembles {G_{ℓ,θ,γ}(w_{n})}_{n≥1} has hubs in distinct regimes if the additional hypothesis is verified:

[H1’] there exist sequences of constants {σ_{i}}, {τ_{i}} ⊂ (0, 1] such that both are strictly decreasing and, for any fixed index i < ℓ(n),

lim inf_{n→∞} \frac{w_{i}}{max_{1≤k≤n} w_{k}} > σ_{i} ≥ τ_{i} > lim sup_{n→∞} \frac{w_{i+1}}{max_{1≤k≤n} w_{k}} .

We commit again abuse of notation by extending such a designation to any element of the sequence, which will be denoted by G′_{ℓ,θ,γ}(w_{n}).

3 Main Theorems and Discussion

Consider the uncoupled equations (1). Due to the asymptotic nature of our analysis, we assume from now on that

max_{i≥1} ∥V_{i}∥ < +∞.

The unique solution of each equation can be represented in terms of the transition matrix

x_{i}(t) = T_{i}(t, s)x_{i}(s), i = 1, …, n.

When we say that solutions are unstable, we mean that there are constants η_{0} > 0 and K_{0} > 0 such that, for all t > s,

∥T_{i}^{−1}(t, s)∥ ≤ K_{0} e^{−η_{0}(t−s)},  i = 1, …, n.  (6)

Notice that we suppose all evolution operators share the same constants η_{0} and K_{0}.

To state our results, it will be convenient to represent coupled equations in a single block form. Consider

X = col(x_{1}, ⋯, x_{n}),

where col denotes the vectorization formed by stacking the column vectors x_{i} into a single column vector. Moreover, we denote

V (t) = ⨁_{i=1}^{n} V_{i}(t) = diag(V_{1}(t), …, V_{n}(t)).

Then the coupled equations (2) can be recast into a block form

Ẋ = [V (t) − αL ⊗ H]X,  (7)

where L = (L_{ij}) is a combinatorial laplacian given by L_{ij} = δ_{ij}κ_{i} −A_{ij} (as usual, δ_{ij} stands for the Kronecker delta), and ⊗ is the Kronecker product [15]. The unique solution of equation (7) can be represented in terms of the transition matrix

X(t) = T (t, s)X(s).

For α = 0, the equations are uncoupled and have only unstable solutions. Our main results show that stable solutions appear when these equations are coupled in heterogeneous random graphs and that increasing the coupling strength α leads to a sequence of bifurcations.

Theorem 1. Consider the ensemble G_{ℓ,θ,γ}(w_{n}), with θ < (3 − \sqrt{5})/2 and γ > (\sqrt{5} − 1)/2. Then, there are constants C, c > 0 and an integer N_{0} > 0 such that, for all n > N_{0}, whenever

c < α max_{1≤k≤n} w_{k} < C( log n)^{γ},

with probability at least 1−n^{−1/2}−2n^{−1/5}, the coupled equations (7) on a graph of G_{ℓ,θ,γ}(w_{n}) admit an exponential dichotomy: for positive constants K and η and a projector P that commutes with T, for all t ≥ s ≥ 0,

∥T (t, s)P (s)∥ ≤ Ke^{−η(t−s)} and ∥T^{−1}(t, s)(I_{d} − P)(t)∥ ≤ Ke^{−η(t−s)}.

Moreover, in such a situation, the dimension of the stable subspace is determined by the network structure

rank P = d × ℓ(n).

Roughly speaking, the constants c and C in our theorem 1 are given by two distinct mechanisms. The constant c comes from the fact that we wish to guarantee the existence of the stable subspace whereas the constant C comes from fact that the complementary subspace of unstable solution must have a uniform exponent divergence. And thereby we ensure the existence of the dichotomy.

On a heterogeneous random graph a natural coupling parameter is given by

α = \frac{α_{0}}{max_{1≤k≤n} w_{k}} .

We regard the parameter α_{0} as the normalized coupling strength capturing the dynamics at the highly connected nodes. In this case, the previous theorem can be restated in the following form.

Theorem 2. For the ensemble G_{ℓ,θ,γ}(w_{n}), with θ < (3 − \sqrt{5})/2 and γ > (\sqrt{5} − 1)/2, there exists a positive constant c = c(H, max_{i≥1} ∥V_{i}∥, c_{0}) such that if

α_{0} > c

then the coupled equations (7) on almost every graph of G_{ℓ,θ,γ}(w_{n}) admit an exponential dichotomy, in which the dimension of the stable subspace is exactly d × ℓ(n).

For the case of hubs in distinct regimes, we highlight a bifurcation-type result.

Theorem 3. Given an ensemble G′_{ℓ,θ,γ}(w_{n}), with θ < (3 − \sqrt{5})/2 and γ > (\sqrt{5} − 1)/2, there are constants C̄, c̄ > 0 and an integer N_{0} > 0 such that for any n > N_{0}, if

\frac{c̄}{σ_{i}} < α max_{1≤k≤n} w_{k} < \frac{C̄}{τ_{i}} for some index i < ℓ(n),

then, with probability greater or equal to 1 − n^{−1/2} − 2n^{−1/5}, the coupled equations (7) on a graph of G′_{ℓ,θ,γ}(w_{n}) admit an exponential dichotomy, in which the dimension of the stable space is d × i.

The constants C̄ = C̄(H, η_{0}) and c̄ = c̄(H, max_{i≥1} ∥V_{i}∥) may be explicitly determined (see section 5). If c̄/C̄ < σ_{i}/τ_{i} for all i < ℓ(n), notice that, as α is increased, the system exhibits a cascade of bifurcations, characterized by the increasing of the dimension of the stable subspace of solutions. For an illustration, suppose that the elements of the problem are chosen so that c̄ < C̄. In this case, we may assume σ_{i} = τ_{i}. Note that σ_{i−1} and σ_{i} control then the proportion of the hub i has with respect to the main hub:

σ_{i} max_{1≤k≤n} w_{k} < w_{i} < σ_{i−1} max_{1≤k≤n} w_{k}

for n large enough. We assume in addition that c̄/C̄ = σ_{i}/σ_{i−1} for all i. Thus, for the coupling constant α = α_{0}/ max_{1≤k≤n} w_{k}, the inequalities

c̄ < α_{0}σ_{i} < C̄

imply that, on almost every graph of G′_{ℓ,θ,γ}(w_{n}), the coupled equations (7) admit an exponential dichotomy, in which the dimension of the stable space is d × i. Besides, as α_{0} is increased, the global bifurcation occurs from the transition of an interval control condition

α_{0}σ_{i+1} < c̄ < α_{0}σ_{i} < C̄ < α_{0}σ_{i−1}

to the next one

α_{0}σ_{i+2} < c̄ < α_{0}σ_{i+1} < C̄ < α_{0}σ_{i}.

We conclude this section describing the main ideas of the proof of theorem 1. Its proof will be given in section 4. In section 5, we point out which minor changes have to be made in order to prove theorem 3.

Strategy of the proof of theorem 1. We rewrite the block form (7) of the coupled equations as

Ẋ = [V (t) − αD ⊗ H]X + α(A ⊗ H)X,

where D = diag(κ_{1}, …, κ_{n}) is the matrix of degrees. Our strategy is to obtain the existence of dichotomies by persistence arguments. Essentially, the proof consists of three steps:

i) Notice that the ensemble of random graphs has concentration properties: the actual degrees κ_{i}’s are almost surely described by the expected degrees w_{i}’s.

ii) Treat α(A ⊗ H) as a perturbation. Using the block form of

Ẏ = ( \begin{matrix}V_{1}(t) − ακ_{1}H & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & V_{n}(t) − ακ_{n}H \end{matrix} ) Y

together with the concentration properties of the degrees and scale separation [H2] of the ensemble G_{ℓ,θ,γ}(w_{n}), we prove that, for a suitable coupling strength α, the first ℓ(n) blocks associated with the highly connected nodes are exponentially stable whereas the remaining ones are unstable.

iii) Include the term α(A ⊗ H) and use persistence of dichotomies. The challenge here is to proof that this coupling term is small. We use the concentration properties of G_{ℓ,θ,γ}(w_{n}) and the additional conditions on the parameters scale separation γ and cardinality of hubs θ to show that, in the limit of large graphs, α∥A ⊗ H∥ can be made arbitrary small with respect to the dichotomy parameters. Then, we apply the persistence of exponential dichotomies to obtain the persistence of the stable subspace of solutions.

4 Proof of Theorem 1

Before providing the details of the proof, we need some auxiliary results. We group them according to the research domain.

4.1 Random Graphs

We start estimating the actual degrees with respect to the expected degrees. The next result will be very useful in such an analysis. For a proof, see the demonstration of lemma 5.7 in [6].

Proposition 4. Graphs in an ensemble G(w_{n}) have degree concentration property in the sense that:

ℙ[|κ_{i} − w_{i}| ≤ 2\sqrt{log n}\sqrt{max\{w_{i}, log n\}} ∀ i = 1, …, n] ≥ 1 − 2n^{−1/5}.

In particular, if log n/ min_{1≤k≤n} w_{k} tends to zero as n goes to infinity, then

κ_{i} = w_{i} [1 + o(1)] , ∀ i = 1, …, n,

holds almost surely.

The previous degree concentration property allows us to highlight interesting facts.

Corollary 5. For graphs in a strongly heterogeneous ensemble G_{ℓ,θ,γ}(w_{n}), whenever n is sufficiently large, the probability of the event

max_{ℓ(n)<i≤n} κ_{i} < \frac{3}{2}Γ_{2}( max_{1≤k≤n} w_{k})^{1−γ} and min_{1≤i≤ℓ(n)} κ_{i} > \frac{1}{2}c_{0} max_{1≤k≤n} w_{k}

is at least 1 − 2n^{−1/5}.

Proof. Thanks to the previous proposition, from hypothesis [H2], for n sufficiently large, the probability of the event

κ_{i} ≤ w_{i}(1 + 2\sqrt{\frac{log n}{w_{i}}}) < Γ_{2}( max_{1≤k≤n} w_{k})^{1−γ}(1 + \frac{2}{\sqrt{Γ_{1}(log n)^{β}}} ), ∀ i = ℓ(n) + 1, …, n,

is greater or equal to 1 − 2n^{−1/5}. Moreover, hypothesis [H1] guarantees that, for n large enough, the event

κ_{i} ≥ w_{i}(1 − 2\sqrt{\frac{log n}{w_{i}}}) > c_{0} max_{1≤k≤n} w_{k} (1 − \frac{2}{\sqrt{Γ_{1}(log n)^{β}}} ), ∀ i = 1, …, ℓ(n),

occurs simultaneously with at least the same probability.

The proof of the next corollary is similar and will be omitted.

Corollary 6. For graphs in a strongly heterogeneous ensemble with hubs in distinct regimes G′_{ℓ,θ,γ}(w_{n}), if n is large enough, then the event

max_{j<i≤n} κ_{i} < \frac{3}{2}τ_{j} max_{1≤k≤n} w_{k} and min_{1≤i≤j} κ_{i} > \frac{1}{2}σ_{j} max_{1≤k≤n} w_{k}, j < ℓ(n),

occurs with probability at least 1 − 2n^{−1/5}.

Given a sequence of expected degrees w_{n} = (w_{1}, …, w_{n}), the second-order average degree is given by

Δ := \frac{∑_{k=1}^{n} w_{k}^{2}}{∑_{k=1}^{n} w_{k}} .

This constant plays an important role for the characterization of the ensemble G(w_{n}).

Proposition 7. Suppose that the largest expected degree satisfies max_{1≤k≤n} w_{k} ≥ log n. Let λ_{max} denote the largest eigenvalue of the adjacency matrix associated with a random graph in G(w_{n}). Then, the probability of the event

λ_{max} ≤ Δ + \frac{3}{2}\sqrt{log n max_{1≤k≤n} w_{k}} + \sqrt{\frac{1}{4} log n max_{1≤k≤n} w_{k} + 3(Δ + log n)\sqrt{log n max_{1≤k≤n} w_{k}}}

is greater or equal to 1 − n^{−1/2}.

Proof. This result is actually a minor modification of lemma 3.2 in [16]. Just repeat the same proof there using

a = \frac{1}{2}\sqrt{log n max_{1≤k≤n} w_{k}} + \sqrt{\frac{1}{4} log n max_{1≤k≤n} w_{k} + 3(Δ + log n)\sqrt{log n max_{1≤k≤n} w_{k}}}.

The previous proposition leads to an important result on the control of the normalized perturbation size for heterogeneous graphs. The following statement will be of fundamental importance for us.

Proposition 8. Consider a strongly heterogeneous ensemble G_{ℓ,θ,γ}(w_{n}) with θ < δ/2 < (3 − \sqrt{5})/2 and γ > 1 − δ/2 > (\sqrt{5} − 1)/2, where δ ≥ 3/4. Then, for n large enough, with probability at least 1−n^{−1/2}, the largest eigenvalue λ_{max} of the adjacency matrix associated with a random graph in G_{ℓ,θ,γ}(w_{n}) verifies

λ_{max} ≤ 5( max_{1≤k≤n} w_{k})^{δ}.

Proof. Assuming strong heterogeneity as above, we first show that

Δ < ( max_{1≤k≤n} w_{k})^{δ}  (8)

for n large enough. Notice that, from (5) and hypotheses [H0] and [H2], we have

( max_{1≤k≤n} w_{k})^{2} < Γ_{0}( max_{1≤k≤n} w_{k})^{1+θ} + Γ_{2} n( max_{1≤k≤n} w_{k})^{1−γ}.

Since θ < 1, for n large enough, we obtain that

( max_{1≤k≤n} w_{k})^{2} < 2Γ_{2} n( max_{1≤k≤n} w_{k})^{1−γ}.

Using again hypotheses [H0] and [H2], for n sufficiently large, we get

∑_{k=1}^{n} w_{k} > n  and  ∑_{k=1}^{n} w_{k}^{2} < Γ_{0}( max_{1≤k≤n} w_{k})^{2+θ} + Γ_{2}^{2} n( max_{1≤k≤n} w_{k})^{2−2γ},

so that

Δ < Γ_{0} \frac{1}{n}( max_{1≤k≤n} w_{k})^{2+θ} + Γ_{2}^{2}( max_{1≤k≤n} w_{k})^{2−2γ}.

Hence, for n large enough,

Δ < 2Γ_{0}Γ_{2}( max_{1≤k≤n} w_{k})^{1+θ−γ} + Γ_{2}^{2}( max_{1≤k≤n} w_{k})^{2−2γ}

and the desired inequality follows from the choice of the parameters θ and γ.

Note now that, when γ ≥ 1/2, clearly log n < (Γ_{1}/Γ_{2})^{\frac{1}{2(1−γ)}} ( log n)^{\frac{1+β}{2(1−γ)}} for n large enough. Thus, from hypothesis [H2], it follows that

log n < \sqrt{max_{1≤k≤n} w_{k}}  (9)

for n sufficiently large.

From inequalities (8) and (9), and from the fact that δ ≥ 3/4, it is easy to deduce for n large enough

Δ + \frac{3}{2}\sqrt{log n max_{1≤k≤n} w_{k}} + \sqrt{\frac{1}{4} log n max_{1≤k≤n} w_{k} + 3(Δ + log n)\sqrt{log n max_{1≤k≤n} w_{k}}} ≤

≤ 5( max_{1≤k≤n} w_{k})^{δ}.

Therefore, the result follows from proposition 7.

4.2 Exponential Dichotomies

One of the most important properties of exponential dichotomies is their roughness. In clear terms, they are not destroyed by small perturbations on the matrix entries. Our proof relies on this persistence. Therefore, for completeness we state the following result. A proof can be found in [13].

Lemma 9. Suppose that the linear differential equation (3) admits an exponential dichotomy (4) on ℝ_{+}. If

δ := sup_{t∈ℝ_{+}} ∥B(t)∥ < \frac{η}{4K^{2}} ,

then the perturbed equation

ẏ = [V (t) + B(t)]y

has a similar exponential dichotomy in the sense that: there exist a constant K̂ > 0 and a projector P̂, which preserves the rank of the original projector P and commutes with the evolution operator T̂ associated with the perturbed equation, such that, for t ≥ s ≥ 0,

∥T̂(t, s)P̂(s)∥ ≤ K̂e^{−(η−2Kδ)(t−s)} and ∥T̂^{−1}(t, s)(I_{d} − P̂)(t)∥ ≤ K̂e^{−(η−2Kδ)(t−s)}.

The next propositions will be important in our proof.

Proposition 10. Consider the equation

ẏ = [V (t) − αH]y,  (10)

where H is a positive-definite matrix. Let T̂ be the associated evolution operator. Then, there exist a constant K̂_{H} > 0 that only depends on H such that

∥T̂(t, s)∥ ≤ K̂_{H}e^{−(αλ_{H}−K̂_{H}∥V ∥)(t−s)}, ∀ t ≥ s,

where λ_{H} > 0 is the smallest eigenvalue of H.

Proof. First we solve ẋ = −αHx. Clearly, in this case T (t, s) = e^{−α(t−s)H} is the associated evolution operator. Notice that there is a positive constant K̂_{H} such that ∥T (t, s)∥ ≤ K̂_{H} exp[−αλ_{H}(t − s)] for all t ≥ s, where λ_{H} > 0 is the smallest eigenvalue of H. For the full equation (10), the variation-of-constants formula yields

T̂(t, s) − T (t, s) = ∫_{s}^{t} T (t, τ)V (τ)T̂(τ, s) dτ.

Hence, we obtain

∥T̂(t, s)∥ ≤ K̂_{H}e^{−αλ_{H}(t−s)} + K̂_{H} ∫_{s}^{t} e^{−αλ_{H}(t−τ)} ∥V (τ)∥ ∥T̂(τ, s)∥ dτ.

Now introducing ω_{s,t}(u) = ω(u) = ∥T̂(u, s)∥ exp[−αλ_{H}(t − u)], we have

ω(t) ≤ K̂_{H}ω(s) + K̂_{H}∥V ∥ ∫_{s}^{t} ω(τ) dτ.

Using a Gronwall estimate, we conclude that

∥T̂(t, s)∥ ≤ K̂_{H}e^{−(αλ_{H}−K̂_{H}∥V ∥)(t−s)}.

Proposition 11. For the equation ẋ = V (t)x, suppose that the associated evolution operator T verifies ∥T^{−1}(t, s)∥ ≤ Ke^{−η(t−s)} for all t ≥ s. Then, the perturbed equation

ẏ = [V (t) + H]y

admits an evolution operator T̂ satisfying

∥T̂^{−1}(t, s)∥ ≤ Ke^{−(η−K∥H∥)(t−s)}, ∀ t ≥ s.

Proof. Notice that the respective evolution operators verify the following partial differential equations

∂_{t}T^{−1}(t, s) = −T^{−1}(t, s)V (t)  and  ∂_{t}T̂^{−1}(t, s) = −T̂^{−1}(t, s)[V (t) + H].

Using variation of constants, we then obtain

T̂^{−1}(t, s) − T^{−1}(t, s) = ∫_{s}^{t} T̂^{−1}(τ, s)[−H]T^{−1}(t, τ) dτ.

Hence, by the triangle inequality, we have

∥T̂^{−1}(t, s)∥ ≤ Ke^{−η(t−s)} + K∥H∥ ∫_{s}^{t} ∥T̂^{−1}(τ, s)∥e^{−η(t−τ)} dτ.

Following the same steps as in the previous proposition, now with ω_{s,t}(u) = ω(u) = ∥T̂^{−1}(u, s)∥ exp[−η(t − u)], we obtain the result.

4.3 The Proof

We follow the strategy presented at the end of section 3.

Proof of Theorem 1.

Step i. – In corollary 5, we have already established in a precise way how the prescribed expected degrees w_{i}’s almost surely determine actual degrees κ_{i}’s.

Step ii. – We can rewrite the equation (7) as follows

Ẋ = [Ω(t, α) + αA ⊗ H]X,  (11)

where Ω(t, α) := ⨁_{i=1}^{n} [V_{i}(t) − ακ_{i}H]. Now consider the system

Ẏ = Ω(t, α)Y.  (12)

Since the system is block diagonal, we can solve each block independently. Let

T̂(t, s) = ⨁_{i=1}^{n} T̂_{i}(t, s)

be the associated evolution operator. On the one hand, applying proposition 10 to the first ℓ(n) blocks, we conclude that

∥T̂_{i}(t, s)∥ ≤ K̂_{H} exp [ − (αλ_{H} min_{1≤i≤ℓ(n)} κ_{i} − K̂_{H} max_{1≤i≤ℓ(n)} ∥V_{i}∥)(t − s)], ∀ 1 ≤ i ≤ ℓ(n).

Recall that by hypothesis max_{i≥1} ∥V_{i}∥ < +∞. On the other hand, proposition 11 shows that the remaining blocks will verify

∥T̂_{i}^{−1}(t, s)∥ ≤ K_{0} exp [ − (η_{0} − α∥H∥ max_{ℓ(n)<i≤n} κ_{i})(t − s)], ∀ ℓ(n) < i ≤ n,

where η_{0} and K_{0} are the universal constants introduced in (6). These observations lead us to consider the operator T̂(t, s) associated with equation (12) in a block form with respect to the direct sum ℝ^{d×ℓ(n)} ⊕ ℝ^{d×(n−ℓ(n))}, namely

T̂(t, s) = ( \begin{matrix}S(t, s) & 0 \\ 0 & U(t, s) \end{matrix} ) ,

as well as the natural projectors

P̂ = ( \begin{matrix}I_{d} & 0 \\ 0 & 0 \end{matrix} )  and  Id − P̂ = ( \begin{matrix}0 & 0 \\ 0 & I_{d} \end{matrix} ) .

Since the operator norm induced by the Euclidean norm has the property

∥T̂(t, s)∥ = max_{1≤i≤n} ∥T̂_{i}(t, s)∥ and ∥T̂^{−1}(t, s)∥ = max_{1≤i≤n} ∥T̂_{i}^{−1}(t, s)∥,

in order to characterize an exponential dichotomy, the contraction rates for stable and unstable directions must satisfy

α min_{1≤i≤ℓ(n)} κ_{i} > \frac{K̂_{H} max_{i≥1} ∥V_{i}∥}{λ_{H}}  and  α max_{ℓ(n)<i≤n} κ_{i} < \frac{η_{0}}{∥H∥}.  (13)

Suppose from now on that n is large enough so that

( max_{1≤k≤n} w_{k})^{γ} > ( log n)^{γ} > \frac{12Γ_{2}∥H∥K̂_{H} max_{i≥1} ∥V_{i}∥}{c_{0}η_{0}λ_{H}}.

Thus, defining

c := \frac{4K̂_{H} max_{i≥1} ∥V_{i}∥}{c_{0}λ_{H}}  and  C := \frac{η_{0}}{3Γ_{2}∥H∥},

let α > 0 be such that

c < α max_{1≤k≤n} w_{k} < C( log n)^{γ}.

Notice now that

\frac{c}{2} < α max_{1≤k≤n} w_{k} ⇒ \frac{1}{2}αc_{0} max_{1≤k≤n} w_{k} > \frac{K̂_{H} max_{i≥1} ∥V_{i}∥}{λ_{H}},
α max_{1≤k≤n} w_{k} < 2C( max_{1≤k≤n} w_{k})^{γ} ⇒ \frac{3}{2}αΓ_{2}( max_{1≤k≤n} w_{k})^{1−γ} < \frac{η_{0}}{∥H∥}.

Therefore, from corollary 5, for n sufficiently large, we conclude that the event (13) occurs with probability at least 1 − 2n^{−1/5}. With the same estimate for the probability, equation (12) admits thus an exponential dichotomy with constants

K̂ = max{K̂_{H}, K_{0}}  and
η̂ = min \{\frac{1}{2}λ_{H}c_{0}α max_{1≤k≤n} w_{k} − K̂_{H} max_{i≥1} ∥V_{i}∥, η_{0} − \frac{3}{2}∥H∥Γ_{2}α( max_{1≤k≤n} w_{k})^{1−γ}\}.

Step iii. – Now we wish to incorporate back the perturbation αA ⊗ H. Notice that ∥αA ⊗ H∥ ≤ α∥A∥∥H∥. Moreover, since A is a real symmetric matrix, ∥A∥ = λ_{max}. Thus, in order to apply lemma 9, we need to estimate the probability of the event αλ_{max} < Λ, where

Λ := \frac{1}{4K̂^{2}} min \{\frac{1}{2} \frac{λ_{H}}{∥H∥}c_{0}α max_{1≤k≤n} w_{k} − \frac{K̂_{H}}{∥H∥} max_{i≥1} ∥V_{i}∥, \frac{η_{0}}{∥H∥} − \frac{3}{2}Γ_{2}α( max_{1≤k≤n} w_{k})^{1−γ}\}

> \frac{1}{4K̂^{2}} min \{\frac{K̂_{H}}{∥H∥} max_{i≥1} ∥V_{i}∥, \frac{1}{2} \frac{η_{0}}{∥H∥}\} > 0.

Thanks to proposition 8, with probability at least 1 − n^{−1/2},

αλ_{max} ≤ 5α( max_{1≤k≤n} w_{k})^{δ}, where \frac{3}{4} ≤ δ < 3 − \sqrt{5}.

Using the definition of α and hypothesis [H2], notice then that

5α( max_{1≤k≤n} w_{k})^{δ} < 5C \frac{Γ_{2}^{γ}}{Γ_{1}^{γ}} ( max_{1≤k≤n} w_{k})^{γ−γ^{2}+δ−1}.

By hypothesis γ > 1 − δ/2. Hence,

( max_{1≤k≤n} w_{k})^{γ−γ^{2}+δ−1} ≤ ( max_{1≤k≤n} w_{k})^{− \frac{δ^{2}−6δ+4}{4}}

tends to zero as n goes to infinity, which concludes the proof.

5 Comments on the Proof of Theorem 3

The proof of theorem 3 follows the same lines of the previous one. Corollary 6 provides us now the first step. Moreover, the last step is exactly as before, only with a convenient η̂ as described below.

Concerning the second step, the set of arguments remains unchanged. However, one first introduces constants

c̄:= \frac{3K̂_{H} max_{i≥1} ∥V_{i}∥}{λ_{H}}  and  C̄ := \frac{η_{0}}{2∥H∥}.

Note that, if c̄/C̄ < σ_{j}/τ_{j} for some j < ℓ(n), then, for all n, it will be possible to consider a suitable parameter α > 0 as in the statement. Applying proposition 10 to the first j blocks and proposition 11 to the remaining ones, one has thus to estimate the probability of the event

α min_{1≤i≤j} κ_{i} > \frac{K̂_{H} max_{i≥1} ∥V_{i}∥}{λ_{H}}  and  α max_{j<i≤n} κ_{i} < \frac{η_{0}}{∥H∥}.  (14)

Corollary 6 and the fact that

\frac{3}{2}ατ_{j} max_{1≤k≤n} w_{k} < 2C̄  and  \frac{1}{2}ασ_{j} max_{1≤k≤n} w_{k} > \frac{c̄}{3}

show that (14) occurs with probability at least 1 − 2n^{−1/5}. Hence, exponential dichotomy is found with this estimated probability, being now

η̂ = min \{\frac{1}{2}ασ_{j} max_{1≤k≤n} w_{k} − \frac{c̄}{3}, 2C̄ − \frac{3}{2}ατ_{j} max_{1≤k≤n} w_{k}\} > min \{\frac{c̄}{6}, \frac{C̄}{2} \} > 0.

References

[1] A. Barrat, M. Barthélemi and A. Vespegnani, Dynamical processes on complex networks, Cambridge University Press (2008).

[2] J. R. Chazottes and B. Fernandez (eds.), Dynamics of coupled map lattices and of related spatially extended systems, Lecture Notes Physics 671, Springer (2005).

[3] J. Koiller and L. S. Young, Coupled map networks, Nonlinearity 23, 1121 (2010).

[4] M. Newman, Networks: an introduction, Oxford University Press (2010).

[5] B. Bollobás, Random graphs, 2nd edition, Cambridge University Press (2001).

[6] F. Chung and L. Lu, Complex graphs and networks, CBMS Regional Conference Series in Mathematics 107, American Mathematical Society (2006).

[7] E. Bullmore and O. Sporns, Complex brain networks: graph theoretical analysis of structural and functional systems, Nature Reviews Neuroscience 10, 186 (2009).

[8] V. M. Eguíluz et al., Scale-free brain functional networks, Physical Review Letters 94, 018102 (2005).

[9] T. Pereira, Hub synchronization in scale-free networks, Physical Review E 82, 036201 (2010).

[10] M. Barahona and L. M. Pecora, Synchronization in small-world systems, Physical Review Letters 89, 054101 (2002).

[11] T. Pereira, J. Eldering, M. Rasmussen and A. Veneziani, Towards a theory for diffusive coupling functions allowing persistent synchronization, Nonlinearity 27, 501 (2014).

[12] A. Arenas et al., Synchronization in complex networks, Physics Reports 469, 93 (2008)

[13] W. A. Coppel, Dichotomies in stability theory, Lecture Notes in Mathematics 629, Springer-Verlag (1978).

[14] P. E. Kloeden and M. Rasmussen, Nonautonomous dynamical systems, Mathematical Surveys and Monographs 176, American Mathematical Society (2011).

[15] G. H. Golub and C. F. Van Loan, Matrix Computations, 4th edition, Johns Hopkins University Press (2012).

[16] F. Chung, L. Lu and V. Vu, Eigenvalues of random power law graphs, Annals of Combinatorics 7, 21 (2003).