Failure Localization in Power Systems via Tree
Partitions
Linqi Guo, Chen Liang, Alessandro Zocca, Steven H. Low, and Adam Wierman
Abstract
—Cascading failures in power systems propagate non-
locally, making the control and mitigation of outages extremely
hard. In this work, we use the emerging concept of the
tree
partition
of transmission networks to provide an analytical char-
acterization of line failure localizability in transmission systems.
Our results rigorously establish the well perceived intuition in
power community that failures cannot cross bridges, and reveal
a finer-grained concept that encodes more precise information
on failure propagations within tree-partition regions. Specifically,
when a non-bridge line is tripped, the impact of this failure only
propagates within well-defined components, which we refer to
as
cells
, of the tree partition defined by the bridges. In contrast,
when a bridge line is tripped, the impact of this failure propagates
globally across the network, affecting the power flow on all
remaining transmission lines. This characterization suggests that
it is possible to improve the system robustness by
temporarily
switching off certain transmission lines, so as to create more,
smaller components in the tree partition; thus spatially localizing
line failures and making the grid less vulnerable to large-scale
outages. We illustrate this approach using the IEEE 118-bus test
system and demonstrate that switching off a negligible portion
of transmission lines allows the impact of line failures to be
significantly more localized without substantial changes in line
congestion.
I. I
NTRODUCTION
Power system reliability is a crucial component in the de-
velopment of sustainable modern power infrastructure. Recent
blackouts, especially the 2003 and 2012 blackouts in North-
western U.S. [1] and India [2], demonstrated the devastating
economic impact a grid failure can cause. In even worse cases,
where facilities like hospitals are involved, blackouts pose
direct threat to people’s health and lives.
Because of the intricate interactions among power system
components, outages may cascade and propagate in a very
complicated, non-local manner [3]–[5], exhibiting very dif-
ferent patterns for different networks [6]. Such complexity
originates from the interplay between network topology and
power flow physics, and is aggravated by possible hidden
failures [7] and human errors [8]. This complexity is the
key challenge for research into the modeling, control, and
mitigation of cascading failures in power systems.
This work has been supported by Resnick Fellowship, Linde Institute
Research Award, NWO Rubicon grant 680.50.1529., NSF grants through
PFI:AIR-TT award 1602119, EPCN 1619352, CNS 1545096, CCF 1637598,
ECCS 1619352, CNS 1518941, CPS 154471, AitF 1637598, ARPA-E grant
through award de-ar0000699 (NODES) and GRID DATA, DTRA through
grant HDTRA 1-15-1-0003 and Skoltech through collaboration agreement
1075-MRA.
The authors are with the Department of Computing and Mathematical Sci-
ences, California Institute of Technology, Pasadena, CA, 91125, USA. Email:
{
lguo, cliang2, azocca, slow, adamw
}
@caltech.edu
.
There are three traditional approaches for characterizing the
behavior of cascades in the literature: (i) using simulation
models [9] that rely on Monte-Carlo approaches to account for
the steady state power flow redistribution on DC [5], [8], [10],
[11] or AC [12]–[14] models; (b) studying purely topological
models that impose certain assumptions on the cascading
dynamics (e.g., failures propagate to adjacent lines with high
probability) and infer component failure propagation patterns
from graph-theoretic properties [16]–[18]; (c) investigating
simplified or statistical cascading failure dynamics [3], [21],
[22], [24]. In each of these approaches, it is typically challeng-
ing to make general inferences across different scenarios due
to the lack of structural understanding of power redistribution
after line failures.
A new approach has emerged in recent years, which seeks
to use spectral properties of the network graph in order
to derive precise structural properties of the power system
dynamics, e.g., [25]–[28]. The spectral view is powerful as
it often reveals surprisingly simple characterizations of the
complicated system behaviors. In the cascading failure context,
a key result from this approach is about the
line outage
distribution factor
[6], [29]. Specifically, it is shown in [26]
that the line outage distribution factor is closely related to
transmission graph spanning forests.
While this literature has yet to yield a precise characteri-
zation of cascades, it has suggested a new structural repre-
sentation of the transmission graph called the
tree partition
,
which is particularly promising. For example, [26] shows that
line failures in a transmission system cannot propagate across
different regions of the tree partition (for more background on
the tree partition, see Section III).
Contributions of this paper:
We prove that the tree
partition proposed in [26] can be used to provide an analytical
characterization of line failure localizability, under a DC
power flow model, and we show how to use this character-
ization to mitigate failure cascades by temporarily switching
off a small number of transmission lines.
Our results rigorously
establish the well perceived intuition in power community
that failures cannot cross bridges, and reveal a finer-grained
concept that encodes more precise information on failure
propagations within tree-partition regions. This work builds
on the recent work focused on the line outage distribution
factor, e.g., [6], [26], [30], and shows that the tree partition
is a particularly useful representation of this factor, one that
captures many aspects of how line failures can cascade.
The formal characterization of localizability is given in
Theorem 6, which summarizes the technical results in Sections
arXiv:1803.08551v3 [cs.SY] 17 Aug 2018
V and VI. In particular, in Section V, we characterize the
power redistribution after the tripping of a non-bridge line
and show that the impact of such failures only propagates
within well-defined components, which we refer to as cells,
inside the tree partition regions. In Section VI, we consider
the failure of bridge lines and prove that, in normal operating
conditions, such failures propagate globally across the network
and impact the power flow on all transmission lines. In order
to prove these results, we depend on properties of the tree
partition proved in [26] as well as some novel properties
derived in Section III. Further, we make use of the block
decomposition of tree partition regions to completely eliminate
the graph spanning forests among distinct cells, which in
the spectral view means failure localization [26]. Lastly, we
apply classical techniques from algebraic geometry to address
potential pathological system specifications and establish our
results.
The characterization we provide in Theorem 6 yields many
interesting insights for the planning and management of power
systems and, further, suggests a new approach for mitigating
the impact of cascading failures. Specifically, our charac-
terization highlights that switching off certain transmission
lines
temporarily
in responds to the real-time injection profile
can lead to more, smaller regions/cells, which localize line
failures, thus making the grid less vulnerable against line
outages. In Section VII, we illustrate this approach using the
IEEE 118-bus test system. We demonstrate that switching off
only a negligible portion of transmission lines can lead to
significantly better control of cascading failures. Further, we
highlight that this happens without significant increases in line
congestion across the network.
II. P
RELIMINARIES
We use the graph
G
= (
N
,
E
)
to describe a power trans-
mission network, where
N
=
{
1
,...,n
}
is the set of buses
and
E ⊂ N ×N
is the set of transmission lines. The terms
bus/vertex and line/edge are used interchangeably. An edge
in
E
between vertices
i
and
j
is denoted either as
e
or
(
i,j
)
.
We assume
G
is connected and simple, and assign an arbitrary
orientation over
E
so that if
(
i,j
)
∈ E
then
(
j,i
)
/
∈ E
. The
line susceptance of
e
is denoted as
B
e
and the branch flow on
e
is denoted as
P
e
. The susceptance matrix is defined to be
the diagonal matrix
B
= diag(
B
e
:
e
∈E
)
.
We denote the power injection and phase angle at bus
i
as
p
i
and
θ
i
, and use
n
and
m
to denote the number of buses
and transmission lines in
G
. The vertex-edge incidence matrix
of
G
is the
n
×
m
matrix
C
defined as
C
ie
=
1
if vertex
i
is the source of
e
−
1
if vertex
i
is the target of
e
0
otherwise.
With the above notation, the DC power flow model can be
written as
p
=
CP
(1a)
P
=
BC
T
θ,
(1b)
Fig. 1. 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.
where (1a) is the flow conservation constraint and (1b) is
Kirchhoff’s and Ohm’s Laws. The slack bus phase angle in
θ
is typically set to
0
as a reference to other buses. With this
convention, the DC model (1) has a unique solution
θ
and
P
for each injection vector
p
such that
∑
j
∈N
p
j
= 0
.
When a line
e
is tripped, the power flow redistributes
according to the DC model (1) on the newly formed graph
G
′
= (
N
,
E\{
e
}
)
. If
G
′
is still connected, then the branch
flow change on a line
ˆ
e
is given as
∆
P
ˆ
e
=
P
e
×
K
e
ˆ
e
,
where
K
e
ˆ
e
is the
line outage distribution factor
[29] from
e
to
ˆ
e
. It is known that this distribution factor is independent of
the original power injection
p
and can be computed from the
matrices
B
and
C
[29].
If the new graph
G
′
is disconnected, then it is possible that
the original injection
p
is no longer balanced in the connected
components of
G
′
. Thus, to compute the new power flow, a
certain power balance rule
B
needs to be applied. Several such
rules have been proposed and evaluated in literature based on
load shedding or generator response [5], [6], [31]–[33]. In this
work, we do not specialize to any such rule and instead opt to
identify the key properties of these rules that allow our results
to hold. With this more abstract approach, we can characterize
the power flow redistribution under a class of power balance
rules.
The line outage distribution factor has been extensively
studied in previous work, and we make use of some important
properties from this literature. In [26], by studying the spec-
trum of the graph Laplacian, a formula for
K
e
ˆ
e
is given in
terms of the graph structure of
G
. This formula plays a central
role in proving almost all of the results in this paper, and we
thus restate it here. To do so, we need some more notation. For
two subsets of vertices
N
1
,
N
2
⊂N
, let
T
(
N
1
,
N
2
)
be the set
of spanning forests of
G
consisting of
exactly
two trees that
contain
N
1
and
N
2
respectively
1
. See Fig. 1 for an illustration.
Given a set
E
⊂ E
of lines, we assign a weight to
E
by
multiplying the susceptances over all lines in
E
χ
(
E
) :=
∏
e
∈
E
B
e
1
This definition does not require
N
1
and
N
2
to be disjoint, and
T
(
N
1
,
N
2
)
is understood to be empty when
N
1
∩N
2
6
=
∅
. See [26] for more discussions.
Fig. 2. The construction of
G
P
from
P
.
and denote the set of all spanning trees of
G
with edges only
from
E
by
T
E
(which can be empty if
E
is too small). The
following result from [26] is used throughout this paper.
Theorem 1.
Let
e
= (
i,j
)
,
ˆ
e
= (
w,z
)
be edges such that the
G
′
= (
N
,
E\{
e
}
)
is connected. Then
K
e
ˆ
e
is given by
B
ˆ
e
×
∑
E
∈T
(
{
i,w
}
,
{
j,z
}
)
χ
(
E
)
−
∑
E
∈T
(
{
i,z
}
,
{
j,w
}
)
χ
(
E
)
∑
E
∈T
E\{
(
i,j
)
}
χ
(
E
)
This result reflects Kirchhoff’s Law in a precise way and
shows that the impact of a line failure propagages through
spanning forests inside
G
. Interested readers are directed to
[26] for a more detailed discussion.
III. T
REE
P
ARTITION
: D
EFINITION AND
P
ROPERTIES
The idea of tree partition for analyzing cascading failure
was first introduced in [26]. Here, we define the tree partition,
discuss its uniqueness and show that the “finest” tree partition
of a general graph can be computed in linear time.
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
N
i
∩N
j
=
∅
for
i
6
=
j
and
∪
k
i
=1
N
i
=
N
. For any
partition, we can define a reduced multi-graph
G
P
from
G
as
follows. First, we reduce each subset
N
i
to a super node (see
Fig. 2). The collection of all super nodes forms the node set
for
G
P
. Second, we add an undirected edge connecting the
super nodes
N
i
and
N
j
for each pair of
n
i
,n
j
∈N
with the
property that
n
i
∈N
i
,
n
j
∈N
j
and
n
i
and
n
j
are connected
in
G
. Note that multiple ledges are added when multiple pairs
of such
n
i
,n
j
exist. Unlike the graph
G
to which we assign an
arbitrary orientation (and thus is a directed graph), the reduced
multi-graph
G
P
is undirected.
Definition 2.
A partition
P
=
{N
1
,
N
2
,
···
,
N
k
}
of
G
is said
to be a
tree partition
if the reduced graph
G
P
forms a tree.
Definition 3.
Given a tree partition
P
=
{N
1
,
N
2
,
···
,
N
k
}
,
the sets
N
i
are called the
regions
of
P
. An edge
e
= (
w,z
)
with both endpoints inside
N
i
is said to be
within
N
i
. If
e
is
not within
N
i
for any
i
, then we say
e
forms a
bridge
2
.
Tree partitions of a power network
G
are generally not
unique. For instance, one can always collapse
G
into a single
2
We remark that our definition of bridges agrees with the classical definition
of bridges in graph theory (i.e., the removal of any such edge disconnects the
original graph) in the sense that if the tree partition
P
is irreducible (see
Definition 4 later) any bridge defined in our sense is a bridge in the classical
sense, and vice versa.
Fig. 3. An illustration of the partial order
over tree partitions. The partition
P
1
=
{
N
1
1
,
N
2
2
,
N
1
3
,
N
1
4
}
is finer than
P
2
=
{
N
2
1
,
N
2
2
}
.
region with the partition
P
0
=
{N}
, which is a trivial tree
partition of
G
. This yields a different tree partition for the
graph shown in Fig. 2. Nevertheless, if we require the tree
partition to be as “fine” as possible, such a partition is unique.
More concretely, 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. 3). It is routine to check that
defines
a partial order over all possible tree partitions of
G
.
Definition 4.
A tree partition
P
of
G
is said to be
irreducible
if
P
is maximal with respect to the partial order
.
In other words, an irreducible tree partition
P
of
G
is a
partition that cannot be reduced to a finer tree partition.
Proposition 5.
For any graph
G
, there exists a unique irre-
ducible tree partition.
See Appendix A for a proof.
We remark that our proof of Proposition 5 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 reduces to finding all bridges of
G
. As a result,
we can adapt Tarjan’s bridge-finding algorithm [34] to devise
an algorithm that computes the irreducible tree partition of
G
in
O
(
n
+
m
)
time. This is summarized in Algorithm 1.
Interested readers are referred to the proof of Proposition 5 in
Appendix A for more details on the algorithm.
To summarize, we have shown that each graph
G
has a
unique irreducible tree partition, which can be computed in
linear time. Thus, to simplify the terminology, whenever we
say the tree partition of
G
in the sequel, we always refer to
its irreducible partition.
IV. S
UMMARY OF
R
ESULTS
In this section we state our main result, which analytically
characterizes line failure localization. It summarizes the tech-
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
.
nical results in the two sections that follow.
Our main result applies in contexts where the system is
operating under
normal
conditions, i.e., when the following
two assumptions are satisfied: (a) the injection is
island-free
(see Definition 10 for a formal definition); and (b) the grid is
participating
with respect to its power balance rule (see Defi-
nition 11 for a formal definition). Moreover, to address certain
pathological cases, we add a perturbation drawn from certain
probability measure
μ
to the line susceptances and assume
μ
is absolutely continuous with respect to the Lebesgue measure
L
m
on
R
m
(see Section VI).
Theorem 6.
For a power network operating under normal
conditions,
K
e
ˆ
e
6
= 0
almost surely in
μ
if and only if:
1)
e,
ˆ
e
are within a common tree partition region and
e,
ˆ
e
belong to the same cell; or
2)
e
is a bridge.
This result highlights that, for a practical system, the tree
partition encodes rich information on how the failure of a line
propagates through the network. We emphasize that: (i) the
condition that
μ
is absolutely continuous with respect to
L
m
is satisfied by almost all practical probability models for such
perturbations (see Section V); and (ii) the conditions that the
injection is island-free and the grid is participating are satisfied
in typical operating scenarios (see Section VI). Therefore,
the conditions posed in Theorem 6 are satisfied in practical
settings.
Fig. 4 shows how the tree partition is linked to the sparsity
of the
K
e
ˆ
e
matrix through Theorem 6. It suggests that,
compared to a full mesh transmission network consisting of
single region/cell, it can be beneficial to
temporarily
switch
off certain lines so that more regions/cells are created and the
impact of a line failure is localized within the cell in which
the failure occurs. We study this network planning and design
opportunity in Section VII.
In the next two sections we prove Theorem 6. We first
characterize the power redistribution after the tripping of a
non-bridge line in Section V, and then consider the failure of
bridge lines in Section VI.
V. N
ON
-B
RIDGE
F
AILURES ARE
L
OCALIZABLE
In this section, we characterize the power flow redistribution
under the DC model when a non-bridge line is tripped and
show that such failures are localized by the tree partition
regions. More specifically, we study how the tripping of a
line
e
∈E
impacts the branch flow on a different edge
ˆ
e
∈E
.
Fig. 4. Non-zero entries of the
K
e
ˆ
e
matrix (as represented by the dark
blocks) for a graph with tree partition
{N
1
,
N
2
,
···
,
N
k
}
and bridge set
E
b
.
The small blocks represent cells inside the regions.
Recall, we mentioned in Section II that when
e
is not a bridge,
the power flow change on
ˆ
e
due to tripping
e
is given by
∆
P
ˆ
e
=
K
e
ˆ
e
×
P
e
.
The impact of the line failure of
e
can thus be characterized
by the distribution factor
K
e
ˆ
e
.
A. Impact across Regions
To start with, we consider the case where
ˆ
e
does belong to
the same region as
e
, that is,
ˆ
e
either belongs to a different
region or
ˆ
e
is a bridge. This case was studied in [26] where
the following result was shown.
Proposition 7.
Consider a power network
G
with tree parti-
tion
{N
1
,
N
2
,
···
,
N
k
}
. Let
e,
ˆ
e
∈ E
be two different edges
such that
e
is not a bridge. Then,
K
e
ˆ
e
= 0
for any
ˆ
e
that is not in the same the region containing
e
.
This result implies that, when a non-bridge line
e
fails, any
line
ˆ
e
not in the same tree partition region as
e
will not be
affected, regardless of whether
ˆ
e
is a bridge. In other words,
non-bridge failures cannot propagate through the boundaries
formed by the tree partition regions of
G
.
B. Impact within Regions
It is reasonable, based on physical intuition, to expect that
the converse to the above result is also true. That is, if
e,
ˆ
e
belong to a common region (and thus
e
is not a bridge), we
would expect
K
e
ˆ
e
6
= 0
. This, however, is not always the case
for two reasons: (a) some vertices within a tree partition region
may “block” spanning forests from
e
to
ˆ
e
; (b) the graph
G
may be too symmetric. We elaborate on these two scenarios
separately in the following two subsections.
1) Block Decomposition:
To illustrate the issue described
above, we use the following example to demonstrate that
certain vertices within a tree partition region may “block”
spanning forests from
e
to
ˆ
e
.
Example 1.
Consider a butterfly network shown in Fig. 5(a)
and pick
e
= (
i,j
)
and
ˆ
e
= (
w,z
)
from the butterfly wings. It
(a)
(b)
Fig. 5. (a) A butterfly network. (b) The block decomposition of the butterfly
network into cells
C
1
and
C
2
.
is not hard to see that any tree containing
i,w
simultaneously
must contain the body vertex
c
, and so is any tree containing
j,z
. As a result, we see
T
(
{
i,w
}
,
{
j,z
}
)
is empty. Similarly
we also know
T
(
{
i,z
}
,
{
j,w
}
)
is empty. By Theorem 1, we
then have
K
e
ˆ
e
= 0
.
The issue with Example 1 is that the butterfly graph is not
2-connected. In other words, it is possible that the removal of
a single vertex (in this case the body vertex
c
) can disconnect
the original graph. We refer to such a vertex as a
cut vertex
following graph-theoretic convention. From Example 1, we see
that cut vertices may “block” spanning forests between edges
in a tree partition region. That is, two disjoint trees cannot
pass through a common cut vertex.
Fortunately, we can precisely capture such an effect by
decomposing each tree partition region further through the
classical
block decomposition
[35]. Recall that the block
decomposition of a graph is a partition of its
edges
such that
each partitioned component is 2-connected. See Fig. 5(b) for
an illustration. We refer to such components as
cells
to reflect
the fact that they are smaller parts within a tree partition
region. Note that two different cells within a tree partition
region may share a common vertex as the block decomposition
is over graph edges. The block decomposition of a graph
always exists and can be found in linear time [36].
Lemma 8.
Consider a power network
G
and let
e,
ˆ
e
be two
distinct edges within the same tree partition region but across
different cells. Then
K
e
ˆ
e
= 0
.
Proof.
Let
e
= (
i,j
)
be within the cell
C
e
and
ˆ
e
= (
w,z
)
be within the cell
C
ˆ
e
. It is a classical result that any path
originating from a vertex within
C
e
to a vertex within
C
ˆ
e
must
pass through a common cut vertex in
C
e
[35]. As a result, it is
impossible to find two disjoint trees in
G
containing
i,w
and
j,z
respectively. Thus
T
(
{
i,w
}
,
{
j,z
}
)
is empty. Similarly
T
(
{
i,z
}
,
{
j,w
}
)
is also empty. By Theorem 1, we then know
K
e
ˆ
e
= 0
.
2) Symmetry:
Next, we demonstrate that graph symmetry
3
may also block the propagation of failures. Again, we illustrate
the issue with a simple example.
Example 2.
Consider the complete graph on
n
vertices and
pick
e
= (
i,j
)
and
ˆ
e
= (
w,z
)
such that
e
and
ˆ
e
do not share
3
By symmetry, we refer to graph automorphisms. The exact meaning of
symmetry, however, is not important for our purpose.
any common endpoints:
i
6
=
j
6
=
w
6
=
z
. Assume the line
susceptances are all
1
. By symmetry, it is easy to see that
there is a bijective correspondence between
T
(
{
i,w
}
,
{
j,z
}
)
and
T
(
{
i,z
}
,
{
j,w
}
)
, and thus
∑
E
∈T
(
{
i,w
}
,
{
j,z
}
)
χ
(
E
)
−
∑
E
∈T
(
{
i,z
}
,
{
j,w
}
)
χ
(
E
) = 0
.
By Theorem 1, we then have
K
e
ˆ
e
= 0
.
A complete graph is 2-connected and thus forms a cell.
Example 2 shows that even if the two edges
e,
ˆ
e
are within
the same cell, when the graph
G
is rich in symmetries,
it is still possible that a failure of
e
does not impact
ˆ
e
.
Nevertheless, this issue is not critical as such symmetry almost
never happens in practical systems because of heterogeneity
in line susceptances. In fact, even if the system is originally
symmetric, an infinitesimal change on the line susceptances is
enough to break the symmetry, as we now show.
More formally, we adopt a form of perturbation analysis
on the line susceptances. That is, instead of requiring the
line susceptance to be fixed values
B
e
, we add a random
perturbation
ω
= (
ω
e
:
e
∈ E
)
drawn from a probability
measure
μ
. Such perturbations can come from manufacturing
error or measurement noise. The perturbed system
4
shares the
same topology (and thus tree partition) as the original system,
yet admits perturbed susceptances
B
+
ω
. The randomness
of
ω
implies the factor
K
e
ˆ
e
is now a random variable. Let
L
m
be the Lebesgue measure on
R
m
. Recall
μ
is
absolutely
continuous
with respect to
L
m
if for any measurable set
S
such that
L
m
(
S
) = 0
, we have
μ
(
S
) = 0
.
Proposition 9.
Consider a power network
G
under perturba-
tion
μ
and let
e,
ˆ
e
be two distinct edges within the same cell.
If
μ
is absolutely continuous with respect to
L
m
,
μ
(
K
e
ˆ
e
6
= 0) = 1
.
See Appendix B for a proof.
Note that, by Radon-Nikodym theorem [37], the probability
measure
μ
is absolutely continuous with respect to
L
m
if
and only if it affords a probability density function. In other
words, there are no requirements on either the power or the
correlation of the perturbation for Proposition 9 to apply. The
only necessary condition is that the measure
μ
cannot contain
Dirac masses. As a result, we see that for almost all prac-
tical probability models of such perturbation (e.g., truncated
Gaussian noise with arbitrary covariance, bounded uniform
distribution, truncated Laplace distribution),
K
e
ˆ
e
6
= 0
for
e,
ˆ
e
within the same cell almost surely, no matter how small the
perturbation is.
VI. B
RIDGE
F
AILURES
P
ROPAGATE
The remaining case necessary to prove Theorem 6 is a char-
acterization of the power flow redistribution when a bridge is
tripped. Here, we show that such failures generally propagate
through the entire network.
4
We assume the perturbation ensures
B
e
+
ω
e
>
0
for any
e
∈E
so that
the new susceptance is physically meaningful.
Recall that, when
e
is not a bridge, the branch flow change
on
ˆ
e
due to tripping
e
is given by
∆
P
ˆ
e
=
K
e
ˆ
e
×
P
e
.
(2)
When
e
is a bridge, tripping
e
disconnects the power grid into
two components, and the power in each connected component
may not be balanced. Such power imbalance can be resolved
by a power balance rule
B
(see [5], [31]–[33] for examples
of such rules), which together with the DC model uniquely
determines the new branch flows (and thus the branch flow
change
∆
P
ˆ
e
). We extend the definition of
K
e
ˆ
e
through (2)
to the case where
e
is a bridge and call it the
extended line
outage distribution factor
. Besides being related to the
B
and
C
matrices, this extended
K
e
ˆ
e
factor also depends on the
power injection
p
and the power balance rule
B
.
Power networks without microgrids typically operate in
“island-free mode” as islanding (i.e., isolating a part of the grid
power flow from the rest of the network) poses a safety hazard
to utility maintainence and repair personnel and potentially
leads to damage of the infrastructure [38]. Formally we define
the concept of island-free as follows.
Definition 10.
For a power network
G
, an injection
p
is said
to be
island-free
if under the injection
p
, the branch flow
P
in
G
satisfies
P
e
6
= 0
for any bridge
e
.
Intuitively, island-free means that no part of the grid bal-
ances its own power.
For a grid
G
operating with the balance rule
B
, when a net
power imbalance of level
M
is detected, the rule
B
selects a
set of
participating
buses from
G
and adjust their injections
properly to cancel
M
. The rules studied in the literature [5],
[6], [31]–[33] are typically
linear
in the sense that, for any
participating bus
j
, the injection adjustment
δp
j
dictated by
the rule
B
is linear in
M
.
Denote the set of participating buses of
B
as
N
B
and let
n
b
=
|N
B
|
. The rule
B
can then be interpreted as a linear
transformation from
R
to
R
n
b
given by
B
(
M
) = (
α
j
M
:
j
∈N
B
)
,
where
α
j
are positive constants that sum to
1
. For instance, if
the imbalance is uniformly absorbed by the generators as in
[5], [6], we have
N
B
to be the set of generators and
α
j
= 1
/G
,
where
G
is the number of generators. As another example,
if the imbalance is regulated through Automatic Generation
Control, then we have
N
B
to be set of controllable generators
and
α
j
are the normalized generator participation factors.
Definition 11.
For a power grid
G
with tree partition
P
=
{N
1
,
N
2
,
···
,
N
k
}
operating under power balance rule
B
,
a region
N
i
with block decomposition
{
C
i
1
,
C
i
2
,
···
,
C
i
m
i
}
is
said to be a
participating region
if
N
B
∩C
i
j
contains a non-
cut-vertex for
j
= 1
,
2
,...,m
i
. The grid
G
is said to be a
participating grid
if
N
i
is participating for
i
= 1
,
2
,...,k
.
A power grid is usually participating. For instance, if
B
allocates the power imbalance uniformly to the generators as in
[5], [6], as long as each cell in the network contains a generator
that is not at the “gate” (i.e., it is not a cut vertex
5
), the grid is
participating. If in addition load-side participation is exploited
and
B
also allocates the power imbalance to controllable loads,
then the power grid is participating if the controllable loads
are ubiquitously deployed to all buses.
Given the above, we now state our main result.
Proposition 12.
Consider a participating power network
G
with island-free injection
p
and under line susceptance
perturbation
μ
that is absolutely continuous with respect to
L
m
. If
e
is a bridge of
G
, then for any
ˆ
e
6
=
e
, we have
μ
(
K
e
ˆ
e
6
= 0) = 1
.
See Appendix C for a proof.
The proof of Proposition 12 provides interesting insights. In
particular, both the participating grid and island-free injection
conditions are in fact necessary. For instance, if the supply and
demand is balanced within a region (which violates the island-
free condition), then when the bridge connecting this region
to other parts of the grid is tripped, the power is still balanced
and thus the power flow within the region stays unchanged.
This is precisely the case when a microgrid is connected to the
power network: by disconnecting the microgrid from the main
grid (which effectively trips a bridge in the original system),
branch flows within both the microgrid and the main grid are
not impacted.
Note that the result in Proposition 12 can be easily extended
to more general settings. It is straightforward to extend our
proof to cover the case where neither condition is posed.
We prefer not to present this generalization here because it
would unnecessarily complicate the proof of the result without
providing new insights.
VII. L
OCALIZING
C
ASCADING
F
AILURES
Our findings highlight a new approach for improving the
robustness of the network. More specifically, Theorem 6 and
the discussion in Section V suggest that it is possible to lo-
calize failure propagation by
temporarily
switching off certain
transmission lines based on the specific injection. This creates
more, smaller areas where failure cascades can be contained.
We remark that the lines that are switched off are still part
of the system. In cases where the newly created bridges are
tripped, some of these lines should be switched on so the
system are still connected. The examples presented below are
preliminary and we are still investigating how to optimally
tradeoff the increased robustness from localized failures and
the yet also increased vulnerability from having more bridges.
It is reasonable to expect that such an action may increase
the stress on the remaining lines and, in this way, worsen the
network congestion. In fact, one may expect that improved
system robustness obtained by switching off lines
always
comes at the price of increased congestion levels. In this
section, we argue that this is not necessarily the case, and show
that if the lines to switch off are selected properly, it is possible
5
A cut vertex is always at the “gate” of a cell as all paths from outside
towards vertices in the cell must pass through a cut vertex [35].
(a)
(b)
Fig. 6. (a) A double-ring network.
G
is the generator bus and
L
is the load
bus. Arrows represent the original power flow. (b) The new network after
removing an edge. Arrows represent the new power flow.
to
improve the system robustness and reduce the congestion
simultaneously.
We corroborate this claim by considering first
a small stylized example and then an IEEE test system.
A. Double-Ring Network
Consider the double-ring network in Fig. 6(a), which con-
tains exactly one generator and one load bus. The original
power flow on this network is also shown in Fig. 6(a).
Suppose we switch off the upper tie-line. The new network
and the redistributed power flow are shown in Fig. 6(b). In
this example, by switching off one transmission line, the
circulating flows inside the hexgons are removed and the
overall network congestion is decreased. In fact, it is easy
to show that the topology in Fig. 6(b) minimizes the sum of
(absolute) branch flows over all possible topologies.
B. IEEE test system
In the simple example above, removing a line provides
improvements in both robustness and congestion. Now, we
move to the case of a more realistic network, the IEEE 118-
bus test system. In this case, we also see that line removals
can improve robustness without more than minor increase in
congestion.
In our experiments, the system parameters are taken from
the Matpower Simulation Package [40] and we plot the influ-
ence graphs among the transmission lines to demonstrate how
a line failure propagates in this network
6
. More specifically, in
the influence graph we plot, two edges
e
and
ˆ
e
are connected
if the impact of tripping
e
on
ˆ
e
is not negligible (we use
|
K
e
ˆ
e
| ≥
0
.
005
as a threshold). In Fig. 7(a), we plot the
influence graph of the original network. It can be seen that this
influence graph is very dense and connects many edges that
are topologically far away, showing the non-local propagation
of line failures within this network.
Next, we switch off three edges (indicated as
e
1
,
e
2
and
e
3
in Fig. 7(b)) to obtain a new topology that has a bridge and
whose tree partition now consists of two regions of comparable
size. The new influence graph is shown in Fig. 7(b). One can
see that, compared to the original influence graph in Fig. 7(a),
the new influence graph is much less dense and, in particular,
there are no edges connecting transmission lines that belong to
6
The original IEEE 118-bus network has some trivial “dangling” bridges
that we remove (collapsing their injections to the nearest bus) to obtain a
more transparent influence graph.
different tree partition regions. We also note that the network
in Fig. 7(b) contains two cut vertices (indicated by
c
1
and
c
2
in the figure, with
c
2
being created when we switch off the
lines). It can be checked that line failures are “blocked” by
these cut vertices, which verifies our results in Section V.
It is also of interest to see how the network congestion
is impacted by switching off these lines. To do so, we
collect statistics on the difference between the branch flows
in Fig. 7(b) and those in 7(a). In Fig. 8(a), we plot the
histogram of such branch flow differences normalized by
the original branch flow in Fig. 7(a). It shows that roughly
half (the exact percentage is
47
.
41%
) of the transmission
lines have higher congestion yet the majority of these branch
flow increases are negligible. To more clearly see how much
the congestion becomes worse on these lines, we plot the
cumulative distribution function of the normalized positive
branch flow changes, which is shown in Fig. 8(b). One can
see from the figure that
90%
of the the branch flows increase
by no more than
10%
.
VIII. C
ONCLUSION
In this work, we provide an analytical characterization of
line failure localizability in power systems. We demonstrate
that the transmission network graph encodes rich information
on the regions that a line failure can impact and that such
regions can be computed in linear time. Further, using a
case study on the IEEE 118-bus test network, we show that
switching off certain transmission lines can improve the grid
robustness against line failures without significantly increasing
line congestion.
This work can be extended in several directions. First, we
provide an analytical characterization of power flow redistri-
bution when a line fails, and our results are generalizable to
bus failures. It is of interest to understand how these two
types of failures interact. Second, we demonstrate in our case
studies that by switching off certain transmission lines, grid
robustness can potentially be improved. It would be useful
if the selection of such lines can be optimized for a certain
objective function, such as the sparsity of the influence graph
or the total load loss when some critical lines are tripped.
Third, to fully capture the cascading failure dynamics, both the
power flow redistribution and the line capacities are relevant.
It is important to investigate how line capacities can be
incorporated to our framework.
R
EFERENCES
[1] “U.S.-Canada power system outage task force. report on the August
14, 2003 blackout in the United States and Canada: Causes and recom-
mendation,” 2004.
[2] “Report of the enquiry committee on grid disturbance in Northern region
on 30th July 2012 and in Northern, Eastern and North-Eastern region
on 31st July 2012,” Aug 2012.
[3] P. D. Hines, I. Dobson, and P. Rezaei, “Cascading power outages
propagate locally in an influence graph that is not the actual grid
topology,”
IEEE TPS
, vol. 32, no. 2, pp. 958–967, 2017.
[4] I. Dobson, B. A. Carreras, D. E. Newman, and J. M. Reynolds-Barredo,
“Obtaining statistics of cascading line outages spreading in an electric
transmission network from standard utility data,”
IEEE TPS
, vol. 31,
no. 6, pp. 4831–4841, Nov 2016.
[5] A. Bernstein, D. Bienstock, D. Hay, M. Uzunoglu, and G. Zussman,
“Power grid vulnerability to geographically correlated failures: Analysis
and control implications,” in
IEEE INFOCOM
, 2014, pp. 2634–2642.
[6] S. Soltan, D. Mazauric, and G. Zussman, “Analysis of failures in power
grids,”
IEEE TCNS
, no. 99, 2015.
[7] J. Chen, J. S. Thorp, and I. Dobson, “Cascading dynamics and mitigation
assessment in power system disturbances via a hidden failure model,”
International Journal of Electrical Power & Energy Systems
, vol. 27,
no. 4, pp. 318–326, 2005.
[8] B. A. Carreras, V. E. Lynch, I. Dobson, and D. E. Newman, “Critical
points and transitions in an electric power transmission model for
cascading failure blackouts,”
Chaos: An interdisciplinary journal of
nonlinear science
, vol. 12, no. 4, pp. 985–994, 2002.
[9] I. Dobson, B. A. Carreras, V. E. Lynch, and D. E. Newman, “Complex
systems analysis of series of blackouts: cascading failure, critical points,
and self-organization,”
Chaos: An Interdisciplinary Journal of Nonlinear
Science
, vol. 17, no. 2, p. 026103, 2007.
[10] M. Anghel, K. A. Werley, and A. E. Motter, “Stochastic model for power
grid dynamics,” in
HICSS
. IEEE, 2007, pp. 113–113.
[11] J. Yan, Y. Tang, H. He, and Y. Sun, “Cascading failure analysis with DC
power flow model and transient stability analysis,”
IEEE TPS
, vol. 30,
no. 1, pp. 285–297, 2015.
[12] D. P. Nedic, I. Dobson, D. S. Kirschen, B. A. Carreras, and V. E. Lynch,
“Criticality in a cascading failure blackout model,”
International Journal
of Electrical Power & Energy Systems
, vol. 28, no. 9, pp. 627–633, 2006.
[13] M. A. Rios, D. S. Kirschen, D. Jayaweera, D. P. Nedic, and R. N. Allan,
“Value of security: modeling time-dependent phenomena and weather
conditions,”
IEEE TPS
, vol. 17, no. 3, pp. 543–548, 2002.
[14] J. Song, E. Cotilla-Sanchez, G. Ghanavati, and P. D. Hines, “Dynamic
modeling of cascading failure in power systems,”
IEEE TPS
, vol. 31,
no. 3, pp. 2085–2095, 2016.
[15] A. E. Motter and Y.-C. Lai, “Cascade-based attacks on complex net-
works,”
Phys Rev E
, Dec. 2002.
[16] C. D. Brummitt, R. M. DSouza, and E. A. Leicht, “Suppressing cas-
cades of load in interdependent networks,”
Proceedings of the National
Academy of Sciences
, vol. 109, no. 12, pp. E680–E689, 2012.
[17] Z. Kong and E. M. Yeh, “Resilience to degree-dependent and cascading
node failures in random geometric networks,”
IEEE TIT
, vol. 56, no. 11,
pp. 5533–5546, Nov 2010.
[18] P. Crucitti, V. Latora, and M. Marchiori, “A topological analysis of the
italian electric power grid,”
Physica A: Statistical mechanics and its
applications
, vol. 338, no. 1-2, pp. 92–97, 2004.
[19] C. L. DeMarco, “A phase transition model for cascading network
failure,”
IEEE Control Systems
, vol. 21, no. 6, pp. 40–51, Dec 2001.
[20] T. Nesti, A. Zocca, and B. Zwart, “Emergent failures and cas-
cades in power grids: a statistical physics perspective,”
arXiv preprint
arXiv:1709.10166
, 2017.
[21] I. Dobson, B. A. Carreras, and D. E. Newman, “A loading-dependent
model of probabilistic cascading failure,”
Probab. Eng. Inf. Sci.
, vol. 19,
no. 1, pp. 15–32, Jan. 2005.
[22] Z. Wang, A. Scaglione, and R. J. Thomas, “A markov-transition model
for cascading failures in power grids,” in
HICSS
.
IEEE, 2012, pp.
2115–2124.
[23] J. Qi, K. Sun, and S. Mei, “An interaction model for simulation and
mitigation of cascading failures,”
IEEE TPS
, vol. 30, no. 2, pp. 804–
819, March 2015.
[24] M. Rahnamay-Naeini, Z. Wang, N. Ghani, A. Mammoli, and M. M.
Hayat, “Stochastic analysis of cascading-failure dynamics in power
grids,”
IEEE TPS
, vol. 29, no. 4, pp. 1767–1779, 2014.
[25] L. Guo and S. H. Low, “Spectral characterization of controllability and
observability for frequency regulation dynamics,” in
CDC
. IEEE, 2017,
pp. 6313–6320.
[26] L. Guo, C. Liang, and S. H. Low, “Monotonicity properties and spectral
characterization of power redistribution in cascading failures,”
55th
Annual Allerton Conference
, 2017.
[27] L. Guo, C. Zhao, and S. H. Low, “Graph laplacian spectrum and primary
frequency regulation,”
arXiv preprint arXiv:1803.03905
, 2018.
[28] ——, “Cyber network design for secondary frequency regulation: A
spectral approach,” in
PSCC
. IEEE, 2018.
[29] A. Wood and B. Wollenberg,
Power Generation, Operation, and Control
.
Wiley-Interscience, 1996.
[30] C. Lai and S. H. Low, “The redistribution of power flow in cascading
failures,” in
51st Annual Allerton Conference
, Oct 2013, pp. 1037–1044.
[31] 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.
[32] D. Bienstock, “Optimal control of cascading power grid failures,” in
CDC
, Dec 2011, pp. 2166–2173.
[33] A. Bernstein, D. Bienstock, D. Hay, M. Uzunoglu, and G. Zussman,
“Power grid vulnerability to geographically correlated failures 2014:
analysis and control implications,” in
IEEE INFOCOM
, April 2014, pp.
2634–2642.
[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] F. Harary, “Graph theory,”
Addison-Wesley
, 1969.
[36] R. E. Tarjan and U. Vishkin, “An efficient parallel biconnectivity
algorithm,”
SIAM Journal on Computing
, vol. 14, no. 4, pp. 862–874,
1985.
[37] H. Royden and P. Fitzpatrick,
Real Analysis
, 2010.
[38] M. E. Ropp, M. Begovic, and A. Rohatgi, “Analysis and performance
assessment of the active frequency drift method of islanding prevention,”
IEEE TEC
, vol. 14, no. 3, Sep 1999.
[39] G. Dantzig and D. R. Fulkerson, “On the max flow min cut theorem of
networks,”
Linear inequalities and related systems
, vol. 38, pp. 225–231,
2003.
[40] R. D. Zimmerman, C. E. Murillo-S
́
anchez, and R. J. Thomas, “Mat-
power: Steady-state operations, planning, and analysis tools for power
systems research and education,”
IEEE TPS
, vol. 26, no. 1, pp. 12–19,
2011.
[41] K. Menger, “Zur allgemeinen kurventheorie,”
Fundamenta Mathemati-
cae
, vol. 10, no. 1, pp. 96–115, 1927.
[42] H. Federer,
Geometric measure theory
, ser. Grundlehren der mathema-
tischen Wissenschaften. Springer, 1969.
A
PPENDIX
A
P
ROOF OF
P
ROPOSITION
5
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 a 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 way we form
G
P
∗
, there exist vertices
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 vertices
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
. As a result, not all
spanning trees pass through
e
1
,
2
and thus
e
1
,
2
/
∈ E
b
, which
leads to a contradiction.
Next we show
P
∗
is irreducible. To do so, we prove 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
C
1
⊂N
1
. Otherwise, there exists
another region in
P
, say
N
2
, such that
C
1
∩N
2
6
=
∅
. Pick
n
1
∈
C
1
∩N
1
and
n
2
∈
C
1
∩N
2
. Then
n
1
6
=
n
2
because
N
1
∩N
2
=
∅
. Now since
n
1
,n
2
∈
C
1
, and
C
1
does not contain any bridge
(in classical graph theory sense), by Menger’s Theorem [41],
there exists a cycle (which is not necessarily simple
7
) in
C
1
containing both
n
1
and
n
2
. By collapsing adjacent vertices in
this cycle that belong to common regions, we can find regions
N
1
l
1
,
N
1
l
2
,
···
,
N
1
l
p
1
,
N
2
l
1
,
N
2
l
2
,
···
,
N
2
l
p
2
so that the path from
n
1
to
n
2
in this cycle is given by
(
P
1
1
,e
1
1
,l
1
,P
1
l
1
,e
1
l
1
,l
2
,
···
,e
1
l
p
1
,
2
,P
1
2
)
and the path from
n
2
to
n
1
in this cycle is given by
(
P
2
2
,e
2
2
,l
1
,P
2
l
1
,e
2
l
1
,l
2
,
···
,e
2
l
p
2
,
1
,P
2
1
)
where
e
1
i,j
,e
2
i,j
are edges with source vertices in
N
i
and target
vertices in
N
j
and
P
1
i
,P
2
i
are paths contained in
N
i
. As a
result, we see
(
N
1
,
N
1
l
1
,
···
,
N
1
l
p
1
,
N
2
,
N
2
l
1
,
···
,
N
2
l
p
2
)
forms a loop in
G
P
. This implies
P
is not a tree partition,
contradicting our assumption.
We thus have shown that
P
∗
is a irreducible tree partition
of
G
. Moreover, for any other irreducible tree partition
P
, the
above proof shows that
P
∗
P
Since
P
is irreducible and thus maximal with respect to
,
we see
P
=
P
∗
. In other words, any irreducible tree partition
of
G
must coincide with
P
∗
. This completes our proof.
A
PPENDIX
B
P
ROOF OF
P
ROPOSITION
9
Let
C
be the cell that
e
and
ˆ
e
belong to and write
e
= (
i,j
)
and
ˆ
e
= (
w,z
)
. Consider the polynomial in line susceptances
(
B
e
:
e
∈E
)
defined as
f
(
B
) :=
∑
E
∈T
(
{
i,w
}
,
{
j,z
}
)
χ
(
E
)
−
∑
E
∈T
(
{
i,z
}
,
{
j,w
}
)
χ
(
E
)
We claim
f
is not identically zero.
First, let
C
be a simple cycle in
C
that contains both
e
and
ˆ
e
.
Such a cycle always exists as
C
is 2-connected by construction,
and it is a classical result that any pair of edges are contained
in a simple cycle for 2-connected graphs [35]. Therefore, we
can find two disjoint paths
P
1
and
P
2
connecting the endpoints
of
e
and
ˆ
e
. Without loss of generality, assume
P
1
connects
i
to
w
and
P
2
connects
j
to
z
. By iteratively adding edges from
G
to
P
1
and
P
2
, we can extend
P
1
and
P
2
to a spanning
forest of
G
consisting of exactly two trees. Moreover, the
tree extended from
P
1
contains
i,w
and the tree extended
from
P
2
contains
j,z
. We thus have constructed an element
of
T
(
{
i,w
}
,
{
j,z
}
)
. Denote this element by
E
0
.
Second, we show that
T
(
{
i,w
}
,
{
j,z
}
)
∩T
(
{
i,z
}
,
{
j,w
}
) =
∅
Indeed, consider an element
E
1
from
T
(
{
i,w
}
,
{
j,z
}
)
, which
consists of two trees
T
1
and
T
2
with
T
1
containing
i,w
and
T
2
containing
j,z
. If
E
1
∈ T
(
{
i,z
}
,
{
j,w
}
)
, then
T
1
must
7
A cycle is simple if it visits each vertex at most once.
also contain
z
. However, this implies
z
∈ T
1
∩T
2
, and thus
T
1
and
T
2
are not disjoint, contradicting the definition of
T
(
{
i,w
}
,
{
j,z
}
)
.
As a result, we see that the element
E
0
constructed in
our first step contributes a term to
∑
E
∈T
(
{
i,w
}
,
{
j,z
}
)
χ
(
E
)
but not to
∑
E
∈T
(
{
i,z
}
,
{
j,w
}
)
χ
(
E
)
. Therefore
f
(
B
)
contains
nonvanishing terms and is not identically zero.
It is well-known from algebraic geometry that the root set
of a polynomial which is not identically zero has Lebesgue
measure zero [42]. That is, we have
μ
(
f
(
B
+
ω
) = 0) =
L
m
(
f
(
B
+
ω
) = 0) = 0
where the first equality is because
μ
is absolutely continuous
with respect to
L
m
(it is clear that the root set of the
polynomial
f
is measurable).
Finally, by Theorem 1, we know
K
e
ˆ
e
= 0
if and only if
f
(
B
+
ω
) = 0
. This then implies
μ
(
K
e
ˆ
e
6
= 0) = 1
−
μ
(
K
e
ˆ
e
= 0) = 1
−
μ
(
f
(
B
+
ω
) = 0) = 1
and completes our proof.
A
PPENDIX
C
P
ROOF OF
P
ROPOSITION
12
Denote the two connected components of
G
after
e
is
tripped as
D
1
,D
2
. Since the injection is island-free, we know
∑
j
∈
D
1
p
i
6
= 0
and
∑
j
∈
D
2
p
i
6
= 0
, and thus the power is not
balanced in neither
D
1
nor
D
2
. We will show that
K
e
ˆ
e
6
= 0
for any
ˆ
e
within
D
1
. The case where
ˆ
e
belongs to
D
2
can be
addressed similarly.
First we consider the case where
ˆ
e
is a bridge. Denote the
two connected components of
D
1
after removing
ˆ
e
as
D
1
,
1
and
D
1
,
2
, and without loss of generality assume
D
1
,
2
is originally
connected to
e
in
G
. It is easy to see that the branch flow
change on
ˆ
e
is given by
∆
P
ˆ
e
=
∑
j
∈
D
1
,
1
δp
j
6
= 0
where the last
6
=
is because the grid is participating and thus
all tree partition regions in
D
1
,
1
would adjust their injections
(in the same “direction” as
α
j
’s are positive). As a result we
see
K
e
ˆ
e
= ∆
P
ˆ
e
/P
e
6
= 0
.
Next we consider the case where
ˆ
e
is not a bridge. In this
case,
ˆ
e
belongs to a certain tree partition region, say
N
1
. Let
n
1
,n
2
,
···
,n
l
be the set of participating buses in
N
1
. By
collapsing all regions other than
N
1
, we can define a localized
graph
G
N
1
centered around
N
1
as shown in Fig. 9. Specifically,
for each bridge
b
incident to
N
1
, we create an imaginary bus
that aggregates all injections inside all tree partition regions
that can be reached by
N
1
through
b
before
e
is tripped, and
this imaginary bus is connected to
N
1
via the corresponding
bridge
b
. If
e
is not directly incident to
N
1
, then
e
must connect
two regions that are collapsed to a common imaginary bus, say
N
t
. If
e
is incident to
N
1
and its end point in
N
1
is
n
e
, then we
let
N
t
be an additional imaginary bus that is connected to
n
e
to mimic the edge
e
(that is, before
e
is tripped, this imaginary
bus
N
t
supplies power
P
e
towards
n
e
and after
e
is tripped,
N
t
loses all its injection; moreover the edge connecting
N
t
to
n
e
has susceptance
B
e
). Denote other imaginary buses as
N
1
,
1
,
N
1
,
2
,
···
,
N
1
,q
.
Without loss of generality, let us assume because of the
tripping of
e
, the aggregate power in
D
1
is in shortage of
M
. Then the enforcement of the power balance rule
B
would
increase the power injection at each participating bus in
D
1
,
which translates to the power adjustment as demonstrated
in Fig. 9. Specifically, the injection at
N
t
would drop by
α
N
t
M
as the power flow from
e
is lost (the drop is generally
not
M
unless
e
is directly incident to
N
1
); the injections
at
N
1
,
1
,
N
1
,
2
,
···
,
N
1
,q
increase by
α
N
1
,i
M
; and injections
at the participating buses
n
1
,n
2
,
···
,n
l
in
N
1
increase by
α
n
i
M
. In other words, by rebalancing power according to
the rule
B
, we effectively shift the injections from
N
t
to
N
1
,
1
,
N
1
,
2
,
···
,
N
1
,q
and
n
1
,n
2
,
···
,n
l
.
Let the set of edges in
G
N
1
be
E
1
. Pick
N
t
to be the slack
bus in this localized graph
G
N
1
and define an index set
I
:=
{N
1
,
1
,
N
1
,
2
,
···
,
N
1
,q
,n
1
,n
2
,
···
,n
l
}
For any
i
∈ I
, let
g
i
(
B
)
be the following polynomial in line
susceptances
(
B
e
:
e
∈E
1
)
∑
E
∈T
E
1
(
{
i,w
}
,
{N
t
,z
}
)
χ
(
E
)
−
∑
E
∈T
E
1
(
{
i,z
}
,
{N
t
,w
}
)
χ
(
E
)
where
T
E
1
(
N
1
,
N
2
)
is the set of spanning forests of
G
N
1
consisting of exactly two trees that contain
N
1
and
N
2
re-
spectively (see Section II for more details on the corresponding
notion in
G
). By Proposition V.3 from our previous work [26],
the branch flow change on
ˆ
e
coming from the power shift from
N
t
with amount
α
i
M
towards
i
is given by
∆
P
i
ˆ
e
=
α
i
M
×
g
i
(
E
)
∑
E
∈T
E
1
χ
(
E
)
where
T
E
1
denotes the set of all spanning trees of
G
N
1
. Put
g
(
B
) :=
∑
i
∈I
α
i
g
i
(
B
)
By linearity, we know
∆
P
ˆ
e
=
M
×
g
(
B
)
∑
E
∈T
E
χ
(
E
)
We claim
g
(
B
)
is not identically zero. Indeed, by a similar
argument to the proof of Proposition 9, we know that for any
i,j
∈I
(including the case
i
=
j
), the following is true:
T
E
1
(
{
i,w
}
,
{N
t
,z
}
)
∩T
E
1
(
{
j,z
}
,
{N
t
,w
}
) =
∅
As a result, a term in
g
i
(
B
)
with coefficient
1
is never canceled
by a term in
g
j
(
B
)
with coefficient
−
1
, and vice versa.
Therefore, to show
g
(
B
)
is not identically zero, it suffices
to show at least one of
g
i
(
B
)
is not identically zero.
To do so, let
C
be the cell that contains
ˆ
e
. Since
N
1
is
participating with respect to
B
, we know there exists a bus
within
C
, say
n
1
, that participates the power balance and is
not a cut vertex. Recall that any path from
N
t
to
C
must go
through a common cut vertex in
C
[35], say
n
e
. Now by adding
an edge between
n
e
and
n
1
(if it does not exist originally),
the resulting cell
C
′
is still 2-connected. Thus there exists a
simple loop in
C
′
that contains the edge
(
n
e
,n
1
)
and
ˆ
e
=
(
w,z
)
, which implies we can find two disjoint paths
P
1
and
P
2
connecting the endpoints of these two edges. Without loss
of generality, assume
P
1
connects
n
e
to
w
and
P
2
connects
n
1
to
z
. By concatenating the path from
N
t
to
n
e
, we can
extend
P
1
to a path
̃
P
1
from
N
t
to
w
, which is still disjoint
from
P
2
. Now, by iteratively adding edges, we can extend
̃
P
1
and
P
2
to a spanning forest of
G
N
1
consisting of exactly two
trees, which is an element of
T
E
1
(
{
n
1
,z
}
,
{N
t
,w
}
)
. This in
particular implies
g
n
1
(
B
)
is not identically zero and therefore
g
(
B
)
is not identically zero.
Again by the classical algebraic geometry result asserting
the root set of any polynomial that is not identically zero
has Lebesgue measure zero [42], and because of the absolute
continuity of
μ
, we know
μ
(∆
P
ˆ
e
= 0) =
L
m
(
g
(
B
+
ω
) = 0) = 0
and thus
μ
(
K
e
ˆ
e
6
= 0) =
μ
(∆
P
ˆ
e
6
= 0) = 1
This completes our proof.
(a) Original influence graph.
(b) The influence graph after switching off
e
1
,
e
2
and
e
3
. The black dashed line indicates the failure propagation boundary defined
by the tree partition. The vertices
c
1
and
c
2
are cut vertices.
Fig. 7. Influence graphs on the IEEE 118-bus network before and after switching off lines
e
1
,
e
2
and
e
3
. Blue edges represent physical transmission lines
and grey edges represent connections in the influence graph.
(a)
(b)
Fig. 8. (a) Histogram of the normalized branch flow changes. (b) Cumulative
distribution function of the positive normalized branch flow changes. Note that
the curve intercepts the
y
-axis since
52
.
59%
of the branch flows decrease.
Fig. 9. The localized graph
G
N
1
.
N
t
is the imaginary bus containing
e
and
N
1
,i
’s are remaining imaginary buses. The power adjustments from the power
balance rule
B
are shown near each participating bus in reaction to a power
loss of
M
.