IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS

1

Asymptotic Network Robustness

arXiv:1712.05273v2 [] 1 Jan 2018

T. Sarkar, M. Roozbehani, M. A. Dahleh

Abstract—This paper examines the dependence of performance measures on network size with a focus on large networks. We develop a framework where it is shown that poor
performance can be attributed to dimension–dependent scaling
of network energy. Drawing from previous work, we show
that such scaling in undirected networks can be attributed
to the proximity of network spectrum to unity, or distance
to instability. However, such a simple characterization does
not exist for the case of directed networks. In fact, we show
that any arbitrary scaling can be achieved for a fixed distance
to instability. The results here demonstrate that it is always
favorable, in terms of performance scaling, to balance a large
network. This justifies a popular observation that undirected
networks generally perform better. We show the relationship
between network energy and performance measures, such as
output shortfall probability or centrality, that are used in
economic or financial networks. The strong connection between
them explains why a network topology behaves qualitatively
similar under different performance measures. Our results
suggest that there is a need to study performance degradation
in large networks that focus on topological dependence and
transcend application specific analyses.

I. I NTRODUCTION
Networks have been successfully used to model many real
world phenomena appearing in fields such as economics,
transportation and social sciences. These networks are characterized by the nature of interconnections, or topology, and
dimension, which is typically very large. Due to the preponderance of such networks, there is extensive literature on
suitable performance measures and their behavior on different
topologies. However, the idea of a “suitable” performance
measure, as we discuss below, varies across applications. A
major objective of this paper is to understand the underlying
relationship between existing performance measures for large
networks.
There is a substantial body of interdisciplinary research
to find appropriate performance measures for large interconnected networks with stable dynamics and understand the
underlying causes of dimension dependent scaling of these
measures (See [1], [2], [3], [4] and [5] for example). A
commonly used performance measure for design of optimal
controllers is the H2 –norm. Specifically, Lin et. al. in [6]
study the design of structured controllers for vehicular platoons with minimum H2 –norm. It is observed there that optimal structured controllers with asymmetric feedback exhibit
lower scaling (of H2 –norm) with the number of vehicles than
its symmetric counterpart and performs better in that sense.
On the other hand, [2], [4] study the dependence of H2 –norm
on structural properties of the network such as edge weights
T. Sarkar, M. Roozbehani, M. A. Dahleh are with the EECS Department,
Massachusetts Institute of Technology, Cambridge, MA 02139 USA (e-mail:
tsarkar, mardavij, dahleh@mit.edu).

and underlying graph spectrum. Huang et. al. study H2 –norm
based volatility measures in undirected (symmetric) and stable network, where the volatility measure can be represented
completely by the network spectrum. The scaling of H2 –
norm for different network topologies such as ring, star and
cycle along with the effect of nodal degree perturbation and
the consequent problem of critical edge identification are also
studied there. Another important performance measure for
vehicular platoon networks is the H8 –norm. The notion of
harmonic instability, i.e., exponential scaling of H8 –norm
in vehicular platoons is studied in [3]. Herman et. al. study
network topologies where a shock on the leader vehicle of a
stable platoon network is magnified exponentially in its size.
Due to this exponential scaling, control of such a network
becomes increasingly problematic as its dimension grows.
A seemingly different performance measure than the system norms discussed before is studied in [1], [7]. Acemoglu
et. al. introduce a measure called tail risk to assess performance in economic production networks. Tail risk measures
the probability of output falling below a certain threshold in
response to an input shock. A key feature of tail risk is that
it can manifest only in networks with large dimension, and
hence captures the idea of performance degradation when
network size increases perfectly. A major conclusion of their
work is that some amount of balancedness is needed in a
large network to exhibit no tail risk.
In control systems theory robust stability, with no structural
constraints on the feedback, is well understood (See [8] for
details). Robust stability entails the study of controllers that
provide internal stability to all networks (or plants) in a
given set. This is particularly useful in the case when there
is some uncertainty about the network, such as unknown
edge weights etc. The notion of “network robustness” that
we discuss here is different from traditional robust stability.
We focus on large and deterministic networks with stable dynamics where we study the behavior of suitable finite valued
performance measures. Specifically, we are interested in the
scaling of these measures as a function of network dimension.
We study the underlying causes of this scaling and find
conditions under which it can be attributed to the proximity
of network spectrum to unity. This introduces the idea of
asymptotic instability which is characterized by the spectral
radius approaching unity as network size increases, for a
given topology. We will study the dependence of performance
scaling on asymptotic instability and show when it does
not completely explain such scaling. We will observe that
excessive scaling in performance measures are closely related
to notions of criticality, centrality and robustness in graphs,
that are well studied in algebraic graph theory. However, there
the graphs considered are “static” (no associated dynamics)

2

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS

or at equilibrium conditions. Real life networks, on the other
hand, are characterized by their associated topology along
with their complex interconnections and system dynamics.
Therefore, a simultaneous consideration of control and graph
theoretic tools is necessary for the design of robust networks,
where performance measure scales gracefully with network
size.
Although there is a myriad of techniques to assess performance in large networks it is not clear if there exists
some connection between them. For example it is shown
by Acemoglu et. al. that balanced networks exhibit no tail
risk; on the other hand Lin et. al. show that symmetric
networks (a subclass of balanced networks) do not perform
optimally. The dichotomy of these results is surprising since
the underlying dynamics are similar. A major contribution of
this work is that we provide a general framework to analyze
these seemingly disparate results. We also find optimal (in an
appropriate sense) topologies, where performance measures
scale gracefully as network size increases.
The presentation of the paper is as follows, we introduce
some mathematical notation in Section II. In Section III we
present the mathematical preliminaries required to understand
the paper. We formalize the notion of large networks used in
this paper and describe the network topologies that will be
discussed throughout the paper. Following this, in Section IV
we formally define network robustness in large networks. We
completely characterize this for undirected (symmetric) networks and prove that such a characterization does not extend
to directed networks. Through these observations, we show
that undirected topologies exhibit the most graceful scaling
for a fixed spectral radius. We establish connections between
network robustness and different performance measures used
in economics, transportation and finance in Section V. The
main results of the paper can be found in Sections IV, V.
Finally, we conclude in Section VI. All proofs are in the
appendix.
II. M ATHEMATICAL N OTATION
Matrix Theory: A vector v P Rnˆ1 is of the form
rv1 , . . . , vn sT , where vi denotes the ith element, unless specified otherwise. The vector 1 is the all 1s vector of appropriate
dimension; to specify the dimension we sometimes refer to
it as 1n , where it is a n ˆ 1 vector. Similarly, for a m ˆ n
matrix, A, we refer to it as Amˆn when we want to specify
dimension. We denote A that is a nˆn matrix as An for short
hand. For a matrix, A, we denote by ρpAq its spectral radius,
and by ρi pAq the ith largest eigenvalue of A (in absolute
value sense). Thus, ρ1 pAq “ ρpAq. We have a similar
notation for the singular values of A denoted by σi pAq. I is
the identity matrix of appropriate dimension. The Lp norm
of a matrix, A, is given by ||A||pÑq “ supv ||Av||q {||v||p
and ||A||p is shorthand
řnfor ||A||pÑp . ||A||S is the Schatten
norm, i.e., ||A||S “ i“1 σi pAq. For positive semidefinite
matrices the Schatten norm equals the trace of the matrix.
Order Notation: For functions, f p¨q, gp¨q, we have f pnq “
Opgpnqq, when there exist constants C, n0 such that f pnq ď
Cgpnq for all n P N ą n0 . Further, if f pnq “ Opgpnqq,

then gpnq “ Ωpf pnqq. For functions gp¨q, hp¨q, we have
gpnq “ Θphpnqq when there exist constants C1 , C2 , n1 such
that C1 hpnq ď gpnq ď C2 hpnq for all n P N ą n1 . Finally,
for functions h1 p¨q, h2 p¨q, we have h1 pnq “ oph2 pnqq when
limnÑ8 |h1 pnq{h2 pnq| “ 0.
Graph Theory: A graph is the tuple G “ pVG , EG , wG q,
where VG “ tv1 , v2 , . . . , vn u represents the set of nodes and
EG Ď VG ˆ VG represents the set of edges or communication
links. An edge or link from node i to node j is denoted
by eri, js “ pvi , vj q P EG , and wG : EG Ñ R. Denote by
AG the incidence matrix of G. A graph, G, is symmetric or
undirected if wG pvi , vj q “ wG pvi , vj q for all 1 ď i, j ď |VG |.
G is induced by a matrix, Anˆn if VG “ t1, . . . , nu, and
pi, jq P EG if rAsij ‰ 0, and wG pi, jq “ rAsij .
Miscellaneous: Denote by Pd is the family of polynomials
with maximum degree d P N.
III. P RELIMINARIES
Consider the following discrete time LTI dynamics:
xpk ` 1q “ A xpkq ` ω δp0, kq, k P t0, 1, 2, . . .u
(1)
T
Here xpkq “ rx1 pkq, . . . , xn pkqs is the vector of state
variables. A is the n ˆ n state transition matrix. δp0, kq
is the Kronecker delta function, with δp0, 0q “ 1 and
δp0, kq “ 0 @ k ‰ 0 and ω “ rω1 , . . . , ωn sT is exogenous to
the system. We further assume that xp0q “ 0. Additionally,
we have the following assumptions
Assumption 1. The network matrix A is Schur stable, i.e.,
ρpAq ă 1.
Assumption 2. ω is an n ˆ 1 random vector with Erωω T s “
Inˆn and Erωs “ 0.
Assumption 1 is a stability assumption on the network
dynamics that will be enforced on all networks in this work,
unless otherwise stated.
Definition 1. A signal, wpkq, is a shock if wpkq “ 0 for all
k ą 0 but wp0q ‰ 0.
Then wpkq “ ωδp0, kq is a shock.
Definition 2. A network, N pA; Gq, is a graph G “
pVG , EG , wG q, where VG “ t1, 2, . . . , nu, and for each node,
i P VG , there is an associated dynamical behavior, i Ñ xi p¨q.
Further, wG pi, jq “ rAsij for all 1 ď i, j ď n.
In this work, we will focus on networks with linear
dynamics given by Eq. (1).
!n1

!n4
xn1

xn4

xn2

!n5
xn5

!n2

!n3

xnn
xn3
k=0

!nn

Fig. 1: Network with noise on every node, k “ 0
The key feature of our work is that we address large
networks. We denote a large network by “a sequence of

ASYMPTOTIC NETWORK ROBUSTNESS

3

networks with network matrices tAn u8
n“1 , where the topology of each network in the sequence is fixed but network
dimension grows successively”. This treatment is along the
lines of graph limits as discussed in [9]. For example, to
denote a large star network we define a sequence of star
networks tAn u8
n“1 with dimensions n “ 1, 2, 3, . . . as shown
in Fig. 2. In this example we have
fi
»
1
1
1
. . . n´1
0 n´1
n´1
—1
0
0
...
0 ffi
ffi
—
An “ — .
.
.
.. ffi
.
..
..
..
– ..
. fl
1
0
0
...
0
A formal discussion on network sequences can be found
in Section VII-A. From here on, whenever we use “sequence
of networks” we will mean a “large” network.

Fig. 2: Sequence of Star Networks
A mathematical quantity that will play an important role
in the discussion of performance scaling is the (identity)
gramian that we define below.
Definition 3. The (identity) gramian of a stable matrix, A,
is given by P pAq, or, P , where P “ AT P A ` I.
Throughout this paper we will discuss robustness properties of some commonly encountered networks. We summarize them below.
Networks with degree normalization
These networks are of the form An “ γDn´1 An where Dn
is the degree matrix, An is the incidence matrix of An and
0 ă γ ă 1. Edges with arrow are directed edges. We will

Regular

Star

Cycle

Directed Line

Fig. 3: Different Network Topologies
refer to the regular, star, cycle, directed line degree networks
as Rn , Sn , Cn , DLn respectively.
Network with loops
The topology in Fig. 4 appears frequently in transportation
networks as vehicular platoons. The values of λi , i are
chosen to ensure Schur stability of the network.

Fig. 4: Network Gn
IV. ROBUSTNESS IN L ARGE N ETWORKS
We start by focusing on undirected large networks and
a commonly used network performance measure, H2 –norm.
We will give a more general definition of robustness later
in this section. Following the work in [4], [10], [11] (and
references therein), we observe that the scaling of H2 –norm
of a network is limited by the proximity of its spectra to
unity.
Proposition 1. (See [12]) For a sequence of undirected
networks, tAn u8
n“1 , define H2 pAn q as the H2 –norm corresponding to the network An . Then we have,
H2 pAn q “ Opn{p1 ´ ρpAn qqq
Proposition 1 is an extension of Proposition 1 in [4].
According to this, the scaling in the “network volatility” or
H2 –norm of a large network is limited by the proximity of
its spectral radius to unity. The natural question to ask is if
there exists a similar characterization of scaling in directed
networks.
Proposition 2. For the large network Gn with i “ 1 and
δ1 ă λi ă δ2 for all i and some 0 ă δ1 , δ2 ă 1, we have
that the H2 pGn q is Ωpexp pcnqq and ρpGn q ď δ2 .
Based on Proposition 2, we see that poor scaling of
performance measures, in general networks, cannot not be
attributed to their spectra. In fact, under certain conditions
they might turn out to be independent. With these observations in mind, we propose a more general definition of
robustness. We will later show that this idea of robustness is
also closely related to many standard performance measures
for networks.
Definition 4. A sequence of networks, tN pAn , Gn qu8
n“1 is
robust (in an asymptotic sense) if we have:
‚ Network matrix, An , is stable for each n
‚ tracepP pAn qq “ Opppnqq
Here pp¨q P Pd for some d P N. The smallest such d is
the degree of robustness. Fragility is the lack of robustness
in the sense of super-polynomial or exponential scaling of
tracepP pAn qq for the network matrix sequence tAn u8
n“1 .
Although Definition 4 uses the Schatten norm of gramian
to measure robustness, one should note that a network is
robust even when the L2 –induced norm is polynomial, for
example. Subsequently the idea of robustness in large networks should be extended to polynomial scaling in a broader
class of norms. We call this class the consistent norm set and
define it below.

4

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS

Definition 5. The set of norms, C,
C “ t|| ¨ || : pppnqq´1 ||An ||S ď ||An || ď

We will refer to EpAq as the average disruption energy of
N pA; Gq.

ppnq||An ||S u
řn
where pp¨q P Pd for some d P N and ||A||S “ i“1 σi pAq.
The set C is called the consistent norm set.

Proposition 3. (See [12]) The max norm, MpAq, is
σ1 pP pAqq, and the average norm, EpAq, is p1{nqtrpP pAqq.

Examples of some norms in the consistent norm set are Lp
induced norms of An (for p ě 1), but exp pnq||An ||p will not
lie in the consistent norm set although it is a valid norm on
An . We can now define a robustness measure for a network
in terms of its gramian and the consistent norm set.
Definition 6. A robustness measure for a large network An
is the pair p||¨||, P pAn qq where ||¨|| is in the consistent norm
set.
A trivial conclusion of Definition 4 and 5 is that a large
network is robust if ||P pAn q|| “ Opppnqq for any robustness
measure p|| ¨ ||, P pAn qq. Robustness by itself may not ensure
good performance in some applications. As we show later,
such cases often require a constraint on the degree of robustness. The motivation behind introducing the consistent norm
set will become clear then. Although H2 –norm is a useful
measure to assess large networks, many applications require
specific norms to quantify performance.
V. C ONNECTIONS TO P ERFORMANCE M EASURES
A. Robustness as Network Energy
Here we present a network energy interpretation of robustness. Such a formulation has applications in optimal controller design, for e.g.: finding the topology with minimum
energy. We revisit the network formulation in Fig. 1, with
some state matrix, An . At time k “ 0, each node i is hit
with a shock, ωi , then we are interested in the following
questions T
‚ If ω “ rω1 , . . . , ωn s
is a deterministic shock, with
||ω||2 ď 1, then what is maximum effect of the shock
on the network ?
‚ If ω is a random shock, then what is the effect of the
shock on the network, on average ?
We measure
ř8 the energy of the network by the quantity,
E8 “ k“0 xT pkqxpkq, and without loss of generality we
will assume xp0q “ 0.
Definition 7. Given a network, N pA; Gq, with a stable A,
as in Eqn. (1) and a deterministic shock, ω, at time k “ 0,
to the system, the max norm, MpAq, or just M, is given by:
MpAq “ sup E8

(2)

||ω||2 “1

We will refer to MpAq as the maximum disruption energy of
N pA; Gq.
Definition 8. Given a network, N pA; Gq, with a stable A,
as in Eqn. (1) and a random shock, ω, at time k “ 0, that
satisfies Assumption 2, the average norm, EpAq, or just E, is
defined as the following:
EpAq “ p1{nqEω rE8 s
(3)

MpAq and EpAq represent two different aspects of network robustness which can be best described by the following
proposition.
Proposition 4. For large networks Sn and Rn we have the
following relation, MpSn q “ Θpnq, EpSn q “ Θp1q and
MpRn q “ Θp1q, EpRn q “ Θp1q.
The proof of this proposition can be found in Section VII-B. It turns out that the maximum disruption in Sn is
more than in Rn . This happens because one unit of energy
given to the central node is transferred to every other node at
the next time instant (an amplification of n´1). On the other
hand in Rn only 1{pn´1q energy is transferred to every other
node. However, both have the similar disruption on average
because the probability of picking the central node is 1{n
(assume uniform) and as a result
n
ÿ
EpSn q « p1{nqpn ´ 1q `
p1{nq “ Θp1q
j“2

We revisit the discussion of H2 –norm scaling in different
networks (directed and undirected) from the previous section.
We observe that, whenever possible, making a network more
undirected always results in better performance scaling. First,
we define how to balance a network
Definition 9. Given a large balanced network, An , we define
its –balanced version as
An “ p1 ´ qAn ` γ11T {n
where ρpAn q “ γ.
Proposition 5. For any 0 ă  ă 1, and ρpAn q “ γ ă 1, we
have that
ρpAn q ă 1
Remark 1. It is easy to observe that for an –balanced
version we have that
maxpaji , aij q
maxpaji , aij q
ď
minpaji , aij q
minpaji , aij q
for every pair i, j. Balancing makes a network more undirected.
Theorem 1. For any large network An with ρpAn q “ γ we
have that
EpAn q “ OpEpAn qq, MpAn q “ OpMpAn qq
whenever An is Schur stable and  “ Ωp1q.
Theorem 1 gives us a sense of global and local optimality
of undirected networks in terms of performance scaling. For
the case of  “ 1 it follows that, for a fixed γ, undirected
networks do not perform any worse than directed ones in an
order sense. Now if γ ă 1, then there exists a small enough
 such that ρpAn q ă 1. This follows from the continuity
of characteristic polynomial roots in  (See [13]). Then one
can conclude from Theorem 1 that it is no worse to move

ASYMPTOTIC NETWORK ROBUSTNESS

5

in an undirected fashion “locally”. Although we have shown
that it is favorable to design undirected networks, in many
cases we may be constrained by the problem definition that
moving in the space of undirected networks is not possible.
Even under such conditions we show that the basic principle
of Theorem 1 is not violated.
Scaling in Network Controllers
Here we present more concrete examples from transportation networks to show how robustness scaling manifests in
controllers for vehicular platoons. We consider the vehicular
platoon network discussed in [6]. The closed loop dynamical
system (Eqns.(SS) and (VP2) in [6]) is of the form (discretized single integrator version)
xpk ` 1q ´ xpkq “ ´Kxpkq ` dpkq
(4)
Here K is of» the form
fi
k1 ` k2
´k2
—
ffi
..
— ´k2
ffi
.
k2 ` k3
ffi
K“—
—
ffi
..
..
–
.
.
´kn fl
´kn kn ` kn`1
Here I ´ K is symmetric and xi pkq is the relative position
error for vehicle i. Then we have that
xi pk ` 1q ´ xi pkq “ ki,i´1 pxi´1 pkq ´ xi pkqq
` ki,i`1 pxi`1 pkq ´ xi pkqq
Additionally, ρpI ´ Kq ă 1 for stability. The structure of the
feedback is given in Fig. 5. xi denotes the position of vehicle
i.

k3 (x2 − x3 )

k2 (x1 − x2 )

x1

x2
−k2 (x1 − x2 )

x3

xn

−k3 (x2 − x3 )

Fig. 5: Feedback structure for platoon

Now, the optimal controller design is given by
minimizeK
tracepP q
where

pI ´ K T qP pI ´ Kq ` I “ P

(5)

Proposition 6. The H2 –norm and σ1 pP q of the network
governed by the optimal controller, Ksymmetric , in Eq. (4) are
Ωpn2 q and Ωpnq respectively.
Although the number of nodes in the network are n, we
observe that even the optimal controller gives a Ωpnq per vehicle scaling in the robustness measure. Such a performance
degradation might be harmful when strict control is required.
Next, we consider an asymmetric controller studied in [3]
given by K (0 ď i ď 1)

»
—
—
K “ —
—
–

k1 ` k2 2

´k2 2

´k2

k2 ` k3 3
..
.

fi
..
..

.

.
´kn

´kn n
kn ` kn`1 n`1

ffi
ffi
ffi
ffi
fl

Now, K1 “ Ksymmetric , i.e., the symmetric controller discussed before. On the other extreme is K0 (i “ 0) which
is a purely asymmetric controller. Then for the optimal
asymmetric controller problem we have that

Proposition 7. The H2 –norm of the network governed by
the optimal asymmetric controller, Kasymmetric , in Eq. (4) is
Opn3{2 q.

Propositions 6, 7 suggest that an optimal asymmetric
controller is better than a symmetric one that seems to
contradict our finding in Theorem 1. To resolve this, we
introduce the “scaled” H2 –norm, H2 pAn qp1 ´ ρpAn qq. Since
the term p1´ρpAn qq measures the distance to instability, one
can interpret the scaled H2 –norm as a performance measure
where the effect of distance to instability has been removed. It
is likely that performance degrades as a network approaches
instability, for example consider the extreme case when network dynamics are unstable then there exist no guarantees on
performance even for small networks. The scaled H2 –norm
separates the effect of distance to instability on performance
degradation. Now for the symmetric controller scaled H2 –
norm is Opnq (Proposition 1). Due to the structural constraints on the symmetric feedback, i.e., diagonal elements
equal the sum of corresponding off-diagonal elements and
pI ´ Ksymmetric q be stable, it is not possible for the controlled
network to achieve eigenvalues that are further from unity.
On the other hand, the asymmetric controller that achieves
Opn3{2 q is given by Kasymmetric “ 1{2pInˆn ´ DLn q and
has spectral radius ρpI ´ Kasymmetric q “ 1{2. Here scaled
H2 –norm is Θpn3{2 q which is worse than the symmetric
case. This observation suggests that performance scaling in
the asymmetric controller cannot be attributed to asymptotic
instability (distance to instability vanishes as network size
grows to infinity), unlike the symmetric case. In Fig. 6, we –
balance the asymmetric controller, Kasymmetric , for some small
enough . Specifically, we refer to balancing in Definition 9
as dense balancing. The sparse balancing is when we replace
γ11T {n by Πn “ γInˆn . Observe that claims of Theorem 1
and Remark 1 hold true even for sparse balancing. We call
Πn as sparse balancing since it affects only the diagonal
(local) nodes. We choose  “ 0.01 to ensure that balancing
results in a Schur stable matrix. We observe that –balancing
reduces the H2 –norm which conforms to Theorem 1. It
is also not surprising that dense balancing exhibits better
scaling. However, due to the structural constraints of K , i.e.,
ai,i “ ´i ai,i`1 ´ ai`1,i , it is not possible to significantly
balance the asymmetric controller.

6

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS

Fig. 6: H2 –norm variation of Kasymmetric with dense and
sparse random symmetric perturbations

B. Robustness as a Tail Risk Measure
In Eq. (1) assume that the shock ω „ N p0, Iq, i.e.,
the multivariate standard normal distribution. Define the
aggregate output x8 as
8
ÿ
x8 “
1T xpkq
(6)
k“0

with xp0q “ 0 (for simplicity). In general, xp0q is the predefined output, and the model here captures the deviation from
this value in response to a shock. Then it is easy to check that
x8 is a linear combination of independent standard normal
random variables and hence, Gaussian (See [14]).
? However,
as n increases, for some networks even x8 { n does not
behave like ?
a Gaussian random variable (See Fig. 7). The
tails of x8 { n from the star network Sn becomes wider as
n increases. The reason behind this is that σpx8 q Ñ 8 as
n Ñ 8 for Sn . In this section we show how such scaling in
σpx8 q causes performance degradation.
We assume now that the shock ω in Eq. (1) has exponential
tails, i.e., ωi „ Ep0, 1q, ωi s are i.i.d. and x8 defined as
Eq. (6). Here Epµ, σq1 is a continuous probability distribution, such that
ErXi s “ µ
ErpXi ´ µq2 s “ σ 2
Erexp pbXi qs ă 8, for some b ą 0
We will study the distribution of aggregate output in response
to a shock with a certain p.d.f. Specifically, we focus on
“worst case” analysis of aggregate output and will be interested in the its tail behavior. From the perspective of tail
probability behavior, Epµ, σq is a richer class compared to
the family of Gaussian distributions. At the same time, these
distributions exhibit favorable tail behavior (such as the Large
Deviation Principle [15] etc.) that make them amenable to
1 Example

of Epµ, σq is the standard normal where µ “ 0, σ “ 1

?
Fig. 7: pdf of x8 { n as n increases

analysis. We impose additional assumptions on the class of
networks we consider in this section,
Assumption 3. Network matrix An has the following properties
‚
‚

rAn sij ě 0.
There exists v such that
Av “ λP F v
where vmax {vmin “ Op1q and λP F is the Perron root.

Examples of such networks include networks with degree
normalization introduced in Section III. These fall under the
more general class of networks where An “ γWn and Wn
is row–stochastic. Note that this assumption is weaker than
those required for irreducibility or aperiodicity. For example
the star network, Sn , is neither aperiodic nor irreducible,
however vmax “ vmin in that case. Then we define tail risk
in a network as
Definition 10. For x8 in response to ωi „ Ep0, 1q, define
Rn pzq “ ´p1{nq log pPp|x8 | ą nzqq
Then a large network, tAn u8
n“1 , exhibits no tail risk if there
exists z ą 0 such that limnÑ8 Rn pzq ą 0 for every ω.

ASYMPTOTIC NETWORK ROBUSTNESS

7

Rn p¨q is a measure of how likely it is for the average
aggregate output to fall below a certain threshold ´z in
response to a shock. In this context, a robust large network is
resistant to random shocks, i.e., average output is not affected
too much. Consider the special case when An “ µInˆn .
Then by Cramer’s theorem we have that limnÑ8 Rn pzq ą 0.
Next, when An “ µr1, 1, . . . , 1sT r1, 0, . . . , 0s, i.e., xi pk `
1q “ µx1 pkq, then limnÑ8 Rn pzq “ 0 implying the outputs
are heavily dependent on each other. In large networks, a
graceful decay of “failure” or “shortfall” probability with
network dimension is ideal. Rn p¨q captures this notion of
risk in networks – the more dependent individual components
become, more likely the failure. Another measure of risk
introduced by Acemoglu et. al. involves comparing the tail
distribution of the aggregate output to that of the standard
normal. We will argue later that these notions of tail risk are
closely related to centrality in networks as discussed in [16].
Definition 11. Random variable z exhibits tail risk relative
to standard normal distribution if limτ Ñ8 rz pτ q “ 0 where
“ ‰
log pPpz ´ E z ă ´τ σpzqqq
rz pτ q “
log pΦp´τ qq

0.4
Normal
Logistic

0.35
0.3

pdf(x)

0.25
0.2

0.15
0.1

Fatter Tails

0.05
0
-5

-4

-3

-2

-1

0

x

1

2

3

4

5

Fig. 8: Logistic vs Normal tails
Figure 8 shows a pair of distributions in the family Epµ, σq
but logistic distribution exhibits tail risk relative to standard
normal distribution due to “fatter tails”. Such a notion was
used by Acemoglu et. al. in [7] to measure disruption in
economic production networks. Following [1], [7], we extend
this definition to the case of networks.
Definition 12. A large economic network exhibits tail risk
relative to the standard
normal (or macroeconomic tail risk)
?
if limnÑ8 Rx8 p nq “ 0 where
log pPpx8 ´ µpx8 q ă ´τ σpx8 qqq
Rx8 pτ q “
log pΦp´τ qq
Tail risk differs from macroeconomic tail risk in the sense
that macroeconomic tail risk (after normalization by its mean
and variance) is measured relative to the standard normal
distribution. These notions of risk are applied extensively in
economic networks and financial systems and as a result,
it becomes important to understand how they relate to each
other and robustness measures.
Theorem 2. Under Assumption 3, a large network, An ,

exhibits no tail risk if and only if
a
||P pAn { λP F q||1 “ Θp1q
where λP F is its Perron root.
We show that a lack of tail risk is equivalent to constant
scaling in p||¨||1 , P pAn qq–robustness measure. The condition
required to exhibit no tail risk in Theorem 2 appears to
be very restrictive. Further we can show that this condition
cannot be relaxed to any other norm (such as || ¨ ||2 ) on the
gramian. For example consider the network, Tn ,
˜˜
¸
¸
1
0.9n
1
T
T
? ´
110 ` 11 {n
Tn “ ?
(7)
n`n´1
n n
where 1T0 “ r1, 0, . . . , 0s. Now λP F?“ ρpTn q “ 0.9, clearly
we have that ||pI ´ Tn q´1?
||1 “ Ωp nq, i.e., it exhibits tail
risk (because ||Tn ||1 “ Ωp nq). But we also have,
Proposition
? 8. For Tn defined in Eq. (7) we have that
||P pTn { λP F q||2 “ Θp1q.
Proposition 8 shows that the condition in Theorem 2 can
not be relaxed any further. In the following discussion we
show that tail risk coincides with macroeconomic tail risk
for a widely studied economic model.
Tail Risk in Input Output Networks
Consider the economy consisting of n competitive sectors
denoted by t1, 2, . . . , nu, each producing a distinct product.
Each sector corresponds to a node in the network graph.
Firms in each sector employ Cobb-Douglas production technologies with constant returns to scale. Formally, for each
sector, i, we have
log pxi,t`1 q “ log pΣi,t q ` log pηi,t q`
˜
¸
n
ÿ
µ
aij log pyij,t q ` p1 ´ µq log pli,t q (8)
j“1

At, each time, t, xi,t is the output of sector i, Σi,t ě 0
(since output of the network is always nonnegative) is the
total factor productivity, li,t is labor input to sector i, yij,t
is amount of output of sector j used for the production
of output of sector i, and ηi,t ą 0 is some normalization
constant. A larger aij means that sector j is more important
in the production
řn of output of sector i. Constant returns to
scale implies j“1 aij “ 1 for all i, where aij ě 0. From
now, An “ raij s will be referred as the economy’s inputoutput, or network, matrix, where the network is denoted by
N pAn ; Gq, and G is the graph induced by An . In Eq. (8), Σi,t
is a multiplicative production factor in the dynamics of the
network, where under no shock, Σi,t “ 1. We are interested
in the case when Σi,0 ă 1 and Σi,t “ 1 for all t ą 0 and
i P t1, 2, . . . , nu. This corresponds to a negative shock of the
form log pΣi,0 q in the notation of Eq. (1). We further assume
that log pΣi,0 q „ Ep´m2 , 1q. The mathematical formulation
in (8) is completed by two resource constraints:
n
ÿ
xi,t “
yij,t ` ci,t
j“1

8

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS

H“

t
ÿ

li,t ` Zt

(9)

n“1

Here Zt is the total leisure, ci,třis the consumption of product
n
i at node i at time t, ct “ i“1 ci,t and the sum of total
input labor and leisure is a constant. Finally, we assume that
economy maximizes the following preference function over
consumption and leisure (See Sections 2, 3 in [17]):
«
ff
8
ÿ
V0 “ maxc,Z EΣ0
upcs , Zs q
s“0

upct , Zt q “ β0 Zt `

n
ÿ

βi log pci,t q

(10)

i“1

řn
where βi ě 0 but β0 “ 0, and j“1 βj “ 1; βi is
i’s share in the household’s utility function. There are two
forms of heterogeneity - primitive and network (See [7]).
Intuitively, primitive heterogeneity stems from the difference
in preferences, i.e., βi , across different sectors, meanwhile
network heterogeneity is due to interconnections of inputoutput matrix. Since in this work we are concerned with
topological dependence only, we will impose the following
additional assumption.
Assumption 4. The utility function has no sectoral preferences, i.e., βi “ 1{n.
Under optimal consumption and labor, i.e., optimizing V0
under the constraints Eqns. (8), (9), we have Eq. 20 of [17],
x̂t`1 “ µAn x̂t ` η ` t

(11)

Here i,t “ log pΣi,t q, x̂t “ rlog px1,t q, . . . , log pxn,t qsT , and
η is some constant input to the network. Now, we assume
that the economic network is hit with a shock, t “ , at
t “ 0 (t “ 0 for all t ě 1);
Under no shock, i.e., t “ 0 for all t ě 0, we have in
Eq. (11) that
shock
shock
x̂no
“ µAn x̂no
`η
t`1
t
This gives us,
shock
shock
x̂t`1 ´ x̂no
“ µAn px̂t ´ x̂no
q ` t
(12)
t`1
t
no shock
The quantity of interest here is yt “ x̂t ´ x̂t ř, i.e., the
8
output deficit in presence of a shock. Then x8 “ t“0 1T yt
is the aggregate deficit. The aggregate deficit is useful in
estimating business cycles and computing GDP (See [1], [7]).
Surprisingly, under conditions of optimality, a nonlinear
economic system can be reduced into the familiar form of
Eq. (1). Then from Theorem 2 we have that µAn exhibits no
?
tail risk if and only if ||P p µAn q||1 “ Θp1q. Further, under
Assumptions 3, 4 we have that
Theorem 3. A large economic network exhibits no macroeconomic tail risk if and only if it exhibits no tail risk.
Through Theorems 2, 3 we show that different notions of
risk can be represented as robustness measures, i.e., manifestation of tail risk in a network is equivalent to poor scaling
of a robustness measure. We conclude with some examples
of network topologies and comment on their robustness (to
tail risk).

Proposition 9. The regular network, Rn , and cycle network,
Cn , exhibits no macroeconomic tail risk. On the other hand,
star network, Sn , exhibits macroeconomic tail risk.
It is perhaps no coincidence that the star network which
has a high degree centrality (See [16]) demonstrates tail risk.
A generalization of degree centrality is eigenvector centrality.
Definition 13. An irreducible network matrix, An , demonstrates no eigenvector centrality if
πmax {πmin “ Θp1q
where π T An “ π T .
Then ?it follows trivially from Theorem 2 that
||P pAn { λP F q||1 “ Θp1q, i.e., if there is no centrality then
there is no dimension dependent scaling in network energy.
In addition to showing that tail risk is closely related to
network energy. We also relaxed some of the assumption
on network structure imposed by Acemoglu et. al. in [7].
Our analysis can be extended ř
to the case when we have
n
increasing returns to scale, i.e., j“1 aij ą 1 for example.
VI. C ONCLUSIONS
This work developed a general framework to study performance degradation in large networks. It is shown that
dimension–dependent scaling of network energy is closely
related to such degradation. The results here provide an
analytical characterization of performance degradation for an
undirected network in terms of its distance to instability. It
is shown that, for a fixed distance to instability, the network
energy scales at most linearly in the size of network. On
the contrary, results here suggest that for directed networks
distance to instability and performance degradation may
be completely unrelated. The observation that undirected
networks exhibit a certain optimality in energy scaling could
be used as a design principle to obtain more graceful performance. Under this general framework, notions of centrality
and tail risk that appear more commonly in areas such as
economics, finance etc. are related to network energy. This
is a step towards more interdisciplinary research in design of
graceful network controllers.
The work here is confined to networks with linear stable
dynamics. Further extensions to marginally stable dynamics,
such as those in consensus networks, will be discussed in a
future work. Another interesting future step may be to explore
if similar conclusions can be drawn for the case of random
networks.
R EFERENCES
[1] D. Acemoglu, V. Carvalho, A. Ozdaglar, and A. Tahbaz-Salehi, “The
network origins of aggregate fluctuations,” Econometrica, vol. 80,
no. 5, pp. 1977–2016, 2012.
[2] G. F. Young, L. Scardovi, and N. E. Leonard, “Robustness of noisy
consensus dynamics with directed communication,” in American Control Conference (ACC), 2010. IEEE, 2010, pp. 6312–6317.
[3] I. Herman, D. Martinec, Z. Hurak, and M. Sebek, “Nonzero bound
on fiedler eigenvalue causes exponential growth of h-infinity norm
of vehicular platoon,” CoRR, vol. abs/1409.4605, 2014. [Online].
Available: http://arxiv.org/abs/1409.4605

ASYMPTOTIC NETWORK ROBUSTNESS

[4] Q. Huang, Y. Yuan, J. Gonalves, and M. A. Dahleh, “H2 norm based
network volatility measures,” in 2014 American Control Conference,
June 2014, pp. 3310–3315.
[5] R. Sandhu, T. Georgiou, and A. Tannenbaum, “Market Fragility,
Systemic Risk, and Ricci Curvature,” ArXiv e-prints, May 2015.
[6] F. Lin, M. Fardad, and M. R. Jovanovic, “Optimal control of vehicular
formations with nearest neighbor interactions,” IEEE Transactions on
Automatic Control, vol. 57, no. 9, pp. 2203–2218, 2012.
[7] D. Acemoglu, A. Ozdaglar, and A. Tahbaz-Salehi, “Microeconomic
origins of macroeconomic tail risks,” The American Economic Review,
vol. 107, no. 1, pp. 54–108, 2017.
[8] M. Morari and E. Zafiriou, Robust process control. Prentice hall
Englewood Cliffs, NJ, 1989.
[9] L. Lovász, Large networks and graph limits, vol. 60.
[10] M. Siami and N. Motee, “Fundamental limits and tradeoffs on disturbance propagation in linear dynamical networks,” IEEE Transactions
on Automatic Control, vol. 61, no. 12, pp. 4055–4062, 2016.
[11] ——, “Systemic measures for performance and robustness of largescale interconnected dynamical networks,” in Decision and Control
(CDC), 2014 IEEE 53rd Annual Conference on. IEEE, 2014, pp.
5119–5124.
[12] T. Sarkar, M. Roozbehani, and M. A. Dahleh, “Robustness scaling in
large networks,” in 2016 American Control Conference (ACC), July
2016, pp. 197–202.
[13] A. Alexanderian, “On continuous dependence of roots of polynomials
on coefficients.”
[14] B. Eisenberg and R. Sullivan, “Why is the sum of independent normal
random variables normal?” Mathematics Magazine, vol. 81, no. 5, pp.
362–366, 2008.
[15] A. Dembo and O. Zeitouni, “Large deviations techniques and applications, volume 38 of stochastic modelling and applied probability,”
2010.
[16] M. E. Newman, “The mathematics of networks.”
[17] J. B. Long Jr and C. I. Plosser, “Real business cycles,” Journal of
political Economy, vol. 91, no. 1, pp. 39–69, 1983.
[18] E. Häusler and H. Luschgy, Stable convergence and stable limit
theorems. Springer, 2015, vol. 74.
[19] M. Gromov, “Metric structures for riemannian and non-riemannian
spaces,” Bull. Amer. Math. Soc, vol. 38, pp. 353–363, 2001.
[20] V. D. Blondel and Y. Nesterov, “Computationally efficient approximations of the joint spectral radius,” SIAM Journal on Matrix Analysis
and Applications, vol. 27, no. 1, pp. 256–272, 2005.
[21] A. M. Ostrowski, “On the eigenvector belonging to the maximal root
of a non-negative matrix,” Proceedings of the Edinburgh Mathematical
Society, vol. 12, no. 2, pp. 107–112, 1960.

9

The third condition is the requirement of a limit - not all
infinite dimensional maps are bounded. First, we assume the
existence of an infinite dimensional map T , that satisfies
Condition 2, i.e., its range is non trivial for some sequences.
Then we require (Condition 3) that for every such sequence,
v, the map of An on the truncated version of v approaches
T v, as the level of truncation is reduced (n Ñ 8). Now, for
the remaining sequences in S, we expect that the map of An
“goes to infinity” at a certain rate given by f p¨q (Condition
4).
As an example, consider the class of networks An “
γWn where γ ă 1 and Wn is row–stochastic, then from
Portmanteau Theorem and Definition 2.2 in [18] the weak
convergence of Wn over all input randomizations (τ pP q)
implies that limit of An exists in the sense defined above.
Indeed, let Ω “ N, F “ BpNq then first and second
item hold trivially for this class of networks. For items
3, 4, think of sequence, v, as function of its index, i.e.,
vi “ vpiq, and the function vp¨q is Lipschitz and bounded by
definition. Since, Wn converges weakly
to K, we şhave, from
ş
Portmanteau theorem, Wn risv n “ vdWn ris Ñ vdfi , thus
n
W n v n Ñ vK
, where vK “ Kv. Item 4 holds trivially because
the expectation of bounded function is always bounded.
The set up in our case does not require the graphs to
be symmetric (or undirected). The limit of a sequence of
undirected networks, or graph limits, has been studied in [9].
More generally the limit theory of metric spaces has been
studied [19], and can be perhaps extended to our case.

B. Robustness of Networks
For brevity, we prove here the scaling of the networks we
introduced in Section III.
Star Network pSn q:

VII. A PPENDIX
»

0
—1
—
Sn “ γ — .
– ..

A. Sequences of Networks
In this section we formalize our notion of “keeping topology invariant and increasing dimension” for networks. First,
we define S, the space of sequences s “ ps0 , s1 , s2 , . . .q such
that ||s||8 “ supk |sk | ă 8. Next, for every such sequence,
s, we have its truncated version sn “ ps0 , s1 , . . . , sn q.
Now, a sequence of network matrices, tAk u8
k“1 is a limiting
sequence of networks if –
‚ Each An in the sequence is a n ˆ n matrix.
‚ There exists a linear map, T , such that V||¨||8 “
ts | ||T s||8 {||s||8 ă 8u is nonempty.
n
‚ Let v be the truncated version of some sequence v,
||An v n ´ vTn ||8
then supvPV||¨||8
Ñ 0 and vT “ T v.
||v||8
`
‚ There exists a function f : N Ñ R
such that
supbPSzV||¨||8 ||p1{f pnqq ˆ An pbn {||b||8 q ´ tn ||8 Ñ 0
for some t P S.
The first condition is a dimension based constraint, which
accounts for all network matrices and the second condition
is merely a regularity requirement on arbitrary linear maps.

1
n´1

1
n´1

0
..
.
0

1

1
n´1

0
..
.

...
...
..
.

0

...

0

0
..
.

fi
ffi
ffi
ffi
fl

We can verify that
»

Sn2k`1

0
—1
—
“ γ 2k`1 — .
– ..
1

1
n´1

1
n´1

1
n´1

0
..
.

...
...
..
.

0
..
.
0

0

...

0

0
..
.

fi
ffi
ffi
ffi
fl

and
fi
1
0
0
...
0
1
1 ffi
1
—0 n´1
. . . n´1
n´1
ffi
—
Sn2k “ γ 2k — .
..
..
.. ffi
..
– ..
.
.
.
. fl
1
1
1
0 n´1 n´1 . . . n´1
ř8
T 2k`1 2k`1
Since P pSn q ľPSD
Sn
we have that
k“0 pSn q
2 ´1
||P pSn q||2 ě γp1 ´ γ q ||Sn ||22 . But
8
8
ÿ
ÿ
P pSn q “ I `
γ 2k pSn2 qT Sn2 `
γ 2j`1 pSn qT Sn
»

k“0

j“0

10

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS

thus, ||P pSn q||2 ď 1 ` p1 ´ γ 2 q´1 p||Sn ||22 ` ||Sn2 ||22 q which
follows from the subadditivity of L2 –norm. Further, since
||SnT Sn ||max ď ||SnT Sn ||2 ď ||SnT Sn ||S
we have that ||Sn ||22 “ Θpnq and since Sn2 is symmetric we
have ||Sn2 ||22 “ Θp1q, then our claim follows. By a similar
argument, ||P pSn q||S “ Θpnq.
Regular Network pRn q:
»
0
— 1
— n´1
Rn “ γ — .
– ..

1
n´1

1 fi
. . . n´1
1 ffi
0
. . . n´1
ffi
..
.. ffi
..
.
.
. fl
1
1
...
0
n´1
n´1
Since Rn is symmetric then ||P pRn q||2 “ p1{p1 ´
ρ2 pRn qqq´1 and ρpRn q “ γ (By Perron-Frobenius Theorem)
and from Proposition 1 we have ||P pRn q||2 “ Θp1q and due
to the symmetry of topology we have tracepP pRn qq “ Θpnq.

Directed Line pDLn q:
»

0
—1
—
DLn “ — .
– ..

0
0
..
.

...
...
..
.

fi
0
0ffi
ffi
.. ffi
. fl

0 ... 1 0
DLn is nilpotent, i.e., DLnn “ 0nˆn . One can check that
1, . . ., loomoon
0, 0, . . .q, where Diagpvq is
pDLkn qT DLkn “ Diagp1,
loomoon
n-k

k

the matrix with diagonal
ř8 elements as v. Then we have
that ||P pDLn q||2 “ || k“0 pDLkn qT DLkn ||2 “ ||∆n ||2 “
Θpnq, ||P pDLn q||S “ Θpn2 q where
fi
»
n
0
... 0
— 0 n ´ 1 . . . 0ffi
ffi
—
∆n “ — .
. ffi
..
..
– ..
. .. fl
.
0

...

0

1

nonnegative. For a vector of the form 1 it is easy to check
that both sides are equal. Then
1{k

p||Aσ ||22 q1{2k ď γ n2 {k ||An1 1 ||2
lim supp||Aσ ||22 q1{2k ă 1
kÑ8

1{k

The last inequality follows from lim supkÑ8 ||An1 1 ||2
by Gelfand’s Formula, for n1 ď k.

ă 1,

D. Proof of Proposition 2
»

fi
0 ... 0
1 . . . 0 ffi
ffi
.. . .
.. ffi
. . fl
.
0 0 0 ... λ
Notice that
jordan block. Then J n pλq “ pλI `
`n˘ isr an´r
řn Jpλq
n
N q “ r“0 r λ N
where N is the nilpotent matrix –
»
fi
0 1 0 ... 0
—0 0 1 . . . 0ffi
—
ffi
N “ —. . . .
. . ... ffi
– .. .. ..
fl
0 0 0 ... 0
Then we have
` ˘ fi
» n `n˘ n´1 `n˘ n´2
. . . ` n1˘ λ
λ
1 λ
2 ˘λ
`
n n´1
—0
λn
. . . n2 λ2 ffi
1 λ
ffi
—
J n pλq “ — .
..
..
.. ffi
..
– ..
.
.
.
. fl
λ
—0
—
Jpλq “ — .
– ..

1
λ
..
.

0
0
0
...
λn
n
n
Thus ||J pλq||8 “ p1 ` λq ´ 1 ùñ ||J pλq||2 “ exp pcnq
because both || ¨ ||8 and || ¨ ||2 are in the consistent norm set.
Since,
P pJpλqq ´ pJ n pλqqT J n pλq ľPSD 0
n

ùñ ||P pJ n pλqq||2 ą ||J n pλq||22
our claim is now proven.
E. Proof of Theorem 1

Cycle Network pCn q:
1
pDLn ` DLTn q
2
The proof is similar to that of Rn (a combination of
Proposition 1 and symmetric topology). ||P pCn q||2 “
Θp1q, ||P pCn q||S “ Θpnq.
Cn “

We will need the following lemmas for the proof of this
theorem.
Lemma 1. For any matrices A, B we have that
AT B ` B T A ĺP SD AT A ` B T B
Proof. This follows from observing that
pA ´ BqT pA ´ Bq ľP SD 0

C. Proof of Proposition 5



Proof of this follows from Lemma 1 in [20]. Observe that
for An we have A1 “ An , A2 “ γ11T {n and for any σ P
t1, 2uk we can write Aσ
t1

t2

t1

t2

Aσ “ A1i A2i . . . A1j A2j
ř 1
ř
where j tj “ n1 and j t2j “ n2 . Observe that for any
t1 , t2
pAT2 qt2 pAT1 qt1 At11 At22 ĺP SD γ 2t2 pAT1 qt1 At11
This follows from the fact that for any vector in an orthogonal
subspace to 11T {n we have that the left hand side is 0 but
due to the PSDness of pAT1 qt1 At11 the right hand side is

Lemma 2. For any A, the corresponding gramian, P pAq and
Λ “ γ11T {n, then for any word generated of the following
form
λ

λ

λ

λ

B “ pAT qtk Λtk pAT qtk´1 Λtk´1 . . . Λtk´1 Atk´1 Λtk Atk
řk
where j“1 tλj “ tλ then σ1 pBq ď γ 2t σ1 pP pAqq.
Proof. For any t1 , t2 we have that
Λt1 P pAqΛt1 ľP SD Λt1 pAt2 qT At2 Λt1
Next observe that
γ 2t1 P pAq ľP SD Λt1 P pAqΛt1

ASYMPTOTIC NETWORK ROBUSTNESS

11

Using a similar argument as in the proof of Proposition 5.
For any vector in an orthogonal subspace to 11T {n we have
that the right hand side is 0 but due to the PSDness of P pAq
the left hand side is nonnegative. For a vector of the form 1
it is easy to check that both sides are equal. Then replacing
with innermost subword in B, of the form Λt0 pAt1 qT At1 Λt0 ,
with γ 2t0 P pAq successively we get
λ

B ĺP SD γ 2t P pAq
The claim of our lemma now follows. The proof is similar
when we use the Schatten norm in place of the singular value.

For any A “ p1 ´ qA ` Λ where Λ is as in Lemma 2.
Observe that, where A “ p1 ´ qA, Λ “ Λ for shorthand,
k´1
pA ` Λ qk “ Ak ` A
Λ ` Ak´2
Λ  A ` . . .


loooooooooooooooomoooooooooooooooon
k
1

p qarrangements
`

k´2 2
A
Λ ` Ak´3
Λ2 A ` . . .


loooooooooooooooomoooooooooooooooon

pk2qarrangements
From Lemma 2 we can bound the individual singular values
as they only depend on the number of times Λ appears.
Then, where ρpΛq ď γ
k ˆ ˙
ÿ
a
k
σppA ` Λ qk q ď
p1 ´ qk´j j σ1 pP pAqqγ j
j
j“0
a
ď p1 ´  ` γqk σ1 pP pAqq
ř8
Since P pA q “ k“0 ppAT q qk pA qk it follows that
8
ÿ
σ1 pP pA qq ď
p1 ´  ` γq2k σ1 pP q
k“0

“ p1{p1 ´ p1 ´  ` γq2 qqσ1 pP q
“ Opσ1 pP pAqqq
Following Lemma 1 we have
ppA ` Λ qk qT pA ` Λ qk ĺP SD kppAT qk Ak
` pAk´1
Λ ` . . .qT looooooooooooooooomooooooooooooooooon
pAk´1
Λ ` Ak´2
Λ A ` . . .q



pk1qarrangements
` pAk´2
Λ2 ` . . .qT loooooooooooooooooomoooooooooooooooooon
pAk´2
Λ2 ` Ak´3
Λ2 A ` . . .q



pk2qarrangements
` ...
Using Lemma 1, Lemma 2 again on the individual products
we get
tracepppA ` Λ qk qT pA ` Λ qk q
˜
¸
k ˆ ˙2
ÿ
k
2pk´jq
2j
ďk
p1 ´ q
pγq
tracepP q
j
j“0
“ kp1 ´  ` γq2k tracepP q
8
ÿ
tracepP pA qq ď
kp1 ´  ` γq2k tracepP q
k“0

tracepP pA qq “ Opp1{qtracepP pAqqq
tracepP pA qq “ OptracepP pAqqq

F. Proof of Proposition 6
For a symmetric stable matrix, the gramian P pAq “ pI ´
A2 q´1 . Since pI ´ Kq is symmetric then we have that for
any P “ pI ´ pI ´ Kq2 q´1 .
P “ pI ´ pI ´ Kq2 q´1
“ p2K ´ K 2 q´1
“ p1{2qK ´1 pI ´ p1{2qKq´1
Since K 2 is positive semidefinite, and since pI ´Kq is stable
we have that ρpKq ă 2 since ρpI ´ Kq “ |1 ´ ρpKq|. Then
we have that ρpp1{2qKq ă 1 and that all eigenvalues of
I ´ p1{2qK are nonnegative and it is positive semidefinite.
Now we expand p1{2qK ´1 pI ´ p1{2qKq´1
p1{2qK ´1 pI ´ p1{2qKq´1 “ p1{2qK ´1
` p1{4qI ` p1{8qK`
p1{16qK 2 pI ´ p1{2qKq´1
We observe that K 2 pI ´ p1{2qKq´1 is psd because if AB “
pABqT for two psd matrices A, B then AB is psd. Then
tracepp1{2qK ´1 pI ´ p1{2qKq´1 q ě n{4 ` tracepp1{2qK ´1
` p1{8qKq
Now our claim follows from Eq. (8), (9), (10) in [6]. Unlike
there, here we have the following constraint for stability that
0 ď ki ď 2. The second claim follows because if H2 –norm
is Ωpn2 q then the largest singular value has to be Ωpnq.
G. Proof of Proposition 7
Consider the following controller
K 21 “ ´p1{2qDLn ` p1{2qInˆn
K 21 is an asymmetric controller with spectral radius“ 1{2.
Then pI ´ Kq “ p1{2qDLn ` p1{2qInˆn “ p1{2qJp1q (from
Proof of VII-D). Now for t ď n,
ˆ ˙2
t
ÿ
t
traceppJ t p1qqT J t p1qq ď
pt ´ rq
r
r“0
t ˆ ˙2
ÿ
t
ďt
r
r“0
ˆ
˙
2t
“t
t
?
“ C t22t
The last equality follows from Stirling’s approximation.
Therefore for t ď n we have,
n
ÿ
?
tracepp1{22t qpJ k p1qqT J k p1qq ď Cn n
k“0

For the other case when t ą n, we have
n n´k
ÿ
ÿ ˆ t ˙2
traceppJ t p1qqT J t p1qq ď
r
k“1 r“1
ˆ ˙2
n´1
ÿ
t
a
“
pn ´ rq
r
r“0
n´1
ÿ ˆ t ˙2
ďn
r
r“0

12

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS

Equality a comes from applying Fubini’s theorem. We break
our analysis into t P pn, 2nq, p2n, 4nq, . . ., i.e.,
n´1 ˆ ˙2
8
8
ÿ
ÿ
n ÿ t
tracepp1{22t qpJ t p1qqT J t p1qq ď
22t r“0 r
t“n`1
t“n`1
2n
n´1 ˆ ˙2
ÿ
n ÿ t
“
22t r“0 r
t“n`1
4n
n´1 ˆ ˙2
ÿ
n ÿ t
...
`
22t r“0 r
t“2n`1
First for t P pn, 2nq we have the following upper bound
2n
2n
n´1 ˆ ˙2
ÿ
ÿ
a
n ÿ t
n 22t
?
ď
C
22t r“0 r
22t t
t“n`1
t“n`1
?
ď Cn n
Inequality a comes from Stirling’s approximation assuming n ´ 1 “ t. The key idea of the proof is to divide the range p0, tq into p0, nq, pn, 2nq, p2n ` 1, 4nq, p4n `
řn´1 ` ˘2
1, 8nq . . . , p2k , tq. We observe that r“0 rt
is at most
`
˘
`
˘
ř
2
t
p1{2k q r“0 rt because rt monotonically increases for
r ă t{2.
Now, we can generalize for t P p2k n, 2k`1 nq for k ą 0,
2k`1
2k`1
ÿ n n n´1
ÿ ˆ t ˙2
ÿ n n 22t
?
ď
C
22t r“0 r
22t 2k t
k
k
t“2 n`1
t“2 n`1
c
n
ď Cn
2k
Now, summing for all k “ 1, 2, . . . we get that
c
8
2k`1
8
ÿ
ÿ n n n´1
ÿ ˆ t ˙2
ÿ
n
ď
Cn
2t
k
2
r
2
r“0
k“1 t“2k n`1
k“1
?
tracepP pJp1qqq “ Opn nq “ opn2 q
H. Proof of Theorem 2
Observe that after a shock at time k “ 0 and with xp0q “
0. We have that xpkq “ Ak ω. Then
8
ÿ
1T Ak ω
x8 “
k“0

Since ρpAq ă 1, we have that x8 “ 1T pI ´ Aq´1 ω “
ř
n
´1
. If
i“1 ci ωi , where ci are the column sums of pI ´ Aq
cmax “ Θp1q then it is obvious that, by Large Deviation
Principle (or even a simple Chernoff Bound), would give us
´ lim p1{nq log pPp|x8 | ą nzqq ă 8
nÑ8

On the other hand if cmax “ Ωpgpnqq where gpnq Ñ 8 with
n. Then it is true that
Pp|x8 | ą nzq ą Ppcmax x1 ą nzq
Pp|x8 | ą nzq ą exp p´nz{cmax q
ùñ ´ lim p1{nq log pPp|x8 | ą nzqq ą 8
nÑ8

Lemma 3. Under Assumption 3, we have that
a
||pI ´ An q´1 ||1 “ Op1q ðñ ||P pAn { ρpAn qq||1 “ Op1q

Proof. By the assumptions on network matrix and from Eq.
32 in [21] that
Rpkq
“ Θp1q
rpkq
for every k, where Rpkq , rpkq are the largest and smallest
row sum respectively of Ak . Further observe that the matrix
Ak {λkP F has Perron root 1. Then from the Perron-Frobenius
theorem for non–negative matrices and the preceding result
of Ostrowski et. al. it follows that any row sum of Ak {λkP F
is Θp1q. Thus we have that
¸k
˜
AT
Ak ||1 “ Θp||Ak ||1 q
||
λP F
Since all matrices are non–negative
˜
¸k
8
ÿ
AT
||
Ak ||1
λ
P
F
k“0
˜
¸k ˜
¸k
8
T
ÿ
A
A
?
?
||1
||
λP F
λP F
k“0
a
||P pA{ λP F q||1

we have that
8
ÿ

“

Θp||Ak ||1 q

k“0

“ Θp||pI ´ Aq´1 ||1 q
“ Θp||pI ´ Aq´1 ||1 q


I. Proof of Proposition 8
Consider the matrix
?
Ak “ ak 11T0 { n ` bk 11T {n
Then
˜
¸˜
¸
˜
¸
ak
1 11T0
ak
11T
? ` ? ` bk
Ak Tn “ ? ` bk
1´ ?
n
n
n
n
n
˜
¸˜
¸
˜
1
ak
ak
Then ak`1 “ ? ` bk
1´ ?
and bk`1 “ ? `
n
n
n
¸
¸
˜
1
bk further it is clear that ak “ bk 1 ´ ?
, and thus
n
¸
˜
1
1
bk . We have
bk`1 “ 1 ` ? ´
n n
˜
¸k
0.9n
k
?
Tn “
Ak
n´ n`1
Then it is obvious that ||Tnk ||2 ď 2p0.9qk , and our assertion
holds.
J. Proof of Theorem 3
From Eqn. (1), we have xpkq “ Ak  for all k. Then,
ř8
´1
. From Proposition 5 in [7] we
k“0 xpkq “ pI ´ Aq
have that a large network exhibits tail risk with respect to
the standard normal
? distribution (or macroeconomic tail risk)
iff limnÑ8 ||v||8 n{||v||2 “ 8, where v “ 1T pI ´ Aq´1 .
From Assumption 3 we have that ||pI ´ Aq´1 ||8 “ Θp1q.
Then this means that the sum of all elements of pI ´ Aq´1
is Θpnq (since the ratio of maximum row sum and minimum
row sum is of constant order). The condition
?
lim ||v||8 n{||v||2 ă 8
nÑ8

ASYMPTOTIC NETWORK ROBUSTNESS

implies that all column sums are of the same order (in n)
which means that ||pI ´ An q´1 ||1 “ Θp1q (because sum of
column sum must equal sum of row sum). Thus
?
lim ||v||8 n{||v||2 ă 8 ùñ ||pI ´ An q´1 ||1 “ Θp1q
nÑ8

The other direction is trivial, implying that
?
lim ||v||8 n{||v||2 ă 8 ðñ ||pI ´ An q´1 ||1 “ Θp1q
nÑ8

K. Proof of Proposition 9
For Rn , Cn we have that π T “ p1{nq1T . Since
πmax {πmin “ 1, we have that ||pI ´ An q´1 ||1 “ Θp1q for
both of these.
||π T pI ´ An q´1 ||8 “ ||π T ||8 p1 ´ λP F q´1
πmin ||pI ´ An q´T ||8 ď πmax p1 ´ λP F q´1
For Sn we have that ||Sn ||1 “ Θpnq.

13

