of 12
arXiv:2005.10199v3 [eess.SY] 26 May 2020
Localization & Mitigation of Cascading Failures in Power Sy
stems,
Part I: Spectral Representation & Tree Partition
Linqi Guo, Chen Liang, Alessandro Zocca, Steven H. Low, and A
dam Wierman
Abstract
— Cascading failures in power systems propagate
non-locally, making the control of outages extremely diffic
ult.
In this work, we propose a new framework that offers strong
analytical guarantees on both the localization and mitigat
ion
of cascading failures in power systems. The key component of
this framework leverages the concept of
tree partition
, which
characterizes regions of a power network inside which line
failures are automatically localized. In Part I of this pape
r
we establish a mathematical theory that underlies all the
performance guarantees of tree partition as well as its fail
ure
localization properties. This theory consists of a set of to
ols
developed using the Laplacian matrix of the transmission ne
t-
work and reveals a novel perspective that precisely capture
s the
Kirchhoff’s Law in terms of topological structures. Our res
ults
show that the distribution of different families of subtree
s of
the transmission network plays a critical role on the patter
ns
of power redistribution, and motivates tree partitioning o
f the
network as a strategy to eliminate long-distance propagati
on of
disturbances. These results are used in Parts II and III of th
is
paper to design strategies to localize and mitigate line fai
lures.
I. I
NTRODUCTION
Cascading failures in power systems propagate non-
locally, making their analysis and mitigation difficult. Th
is
fact is illustrated by the sequence of events leading to the
1996 Western US blackout (as summarized in Fig. 1 from
[1], [2]), in which successive failures happened hundreds o
f
kilometers away from each other (e.g. from stage
3
to stage
4
and from stage
7
to stage
8
). Non-local propagation
makes it challenging to design distributed controllers tha
t
reliably prevent and mitigate cascades in power systems. In
fact, such control is often considered impossible, even whe
n
centralized coordination is available [3], [4].
Current industry practice for mitigating cascading fail-
ures mostly relies on simulation-based contingency analys
is,
which focuses on a small set of most likely initial failures
[5]. Moreover, the size of the contingency set which is teste
d
(and thus the level of security guarantee) is often constrai
ned
by computational power, undermining its effectiveness in
view of the enormous number of components in power
networks. After a blackout event, a detailed study typicall
y
leads to a redesign of such contingency sets, potentially
together with physical network upgrades and revision of
system management policies and regulations [4].
The limitations of the current practice have motivated a
large body of research on cascading failure; see e.g. [6]
for a recent review with extensive references. In particula
r,
This work has been supported by Resnick Fellowship, Linde In
stitute
Research Award, NWO Rubicon grant 680.50.1529, NSF through
grants
CCF 1637598, ECCS 1619352, ECCS 1931662, CNS 1545096, CNS
1518941, CPS ECCS 1739355, CPS 154471.
LG, CL, SHL, AW are with the Department of Computing and Mathe
-
matical Sciences, California Institute of Technology, Pas
adena, CA, 91125,
USA. Email:
{
lguo, cliang2, slow, adamw
}
@caltech.edu
.
AZ is with the Department of Mathematics of the Vrije Univers
iteit
Amsterdam, 1081HV, The Netherlands. Email:
a.zocca@vu.nl
.
Fig. 1: The sequence of events, indexed by the circled number
s, that lead
to the Western US blackout in 1996 from [1], [2].
the literature on analytical properties of cascading failu
re
can be roughly categorized as follows: (a) applying Monte-
Carlo methods to analytical models that account for the
steady state power redistribution using DC [7]–[10] or AC
[11]–[13] power flow models; (b) studying pure topological
models built upon simplifying assumptions on the propa-
gation dynamics (e.g., failures propagate to adjacent line
s
with high probability) and inferring component failure pro
p-
agation patterns from graph-theoretic properties [14]–[1
6];
(c) investigating simplified or statistical cascading fail
ure
dynamics [2], [17]–[19].
In all these approaches, it is often difficult to make general
inferences about failure patterns. For example, power flow
over a specific transmission line can increase, decrease and
even reverse direction as cascading failure unfolds [20]. T
he
failure of a line can cause another line that is arbitrarily
far away to trip [21]. Load shedding instead of mitigating a
cascading failure, can actually increase the congestion on
certain lines [22]. This lack of structural properties is a
key challenge in the modeling, control, and mitigation of
cascading failures in power systems.
In this work, we take a different approach that leverages
the spectral representation of transmission network topol
ogy
to establish several structural properties. The spectral v
iew
is powerful as it reveals surprisingly simple characteriza
tions
of complex system behaviors, e.g., on controllability and
observability of power system dynamics [23], on dynamic
properties of frequency control [24], [25], and on mono-
tonicity properties and power flow redistribution [26]. In
the context of cascading failures, our spectral approach [2
6]
motivates the use of the network
tree partition
to eliminate
long-distance propagation of disturbances, and allows us t
o
develop a new control framework that offers strong analytic
al
guarantees in both the mitigation and localization of casca
d-
ing failures.
Contributions of Part I of this paper:
We establish a
mathematical theory that underlies the performance guar-
antees of the tree partition of a transmission network and
the failure localization properties that tree partitions b
ring
to the proposed control framework.
This theory starts from
the Laplacian matrix of a transmission network and unveils
a close connection between power redistribution patterns
and the distribution of different families of (sub)trees of
the power network topology. This connection uncovers new
topological structures of several important and well-stud
ied
quantities in power system contingency analysis, such as
the generation shift sensitivity factor and the line outage
redistribution factor. Further, in contrast to pure graphi
cal
models such as those in [14], [15], [27], such topological
interpretations capture Kirchhoff’s Law in a precise way an
d
do not rely on any assumptions or simplifications on the
failure propagation dynamics.
The key result that relates the power redistribution to
graphical structures is given in Proposition 4, which state
s
that the distribution of different families of subtrees of
the transmission network fully determines the system state
under a given set of injections. In Section III, we establish
a new set of graphical representations of generation shift
sensitivity factors and line outage distribution factors i
n
contingency analysis. This novel graph-theoretical viewp
oint
enables us to derive precise algebraic properties of power
redistribution using purely graphical arguments, and show
s
that disturbances propagate through “subtrees” in a power
network. Using this framework, in Section III-E we derive
the
Simple Loop Criterion
that fully determines whether the
failure of one line can impact another line in a given network
topology.
In order to prove these results, we exploit the celebrated
Kirchhoff Matrix Tree Theorem as well as its generalization
known as the All Minors Matrix Tree Theorem. Further, we
make use of some novel properties of the Laplacian matrix
derived in the context of DC power flow and characterize
certain quantities of interest by different families of spa
nning
forests in the transmission network.
Our graphical interpretation of power redistribution natu
-
rally suggests that we can eliminate long-distance propaga
-
tion of system disturbances by refining the (possibly trivia
l)
tree partition of a transmission network. In Section IV, we
formally define the notion tree partition and show that the
“finest” tree partition of a general graph is unique and can
be computed in linear time. In Section V, we demonstrate
how tree partitioning localizes the impacts of a line failur
e
to the region of the network where the failure happens. The
rigorous proof of such localization properties and how they
can be leveraged to provide analytical guarantees for failu
re
mitigation are presented in Part II and Part III of this paper
,
respectively.
II. P
RELIMINARIES
In this section, we present the DC power flow model,
explain its network Laplacian matrix, and introduce some of
its basic properties that will be used throughout this paper
.
A. Power network and DC power flow
We describe a transmission network using a graph
G
=
(
N
,
E
)
, whose node set
N
=
{
1
, . . . , n
}
models the
n
=
|N|
buses and whose edge set
E ⊆ N × N
models the
m
=
|E|
transmission lines. We without loss of generality
assume the graph is simple and use the terms bus/node and
line/edge are used interchangeably. An edge in
E
between
node
i
and
j
is denoted either as
e
or
(
i, j
)
. We assign
an arbitrary orientation over
E
so that if
(
i, j
)
∈ E
then
(
j, i
)
/
∈ E
. The line susceptance (weighted by nodal voltage
magnitudes [28]) of line
e
= (
i, j
)
is denoted as
B
e
=
B
ij
and the susceptance matrix is the
m
×
m
diagonal matrix
B
:= diag(
B
e
:
e
∈ E
)
. Let
f
be the
m
-dimensional vector
consisting of all branch flows, with
f
e
denoting the branch
flow on line
e
. The node-edge incidence matrix of
G
is the
n
×
m
matrix
C
defined as
C
ie
=
1
if node
i
is the source of
e,
1
if node
i
is the target of
e,
0
otherwise.
We introduce the
n
-dimensional vectors
p
and
θ
, where
p
i
and
θ
i
are the power injection and voltage phase angle at
bus
i
, respectively. With the above notation, the DC power
flow model can be written as
p
=
Cf
(1a)
f
=
BC
T
θ,
(1b)
where (1a) is the flow conservation (Kirchhoff’s) law and
(1b) is the Ohm’s laws. Given an injection vector
p
that is
balanced over the network
P
j
∈N
p
j
= 0
, the DC model (1)
has a solution
(
θ, f
)
where
θ
is unique up to an arbitrary
reference angle. Without loss of generality, we choose node
n
as a reference node and set
θ
n
= 0
. With this convention,
the solution
(
θ, f
)
is unique.
When a line
e
is tripped, the power redistributes according
to the DC model (1) on the newly formed graph
G
:=
(
N
,
E\ {
e
}
)
. If
G
is still connected, then the flow change
on a line
ˆ
e
with the same power injection
p
can be given in
terms of the
line outage distribution factor
K
ˆ
ee
from
e
to
ˆ
e
as
f
ˆ
e
=
K
ˆ
ee
f
e
.
It is known that these distribution factors depend solely on
the network topology, in the sense that they are independent
of the power injections
p
and can be computed directly from
the matrices
B
and
C
[29]. In Section III-D, we derive a new
formula for
K
ˆ
ee
that precisely captures how the Kirchhoff’s
law redistributes branch flows along subtrees of
G
and that is
the foundation for our results on the localization properti
es
of network tree partitions.
B. Laplacian matrix
The DC power flow equations (1) imply that
p
=
CBC
T
θ.
In other words, the phase angles
θ
are determined from the
power injection
p
via the matrix
CBC
T
. This matrix, which
we denote as
L
=
CBC
T
, is known as the Laplacian matrix
of
G
and plays a central role in our analysis. Since for any
v
R
n
we have that
v
T
Lv
=
X
(
i,j
)
∈E
B
ij
(
v
i
v
j
)
2
0
,
(2)
the matrix
L
is positive semidefinite. Moreover, equality is
attained in (2) if and only if
v
i
=
v
j
for every
(
i, j
)
∈ E
.
Fig. 2: An example element in
T
(
N
1
,
N
2
)
, where circles correspond to
elements in
N
1
and squares correspond to elements in
N
2
. The two trees
containing
N
1
and
N
2
are highlighted as solid lines.
Thus the Laplacian matrix
L
is singular and the eigenspace
of
L
corresponding to
0
, i.e., the kernel of
L
, consists of
vectors that take the same value on each of the connected
components of
G
. The following well-known result summa-
rizes a special case.
Lemma 1.
If the graph
G
is connected, then the kernel of
L
is
span (
1
)
, the set of vectors with uniform entries.
This result implies that the Laplacian matrix
L
of a
connected graph has rank
n
1
and, hence, contains an
invertible submatrix of size
(
n
1)
×
(
n
1)
. Consider
the submatrix
L
obtained from
L
deleting the last row and
the last column (i.e., those corresponding to the reference
node
n
). The Kirchhoff’s Matrix Tree Theorem (stated below,
see [30] for more details) relates the determinant of
L
to a
weighted sum of spanning trees of
G
.
Proposition 2.
If the graph
G
is connected, the determinant
of
L
is given by
det(
L
) =
X
E
∈T
E
Y
e
E
B
e
,
where
T
E
is the set of all spanning trees of
G
.
This result implies, in particular, that
L
is invertible since
the set of spanning trees
T
E
is non-empty for a connected
graph and
B
e
>
0
for all
e
. Define the
n
×
n
matrix
A
as
follows:
A
=

L

1
0
0
0

.
(3)
The entries of
A
encode information on the topology of
G
and have a clear graph-theoretical interpretation. More
specifically, as we show in Section III, all entries of
A
are
closely related to the subtree distributions of
G
and suggest
how the DC power flow equations (1) inherit features from
the structure of the graph
G
.
III. P
OWER
R
EDISTRIBUTION AND
T
REES
In this section, we show how the entries of the matrix
A
are related to specific families of subtrees of the power
network
G
. This relation reveals new perspectives on many
important and well-studied quantities in contingency anal
ysis
and it is at the core of a new criterion, we call the Simple
Loop Criterion, that characterizes whether the failure of a
line impacts other lines. This new representation in terms
of network subtrees is extensively used to develop further
results in Parts II and III of this paper.
A. Spectral representation
Proposition 2 relates
det(
L
)
to the spanning trees of
G
and hints at the fact that the subtree families of
G
determine
certain algebraic properties of the matrix
A
. We now present
a finer-grained result that explicitly characterizes each e
ntry
of
A
using the tree structure of
G
.
We first introduce some more notation. Given a subset
E
⊆ E
of edges, we denote by
T
E
the set of spanning trees
of
G
with edges from
E
(which can possibly be empty if
E
is
too small or if
G
is disconnected). In particular,
T
E
is the set
of spanning trees on
G
. For any pair of subsets
N
1
,
N
2
⊂ N
,
we define
T
(
N
1
,
N
2
)
to be the set of spanning forests of
G
consisting of exactly two trees (necessarily disjoint) tha
t
contain
N
1
and
N
2
, respectively (see Fig. 2 for an illustration
of
T
(
N
1
,
N
2
)
). Given a subset
E
⊆ E
of edges, we write
χ
(
E
) :=
Y
e
E
B
e
.
Then, the All Minors Matrix Tree Theorem [30] applied to
the matrix
L
yields the following result.
Proposition 3.
The determinant of the matrix
L
ij
, obtained
from
L
by deleting the
i
-th row and
j
-th column, is equal to
det

L
ij

= (
1)
i
+
j
X
E
∈T
(
{
i,j
}
,
{
n
}
)
χ
(
E
)
.
This result leads to our graphical interpretation of the
elements of
A
, formally stated as follows (its proof is
presented in Appendix I):
Proposition 4
(Spectral Representation)
.
For any
i, j
∈ N
,
we have
A
ij
=
P
E
∈T
(
{
i,j
}
,
{
n
}
)
χ
(
E
)
P
E
∈T
E
χ
(
E
)
.
(4)
In the expression (4) for
A
ij
, the denominator is a normal-
ization constant common for all entries of
A
. The sum at the
numerator is over the trees in
T
(
{
i, j
}
,
{
n
}
)
, which means
that
A
ij
is proportional to the (weighted) number of trees
that connect
i
to
j
and can be interpreted as the “connection
strength” between the buses
i
and
j
in
G
.
The matrix
A
fully determines the phase angles
θ
(and thus
the branch flows
f
) from the power injections
p
as prescribed
by (1), more specifically
θ
=
Ap.
In view of this fact, Proposition 4 implies that the power
redistribution under DC power flow model (1) can be de-
scribed using the distribution of subtree families over the
transmission network. In particular, we can deduce analyt-
ical properties of the branch flows using purely graphical
structures, as we do in the following corollary.
Corollary 5.
For all
i, j
∈ N
we have
A
ij
0
,
and equality holds if and only if every path from
i
to
j
contains the reference node
n
.
Proof.
The statement trivially holds when
i
or
j
coincides
with
n
, so in the rest of the proof we focus on the case
i, j
6
=
n
. In this case, since
χ
(
E
)
0
for all
E
, we clearly
have
A
ij
0
and equality holds if and only if the set
T
(
{
i, j
}
,
{
n
}
)
is empty.
If every path from
i
to
j
contains
n
, then since any tree
containing
{
i, j
}
induces a path from
i
to
j
, we know that
this tree also contains
n
. As a result,
T
(
{
i, j
}
,
{
n
}
) =
.
Conversely, if
T
(
{
i, j
}
,
{
n
}
) =
, then any path from
i
to
j
must contain
n
, since for any path from
i
to
j
not
passing through
n
, we can iteratively add edges that do not
have
n
as an endpoint to obtain a spanning tree over the
nodes set
N\ {
n
}
. This tree together with the node
n
itself
is an element of
T
(
{
i, j
}
,
{
n
}
)
. We thus have shown that
T
(
{
i, j
}
,
{
n
}
)
is empty if and only if every path from
i
to
j
contains
n
.
In the following subsections, by making use of Proposi-
tion 4, we derive novel expressions for well-studied quan-
tities in power system analysis, unveiling a new graphical
meaning for each of them. These results allow us to derive
the Simple Loop Criterion, which is the core motivation
behind using the
tree partitioning
of power networks for
failure localization.
B. Generation Shift Sensitivity Factor
Consider a pair of buses
i
and
j
, which may or may not be
adjacent, i.e.,
(
i, j
)
may or may not be an edge in
E
. Suppose
the injection at bus
i
is increased by
ij
, the injection at
bus
j
is reduced by
ij
, and all other injections remain
unchanged so that the new injections remain balanced. Under
such changes, the branch flow change
f
ˆ
e
on an edge
ˆ
e
is determined by the DC power flow equations (1). The
generation shift sensitivity factor
between the pair of buses
i, j
and the edge
ˆ
e
is defined as the ratio [29]
D
ˆ
e,ij
:=
f
ˆ
e
p
.
When
e
:= (
i, j
)
∈ E
is an edge in the network, we also write
D
ˆ
e,ij
as
D
ˆ
e,e
. The factor
D
ˆ
e,ij
is fully determined by the
matrix
A
, and, if
ˆ
e
= (
w, z
)
, it can be explicitly computed
as (see [29]):
D
ˆ
e,ij
=
B
ˆ
e
(
A
iw
+
A
jz
A
iz
A
jw
)
.
Combining this formula with Proposition 4 yields the fol-
lowing result (proved in Appendix II):
Corollary 6.
For
i, j
∈ N
,
ˆ
e
= (
w, z
)
∈ E
, we have
D
ˆ
e,ij
=
B
ˆ
e
P
E
∈T
E
χ
(
E
)
×
X
E
∈T
(
{
i,w
}
,
{
j,z
}
)
χ
(
E
)
X
E
∈T
(
{
i,z
}
,
{
j,w
}
)
χ
(
E
)
!
.
Despite its complexity, this formula carries a clear graph-
ical meaning, as we now explain. The two sums ap-
pearing at the numerator are over the spanning forests
T
(
{
i, w
}
,
{
j, z
}
)
and
T
(
{
i, z
}
,
{
j, w
}
)
respectively. Each
element in
T
(
{
i, w
}
,
{
j, z
}
)
, as illustrated in Fig. 3, specifies
a way to connect
i
to
w
and
j
to
z
through disjoint trees and
captures a possible path for
i, j
to “spread” impact to
(
w, z
)
.
Similarly, elements in
T
(
{
i, z
}
,
{
j, w
}
)
captures possible
paths for
i, j
to “spread” impact to
(
z, w
)
, which counting
orientation, contributes negatively. Therefore, Corolla
ry 6
implies that the impact of shifting generations from
j
to
i
propagates to the edge
ˆ
e
= (
w, z
)
through all possible span-
ning forests that connect the endpoints
i, j, w, z
(accounting
for orientation). The relative strength of the trees in thes
e
two families determines the sign of
D
ˆ
e,ij
.
Fig. 3: An example element in
T
(
{
i, w
}
,
{
j, z
}
)
. The spanning trees
containing
{
i, w
}
and
{
j, z
}
are highlighted as solid lines.
C. Effective Reactance
The Laplacian matrix
L
appears in circuit analysis as the
admittance matrix (with a different weight), which explici
tly
relates the voltage and current vectors in an electrical res
is-
tive network [31]. In particular, given a network of resisto
rs,
it is shown in [31] that the
effective resistance
between two
nodes
i
and
j
can be computed as
R
ij
:=
L
ii
+
L
jj
L
ij
L
ji
,
(5)
where
L
is the Penrose-Moore pseudoinverse of
L
. With an
analogous calculation, we can show that in our setting (5)
gives the
effective reactance
between the buses
i
and
j
. This
means that, assuming we connect the buses
i
and
j
(with
phase angles
θ
i
and
θ
j
respectively) to an external probing
circuit, when there are no other injections in the network,
the branch flow
f
ij
(from the external circuit) into bus
i
and
out of bus
j
(into the external circuit) is given as
f
ij
=
θ
i
θ
j
R
ij
.
Therefore, the network can be equivalently reduced to a
single line with reactance
R
ij
. If
(
i, j
)
∈ E
, the reactance of
(
i, j
)
is given as
X
ij
:= 1
/B
ij
. Then, the physical intuition
suggests that
R
ij
X
ij
, as additional paths from
i
to
j
in the
network should only decrease the overall reactance. We now
give a graphical interpretation for the difference
X
ij
R
ij
and use it to prove this result rigorously.
Corollary 7.
For all
(
i, j
)
∈ E
we have
X
ij
R
ij
=
X
ij
·
P
E
∈T
E\{
(
i,j
)
}
χ
(
E
)
P
E
∈T
E
χ
(
E
)
.
In particular,
X
ij
R
ij
and the inequality is strict if and
only if the graph
G
is still connected after removing
(
i, j
)
.
The proof of this result is presented in Appendix III. From
Corollary 7, we see that for an edge
(
i, j
)
, the reduction
ratio of its reactance coming from the network is precisely
the portion of weighted spanning trees not passing through
(
i, j
)
among all spanning trees. Thus, more connections from
the network leads to more reduction in the effective reactan
ce
on
(
i, j
)
, which agrees with our physical intuition.
We remark that this reactance reduction ratio is closely
related to the
spanning tree centrality measure
[32]. Indeed,
P
E
∈T
E\{
(
i,j
)
}
χ
(
E
)
P
E
∈T
E
χ
(
E
)
+
c
(
i,j
)
= 1
,
Fig. 4: A ring network with clockwise orientation. Line
e
1
can only
spread “negative” impacts to other lines.
where
c
(
i,j
)
is the spanning tree centrality of
(
i, j
)
. As a
result
R
ij
=
X
ij
c
(
i,j
)
,
which means that in a power network the spanning tree
centrality
c
(
i,j
)
of a transmission line
(
i, j
)
precisely captures
the ratio between its effective reactance
R
ij
and its physical
line reactance
X
ij
.
D. Line Outage Distribution Factor
As we discussed in Section II, when a line
e
is tripped
from a power network
G
, the line outage distribution factor
K
ˆ
ee
captures the ratio between the flow change over line
ˆ
e
with respect to the original branch flow on
e
before it is
tripped. Writing
e
= (
i, j
)
,
ˆ
e
= (
w, z
)
with
i, j, w, z
∈ N
,
the constant
K
ˆ
ee
can be computed as [29]:
K
ˆ
ee
=
X
e
X
ˆ
e
·
A
iw
+
A
jz
A
jw
A
iz
X
e
(
A
ii
+
A
jj
A
ij
A
ji
)
.
This formula only holds if the graph
G
:= (
N
,
E\ {
e
}
)
is
connected, as otherwise its denominator is
0
by Corollary
7. An edge of the graph
G
whose removal disconnects the
graph is known as a
bridge
in the literature. We discuss this
concept and its relationship to tree partitions in more deta
il
in Section IV.
Using our previous results, we can readily derive the
following new formula for
K
ˆ
ee
.
Theorem 8.
Let
e
= (
i, j
)
,
ˆ
e
= (
w, z
)
be edges such that
G
:= (
N
,
E\ {
e
}
)
is connected. Then
K
ˆ
ee
is given by
B
ˆ
e
×
P
E
∈T
(
{
i,w
}
,
{
j,z
}
)
χ
(
E
)
P
E
∈T
(
{
i,z
}
,
{
j,w
}
)
χ
(
E
)
P
E
∈T
E\{
(
i,j
)
}
χ
(
E
)
.
(6)
Proof.
This result readily follows by dividing the identity in
Corollary 6 by that in Corollary 7.
Similar to our discussions in Section III-B, each term in (6)
also carries clear graphical meanings: (a) The numerator of
(6) states that the impact of tripping
e
propagates to
ˆ
e
through
all possible trees that connect
e
to
ˆ
e
, counting orientation.
(b) The denominator of (6) sums over all spanning trees
of
G
that do not pass through
e
= (
i, j
)
, and each tree of
this type specifies an alternative path that power can flow
through if
(
i, j
)
is tripped. When there are more trees of
this type, the network has a better ability to “absorb” the
impact of
(
i, j
)
being tripped, and the denominator of (6)
precisely captures this effect by saying that the impact of
e
being tripped on other lines is inversely proportional to th
e
sum of all alternative tree paths in the network. (c) The
B
ˆ
e
in (6) captures the intuition that a line with a larger reacta
nce
tends to be more robust against failures of other lines.
This graphical interpretation of identity (6) allows us to
make general inferences on
K
ˆ
ee
using only knowledge of the
network topology. For example, in the ring network shown
in Fig. 4, by inspecting the graph, we conclude that
K
e
s
e
1
<
0
, s
= 2
,
3
,
4
,
5
,
6
,
as
e
1
can only spread “negative” impacts to other lines (the
positive term in (6) vanishes).
From Theorem 8, we recover the following result from
[33], whose original proof is much longer.
Corollary 9.
For adjacent lines
e
= (
i, j
)
and
ˆ
e
= (
i, k
)
,
we have
K
ˆ
ee
0
.
Proof.
For such
e
and
ˆ
e
, the second term in the numerator
of (6) is over the empty set and thus equals to
0
.
Given two edges
e
and
ˆ
e
,
K
ˆ
ee
captures how the branch
flow on
ˆ
e
changes if
e
is tripped. In particular, if
K
ˆ
ee
=
0
, then the failure of
e
cannot lead to successive failure of
ˆ
e
(in one step) as the branch flow on
ˆ
e
is not impacted.
The following result shows that the converse also holds if
we are allowed to choose the injection and line capacities
adversarially (see Appendix IV for its proof).
Proposition 10.
Given
e,
ˆ
e
∈ E
with
K
ˆ
ee
6
= 0
, there exist
injections
p
and line capacities
f
, such that before
e
trips
|
f
u
| ≤
f
u
u
∈ E
,
while, after
e
trips,
|
f
ˆ
e
|
>
f
ˆ
e
,
where
f
ˆ
e
is the new flow on
ˆ
e
over
G
= (
N
,
E\ {
e
}
)
.
In other words, for
e
and
ˆ
e
such that
K
ˆ
ee
6
= 0
, there
always exists a scenario where the failure of
e
leads to the
failure of
ˆ
e
. As such,
K
ˆ
ee
determines whether it is possible
for the failure of
e
to cause the failure of
ˆ
e
. The factors
K
ˆ
ee
’s can thus be interpreted as indicators on the system’s
ability to localize failures, and it is reasonable to optimi
ze
the topology
G
so that
K
ˆ
ee
= 0
for as many pairs of edges
as possible.
E. Simple Loop Criterion
The formula (6) shows that the spanning forests
T
(
{
i, w
}
,
{
j, z
}
)
and
T
(
{
i, z
}
,
{
j, w
}
)
fully determine if
K
ˆ
ee
is
0
or not. In other words, whether tripping
e
has any
impact on
ˆ
e
depends on how these edges are connected by
subtrees in
G
. We now establish an equivalent criterion that
can be directly verified from the graph.
If
K
ˆ
ee
6
= 0
, then (6) implies that at least one of the
spanning forest sets
T
(
{
i, w
}
,
{
j, z
}
)
and
T
(
{
i, z
}
,
{
j, w
}
)
is nonempty. Without loss of generality, let us assume
T
(
{
i, w
}
,
{
j, z
}
)
6
=
. For any element in
T
(
{
i, w
}
,
{
j, z
}
)
(see Fig. 3), the tree containing
{
i, w
}
induces a path from
i
to
w
, and the tree containing
{
j, z
}
induces a path from
j
to
z
. By adjoining the edges
e
= (
i, j
)
and
ˆ
e
= (
w, z
)
to these
two paths, we obtain a simple loop
1
containing both
e
and
ˆ
e
. As a result,
K
ˆ
ee
6
= 0
implies that we can find a simple
loop in
G
which contains both
e
and
ˆ
e
.
1
A loop is simple if it visits each node in the loop at most once.
Fig. 5: The construction of
G
P
from
P
.
The converse, unfortunately, in general does not hold
because of certain systems with high symmetry. That is, ther
e
exist pathological systems where a simple loop containing
e
and
ˆ
e
exists, yet
K
ˆ
ee
= 0
. Nevertheless, for such systems,
by perturbing the line susceptances
B
e
with an arbitrarily
small noise, we can “break” the symmetry and show that
K
ˆ
ee
6
= 0
almost surely. The detailed technical treatments for
this perturbation analysis is presented in Part II of this pa
per.
The following proposition formally summarizes the dis-
cussions above:
Theorem 11
(Simple Loop Criterion)
.
For
e
= (
i, j
)
,
ˆ
e
=
(
w, z
)
∈ E
such that
G
:= (
N
,
E\ {
e
}
)
is connected, we
have
K
ˆ
ee
6
= 0
“if” and only if there exists a simple loop in
G
that contains both
e
and
ˆ
e
.
We name this criterion “Simple Loop” both because it
involves simple loops in
G
and because it is an intuitive,
hence simple, criterion depending on loops. The “if” part
of Theorem 11 should be interpreted as a probability one
event under proper perturbations (see Part II of this paper
for more details). This proposition shows that a simple loop
containing
e
and
ˆ
e
must exist if tripping
e
can possibly cause
a successive failure of
ˆ
e
, since otherwise the branch flow
on
ˆ
e
is not impacted by the tripping of
e
. As a result, by
clustering the network in smaller regions connected in a loo
p-
free manner, we can prevent long-distance propagation of
line failures. With this motivation in mind, in the next sect
ion
we define precisely a
tree partition
of a power network and
study its properties.
IV. T
REE
P
ARTITIONS OF
P
OWER
N
ETWORKS
For a power network
G
= (
N
,
E
)
, a collection
P
=
{N
1
,
N
2
,
· · ·
,
N
k
}
of subsets of
N
is said to form a
partition
of
G
if
S
k
i
=1
N
i
=
N
and
N
i
∩ N
j
=
for
i
6
=
j
.
Given a partition
P
=
{N
1
,
N
2
,
· · ·
,
N
k
}
of
G
we define
a
reduced multi-graph
G
P
as follows (see Fig. 5). First,
G
P
has
k
nodes, one for each subset
N
i
; we often use
N
i
to
identify the nodes of
G
P
. Second, there is an undirected edge
connecting the nodes
N
i
and
N
j
of
G
P
for every pair of
nodes
v
∈ N
i
,
w
∈ N
j
in the original graph
G
that are
adjacent in
G
, i.e.,
(
v, w
)
∈ E
. There are multiple edges
between nodes
N
i
and
N
j
of
G
P
when multiple pairs of
such nodes
(
v, w
)
exist in the original graph
G
. Unlike the
graph
G
(to which we have assigned an arbitrary orientation),
the reduced multi-graph
G
P
is undirected.
Definition 12.
A partition
P
=
{N
1
,
N
2
,
· · ·
,
N
k
}
of
G
is
a
tree partition
if the reduced graph
G
P
is a tree. The sets
N
i
are referred to as
regions
of
P
. An edge
e
∈ E
with both
endpoints inside the same region
N
i
is said to be
within
N
i
Fig. 6: An illustration of the partial order

over tree partitions. The
partition
P
1
=
{
N
1
1
,
N
1
2
,
N
1
3
,
N
1
4
}
is finer than
P
2
=
{
N
2
1
,
N
2
2
}
.
and it is called a
bridge
2
otherwise. We denote by
E
i
the
set of edges within
N
i
and by
E
b
the set of bridges, so that
E
=
E
b
S
k
i
=1
E
i
.
A tree partition is exhibited in Fig. 5 for the specific graph.
Other tree partitions of the same graph exist: for instance,
one can always consider the trivial partition
P
0
=
{N}
, in
which all the nodes are collapsed into a single region. The
tree partition of a network
G
is thus not unique in general.
Nevertheless, if we require the tree partition to be as “fine”
as possible, such a partition is unique.
Specifically, given a graph
G
, we define a partial order

over the set of all tree partitions of
G
(which is nonempty
as it always contains the trivial partition
P
0
) as follows. For
two tree partitions
P
1
=

N
1
1
,
N
1
2
,
· · ·
,
N
1
k
1
and
P
2
=

N
2
1
,
N
2
2
,
· · ·
,
N
2
k
2
, we say
P
1
is
finer
than
P
2
, denoted
as
P
1
 P
2
, if for any
i
= 1
,
2
, . . . , k
1
, there exists some
j
(
i
)
∈ {
1
,
2
, . . . , k
2
}
such that
N
1
i
⊆ N
2
j
(
i
)
. That is,
P
1
is finer than
P
2
if each region in
P
1
is contained in some
region in
P
2
(see Fig. 6). It is easy to check that

is in
fact a partial order over all possible tree partitions of
G
.
Definition 13.
A tree partition
P
is said to be
irreducible
if
P
is maximal with respect to the partial order

.
In other words, an irreducible tree partition is a tree
partition of
G
that cannot be made finer.
Proposition 14.
For any graph
G
, the irreducible tree
partition of
G
is unique.
See Appendix V for a proof. We remark that our proof
of Proposition 14 not only shows that the irreducible tree
partition of
G
is unique, but also implies that the problem
of computing this unique irreducible tree partition reduce
s
to finding all the bridges of
G
. We can thus adapt Tarjan’s
bridge-finding algorithm [34] and devise an algorithm that
computes the irreducible tree partition of
G
in
O
(
n
+
m
)
time, as we summarize in Algorithm 1 below (see also the
proof of Proposition 14 in Appendix V for more details).
V. G
UARANTEED
L
OCALIZATION
In the previous section, motivated by the Simple Loop
Criterion, we formally introduce the notion of tree partiti
on
of a power network. In this section we demonstrate three
2
We remark that our definition of bridges agrees with the class
ical
definition of bridges in graph theory (i.e., the removal of an
y such edge
disconnects the original graph) in the sense that if the tree
partition
P
is
irreducible (see Definition 13 later) any bridge defined in ou
r sense is a
bridge in the classical sense, and vice versa.
Algorithm 1
Irreducible Tree Partition Finding Algorithm
1:
Execute Tarjan’s bridge-finding algorithm [34] on
G
=
(
N
,
E
)
to compute the set of bridges
E
b
.
2:
Remove edges in
E
b
from
E
to form the partitioned graph
(
N
,
E\E
b
)
.
3:
Breadth-first search on the partitioned graph
(
N
,
E\E
b
)
to compute its set of connected components
P
:=
{
C
1
, C
2
, . . . , C
k
}
. Return
P
.
localization benefits of tree partitioning: (a) It confines t
he
impact of line outages to within their own tree-partition
regions; (b) It confines the impact of certain power injectio
n
disruptions to within their own tree partition-regions; an
d (c)
Tree partitioning can sometimes reduce, rather than increa
se,
line congestions. We demonstrate benefits (a) and (c) using
a stylized example here, and both aspects will be more
extensively studied in Part II of the paper. Benefit (b) is
demonstrated by a more general result, which will also be
used in Part III to design our real-time mitigation strategy
for cascading failure.
A. Localization of Line Failures
Consider the double-ring network in Fig. 7(a), which
contains exactly one generator and one load bus, denoted by
G
and
L
respectively. This network admits only the trivial
tree partition and the branch flows are shown in Fig. 7(a).
Consider a new network obtained by switching off the upper
tie-line, creating a finer tree partition with two regions:
the left ring and the right ring. This new network and the
redistributed branch flows are shown in Fig. 7(b).
It is easy to check that in the original network Fig. 7(a)
there is a simple loop containing any pair of edges. The
Simple Loop Criterion implies that the impact of any single-
line failure in this topology is global, i.e., all the other
branch flows will change almost surely. Hence, after the
single-line failure, every remaining line may carry a new
branch flow that exceeds its capacity and subsequently trips
(see Proposition 10). In contrast, for the network in Fig. 7(
b),
there are only two loops (corresponding to the two rings).
The Simple Loop Criterion guarantees that the line failures
inside one ring do not impact branch flows in the other and,
thus, line failures are localized within their own regions.
Such localization, however, only applies in the first stage
of a cascading failure, as further failures may involve brid
ges
in the graph, to which the Simple Loop Criterion no longer
applies. In fact, as we show in Part II of this paper, tripping
a bridge almost always has a global impact and, therefore,
failures may still propagate from one region to another afte
r
multiple steps. Further, the newly created bridge in Fig. 7(
b)
is a single-point vulnerability, whose failure disconnect
s the
system into two islands. In Part III, we discuss how these
drawbacks can be overcome by adopting a new control
approach for fast-timescale frequency regulation.
B. Localization of Injection Disruptions
Besides the ability to localize the impact of line failures,
the tree partition of a power network also ensures that
disruptions in power injections in one region do not impact
another region. This is due to a “decoupling” structure of th
e
solution space of Laplacian equations, as we now describe.
(a)
(b)
Fig. 7: (a) A double-ring network with
G
as generator bus and
L
as load
bus, with arrows representing the original branch flow. (b) T
he new network
after removing an edge, with arrows representing the new bra
nch flow.
Given a tree partition
P
=
{N
1
,
N
2
,
· · ·
,
N
l
}
of
G
, for
k
= 1
,
2
, . . . , l
, let
N
k
:=
{
j
:
j /
∈ N
k
,
i
∈ N
k
s.t.
(
i, j
)
∈ E
or
(
j, i
)
∈ E}
and
N
k
=
N
k
N
k
. The set
N
k
defined above consists of
the
boundary
buses of
N
k
in
G
and
N
k
can be interpreted as
the
closure
of
N
k
. As an example, in Fig. 7(b), the closure
of the left ring is given by the ring itself together with the
bus
L
, and the closure of the right ring is given by the right
ring itself together with the bus
G
.
Lemma 15.
Let
P
=
{N
1
,
N
2
,
· · ·
,
N
l
}
be a tree partition
of
G
and consider a vector
b
R
n
such that
b
j
= 0
for all
j
∈ N
1
and
P
j
∈N
k
b
j
= 0
for
k
6
= 1
. Then the Laplacian
equation
Lx
=
b
(7)
is solvable, and any solution
x
of
(7)
satisfies
x
i
=
x
j
for
all
i, j
N
1
.
The proof of this result is presented in Appendix VI.
Lemma 15 is used in Part III of this paper to design
mitigation strategy that adjusts power injections in a way t
hat
localizes the impact of initial failures. It implies the fol
lowing
region independence property in the DC power flow context:
If
b
represents perturbations in power injections, then
x
is
the resulting changes in phase angles. Lemma 15 implies
that the changes in phase angles are the same at every node
in
N
1
. Therefore the angle difference across every line in or
incident to
N
1
is zero and the branch flows on these lines
are unchanged, i.e., the branch flows in
N
1
are independent
of the perturbations in power injections in other regions as
long as they are balanced.
This result holds only if the regions form a tree partition.
In fact, the graph in Fig. 7(a) provides a counter-example
when the network is not tree-partitioned: for this graph, if
we set
N
2
:=
{
G, L
}
and collect the remaining buses in
N
1
,
then the injections satisfies the condition that
b
j
= 0
for all
j
∈ N
1
and
P
j
∈N
2
b
j
= 0
, yet the phase angle differences
across edges in
N
1
are not zero.
C. Congestion Reduction
It is reasonable to expect that switching off lines to refine
a tree partition may increase the stress on the remaining lin
es
and, in this way, worsens network congestion. Nonetheless,
by comparing the branch flows in Fig. 7(a) and (b), we
notice that creating a nontrivial tree partition as in Fig. 7
(b)
actually can potentially remove the circulating flows and
hence globally reduce network congestion. In fact, stronge
r
result holds in this stylized example: the tree partition in
Fig. 7(b) further minimizes the sum of absolute branch flows
over all possible topologies on this network where
G
and
L
are connected. To see this, let
C
:=
{G
= (
N
,
E
) :
G
and
L
are connected in
G
}
be the collection of all graphs
G
= (
N
,
E
)
with edge set
E
⊆ N × N
(which do not need to be a sub-graph of
Fig. 7(a)) such that
G
is connected to
L
(but
G
and
L
are
not necessarily adjacent to each other). Let
p
be the vector
of injections described earlier, namely
p
G
=
d
,
p
L
=
d
for
some
d >
0
, and
p
j
= 0
for all the other buses. For each
G
= (
N
,
E
)
C
, define the metric
Ψ(
G
) :=
X
e
∈E
|
f
e
|
,
where
f
e
is the branch flow on
e
under the injection
p
.
Then we have the following result (see Appendix VII for its
proof):
Proposition 16.
The graph in Fig. 7(b) minimizes the sum
of absolute branch flow
Ψ(
·
)
over
C
.
Hence not only may switching off lines
reduce
congestion,
the tree partition in Fig. 7(b) in fact achieves the best
possible congestion reduction in terms of
Ψ(
·
)
. We revisit
this phenomenon with case studies on more complex IEEE
test systems in Part II of this paper.
VI. C
ONCLUSION
In Part I of this work, we develop a spectral theory using
the transmission network Laplacian matrix that precisely
captures the Kirkhhoff’s Law in terms of graphical structur
es.
Our results show that the distributions of different famili
es
of subtrees play an important role in understanding power
redistribution and enables us to derive algebraic properti
es
using purely graphical arguments. By considering a double
ring network, we demonstrate that creating a non-trivial tr
ee
partition not only helps localize impacts of line failures,
but
also potentially reduces system congestion. The results in
this
part underlie the performance guarantees of a tree partitio
n
as well as its localization properties, which we present in
Parts II and III of this paper, respectively.
R
EFERENCES
[1] NERC, “1996 system disturbances: Review of selected 199
6 electric
system disturbances in North America,” The Disturbance Ana
lysis
Working Group, North American Electric Reliability Counci
l, Prince-
ton Forrestal Village, Princeton, NJ, Report, 2002.
[2] P. D. Hines, I. Dobson, and P. Rezaei, “Cascading power ou
tages
propagate locally in an influence graph that is not the actual
grid
topology,”
IEEE TPS
, vol. 32, no. 2, pp. 958–967, 2017.
[3] D. Bienstock and S. Mattia, “Using mixed-integer progra
mming to
solve power grid blackout problems,”
Discrete Optimization
, vol. 4,
no. 1, pp. 115 – 141, 2007.
[4] P. Hines, S. Talukdar
et al.
, “Controlling cascading failures with
cooperative autonomous agents,”
International journal of critical
infrastructures
, vol. 3, no. 1, p. 192, 2007.
[5] R. Baldick, B. Chowdhury, I. Dobson, Z. Dong, B. Gou, D. Ha
wkins,
H. Huang, M. Joung, D. Kirschen, F. Li
et al.
, “Initial review of
methods for cascading failure analysis in electric power tr
ansmission
systems IEEE PES CAMS task force on understanding, predicti
on,
mitigation and restoration of cascading failures,” in
2008 IEEE Power
and Energy Society General Meeting-Conversion and Deliver
y of
Electrical Energy in the 21st Century
. IEEE, 2008, pp. 1–8.
[6] H. Guo, C. Zheng, H. H.-C. Iu, and T. Fernando, “A critical
review
of cascading failure analysis and modeling of power system,
Elsevier
Renewable and Sustainable Energy Reviews
, vol. 80, pp. 9–22, 2017.
[7] B. A. Carreras, V. E. Lynch, I. Dobson, and D. E. Newman, “C
ritical
points and transitions in an electric power transmission mo
del for
cascading failure blackouts,”
Chaos: An interdisciplinary journal of
nonlinear science
, vol. 12, no. 4, pp. 985–994, 2002.
[8] M. Anghel, K. A. Werley, and A. E. Motter, “Stochastic mod
el for
power grid dynamics,” in
HICSS
. IEEE, 2007, pp. 113–113.
[9] J. Yan, Y. Tang, H. He, and Y. Sun, “Cascading failure anal
ysis with
DC power flow model and transient stability analysis,”
IEEE TPS
,
vol. 30, no. 1, pp. 285–297, 2015.
[10] A. Bernstein, D. Bienstock, D. Hay, M. Uzunoglu, and G. Z
ussman,
“Power grid vulnerability to geographically correlated fa
ilures: Anal-
ysis and control implications,” in
IEEE INFOCOM
, 2014, pp. 2634–
2642.
[11] D. P. Nedic, I. Dobson, D. S. Kirschen, B. A. Carreras, an
d V. E.
Lynch, “Criticality in a cascading failure blackout model,
Interna-
tional Journal of Electrical Power & Energy Systems
, vol. 28, no. 9,
pp. 627–633, 2006.
[12] M. A. Rios, D. S. Kirschen, D. Jayaweera, D. P. Nedic, and
R. N.
Allan, “Value of security: modeling time-dependent phenom
ena and
weather conditions,”
IEEE TPS
, vol. 17, no. 3, pp. 543–548, 2002.
[13] J. Song, E. Cotilla-Sanchez, G. Ghanavati, and P. D. Hin
es, “Dynamic
modeling of cascading failure in power systems,”
IEEE TPS
, vol. 31,
no. 3, pp. 2085–2095, 2016.
[14] C. D. Brummitt, R. M. DSouza, and E. A. Leicht, “Suppress
ing
cascades of load in interdependent networks,”
Proceedings of the
National Academy of Sciences
, vol. 109, no. 12, pp. E680–E689, 2012.
[15] Z. Kong and E. M. Yeh, “Resilience to degree-dependent a
nd cascad-
ing node failures in random geometric networks,”
IEEE TIT
, vol. 56,
no. 11, pp. 5533–5546, Nov 2010.
[16] P. Crucitti, V. Latora, and M. Marchiori, “A topologica
l analysis of
the Italian electric power grid,”
Physica A: Statistical mechanics and
its applications
, vol. 338, no. 1-2, pp. 92–97, 2004.
[17] I. Dobson, B. A. Carreras, and D. E. Newman, “A loading-d
ependent
model of probabilistic cascading failure,”
Probab. Eng. Inf. Sci.
,
vol. 19, no. 1, pp. 15–32, Jan. 2005.
[18] Z. Wang, A. Scaglione, and R. J. Thomas, “A Markov-trans
ition model
for cascading failures in power grids,” in
HICSS
. IEEE, 2012, pp.
2115–2124.
[19] M. Rahnamay-Naeini, Z. Wang, N. Ghani, A. Mammoli, and M
. M.
Hayat, “Stochastic analysis of cascading-failure dynamic
s in power
grids,”
IEEE TPS
, vol. 29, no. 4, pp. 1767–1779, 2014.
[20] D. Mazauric, S. Soltan, and G. Zussman, “Computational
analysis
of cascading failures in power networks,” in
Proceedings of the
ACM SIGMETRICS/International Conference on Measurement a
nd
Modeling of Computer Systems
, ser. SIGMETRICS ’13. New York,
NY, USA: ACM, 2013, pp. 337–338.
[21] A. Bernstein, D. Bienstock, D. Hay, M. Uzunoglu, and G. Z
ussman,
“Power grid vulnerability to geographically correlated fa
ilures 2014:
analysis and control implications,” in
IEEE INFOCOM
, April 2014,
pp. 2634–2642.
[22] D. Bienstock and A. Verma, “The
n
k
problem in power grids: New
models, formulations, and numerical experiments,”
SIAM Journal on
Optimization
, vol. 20, no. 5, pp. 2352–2380, 2010.
[23] L. Guo and S. H. Low, “Spectral characterization of cont
rollability
and observability for frequency regulation dynamics,” in
CDC
. IEEE,
2017, pp. 6313–6320.
[24] L. Guo, C. Zhao, and S. H. Low, “Graph laplacian spectrum
and
primary frequency regulation,” in
CDC
. IEEE, 2018, pp. 158–165.
[25] ——, “Cyber network design for secondary frequency regu
lation: A
spectral approach,” in
PSCC
. IEEE, 2018.
[26] L. Guo, C. Liang, and S. H. Low, “Monotonicity propertie
s and
spectral characterization of power redistribution in casc
ading failures,”
55th Annual Allerton Conference
, 2017.
[27] A. E. Motter and Y.-C. Lai, “Cascade-based attacks on co
mplex
networks,”
Phys Rev E
, Dec. 2002.
[28] C. Zhao, U. Topcu, N. Li, and S. Low, “Power system dynami
cs
as primal-dual algorithm for optimal load control,”
arXiv preprint
arXiv:1305.0585
, 2013.
[29] A. Wood and B. Wollenberg,
Power Generation, Operation, and
Control
. Wiley-Interscience, 1996.
[30] S. Chaiken, “A combinatorial proof of the all minors mat
rix tree
theorem,”
SIAM Journal on Algebraic Discrete Methods
, vol. 3, no. 3,
pp. 319–329, 1982.
[31] F. Dorfler and F. Bullo, “Kron reduction of graphs with ap
plications
to electrical networks,”
IEEE Transactions on Circuits and Systems I:
Regular Papers
, vol. 60, no. 1, pp. 150–163, Jan 2013.
[32] A. S. Teixeira, P. T. Monteiro, J. A. Carric ̧o, M. Ramire
z, and A. P.
Francisco, “Spanning edge betweenness,” in
Workshop on mining and
learning with graphs
, vol. 24, 2013, pp. 27–31.
[33] C. Lai and S. H. Low, “The redistribution of power flow in c
ascading
failures,” in
2013 51st Annual Allerton Conference on Communication,
Control, and Computing (Allerton)
, Oct 2013, pp. 1037–1044.
[34] R. E. Tarjan, “A note on finding the bridges of a graph,”
Information
Processing Letters
, vol. 2, no. 6, pp. 160–161, 1974.
[35] K. Menger, “Zur allgemeinen kurventheorie,”
Fundamenta Mathemat-
icae
, vol. 10, no. 1, pp. 96–115, 1927.
[36] D. B. West
et al.
,
Introduction to graph theory
. Prentice hall Upper
Saddle River, NJ, 1996, vol. 2.
A
PPENDIX
I
P
ROOF OF
P
ROPOSITION
4
Recall that without loss of generality, we choose the node
n
as reference node and defined the matrix
A
accordingly
via (3).
If
i
=
n
or
j
=
n
, it is easy to see that
T
(
{
i, j
}
,
{
n
}
) =
so that
A
ij
= 0
. Now suppose
i, j
6
=
n
and let
A
j
denote the
j
-th column of
A
after removing the reference node. Note
from the definition of
A
that
LA
j
=
e
j
,
where
e
j
R
n
1
is the vector with
1
as its
j
-th component
and
0
elsewhere. Cramer’s rule gives
A
ij
=
det

L
i
j

det
L

,
where
L
i
j
is the matrix obtained by replacing the
i
-th column
of
L
by
e
j
. Now, by Proposition 3, we have
det

L
i
j

= (
1)
i
+
j
det

L
ij

=
X
E
∈T
(
{
i,j
}
,
{
n
}
)
χ
(
E
)
,
and by the Kirchhoff’s Matrix Tree Theorem
det
L

=
X
E
∈T
E
χ
(
E
)
.
This finishes the proof.
A
PPENDIX
II
P
ROOF OF
C
OROLLARY
6
Proposition 4 implies that
X
E
∈T
E
χ
(
E
)
!
(
A
iw
+
A
jz
A
iz
A
jw
)
=
X
E
∈T
(
{
i,w
}
,
{
n
}
)
χ
(
E
) +
X
E
∈T
(
{
j,z
}
,
{
n
}
)
χ
(
E
)
X
E
∈T
(
{
i,z
}
,
{
n
}
)
χ
(
E
)
X
E
∈T
(
{
j,w
}
,
{
n
}
)
χ
(
E
)
.
(8)
We can decompose the set
T
(
{
i, w
}
,
{
n
}
)
based on the tree
to which node
j
belongs. This leads to the identity
T
(
{
i, w
}
,
{
n
}
) =
T
(
{
i, j, w
}
,
{
n
}
)
⊔ T
(
{
i, w
}
,
{
j, n
}
)
,
where
means disjoint union. Similarly, we also have
T
(
{
j, z
}
,
{
n
}
) =
T
(
{
i, j, z
}
,
{
n
}
)
⊔ T
(
{
j, z
}
,
{
i, n
}
)
,
T
(
{
i, z
}
,
{
n
}
) =
T
(
{
i, j, z
}
,
{
n
}
)
⊔ T
(
{
i, z
}
,
{
j, n
}
)
,
T
(
{
j, w
}
,
{
n
}
) =
T
(
{
i, j, w
}
,
{
n
}
)
⊔ T
(
{
j, w
}
,
{
i, n
}
)
.
Substituting the above decompositions into (8) and simpli-
fying, we obtain
X
E
∈T
E
χ
(
E
)
!
(
A
iw
+
A
jz
A
iz
A
jw
)
=
X
E
∈T
(
{
i,w
}
,
{
j,n
}
)
χ
(
E
) +
X
E
∈T
(
{
j,z
}
,
{
i,n
}
)
χ
(
E
)
X
E
∈T
(
{
i,z
}
,
{
j,n
}
)
χ
(
E
)
X
E
∈T
(
{
j,w
}
,
{
i,n
}
)
χ
(
E
)
.
(9)
Furthermore, the following set of identities hold:
T
(
{
i, w
}
,
{
j, n
}
)
=
T
(
{
i, w
}
,
{
j, z, n
}
)
⊔ T
(
{
i, w, z
}
,
{
j, n
}
)
,
T
(
{
j, z
}
,
{
i, n
}
)
=
T
(
{
j, z
}
,
{
i, w, n
}
)
⊔ T
(
{
j, w, z
}
,
{
i, n
}
)
,
T
(
{
j, w
}
,
{
i, n
}
)
=
T
(
{
j, w
}
,
{
i, z, n
}
)
⊔ T
(
{
j, w, z
}
,
{
i, n
}
)
,
T
(
{
i, z
}
,
{
j, n
}
)
=
T
(
{
i, z
}
,
{
j, w, n
}
)
⊔ T
(
{
i, w, z
}
,
{
j, n
}
)
.
Substituting these into (9) and rearranging yields
X
E
∈T
E
χ
(
E
)
!
(
A
iw
+
A
jz
A
iz
A
jw
)
=
X
E
∈T
(
{
i,w
}
,
{
j,z,n
}
)
χ
(
E
) +
X
E
∈T
(
{
j,z
}
,
{
i,w,n
}
)
χ
(
E
)
X
E
∈T
(
{
j,w
}
,
{
i,z,n
}
)
χ
(
E
)
X
E
∈T
(
{
i,z
}
,
{
j,w,n
}
)
χ
(
E
)
=
X
E
∈T
(
{
i,w
}
,
{
j,z
}
)
χ
(
E
)
X
E
∈T
(
{
j,w
}
,
{
i,z
}
)
χ
(
E
)
,
where the last equality follows from
T
(
{
i, w
}
,
{
j, z
}
)
=
T
(
{
i, w
}
,
{
j, z, n
}
)
⊔ T
(
{
j, z
}
,
{
i, w, n
}
)
and
T
(
{
j, w
}
,
{
i, z
}
)
=
T
(
{
j, w
}
,
{
i, z, n
}
)
⊔ T
(
{
i, z
}
,
{
j, w, n
}
.
This completes the proof.
A
PPENDIX
III
P
ROOF OF
C
ORROLLARY
7
The proof uses the following relation between
L
and
A
:
Lemma 17.
For every edge
(
i, j
)
∈ E
we have
L
ii
+
L
jj
L
ij
L
ji
=
A
ii
+
A
jj
A
ij
A
ji
.
Proof.
We know that if the equation
p
=
is solvable, the
solution
θ
is unique after quotienting away the kernel of
L
,
which is given by
span (
1
)
. Noting that the latter coincides
with the kernel of
C
T
, we conclude that the vector
f
=
BC
T
θ
is uniquely determined.
To prove the desired identity, we will equate two alterna-
tive formulas for the branch flows
f
. The first one relies on
the fact that
L
p
always gives a feasible
θ
and, therefore,
f
=
BC
T
L
p.
(10)
The second way to calculate
f
is to set the phase angle at
the reference node to zero, which indirectly implies that
̃
θ
=

θ
0

=

L
1
p
0

=
Ap,
where
θ
and
p
are the vector of non-reference node phase
angles and injections. We then have
f
=
BC
T
̃
θ
=
BC
T
Ap.
(11)
Now take
i, j
∈ N
. Setting the injections
p
i
=
p
j
= 1
and
zero elsewhere, by equating the branch flow
f
ij
computed
from (10) and (11), we obtain that
L
ii
+
L
jj
L
ij
L
ji
=
A
ii
+
A
jj
A
ij
A
ji
.
In other words, we can replace the
L
’s in equation (5)
by the matrix
A
, which allows us to apply Proposition 4.
Now by taking
w
=
i
,
z
=
j
in Corollary 6 and applying
Lemma 17, we see that
R
ij
=
A
ii
+
A
jj
2
A
ij
=
P
E
∈T
(
{
i
}
,
{
j
}
)
χ
(
E
)
P
E
∈T
E
χ
(
E
)
.
For each forest in
T
(
{
i
}
,
{
j
}
)
, we can add the edge
(
i, j
)
to form a spanning tree passing through
(
i, j
)
. Conversely,
each spanning tree passing through
(
i, j
)
after removing the
edge
(
i, j
)
produces a forest in
T
(
{
i
}
,
{
j
}
)
. By definition
of
χ
(
E
)
, this fact implies
X
E
∈T
(
{
i
}
,
{
j
}
)
χ
(
E
) =
X
ij
X
E
∈T
χ
(
E
)
,
where
T
denotes the set of all spanning trees passing
through
(
i, j
)
. Therefore,
X
ij
R
ij
=
X
ij
·
P
E
∈T
E
χ
(
E
)
P
E
∈T
χ
(
E
)
P
E
∈T
E
χ
(
E
)
=
X
ij
·
P
E
∈T
E\{
(
i,j
)
}
χ
(
E
)
P
E
∈T
E
χ
(
E
)
,
and the proof is completed.
A
PPENDIX
IV
P
ROOF OF
P
ROPOSITION
10
In order to prove the desired result, we first establish a
lemma that pertains the branch flow directions on all edges
under a specific type of injections. More concretely, given
an edge
e
= (
i, j
)
∈ E
, we can define its “characteristic”
injection
p
e
by
p
e
k
=
1
,
k
=
i,
1
, k
=
j,
0
,
otherwise
.
The following result shows that the sign of the branch flow
on
ˆ
e
under
p
e
is determined by
D
ˆ
ee
, the generation shift
sensitivity factor between
e
and
ˆ
e
(see Section III-B).
Lemma 18.
Under the injections
p
e
, for any
ˆ
e
= (
w, z
)
∈ E
we have
f
ˆ
e
=
D
ˆ
ee
.
Proof.
From the DC power flow equations we have
f
ˆ
e
=
B
ˆ
e
(
θ
w
θ
z
)
, where
θ
=
Ap
is the phase angles vector (with
θ
n
= 0
for the reference bus
n
). By expanding the matrix
products and noting that
A
is symmetric, we see that
f
ˆ
e
=
B
ˆ
e
(
A
iw
+
A
jz
A
iz
A
jw
) =
D
ˆ
ee
.
In particular, for the edge
e
, we know
f
e
=
D
ee
=
B
e
R
e
>
0
, where
R
e
is the effective reactance of
e
, which
agrees with our intuition.
Now let us consider the case
K
ˆ
ee
>
0
. When this holds,
under the injection
p
e
, we have
f
e
>
0
and
f
ˆ
e
>
0
from
Lemma 18. Choose a line capacity vector
f
so that the
capacity at
ˆ
e
is exactly at
f
ˆ
e
and the capacities for other edges
are sufficiently large in the sense that these lines operate
safely before and after tripping
e
. One example of
f
is given
by
f
u
:=

f
ˆ
e
,
u
= ˆ
e
(1 +
k
K
k
)
k
f
k
,
otherwise
,
where
k·k
denotes the sup norm. With this choice of
capacities, before tripping
e
, it is easy to see that
f
is a
safe operating point under
f
. Further, after we trip
e
from
G
, for any edge
u
other than
ˆ
e
, the new flow satisfies
|
f
u
|
=
|
f
u
+
K
ue
f
e
|
≤ |
f
u
|
+
|
K
ue
| |
f
e
|
≤ k
f
k
+
k
K
k
k
f
k
=
f
u
,
and for
ˆ
e
we have
|
f
ˆ
e
|
=
|
f
ˆ
e
+
K
ˆ
ee
f
e
|
=
f
ˆ
e
+
K
ˆ
ee
f
e
>
f
ˆ
e
,
where the second equality is because
f
e
, f
ˆ
e
, K
ˆ
ee
>
0
. In
other words, after power redistributes over the new graph
G
:= (
N
,
E\ {
e
}
)
, the branch flow on
ˆ
e
is over its capacity
yet all other lines stay within the safe range. As a result,
ˆ
e
would be tripped in the next stage.
The case
K
ˆ
ee
<
0
is analogous. In particular, for this case
we have
f
e
>
0
,
f
ˆ
e
<
0
and hence
f
ˆ
e
+
K
ˆ
ee
f
e
< f
ˆ
e
.
The remaining argument follows a similar construction to th
e
case
K
ˆ
ee
>
0
. The desired result then follows.
A
PPENDIX
V
P
ROOF OF
P
ROPOSITION
14
For
G
= (
N
,
E
)
, let
E
b
be the set of edges that all spanning
trees of
G
pass through. In other words,
E
b
is the set of all
bridges in classical graph theory. Let
G
b
= (
N
,
E\E
b
)
denote
the graph obtained from
G
by removing all edges in
E
b
, and
let
P
=
{
C
1
, C
2
,
· · ·
, C
k
}
be its connected components,
where
k
=
|E
b
|
+ 1
. We claim
P
is an irreducible tree
partition of
G
.
First we show that the reduced graph
G
P
is a tree. Assume
not, then there is a loop in
G
P
. Without loss of generality,
let us assume the loop is
(
C
1
, C
2
,
· · ·
, C
l
)
for some
2
l
k
. Then by the construction of
G
P
, there exist nodes
n
t
1
, n
s
1
, n
t
2
, n
s
2
, n
t
3
,
· · ·
, n
t
l
, n
s
l
such that:
1) For each
i
, the nodes
n
s
i
, n
t
i
C
i
;
2) For each
i
, the edge
e
i,i
+
l
1
:= (
n
s
i
, n
t
i
+
l
1
)
∈ E
, where
+
l
denotes the addition modulo
l
.
For any
i
, since
C
i
is connected, we can find a path
P
i
from
n
t
i
to
n
s
i
. It is then clear that the concatenated path
(
P
1
, e
1
,
2
, P
2
, e
2
,
3
. . . e
l
1
,l
, P
l
, e
l,
1
)
forms a loop in the original graph
G
. Consequently, not all
spanning trees pass through
e
1
,
2
and thus
e
1
,
2
/
∈ E
b
, which
leads to a contradiction.
Next we prove
P
is irreducible by showing that
P
is finer than any tree partition
P
:=
{N
1
,
N
2
,
· · ·
,
N
k
}
of
G
. Consider a region in
P
, say
C
1
. Since both
P
and
P
are partitions of
G
, there must be some region
in
P
, say
N
1
, such that
C
1
∩ N
1
6
=
. We claim that
C
1
⊂ N
1
. Otherwise, there exists another region in
P
, say