consideration (see [22] for a detailed overview), but it is largely dominated
by $\tau(G_{\mathcal{P}})$, the number of spanning trees of $G_{\mathcal{P}}$,
that increases exponentially in the graph size $b$.

This latter issue disappears if the selected target partition $\mathcal{P}$
consists of only two clusters, say $\mathcal{V}_{1}$ and $\mathcal{V}_{2}$, as
the reduced multi-graph $G_{\mathcal{P}}$ has a number of spanning trees at
most linear in the number of edges of the original network $G$. Indeed, in
this case any spanning tree for $G_{\mathcal{P}}$ consists of a single cross-
edge in $E_{c}(\mathcal{P})$. Therefore, selecting a subset
$\mathcal{E}\subset E_{c}(\mathcal{P})$ of cross-edges between
$\mathcal{V}_{1}$ and $\mathcal{V}_{2}$ feasible for the OBS problem is
equivalent to choosing the unique cross-edge $e\in E_{c}(\mathcal{P})$ to
keep, which become the unique bridge of the reduced graph
$(G^{\mathcal{E}})_{\mathcal{P}}$. Thus the number of feasible sets
$\mathcal{E}$ for the OBS problem is precisely equal to that of the cross-
edges, and, trivially, $|E_{c}(\mathcal{P})|\leq|E|$. Restricting ourselves to
bi-partitions $\mathcal{P}\in\Pi_{2}(G)$, the OBS problem (30) becomes

$\min_{e\in E_{c}(\mathcal{P})}\gamma(E_{c}(\mathcal{P})\backslash\\{e\\}).$
(31)

where the constraint (30b) disappears because
$(G^{\mathcal{E}})_{\mathcal{P}}$ is always trivially a tree in this case.
This optimization problem is much simpler and faster to solve than the
original one: instead of optimizing over a complex combinatorial object,
namely the family of spanning trees of the reduced graph $G_{\mathcal{P}}$,
the feasible set is just the collection of cross-edges $E_{c}(\mathcal{P})$.

This fact suggests the idea that it may be computationally more efficient to
refine the bridge-block decomposition progressively, splitting the current
largest bridge-block into two smaller bridge-blocks in a recursive fashion. We
thus propose a second algorithm that leverages this idea. Besides drastically
simplifying the structure of the OBS problem to be solved, this recursive
approach embeds a natural stopping rule for the bridge-block decomposition
refinement. As we hinted at already, it is impossible to estimate a priori how
much the bridge-block decomposition of a power network can be refined without
creating congestion on any line. In this respect, a procedure that increases
the number of blocks by one at each step while monitoring the network
congestion level can help find the best trade-off between the number of
bridge-blocks and network congestion level. We introduce the following
stopping rule. We keep refining the bridge-block decomposition splitting the
largest bridge-block in a recursive fashion as long as:

  * (i)

the current maximum number of splits is less than a predefined threshold
$i_{\mathrm{max}}\in\mathbb{N}$, and

  * (ii)

the obtained network congestion level $\gamma^{*}$ is not larger than a
threshold $\delta\in(0,1]$ describing the maximum tolerable congestion that
the network operator can set.

The high-level structure of the proposed recursive procedure is shown in
Algorithm 2.

Input : A power network $G=(V,E,\bm{b})$, a maximum number of iterations
$i_{\mathrm{max}}$, and a congestion threshold $\delta$

1 Set $i=0$;

2 Set $E_{0}=E$ and $G_{0}=(V,E_{0})$;

3 Calculate the line flows $\bm{f}_{0}$ and the current network congestion
level $\gamma_{0}^{*}:=\gamma(\emptyset)$;

4 while  _$\gamma^{*}_{i} <\delta$ and $i<i_{\mathrm{max}}$_ do

5 Calculate the current bridge-block decomposition
$\mathcal{B}\mathcal{B}(G_{i})$;

6 Consider in isolation the largest bridge-block in size of the current
bridge-block decomposition, say $\mathcal{V}\in\mathcal{B}\mathcal{B}(G_{i})$;

7 Solve a OBI-2 problem for $\mathcal{V}$ in isolation to find its optimal
bipartition $\mathcal{P}^{*}_{i}$;

8 Solve the simplified OBS problem (31) for $\mathcal{V}$ in isolation with
target bipartition $\mathcal{P}^{*}_{i}$, obtaining an optimal subset
$\mathcal{E}^{*}_{i}\subset E_{c}(\mathcal{P}^{*}_{i})$ and the new network
congestion level $\gamma^{*}_{i}=\gamma(\mathcal{E}^{*}_{i})$;

9 Calculate the new set of active lines to be
$E_{i+1}:=E_{i}\setminus\mathcal{E}^{*}_{i}$ and set $G_{i+1}=(V,E_{i+1})$;

10 Increase $i$ by $1$;

11

12 end while

Output : $i$, $G_{i}$, $\mathcal{B}\mathcal{B}(G_{i})$, $\gamma^{*}_{i}$

Algorithm 2 Recursive bridge-block decomposition refinement

Note that in Step 6 we select the current largest bridge-block to be further
split, so that all the bridge-blocks progressively become smaller, indirectly
ensuring that, when the algorithm stops, the sizes of the resulting bridge-
blocks are similar. However, we could tweak the algorithm to select either (i)
the bridge-block with the lowest congestion level (inside which is probably
safer to switch off lines without creating overloads) or (ii) the one with the
highest potential to be clustered in terms of modularity score. Both these
approaches, however, could possibly lead to ineffective bridge-block
decompositions, where there are still very large bridge-blocks and several
small (trivial) ones.

The OPS problem needs to be solved several times in this recursive variant
(and not only once as prescribed in the one-shot variant, Algorithm 1), which
means that Algorithm 2 requires possibly many more power flows calculations.
However, a remarkable feature of the recursive approach is that all these
power flow redistribution calculations can be done “locally” (i.e., inside the
bridge-block that is being split) and thus become progressively faster as the
size of the largest bridge-block decreases. More specifically, let
$\mathcal{V}$ be the bridge-block selected to be further split in Step 6 of
Algorithm 2. By virtue of Proposition 4.4, any switching action (which is
effectively equivalent to line failure in this context) inside the bridge-
block $\mathcal{V}$ does not affect the line flows in any other bridge-block
$\mathcal{V}^{\prime}\neq\mathcal{V}$ of the current bridge-block
decomposition. Therefore, only the line flows inside $\mathcal{V}_{i}$ needs
to be recalculated and this can be done by solving the DC power flow equations
(3) only for the subgraph induced by $\mathcal{V}$ and the corresponding local
power injections. The only caveat is that we need to adjust the net power at
all the nodes of $\mathcal{V}$ that are endpoints of bridges to account for
the outgoing flow.

Adopting this recursive splitting strategy, the bridge-blocks become smaller
at every iteration, which in turn means that fewer flows (and congestion
levels) need to be recalculated at each step when solving the OBS problem
(31), making it increasingly faster to solve.

The recursive structure also makes Step 10 of Algorithm 2 faster: the bridge-
block decomposition does not have to be recomputed globally, since all the
bridge-blocks but the one considered in this iteration will be unchanged and
we only need to identify the new bridge-blocks created locally. We remark that
this step cannot be skipped as the optimal set of switch action may
accidentally split the considered bridge-block into more than two bridge-
blocks.

Figs. 6 and 7 visualize the various steps that Algorithm 2 takes when set with
$i_{\mathrm{max}}=2$ and applied to the same network considered in Fig. 5,
namely the IEEE 73-bus network. It is clear that the OBS problem is
essentially trivial for the recursive algorithm in both steps, see Figs. 6(d)
and 7(b), while it was more involved for the one-shot algorithm, cf. Fig.
5(d).

(a) The graph $G_{0}$ corresponding to IEEE 73 network with its bridge-block
decomposition $\mathcal{B}\mathcal{B}(G_{0})$ consisting of three bridge-
blocks, two of which are trivial.

(b) The bridge-block tree of $G_{0}$, i.e., the reduced graph
$(G_{0})_{\mathcal{B}\mathcal{B}(G_{0})}$ corresponding to the bridge-block
decomposition of the network in (a)

(c) The biggest bridge-block of the network in (a) is split into 2 clusters by
solving a simplified OBI-$2$ problem, obtaining a finer partition
$\mathcal{P}^{*}_{0}$. The cross-edges of $\mathcal{P}^{*}_{0}$ inside the
original bridge-block are highlighted in red.

(d) The reduced graph $G_{\mathcal{P}^{*}_{0}}$ corresponding to the optimal
partition $\mathcal{P}^{*}_{0}$ in (c), with the set
$E_{c}(\mathcal{P}^{*}_{0})$ of its cross-edges highlighted in red. The
spanning trees of $G_{\mathcal{P}^{*}_{0}}$ (and thus the feasible switching
actions) to consider do not grow exponentially with the size of
$G_{\mathcal{P}^{*}_{0}}$, being in one-to-one correspondence with
$E_{c}(\mathcal{P}^{*}_{0})$.

(e) The network $G_{1}$ obtained after switching off the cross-edges in
$\mathcal{E}^{*}_{0}$. The vertex colors display its bridge-block
decomposition $\mathcal{B}\mathcal{B}(G_{1})$, which is finer than the
original one $\mathcal{B}\mathcal{B}(G_{0})$.

(f) The bridge-block tree of $G_{1}$, i.e., the reduced graph
$(G_{1})_{\mathcal{B}\mathcal{B}(G_{1})}$ corresponding to the new bridge-
block decomposition of the post-switching network $G_{1}$ in (e).

Figure 6: Recursive algorithm at work – first iteration $i=1$

(a) The biggest bridge-block of the network $G_{1}$ in Fig. 6(e) is split into
2 clusters by solving a simplified OBI-$2$ problem, obtaining a finer
partition $\mathcal{P}^{*}_{1}$. The cross-edges of $\mathcal{P}^{*}_{1}$
inside the original bridge-block are highlighted in red.

(b) The reduced graph $(G_{1})_{\mathcal{B}\mathcal{B}(G_{1})}$ corresponding
to the bridge-block decomposition of the network in (a)

(c) The network $G_{2}$ obtained after switching off the cross-edges in
$\mathcal{E}^{*}_{1}$. The vertex colors display its bridge-block
decomposition $\mathcal{B}\mathcal{B}(G_{2})$, which is finer than the
previous one $\mathcal{B}\mathcal{B}(G_{1})$

(d) The bridge-block tree of $G_{2}$, i.e., the reduced graph
$(G_{2})_{\mathcal{B}\mathcal{B}(G_{2})}$ corresponding to the new bridge-
block decomposition of the post-switching network $G_{2}$ in (c).

Figure 7: Recursive algorithm at work – second iteration $i=2$

Both the one-shot and the recursive algorithms focus on the scenario where the
power injections are fixed. However, in practical settings the network
operator could jointly reconfigure the network topology by means of switching
actions and adjust (some of) the power injections, either by shedding load or
by adjusting generator levels. In this scenario, the OBS problem could
potentially find a solution with an even lower network congestion level, but
analyzing this joint optimization problem or proposing heuristics leveraging
this additional injection flexibility is beyond the scope of this paper.

We remark that one such possible strategy, in the spirit of [87], is aiming
for local power adjustments and only change the power injections at the
endpoints of each line that is being switched off by an amount exactly equal
to its original flow on that line. This strategy would guarantee that the
power flows on the entire surviving network will be unchanged and no
congestion will be created. However, there might not be enough flexibility in
terms of injection adjustment in each pair of endpoints. Alternatively, one
can solve a global OPF problem for the whole network after the switching
actions, hence ensuring that no line will be overloaded. Even better results
could be obtained when considering the line switching and power injection
adjustment jointly in the same optimization problem.

##  6 Numerical examples

This section is devoted to the implementation of the bridge-block
decomposition refinement strategy introduced in Section 5. In Subsection 6.1
we first review the structural properties of several power grids used in the
literature as test networks, from which it becomes evident the need of finer
and more homogeneous bridge-blocks for these networks. In Subsection 6.2 we
introduce two fast approximations algorithms to find locally optimal solutions
for the OBI problem (23) and compare their performance on IEEE test networks
in terms of the clusters’ size and cross-edges. Then, in Subsection 6.3, we
compare the performances of the one-shot algorithm and of its recursive
variant for the same test networks.

###  6.1 Preliminary analysis of power systems topologies

In order to show the potential benefits of applying our method for improving
network reliability, it is important to first understand the relevant
structural properties of typical power networks, in particular their bridge-
block decomposition. In Table 2 below we report statistics about the original
topologies of various standard test networks taken from [4, 25]. For each of
these networks, we find all its bridges and calculate its bridge-block
decomposition. Modulo some minor variations, all the networks exhibit the same
topological features, namely:

  * •

They have only one giant bridge-block that comprises a vast majority of the
network nodes;

  * •

They have substantial number of edges that are bridges (on average roughly
$18\%$), each of them connecting a trivial bridge-block (consisting of one or
two nodes) to the aforementioned giant bridge-block.

These features are also easily recognizable for the IEEE 118-bus network
displayed in Fig. 3. From these statistics it is clear that most power
networks have an essentially trivial bridge-block decomposition and would thus
perform very poorly in terms of failure localization. In particular, a line
failure inside the unique giant bridge-block could propagate to roughly $80\%$
of the other lines (i.e., those in the same bridge-block). Moreover, we note
that all these networks already have a surprisingly large fraction (on average
$\sim 18\%$) of lines that are bridges, which the switching actions prescribed
by our method would increase only marginally.

Test network case | # of edges | # of bridges |  % of edges that are bridges | # of bridge-blocks |  Size(s) of non-trivial bridge-blocks
---|---|---|---|---|---
case14_ieee | 20 | 1 |  5.00 | 2 |  13
case30_ieee | 41 | 3 |  7.32 | 4 |  27
case39_epri | 46 | 11 |  23.91 | 12 |  28
case57_ieee | 80 | 1 |  1.25 | 2 |  56
case73_ieee_rts | 120 | 2 |  1.67 | 3 |  71
case89_pegase | 210 | 16 |  7.62 | 17 |  73
case118_ieee | 186 | 9 |  4.84 | 10 |  109
case162_ieee_dtc | 284 | 12 |  4.22 | 13 |  150
case179_goc | 263 | 43 |  16.35 | 44 |  136
case200_activ | 245 | 72 |  29.39 | 73 |  128
case240_pserc | 448 | 58 |  12.95 | 59 |  182
case300_ieee | 411 | 89 |  21.65 | 90 |  206, 3, 3
case588_sdet | 686 | 229 |  33.38 | 230 |  357
case793_goc | 913 | 290 |  31.76 | 291 |  500
case1354_pegase | 1991 | 561 |  28.18 | 562 |  791
case1888_rte | 2531 | 964 |  38.09 | 965 |  918, 5
case2000_goc | 3633 | 445 |  12.25 | 446 |  1555
case2736sp_k | 3273 | 627 |  19.16 | 628 |  2109
case2737sop_k | 3274 | 627 |  19.15 | 628 |  2110
case2746wp_k | 3281 | 637 |  19.41 | 638 |  2109
case2746wop_k | 3309 | 607 |  18.34 | 608 |  2139
case2848_rte | 3776 | 1410 |  37.34 | 1411 |  1421, 7, 5, 3
case2869_pegase | 4582 | 778 |  16.98 | 779 |  2088
case3120sp_k | 3693 | 731 |  19.79 | 732 |  2382, 8
case3375wp_k | 4161 | 826 |  19.85 | 827 |  2536, 3
case9241_pegase | 16049 | 1665 |  10.37 | 1666 |  7558, 7, 5, 3
Table 2: Summary of bridge and bridge-block statistics for various test
networks. A bridge-block is considered to be non-trivial is it consists of
strictly more than two nodes.

###  6.2 Bridge-block candidate identification

The OBI problem that we introduced in Section 5.1 to find good candidate
bridge-blocks is a variant of the well-known weighted network modularity
maximization. However, this optimization problem cannot be solved exactly,
being NP-hard, especially for large power networks and we need to resort to
locally optimal partition. Before presenting our numerical findings, we first
briefly review the two approximation algorithms that we implemented, namely
the fastgreedy method and the spectral clustering.

Fastgreedy. A very fast approximation algorithm for optimizing modularity on
large networks was proposed by [24]. It uses a bottom-up hierarchical approach
that tries to optimize the modularity in a greedy manner. Initially, every
vertex belongs to a separate community, and communities are merged iteratively
such that each merger is locally optimal (i.e., yields the largest increase in
the current value of modularity). We use the Python library $\mathrm{igraph}$
and the built-in implementation of $\mathrm{fastgreedy}$ modularity
optimization algorithm described in [24], which also implements some
improvements proposed by [142].

Spectral clustering. Spectral clustering was first used in the context of
modularity maximization by [104, 105] and has become one of the most popular
modern clustering algorithms, being simple to implement and very efficient to
solve using standard linear algebra software. In our implementation of this
method we use two matrices that simultaneously capture the network structure
and flow pattern, the modularity matrix and the weighted Laplacian matrix.
They can be both calculated from the graph $G=(V,E)$ with edge weights equal
the absolute power flows $\\{|f_{ij}|\\}_{(i,j)\in\mathcal{E}}$ as follows:

  * •

the modularity matrix $B$, whose $(i,j)$ entry is
$B_{i,j}=|f_{ij}|-\frac{F_{i}F_{j}}{2M}$, and

  * •

the weighted Laplacian matrix $L$, whose entries are $L_{i,j}=-|f_{ij}|$ if
$i\neq j$ and $L_{i,i}=-\sum_{j\neq i}L_{i,j}$.

In both cases we choose to work with their normalized counterparts, namely

$B_{n}:=W^{-1/2}BW^{-1/2}\qquad\text{ and }\qquad L_{n}:=W^{-1/2}LW^{-1/2},$

where $W=\mathrm{diag}(F_{1},\dots,F_{n})$, since, especially in graphs of
large size or with very heterogeneous weights, it has been argued that the
spectral clustering method is more effective and computationally more stable
when using the normalized version of these matrices, see [12, 140].

The spectral clustering performed on the normalized Laplacian matrix $L_{n}$
approximates the optimal solution of the NP-hard problem known as Normalized
Cut (NCut). Working with the normalized modularity matrix $B_{n}$ means that
the spectral clustering method approximates the partition that maximizes a
renormalized version $Q_{n}$ of the network modularity, namely

$Q_{n}(\mathcal{P}):=\frac{1}{2M}\sum_{r=1}^{|\mathcal{P}|}\frac{1}{\sum_{k\in\mathcal{V}_{r}}|F_{k}|}\sum\limits_{i,j\in\mathcal{V}_{r}}\left(|f_{ij}|-\frac{F_{i}F_{j}}{2M}\right).$

If we fix the target number $b$ of clusters the optimal normalized modularity
clustering is equal to the normalized cut clustering, in the sense that
$\arg\max_{\mathcal{P}}Q_{n}(\mathcal{P})=\arg\min_{\mathcal{P}}\mathrm{NCut}(\mathcal{P})$.
This follows from the identity

$Q_{n}(\mathcal{P})=\frac{b-1}{2M}-\frac{1}{2M}\mathrm{NCut}(\mathcal{P}),$

proved in [12, 151] under the assumption that the target number $b$ of
clusters is fixed. This means that the spectral clustering method performed on
either matrix $B_{n}$ and $L_{n}$ solve approximately the same optimization
problem. However, having different eigensystems, they often yield to slightly
different results. For this reason, we consider both of these two variants of
the spectral clustering approximation method in the following subsection and
label them as Spectral $L_{n}$ and Spectral $B_{n}$.

We remark that the authors in [135] also adopt the normalized-Laplacian-based
spectral clustering to power systems, proposing several choices for the edge
weights, including the one we adopted in this paper, i.e., the absolute value
of power flows. In the same paper, some heuristics are outlined to decide the
optimal number of clusters in which to partition the network, but these
leverage the eigensystem structure of the Laplacian matrix, rather than being
informed by a specific target number of clusters $b$ like in our method.

####  6.2.1 Performance comparison

We compare the performance of the three aforementioned clustering methods
(FastGreedy, Spectral $L_{n}$ and Spectral $B_{n}$) to optimally partition
some standard IEEE test cases available in the pglib-opf library [4, 25]. We
consider four networks of various sizes, ranging from small (39 nodes) to
large (2737 nodes).

We first consider the quality of the network partitions returned by three
methods by looking exclusively at graph-related quantities. In the following
tables, we report for different target number $b$ of clusters the normalized
modularity score $Q_{n}$ (the higher the better) of the partition returned by
each algorithm, as well as the sizes of the $b$ clusters and the fraction of
edges that are cross-edges between them. We further report the number of
cross-edges to be switched off to obtained a bridge-block decomposition with
the identified clusters as bridge-blocks. Recall that, as we argued in Section
5.1, it is highly desirable to have a small number of cross-edges between the
identified clusters, since it dramatically reduces the feasible sets of
switching actions for the OBS problem.

Clustering method |  runtime (sec) | $b$ |  $Q_{n}$ |  fraction of cross-edges |  #lines to be switched off |  resulting partition of the largest bridge-block
---|---|---|---|---|---|---
Spectral $L_{n}$ |  0.0192 | 2 |  0.379 |  0.0869 |  3 |  [10, 18]
Spectral $B_{n}$ |  0.0186 | 2 |  0.406 |  0.0652 |  2 |  [11, 17]
FastGreedy |  0.0016 | 2 |  0.406 |  0.0652 |  2 |  [11, 17]
Spectral $L_{n}$ |  0.0247 | 3 |  0.486 |  0.152 |  5 |  [9, 9, 10]
Spectral $B_{n}$ |  0.0210 | 3 |  0.501 |  0.130 |  4 |  [8, 9, 11]
FastGreedy |  0.0018 | 3 |  0.524 |  0.109 |  3 |  [7, 10, 11]
Spectral $L_{n}$ |  0.0306 | 4 |  0.513 |  0.173 |  5 |  [4, 7, 8, 9]
Spectral $B_{n}$ |  0.0291 | 4 |  0.527 |  0.196 |  5 |  [4, 7, 8, 9]
FastGreedy |  0.0027 | 4 |  0.535 |  0.152 |  4 |  [4, 7, 7, 10]
Table 3: 39 EPRI Clustering method |  runtime (sec) | $b$ |  $Q_{n}$ |  fraction of cross-edges |  #lines to be switched off |  resulting partition of largest bridge-block
---|---|---|---|---|---|---
Spectral $L_{n}$ |  0.0255 | 2 |  0.220 |  0.032 |  5 |  [28, 81]
Spectral $B_{n}$ |  0.0294 | 2 |  0.390 |  0.032 |  5 |  [40, 69]
FastGreedy |  0.0032 | 2 |  0.427 |  0.075 |  13 |  [50, 59]
Spectral $L_{n}$ |  0.0338 | 3 |  0.490 |  0.053 |  8 |  [27, 33, 49]
Spectral $B_{n}$ |  0.0341 | 3 |  0.518 |  0.059 |  9 |  [29, 38, 42]
FastGreedy |  0.0061 | 3 |  0.527 |  0.102 |  17 |  [16, 34, 59]
Spectral $L_{n}$ |  0.0366 | 4 |  0.498 |  0.075 |  11 |  [9, 19, 33, 48]
Spectral $B_{n}$ |  0.0477 | 4 |  0.540 |  0.102 |  16 |  [18, 21, 29, 41]
FastGreedy |  0.0381 | 4 |  0.620 |  0.140 |  23 |  [16, 27, 32, 34]
Table 4: IEEE 118 Clustering method |  runtime (sec) | $b$ |  $Q_{n}$ |  fraction of cross-edges |  #lines to be switched off |  resulting partition of largest bridge-block
---|---|---|---|---|---|---
Spectral $L_{n}$ |  0.912 | 2 |  0 |  0.0008 |  1 |  [1, 917]
Spectral $B_{n}$ |  0.844 | 2 |  0.483 |  0.0107 |  26 |  [391, 527]
FastGreedy |  0.443 | 2 |  0.489 |  0.0130 |  32 |  [415, 503]
Spectral $L_{n}$ |  7.536 | 3 |  0.610 |  0.0217 |  51 |  [168, 356, 394]
Spectral $B_{n}$ |  1.201 | 3 |  0.648 |  0.0194 |  46 |  [273, 308, 337]
FastGreedy |  0.461 | 3 |  0.617 |  0.0198 |  48 |  [205, 298, 415]
Spectral $L_{n}$ |  8.167 | 4 |  0.709 |  0.0221 |  52 |  [187, 189, 222, 320]
Spectral $B_{n}$ |  5.693 | 4 |  0.709 |  0.0205 |  48 |  [157, 204, 261, 296]
FastGreedy |  1.028 | 4 |  0.724 |  0.0217 |  52 |  [153, 205, 262, 298]
Table 5: 1888rte Clustering method |  runtime (sec) | $b$ |  $Q_{n}$ |  fraction of cross-edges |  #lines to be removed |  resulting partition of largest bridge-block
---|---|---|---|---|---|---
Spectral $L_{n}$ |  3.949 | 2 |  0.375 |  0.0076 |  24 |  [674, 1436]
Spectral $B_{n}$ |  2.702 | 2 |  0.379 |  0.0058 |  18 |  [690, 1420]
FastGreedy |  0.606 | 2 |  0.461 |  0.0489 |  159 |  [1000, 1110]
Spectral $L_{n}$ |  4.394 | 3 |  0.640 |  0.0150 |  47 |  [659, 698, 753]
Spectral $B_{n}$ |  2.837 | 3 |  0.640 |  0.0159 |  50 |  [667, 702, 741]
FastGreedy |  0.987 | 3 |  0.632 |  0.0516 |  167 |  [410, 590, 1110]
Table 6: Polish 2737sop

In the vast majority of the considered cases, the two spectral clustering
methods yield partitions with smaller values of the normalized modularity
$Q_{n}$ with respect to the FastGreedy method, which, however, consistently
returns partitions with a larger number of cross-edges than the other two
methods. In our experiments, the FastGreedy method is considerably (2x-10x
times) faster than the two spectral clustering methods.

FastGreedy has the advantage that all the partitions for various $b$ are
calculated jointly because the algorithm is nested in that each partition of
size $b$ is obtained from the corresponding one of size $b-1$ by optimally
dividing one of the clusters into two. This recursive nature of the FastGreedy
method makes it faster, but at times it means that partitions with unbalanced
clusters sizes could be returned. On the other hand, the two spectral
clustering methods almost always identify partitions with clusters of balanced
size.

In the cases considered above, all methods always yield partitions with
exactly $b$ connected clusters. It is possible that the actual number of
identified connected clusters could be strictly larger than $b$ because some
of them induce network subgraphs that are disconnected, violating our
assumption (A1). This occurs very rarely as the OBI objective function
severely penalizes such partitions, but even so it would not be an issue as it
would lead to a finer bridge-block decomposition.

###  6.3 Performance of one-shot and recursive algorithms

We first illustrate the numerical results for the one-shot algorithm, i.e.,
Algorithm 1, for various test networks. More specifically, for each network we
solve the OBS problem (30a) three times, using the (possibly different)
optimal partition $\mathcal{P}$ into $b$ clusters returned by each of the
three different clustering algorithms (cf. Subsection 6.2). Recall that there
is a one-to-one correspondence between the feasible subsets of cross-edges
$\mathcal{E}\subset E_{c}(\mathcal{P})$ and the spanning trees of the reduced
multi-graph $G_{\mathcal{P}}$. This means that the one-shot algorithm cannot
be solve exactly already for partitions into $b\geq 5$ clusters, since the
spanning trees of the reduced multi-graph grow exponentially with $b$.
However, if we consider a small number of target clusters, say $b\leq 4$, we
can still solve the OBS exactly by considering all possible spanning tree of
$G_{\mathcal{P}}$.

As pre-processing step, for each of the considered networks we first run a DC-
OPF to obtain the power flow configuration and calculate the initial network
congestion level $\gamma(\emptyset)$ (which is possibly equal to $1$ if one or
more line limits are active for the OPF solution). We then run Algorithm 1
with $b=4$ using the three different clustering methods discussed in the
previous section. Table 7 below reports for each network both the initial
congestion level $\gamma(\emptyset)$ and the results of the one-shot algorithm
ran with $b=4$ as target number of clusters. More specifically, for each
network and each clustering algorithm, we report

  * •

the runtime,

  * •

the number of spanning trees of $G_{\mathcal{P}}$ considered,

  * •

the optimal post-switching network congestion level $\gamma(\mathcal{E}^{*})$,

  * •

the number of lines that to be switched off for the optimal set of switching
actions $\mathcal{E}^{*}$ and which fraction they represent on the total
number of network lines.

network |  partition method |  runtime (sec) |  # spanning trees |  $\gamma(\mathcal{E}^{*})$ |  # congested lines |  # of lines switched off |  $\%$ of lines switched off
---|---|---|---|---|---|---|---
case39_epri | initial network configuration |  - |  1.000 |  2 |  - |  -
Spectral $L_{n}$ |  0.238 |  10 |  0.960 |  0 |  3 |  6.52
Spectral $B_{n}$ |  0.270 |  10 |  0.960 |  0 |  3 |  6.52
FastGreedy |  0.245 |  12 |  0.833 |  0 |  3 |  6.52
case57_ieee | initial network configuration |  - |  0.938 |  0 |  - |  -
Spectral $L_{n}$ |  6.210 |  220 |  1.050 |  2 |  13 |  16.25
Spectral $B_{n}$ |  5.454 |  216 |  1.078 |  2 |  12 |  15.00
FastGreedy |  6.829 |  256 |  0.921 |  0 |  14 |  17.50
case73_ieee | initial network configuration |  - |  0.632 |  0 |  - |  -
Spectral $L_{n}$ |  1.330 |  49 |  1.171 |  1 |  8 |  6.66
Spectral $B_{n}$ |  2.010 |  71 |  1.171 |  3 |  10 |  10.83
FastGreedy |  0.970 |  31 |  0.723 |  0 |  6 |  5.00
case118_ieee | initial network configuration |  - |  1.000 |  2 |  - |  -
Spectral $L_{n}$ |  1.912 |  80 |  1.004 |  2 |  10 |  5.38
Spectral $B_{n}$ |  2.259 |  80 |  1.016 |  3 |  10 |  5.38
FastGreedy |  7.958 |  264 |  2.248 |  8 |  18 |  9.68
case179_goc | initial network configuration |  - |  1.000 |  4 |  - |  -
Spectral $L_{n}$ |  1.699 |  54 |  1.243 |  7 |  7 |  2.66
Spectral $B_{n}$ |  10.358 |  312 |  1.035 |  2 |  13 |  4.94
FastGreedy |  2.103 |  69 |  1.000 |  1 |  9 |  3.42
case200_activ | initial network configuration |  - |  0.708 |  0 |  - |  -
Spectral $L_{n}$ |  6.541 |  196 |  0.591 |  0 |  15 |  6.12
Spectral $B_{n}$ |  9.146 |  312 |  0.591 |  0 |  16 |  6.53
FastGreedy |  6.863 |  208 |  0.591 |  0 |  12 |  4.90
case300_ieee | initial network configuration |  - |  1.000 |  11 |  - |  -
Spectral $L_{n}$ |  3.610 |  120 |  1.220 |  7 |  12 |  2.92
Spectral $B_{n}$ |  14.275 |  468 |  1.058 |  5 |  14 |  3.41
FastGreedy |  37.212 |  1112 |  1.161 |  6 |  24 |  5.84
Table 7: Results obtained by the one-shot algorithm with $b=4$ target clusters
using three different methods for the candidate bridge-blocks identification.
We highlight in bold the best method and the resulting post-switching
congestion $\gamma(\mathcal{E}^{*})$ for each network.

From Table 7 we deduce that the resulting post-switching network congestion
level varies a lot depending on the test network and partition method. In
particular, in a few instances the maximum congestion is strictly bigger than
$1$, but when considering all three methods, there is always at least one
solution that does not increase the congestion significantly. Furthermore, in
many instances the post-switching network congestion level even decreases with
respect to the initial configuration and so does the number of congested
lines.

We did not run the one-shot algorithm on larger networks, as it would have
required a substantially (exponentially) larger amount of time. This is not a
surprise, in view of the discussion in Section 5.3 regarding the feasible
region of the OBS problem. Indeed, the runtime of Algorithm 1 does not depend
on the network size per-se, but rather on the the number of spanning trees of
the reduced graph $G_{\mathcal{P}}$ corresponding to the optimal partition
$\mathcal{P}$ identified by each of the three methods. This makes the runtime
of the one-shot algorithm rather unpredictable, discouraging its usage in real
time.

Let us now focus on the performance of the recursive algorithm, i.e. Algorithm
2. In Table 8 below, we report the results for the same test networks
considered in Table 7 s well as a few more networks of larger size. Indeed,
the running time of the recursive algorithm depends solely on the number of
spanning trees that needs to be considered in the OBS problem. By design, for
the recursive algorithm this number is in most cases very small even for large
networks, as we can deduce from the second last column of Table 8. Indeed for
the recursive algorithm the number of considered spanning trees is equal to
the number of cross-edges of the selected bipartition, which is in turn equal
to one plus the number of lines switched off.

For each test network, we run the recursive algorithm with
$i_{\mathrm{max}}=3$, reporting the runtime of each of these three iterations.
This choice for $i_{\mathrm{max}}$ allows us to make a fair comparison with
the one-shot algorithm with a target of $b=4$ clusters, since we expect the
same number of resulting bridge-blocks (modulo “spontaneous” splits in smaller
bridge-blocks).

network |  iteration |  runtime (sec) |  $\gamma(\mathcal{E}^{*})$ |  # congested lines |  # of lines switched off |  $\%$ of lines switched off
---|---|---|---|---|---|---
case39_epri |  initial configuration |  - |  $\gamma(\emptyset)=1.000$ |  2 |  - |  -
1 |  0.091 |  0.794 |  0 |  2 |  4.35
2 |  0.069 |  0.833 |  0 |  1 |  2.17
3 |  0.082 |  0.833 |  0 |  1 |  2.17
final |  0.242 |  0.833 |  0 |  4 |  8.70
case57_ieee |  initial configuration |  - |  $\gamma(\emptyset)=0.938$ |  0 |  - |  -
1 |  0.371 |  1.038 |  2 |  10 |  12.5
2 |  0.142 |  1.038 |  2 |  3 |  3.75
3 |  0.085 |  1.038 |  2 |  1 |  1.25
|  final |  0.598 |  1.038 |  2 |  14 |  17.5
case73_ieee |  initial configuration |  - |  $\gamma(\emptyset)=0.632$ |  0 |  - |  -
1 |  0.076 |  0.778 |  0 |  1 |  0.83
2 |  0.099 |  0.772 |  0 |  2 |  1.67
3 |  0.156 |  0.694 |  0 |  4 |  3.33
|  final |  0.242 |  0.694 |  7 |  6 |  5.83
case118_ieee |  initial configuration |  - |  $\gamma(\emptyset)=1.000$ |  2 |  - |  -
1 |  0.278 |  1.011 |  2 |  5 |  2.69
2 |  0.168 |  1.045 |  2 |  4 |  2.15
3 |  0.135 |  1.045 |  2 |  3 |  1.61
|  final |  0.581 |  1.045 |  2 |  12 |  6.45
case179_goc |  initial configuration |  - |  $\gamma(\emptyset)=1.000$ |  4 |  - |  -
1 |  0.148 |  1.382 |  5 |  3 |  1.14
2 |  0.154 |  1.382 |  5 |  2 |  0.76
3 |  0.251 |  1.382 |  5 |  6 |  2.28
|  final |  0.553 |  1.382 |  5 |  11 |  4.18
case200_activ |  initial configuration |  - |  $\gamma(\emptyset)=0.708$ |  0 |  - |  -
1 |  0.221 |  0.591 |  0 |  5 |  2.04
2 |  0.281 |  0.591 |  0 |  8 |  3.26
3 |  0.141 |  0.605 |  0 |  3 |  1.22
|  final |  0.643 |  0.605 |  0 |  16 |  6.52
case300_ieee |  initial configuration |  - |  $\gamma(\emptyset)=1.000$ |  11 |  - |  -
1 |  0.509 |  1.161 |  5 |  12 |  2.91
2 |  0.223 |  1.161 |  5 |  3 |  0.73
3 |  0.386 |  1.197 |  7 |  8 |  1.95
|  final |  1.118 |  1.197 |  7 |  23 |  5.59
case1888_rte |  initial configuration |  - |  $\gamma(\emptyset)=1.000$ |  14 |  - |  -
1 |  4.567 |  0.869 |  0 |  48 |  1.89
2 |  1.994 |  0.869 |  0 |  9 |  0.36
3 |  2.694 |  0.869 |  0 |  24 |  0.95
|  final |  9.225 |  0.869 |  0 |  81 |  3.20
case2735_sop |  initial configuration |  - |  $\gamma(\emptyset)=1.000$ |  1 |  - |  -
1 |  12.57 |  0.964 |  0 |  116 |  3.54
2 |  1.317 |  0.964 |  0 |  19 |  0.58
3 |  2.145 |  2.637 |  13 |  33 |  1.00
|  final |  16.032 |  2.637 |  13 |  168 |  5.12
Table 8: Results obtained by the recursive algorithm stopped after $3$
iterations using the FastGreedy method for the candidate bridge-blocks
identification.

By comparing Tables 7 and 8 it is clear that among the two algorithms, the
one-shot algorithm is the one with slightly better performance, as it yields
lower network congestion level for almost all the test networks considered. On
the other hand, the recursive algorithm still yields good results (even when
using only the FastGreedy method for the first subproblem), but it is orders
of magnitude faster.

##  7 Concluding remarks & future directions

In this paper, we proposed a novel spectral representation of power systems
which captures the topological and physical interactions within a power grid.
Particularly, we illustrated that the graph Laplacian is of importance to
characterize the power distributions. This spectral perspective further
provides a simple, exact and clear representation of the power redistribution
after line failures, where we introduced the network block decomposition to
precisely characterize the boundary of the region a line failure can impact.

A finer block decomposition of the power grid creates more, smaller management
regions whose operations can be isolated from each other in various aspects,
bringing benefits such as disruption localizability, optimization
parallelization, and more to the control and management of power systems.
Therefore, we introduced a two-stage procedure to optimally modify the network
topology for a finer block decomposition. Specifically, we first identify the
candidate power network blocks by solving a weighted version of the network
modularity problem and then identify the line switching action that has the
least impact on the surviving network with respect to line congestion. This
two-stage procedure is validated with numerical experiments.

In the rest of this section, we present a collection of examples on how
network block decomposition offers powerful analytical guarantees and benefits
in different power system applications beyond the setting of this paper, and
how we can leverage these properties to improve the current industry practices
in these applications.

##### Real-time failure localization and mitigation.

Reliability is a crucial part for the development of sustainable modern power
systems. Current industry practice relies on simulations based contingency
analysis which is usually constrained by computational power [130]. Since the
cascading failures exhibit a complicated and non-local propagation pattern,
such analysis tends to omit the structural properties of failures and may fail
to control and mitigate the failure in real time. There are topological models
adopted from complex network analysis, however, such models are relatively
simple thus cannot reveal physical properties [68].

As introduced in Sections 2 and 4, network block decomposition leads to clear
and well-defined boundaries that can localize the impact of failures. This
suggests a new technique for grid reliability by switching off a small number
of transmission lines so that finer-grained network blocks are created. In
[60], a real-time distributed control strategy utilizing the localizability
from network block decomposition is proposed. Such control strategy is
guaranteed to (i) always prevent successive failures from happening; and (ii)
localize the impact of initial failures as much as possible. Simulation
results show that the controller significantly improves the overall grid
reliability.

##### Security constrained OPF.

Security constrained OPF (SC OPF) is another approach to improve grid
reliability that works by adding a set of contingencies and requiring the
operating point to be safe under any of such contingency. These additional
constraints greatly increase the size of the problem [17]. In practice, the SC
OPF is solved with contingency filtering techniques [18] to reduce the problem
size and/or iterative methods such as Alternating Direction Method of
Multipliers (ADMM) [21] for distributed computations.

With a finer network block decomposition, both approaches can be significantly
accelerated. The block induces a natural way to decompose and decouple the SC
OPF, reducing the number of constraints and variables in each region. In
addition, the messages necessary to pass across are reduced, leading to a fast
convergence for the local optimizations. Therefore, there is huge potential in
accelerating the computation of SC OPF when the network can be decomposed into
comparable blocks.

##### Distributed AC OPF.

Optimal Power Flow (OPF) underlies the efficient and stable operation of power
grids, reducing the generation cost and transmission loss while maintaining
the system stability in steady state. AC OPF problems are challenging because
of their highly non-convex nature stemming from the nonlinear relationship
between voltages and the complex powers. To overcome this challenge,
semidefinite programming (SDP) relaxation of the AC OPF problem, where the
optimization variable is transformed to a matrix $\mathbf{V}$ that needs to be
semidefinite positive, i.e. $\mathbf{V}\succeq 0$, has been proposed; see [98,
86] for surveys to a considerable literature. However, the standard SDP
solvers do not scale well with the network size, necessitating a distributed
solution where multiple agents communicate with each other and solve the
relaxed problem together. This has proved difficult because the
$\mathbf{V}\succeq 0$ constraint is globally coupled, rendering ADMM to be
inapplicable. Nevertheless, it is shown in [29] that if the power grid
exhibits a block decomposition and each block has an nonempty interior, then
the partial matrix with known entries specified by these blocks is chordal and
thus can be completed to a feasible global solution $\mathbf{V}\succeq 0$
(see. e.g., [91]). This enables the application of ADMM if the SDP
optimization is decomposed in accordance with the network block structure and
allows the optimization to be distributed to each block. Therefore, a finer
network block decomposition helps reduce the overall operation cost by
allowing AC OPF to be solved more efficiently.

##### Monitoring of price manipulation.

Aggregators are playing an increasingly important role in the construction of
a morden power grid, especially with the higher penetration level of renewable
energy resources. The aggregators install, monitor and manage household energy
devices such as rooftop solar panels and electric vehicle charging stations,
and coordinate with utilities and Idependent System Operators (ISOs) to
provide renewable generation and demand response. In addition to the benefits
of aggregators, however, aggregators have the potential to manipulate prices
through strategic curtailment for more profit [121]. To quantify the potential
for aggregators to exercise market power, in [121] an algorithmic framework is
given to approximately solve a bilevel quadratic optimization problem. Their
method relies on decomposing the optimization problem into local parts and
solve approximately with dynamic programming, thus only works for radial
networks. It can be shown that similar bound holds in general networks if the
block size of the network is upper bounded. Therefore, it is possible to
extend the analysis from radial networks to general networks with proper block
decomposition.

## Acknowledgements

This research has been supported by NWO Rubicon grant 680.50.1529, Resnick
Fellowship, Linde Institute Research Award, 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.

## References

  * [1] G. Agarwal and D. Kempe.  Modularity-maximizing graph communities via mathematical programming.  The European Physical Journal B, 66(3):409–418, Dec 2008.
  * [2] O. Alsaç, B. Stott, and W. F. Tinney.  Sparsity-oriented compensation methods for modified network solutions.  IEEE Transactions on Power Apparatus and Systems, PAS-102(5):1,050–1,060, May 1983.
  * [3] Awerbuch and Shiloach.  New connectivity and MSF algorithms for shuffle-exchange network and PRAM.  IEEE Transactions on Computers, C-36(10):1258–1263, Oct. 1987\.
  * [4] S. Babaeinejadsarookolaee, A. Birchfield, R. D. Christie, C. Coffrin, C. DeMarco, R. Diao, M. Ferris, S. Fliscounakis, S. Greene, R. Huang, C. Josz, R. Korab, B. Lesieutre, J. Maeght, D. K. Molzahn, T. J. Overbye, P. Panciatici, B. Park, J. Snodgrass, and R. Zimmerman.  The Power Grid Library for Benchmarking AC Optimal Power Flow Algorithms.  arXiv:1908.02788, 2019.
  * [5] R. Bacher and H. Glavitsch.  Network topology optimization with security constraints.  IEEE Transactions on Power Systems, 1(4):103–111, 1986.
  * [6] R. Bacher and H. Glavitsch.  Loss reduction by network switching.  IEEE Transactions on Power Systems, 3(2):447–454, 1988.
  * [7] J. Bialek and V. Vahidinasab.  Tree-partitioning as an emergency measure to contain cascading line failures.  Submitted to IEEE Transactions on Power Systems, 2020.
  * [8] D. Bienstock.  Electrical Transmission System Cascades and Vulnerability.  Society for Industrial and Applied Mathematics, Dec. 2015.
  * [9] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre.  Fast unfolding of communities in large networks.  Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008, oct 2008.
  * [10] S. Blumsack, P. Hines, M. Patel, C. Barrows, and E. C. Sanchez.  Defining power network zones from measures of electrical distance.  In 2009 IEEE Power Energy Society General Meeting, pages 1–8, July 2009.
  * [11] S. Boettcher and A. G. Percus.  Optimization with extremal dynamics.  Complex., 8(2):57–62, Nov. 2002.
  * [12] M. Bolla.  Penalized versions of the newman-girvan modularity and their relation to normalized cuts and $k$-means clustering.  Phys. Rev. E, 84:016108, Jul 2011.
  * [13] Z. M. Boyd, E. Bae, X.-C. Tai, and A. L. Bertozzi.  Simplified energy landscape for modularity using total variation.  SIAM Journal on Applied Mathematics, 78(5):2439–2464, 2018.
  * [14] U. Brandes, D. Delling, M. Gaertler, R. Goerke, M. Hoefer, Z. Nikoloski, and D. Wagner.  Maximizing modularity is hard.  arXiv preprint physics/0608255, 2006.
  * [15] U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner.  On modularity clustering.  IEEE Transactions on Knowledge and Data Engineering, 20(2):172–188, Feb 2008.
  * [16] A. Brouwer and W. Haemers.  Spectra of Graphs.  Universitext. Springer New York, 2011.
  * [17] F. Capitanescu, J. M. Ramos, P. Panciatici, D. Kirschen, A. M. Marcolini, L. Platbrood, and L. Wehenkel.  State-of-the-art, challenges, and future trends in security constrained optimal power flow.  Electric Power Systems Research, 81(8):1731–1741, 2011.
  * [18] F. Capitanescu and L. Wehenkel.  A new iterative approach to the corrective security-constrained optimal power flow problem.  IEEE transactions on power systems, 23(4):1533–1541, 2008.
  * [19] J. G. Caputo, A. Knippel, and N. Retiere.  Spectral solution of load flow equations, 2019.
  * [20] H. Cetinay, F. A. Kuipers, and P. Van Mieghem.  A topological investigation of power flow.  IEEE Systems Journal, 12(3):2524–2532, Sep. 2018.
  * [21] S. Chakrabarti, M. Kraning, E. Chu, R. Baldick, and S. Boyd.  Security constrained optimal power flow via proximal message passing.  In 2014 Clemson University Power Systems Conference, pages 1–8. IEEE, 2014.
  * [22] M. Chakraborty, S. Chowdhury, J. Chakraborty, R. Mehera, and R. K. Pal.  Algorithms for generating all possible spanning trees of a simple undirected connected graph: an extensive review.  Complex & Intelligent Systems, 5(3):265–281, 2019.
  * [23] M. Chen, K. Kuzmin, and B. K. Szymanski.  Community detection via maximization of modularity and its variants.  IEEE Transactions on Computational Social Systems, 1(1):46–65, March 2014.
  * [24] A. Clauset, M. E. J. Newman, and C. Moore.  Finding community structure in very large networks.  Phys. Rev. E, 70:066111, Dec 2004.
  * [25] C. Coffrin and R. Zimmerman.  Github repository pglib-opf v20.07.  https://github.com/power-grid-lib/pglib-opf.
  * [26] E. Cotilla-Sanchez, P. Hines, C. Barrows, S. Blumsack, and M. Patel.  Multi-attribute partitioning of power networks based on electrical distance.  IEEE Transactions on Power Systems, 28(4):4979–4987, Nov 2013.
  * [27] E. Cotilla-Sanchez, P. D. H. Hines, C. Barrows, and S. Blumsack.  Comparing the topological and electrical structure of the north american electric power infrastructure.  IEEE Systems Journal, 6(4):616–626, Dec 2012.
  * [28] L. Cuadra, S. Salcedo-Sanz, J. D. Ser, S. Jiménez-Fernández, and Z. Geem.  A critical review of robustness in power grids using complex networks concepts.  Energies, 8(9):9211–9265, Aug. 2015.
  * [29] E. Dall’Anese, H. Zhu, and G. B. Giannakis.  Distributed optimal power flow for smart microgrids.  IEEE Transactions on Smart Grid, 4(3):1464–1475, 2013.
  * [30] 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 Transactions on Power Systems, 31(6):4831–4841, Nov 2016.
  * [31] F. Dorfler and F. Bullo.  Kron reduction of graphs with applications to electrical networks.  IEEE Transactions on Circuits and Systems I: Regular Papers, 60(1):150–163, 2013.
  * [32] P. G. Doyle and J. L. Snell.  Random Walks and Electric Networks.  American Mathematical Monthly, 94(January):202, 2000.
  * [33] J. Duch and A. Arenas.  Community detection in complex networks using extremal optimization.  Phys. Rev. E, 72:027104, Aug 2005.
  * [34] F. Dörfler and F. Bullo.  Novel insights into lossless AC and DC power flow.  In 2013 IEEE Power Energy Society General Meeting, pages 1–5, 2013\.
  * [35] F. Dörfler and F. Bullo.  Synchronization in complex networks of phase oscillators: A survey.  Automatica, 50(6):1539–1564, 2014.
  * [36] F. Dörfler, J. W. Simpson-Porco, and F. Bullo.  Electrical networks and algebraic graph theory: Models, properties, and applications.  Proceedings of the IEEE, 106(5):977–1005, May 2018.
  * [37] W. Ellens, F. Spieksma, P. Van Mieghem, a. Jamakovic, and R. Kooij.  Effective graph resistance.  Linear Algebra and its Applications, 435(10):2491–2506, nov 2011\.
  * [38] M. K. Enns, J. J. Quada, and B. Sackett.  Fast linear contingency analysis.  IEEE Transactions on Power Apparatus and Systems, PAS-101(4):783–791, April 1982.
  * [39] A. Esmaeilian and M. Kezunovic.  Prevention of power grid blackouts using intentional islanding scheme.  IEEE Transactions on Industry Applications, 53(1):622–629, Jan 2017\.
  * [40] N. Fan, D. Izraelevitz, F. Pan, P. M. Pardalos, and J. Wang.  A mixed integer programming approach for optimal power grid intentional islanding.  Energy Systems, 3(1):77–93, Mar 2012.
  * [41] E. B. Fisher, R. P. O’Neill, and M. C. Ferris.  Optimal transmission switching.  IEEE Transactions on Power Systems, 23(3):1346–1355, 2008.
  * [42] S. Fliscounakis, F. Zaoui, G. Simeant, and R. Gonzalez.  Topology influence on loss reduction as a mixed integer linear programming problem.  In 2007 IEEE Lausanne Power Tech, pages 1987–1990, 2007.
  * [43] S. Fortunato.  Community detection in graphs.  Physics Reports, 486(3):75 – 174, 2010.
  * [44] S. Fortunato and D. Hric.  Community detection in networks: A user guide.  Physics Reports, 659:1 – 44, 2016.  Community detection in networks: A user guide.
  * [45] A. Ghosh, S. Boyd, and A. Saberi.  Minimizing Effective Resistance of a Graph.  SIAM Review, 50(1):37–66, 2008.
  * [46] H. Glavitsch.  Switching as means of control in the power system.  International Journal of Electrical Power & Energy Systems, 7(2):92–100, 1985.
  * [47] S. Gómez, P. Jensen, and A. Arenas.  Analysis of community structure in networks of correlated data.  Phys. Rev. E, 80:016114, Jul 2009.
  * [48] G. Granelli, M. Montagna, F. Zanellini, P. Bresesti, R. Vailati, and M. Innorta.  Optimal network reconfiguration for congestion management by deterministic and genetic algorithms.  Electric Power Systems Research, 76(6):549–556, 2006.
  * [49] P. Gribik, D. Shirmohammadi, S. Hao, and C. Thomas.  Optimal power flow sensitivity analysis.  IEEE Transactions on Power Systems, 5(3):969–976, August 1990.
  * [50] M. Guerrero, C. Gil, F. G. Montoya, A. Alcayde, and R. Bańos.  Community detection in power grids by an evolutionary method.  In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’17, pages 279–280, New York, NY, USA, 2017. ACM.
  * [51] R. Guimerà and L. A. N. Amaral.  Cartography of complex networks: modules and universal roles.  Journal of Statistical Mechanics: Theory and Experiment, 2005(02):P02001, feb 2005.
  * [52] T. Güler and G. Gross.  Detection of island formation and identification of causal factors under multiple line outages.  IEEE Transactions on Power Systems, 22(2):505–513, May 2007.
  * [53] T. Güler, G. Gross, and M. Liu.  Generalized line outage distribution factors.  IEEE Transactions on Power Systems, 22(2):879–881, May 2007.
  * [54] J. Guo, Y. Fu, Z. Li, and M. Shahidehpour.  Direct calculation of line outage distribution factors.  IEEE Transactions on Power Systems, 24(3):1633–1634, Aug 2009.
  * [55] L. Guo, C. Liang, and S. H. Low.  Monotonicity properties and spectral characterization of power redistribution in cascading failures.  In 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 918–925, Oct 2017.
  * [56] L. Guo, C. Liang, A. Zocca, S. Low, and A. Wierman.  Fast-timescale control of cascading failures in power systems.  Submitted. Preprint at arXiv:2005.11319, 2021.
  * [57] L. Guo, C. Liang, A. Zocca, S. Low, and A. Wierman.  Line failure localization of power networks part i: Non-cut outages.  IEEE Transactions on Power Systems, 2021.
  * [58] L. Guo, C. Liang, A. Zocca, S. Low, and A. Wierman.  Line failure localization of power networks part ii: Cut set outages.  IEEE Transactions on Power Systems, 2021.
  * [59] L. Guo, C. Liang, A. Zocca, S. H. Low, and A. Wierman.  Failure localization in power systems via tree partitions.  In 2018 IEEE Conference on Decision and Control (CDC), pages 6832–6839, Miami Beach, FL, Dec 2018.
  * [60] L. Guo, C. Liang, A. Zocca, S. H. Low, and A. Wierman.  Less is more: Real-time failure localization in power systems.  In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 3871–3877, 2019.
  * [61] J. Han and A. Papavasiliou.  The Impacts of Transmission Topology Control on the European Electricity Network.  IEEE Transactions on Power Systems, 31(1):496–507, 2016.
  * [62] F. Harary.  Graph Theory.  Addison Wesley series in mathematics. Addison-Wesley, 1971.
  * [63] A. R. Hassani Ahangar, G. B. Gharehpetian, and H. R. Baghaee.  A review on intentional controlled islanding in smart power systems and generalized framework for ici in microgrids.  International Journal of Electrical Power & Energy Systems, 118:105709, 2020.
  * [64] A. Hauswirth, S. Bolognani, G. Hug, and F. Dörfler.  Generic existence of unique Lagrange multipliers in AC optimal power flow.  IEEE Control Systems Letters, 2(4), October 2018.
  * [65] K. W. Hedman, M. C. Ferris, R. P. O’Neill, E. B. Fisher, and S. S. Oren.  Co-optimization of generation unit commitment and transmission switching with n-1 reliability.  IEEE Transactions on Power Systems, 25(2):1052–1063, 2010.
  * [66] K. W. Hedman, R. P. O’Neill, E. B. Fisher, and S. S. Oren.  Optimal transmission switching with contingency analysis.  IEEE Transactions on Power Systems, 24(3):1577–1586, 2009.
  * [67] K. W. Hedman, S. S. Oren, and R. P. O’Neill.  A review of transmission switching and network topology optimization.  In 2011 IEEE Power and Energy Society General Meeting, pages 1–7, 2011.
  * [68] P. Hines, E. Cotilla-Sanchez, and S. Blumsack.  Do topological models provide good information about electricity infrastructure vulnerability?  Chaos: An Interdisciplinary Journal of Nonlinear Science, 20(3):033122, 2010.
  * [69] P. D. H. Hines, I. Dobson, E. Cotilla-Sanchez, and M. Eppstein.  ”dual graph” and ”random chemistry” methods for cascading failure analysis.  In 2013 46th Hawaii International Conference on System Sciences, pages 2141–2150, Jan 2013.
  * [70] P. D. H. Hines, I. Dobson, and P. Rezaei.  Cascading power outages propagate locally in an influence graph that is not the actual grid topology.  IEEE Transactions on Power Systems, 32(2):958–967, March 2017.
  * [71] J. Hopcroft and R. Tarjan.  Algorithm 447: efficient algorithms for graph manipulation.  Communications of the ACM, 16(6):372–378, June 1973.
  * [72] Y.-F. Huang, S. Werner, J. Huang, N. Kashyap, and V. Gupta.  State estimation in electric power grids: Meeting new challenges presented by the requirements of the future grid.  IEEE Signal Processing Magazine, 29(5):33–43, 2012.
  * [73] J. Hörsch, H. Ronellenfitsch, D. Witthaut, and T. Brown.  Linear optimal power flow using cycle flows.  Electric Power Systems Research, 158:126–135, 2018.
  * [74] J. Johnson and M. Chertkov.  A majorization-minimization approach to design of power transmission networks.  In 49th IEEE Conference on Decision and Control (CDC), pages 3996–4003. IEEE, 2010.
  * [75] Kai Sun, Da-Zhong Zheng, and Qiang Lu.  Splitting strategies for islanding operation of large-scale power systems using obdd-based methods.  IEEE Transactions on Power Systems, 18(2):912–923, May 2003.
  * [76] F. Kaiser, V. Latora, and D. Witthaut.  Inhibiting failure spreading in complex networks, 2020.
  * [77] F. Kaiser, J. Strake, and D. Witthaut.  Collective effects of link failures in linear flow networks.  New Journal of Physics, 22(1):013053, jan 2020.
  * [78] F. Kaiser and D. Witthaut.  Topological theory of resilience and failure spreading in flow networks, 2020.
  * [79] M. Khanabadi, H. Ghasemi, and M. Doostizadeh.  Optimal transmission switching considering voltage security and n-1 contingency analysis.  IEEE Transactions on Power Systems, 28(1):542–550, 2012.
  * [80] D. J. Klein and M. Randić.  Resistance distance.  Journal of Mathematical Chemistry, 12(1):81–95, 1993.
  * [81] F. Koeth.  Investigations of Spectral Properties in Power Systems.  Theses, Université Grenoble Alpes, Dec. 2019.
  * [82] F. Koeth and N. Retiere.  Spectral properties of dynamical power systems.  In 2019 IEEE Milan PowerTech, pages 1–6, 2019.
  * [83] H.-J. Koglin and H. Muller.  Overload reduction through corrective switching actions.  In Int. Conf. Power Sys. Monitor. & Contr, volume 24, 1980.
  * [84] A. S. Korad and K. W. Hedman.  Robust corrective topology control for system reliability.  IEEE Transactions on Power Systems, 28(4):4042–4051, 2013.
  * [85] Y. Koç, M. Warnier, R. Kooij, and F. Brazier.  Structural vulnerability assessment of electric power grids.  In Proceedings of the 11th IEEE International Conference on Networking, Sensing and Control, pages 386–391, April 2014.
  * [86] J. Lavaei and S. H. Low.  Zero duality gap in optimal power flow problem.  IEEE Transactions on Power Systems, 27(1):92–107, 2011.
  * [87] C. Liang, L. Guo, A. Zocca, S. Yu, S. H. Low, and A. Wierman.  An integrated approach for failure mitigation & localization in power systems.  Electric Power Systems Research, 190:106613, 2021.
  * [88] G. Lin, S. Liu, A. Zhou, J. Dai, B. Chai, B. Zhang, H. Qiu, K. Gao, Y. Song, and R. Chen.  Community detection in power grids based on louvain heuristic algorithm.  In 2017 IEEE Conference on Energy Internet and Energy System Integration (EI2), pages 1–4, 2017.
  * [89] L. Liu, W. Liu, D. A. Cartes, and I.-Y. Chung.  Slow coherency and angle modulated particle swarm optimization based islanding of large-scale power systems.  Advanced Engineering Informatics, 23(1):45 – 56, 2009.
  * [90] S. Liu, Z. Lin, Y. Zhao, Y. Liu, Y. Ding, B. Zhang, L. Yang, Q. Wang, and S. E. White.  Robust system separation strategy considering online wide-area coherency identification and uncertainties of renewable energy sources.  IEEE Transactions on Power Systems, 35(5):3574–3587, 2020.
  * [91] S. H. Low.  Convex relaxation of optimal power flow—part ii: Exactness.  IEEE Transactions on Control of Network Systems, 1(2):177–189, 2014\.
  * [92] Z. Lu, X. Sun, Y. Wen, G. Cao, and T. L. Porta.  Algorithms and applications for community detection in weighted networks.  IEEE Transactions on Parallel and Distributed Systems, 26(11):2916–2926, Nov 2015.
  * [93] Z. Lu, Y. Wen, and G. Cao.  Community detection in weighted networks: Algorithms and applications.  In 2013 IEEE International Conference on Pervasive Computing and Communications (PerCom), pages 179–184, March 2013.
  * [94] A. Marot, S. Tazi, B. Donnot, and P. Panciatici.  Guided machine learning for power grid segmentation.  In 2018 IEEE PES Innovative Smart Grid Technologies Conference Europe (ISGT-Europe), pages 1–6, 2018.
  * [95] C. P. Massen and J. P. K. Doye.  Identifying communities within energy landscapes.  Phys. Rev. E, 71:046101, Apr 2005.
  * [96] A. A. Mazi, B. F. Wollenberg, and M. H. Hesse.  Corrective control of power system flows by line and bus-bar switching.  IEEE Transactions on Power Systems, 1(3):258–264, 1986.
  * [97] A. Medus, G. Acuña, and C. Dorso.  Detection of community structures in networks via global optimization.  Physica A: Statistical Mechanics and its Applications, 358(2):593 – 604, 2005.
  * [98] D. K. Molzahn and I. A. Hiskens.  A survey of relaxations and approximations of the power flow equations.  Foundations and Trends in Electric Energy Systems, 4(1-2):1–221, 2019.
  * [99] U. Nakarmi and M. Rahnamay-Naeini.  Analyzing power grids’ cascading failures and critical components using interaction graphs.  In 2018 IEEE Power Energy Society General Meeting (PESGM), pages 1–5, Aug 2018.
  * [100] U. Nakarmi, M. Rahnamay-Naeini, and H. Khamfroush.  Critical component analysis in cascading failures for power grids using community structures in interaction graphs.  IEEE Transactions on Network Science and Engineering, 2019.
  * [101] T. Nesti, A. Zocca, and B. Zwart.  Emergent failures and cascades in power grids: A statistical physics perspective.  Phys. Rev. Lett., 120:258301, 2018.
  * [102] M. E. J. Newman.  Analysis of weighted networks.  Phys. Rev. E, 70:056131, Nov 2004.
  * [103] M. E. J. Newman.  Fast algorithm for detecting community structure in networks.  Phys. Rev. E, 69:066133, Jun 2004.
  * [104] M. E. J. Newman.  Finding community structure in networks using the eigenvectors of matrices.  Phys. Rev. E, 74:036104, Sep 2006.
  * [105] M. E. J. Newman.  Modularity and community structure in networks.  Proceedings of the National Academy of Sciences, 103(23):8577–8582, 2006.
  * [106] M. E. J. Newman and M. Girvan.  Finding and evaluating community structure in networks.  Phys. Rev. E, 69:026113, Feb 2004.
  * [107] A. Y. Ng, M. I. Jordan, and Y. Weiss.  On spectral clustering: Analysis and an algorithm.  In Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, NIPS’01, pages 849–856, Cambridge, MA, USA, 2001. MIT Press.
  * [108] G. A. Pagani and M. Aiello.  The power grid as a complex network: A survey.  Physica A: Statistical Mechanics and its Applications, 392(11):2688 – 2700, 2013.
  * [109] S. Pahwa, M. Youssef, P. Schumm, C. Scoglio, and N. Schulz.  Optimal intentional islanding to enhance the robustness of power grid networks.  Physica A: Statistical Mechanics and its Applications, 392(17):3741–3754, 2013.
  * [110] M. Pirani, J. W. Simpson-Porco, and B. Fidan.  System-Theoretic Performance Metrics for Low-Inertia Stability of Power Networks.  2017 IEEE 56th Annual Conference on Decision and Control (CDC), pages 5106–5111, 2017.
  * [111] M. A. Porter, J.-P. Onnela, and P. J. Mucha.  Communities in networks.  Notices of the AMS, 56(9):1082–1097, 2009.
  * [112] Qianchuan Zhao, Kai Sun, Da-Zhong Zheng, Jin Ma, and Qiang Lu.  A study of system splitting strategies for island operation of power system: a two-phase method based on obdds.  IEEE Transactions on Power Systems, 18(4):1556–1565, Nov 2003.
  * [113] J. Quirós-Tortós and V. Terzija.  A graph theory based new approach for power system restoration.  In 2013 IEEE Grenoble Conference, pages 1–6, 2013.
  * [114] G. Ranjan, Z.-L. Zhang, and D. Boley.  Incremental Computation of Pseudo-Inverse of Laplacian.  In COCOA 2014: 8th International Conference on Combinatorial Optimization and Applications, volume 5573, pages 729–749. Springer International Publishing, 2014.
  * [115] J. Reichardt and S. Bornholdt.  Statistical mechanics of community detection.  Phys. Rev. E, 74:016110, Jul 2006.
  * [116] N. Retire, D. T. Ha, and J.-G. Caputo.  Spectral Graph Analysis of the Geometry of Power Flows in Transmission Networks.  IEEE Systems Journal, 14(2):2736–2747, 2019.
  * [117] T. Richardson, P. J. Mucha, and M. A. Porter.  Spectral tripartitioning of networks.  Phys. Rev. E, 80:036111, Sep 2009.
  * [118] J. G. Rolim and L. J. B. Machado.  A study of the use of corrective switching in transmission systems.  IEEE Transactions on Power Systems, 14(1):336–341, 1999.
  * [119] H. Ronellenfitsch, D. Manik, J. Horsch, T. Brown, and D. Witthaut.  Dual theory of transmission line outages.  IEEE Transactions on Power Systems, 32(5):4060–4068, Sept. 2017\.
  * [120] H. Ronellenfitsch, M. Timme, and D. Witthaut.  A dual method for computing power transfer distribution factors.  IEEE Transactions on Power Systems, 32(2):1007–1015, 2017.
  * [121] N. A. Ruhi, K. Dvijotham, N. Chen, and A. Wierman.  Opportunities for price manipulation by aggregators in electricity markets.  IEEE Transactions on Smart Grid, 9(6):5687–5698, 2017.
  * [122] M. Sales-Pardo, R. Guimerà, A. A. Moreira, and L. A. N. Amaral.  Extracting the hierarchical organization of complex systems.  Proceedings of the National Academy of Sciences, 104(39):15224–15229, 2007.
  * [123] G. Schnyder and H. Glavitsch.  Integrated security control using an optimal power flow and switching concepts.  IEEE Transactions on Power Systems, 3(2):782–790, 1988.
  * [124] G. Schnyder and H. Glavitsch.  Security enhancement using an optimal switching power flow.  IEEE Transactions on Power Systems, 5(2):674–681, 1990.
  * [125] W. Shao and V. Vittal.  Corrective switching algorithm for relieving overloads and voltage violations.  IEEE Transactions on Power Systems, 20(4):1877–1885, 2005.
  * [126] W. Shao and V. Vittal.  Bip-based opf for line and bus-bar switching to relieve overloads and voltage violations.  In 2006 IEEE PES Power Systems Conference and Exposition, pages 2090–2095, 2006.
  * [127] J. Shi and J. Malik.  Normalized cuts and image segmentation.  IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888–905, Aug. 2000\.
  * [128] S. Soltan, D. Mazauric, and G. Zussman.  Analysis of failures in power grids.  IEEE Transactions on Control of Network Systems, 4(2):288–300, June 2017.
  * [129] S. Soltan, M. Yannakakis, and G. Zussman.  Doubly Balanced Connected Graph Partitioning, pages 1939–1950.  SIAM, 2017.
  * [130] J. Song, E. Cotilla-Sanchez, G. Ghanavati, and P. D. Hines.  Dynamic modeling of cascading failure in power systems.  IEEE TPS, 31(3):2085–2095, 2016.
  * [131] M. Stoer and F. Wagner.  A simple min-cut algorithm.  J. ACM, 44(4):585–591, July 1997.
  * [132] B. Stott, O. Alsaç, and F. L. Alvarado.  Analytical and computational improvements in performance-index ranking algorithms for networks.  International Journal of Electrical Power & Energy Systems, 7(3):154–160, July 1985.
  * [133] B. Stott, J. Jardim, and O. Alsac.  DC power flow revisited.  IEEE Transactions on Power Systems, 24(3):1290–1300, 2009.
  * [134] J. Strake, F. Kaiser, F. Basiri, H. Ronellenfitsch, and D. Witthaut.  Non-local impact of link failures in linear flow networks.  New Journal of Physics, 21(5):053009, May 2019.
  * [135] R. Sánchez-García, M. Fennelly, S. Norris, N. Wright, G. Niblo, J. Brodzki, and J. Bialek.  Hierarchical spectral clustering of power grids.  IEEE Transactions on Power Systems, 29(5):2229–2237, Sept 2014\.
  * [136] R. Tarjan.  Depth-first search and linear graph algorithms.  SIAM Journal on Computing, 1(2):146–160, June 1972.
  * [137] R. E. Tarjan and U. Vishkin.  An efficient parallel biconnectivity algorithm.  SIAM Journal on Computing, 14(4):862–874, Nov. 1985.
  * [138] P. Van Mieghem.  Graph Spectra for Complex Networks.  CUP, 2011.
  * [139] V. Vittal, W. Kliemann, Y. . Ni, D. G. Chapman, A. D. Silk, and D. J. Sobajic.  Determination of generator groupings for an islanding scheme in the manitoba hydro system using the method of normal forms.  IEEE Transactions on Power Systems, 13(4):1345–1351, Nov 1998.
  * [140] U. von Luxburg.  A tutorial on spectral clustering.  Statistics and Computing, 17(4):395–416, 2007.
  * [141] D. Wagner and F. Wagner.  Between min cut and graph bisection.  In Mathematical Foundations of Computer Science 1993, pages 744–750, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg.
  * [142] K. Wakita and T. Tsurumi.  Finding community structure in mega-scale social networks: [extended abstract].  In Proceedings of the 16th International Conference on World Wide Web, WWW ’07, pages 1275–1276, New York, NY, USA, 2007. ACM.
  * [143] X. Wang, Y. Koç, R. E. Kooij, and P. Van Mieghem.  A network approach for power grid robustness against cascading failures.  In 2015 7th International Workshop on Reliable Networks Design and Modeling (RNDM), pages 208–214, Oct 2015.
  * [144] X. Wang, E. Pournaras, R. E. Kooij, and P. Van Mieghem.  Improving robustness of complex networks via the effective graph resistance.  The European Physical Journal B, 87(9):221, Sep 2014.
  * [145] J. Westbrook and R. E. Tarjan.  Maintaining bridge-connected and biconnected components on-line.  Algorithmica, 7(1-6):433–464, June 1992.
  * [146] S. White and P. Smyth.  A Spectral Clustering Approach To Finding Communities in Graphs, pages 274–285.  SIAM, 2005.
  * [147] A. J. Wood, B. F. Wollenberg, and G. B. Sheblé.  Power generation, operation, and control.  John Wiley & Sons, 2013.
  * [148] H. You, V. Vittal, and X. Wang.  Slow coherency-based islanding.  IEEE Transactions on Power Systems, 19(1):483–491, 2004.
  * [149] H. You, V. Vittal, and Z. Yang.  Self-healing in power systems: an approach using islanding and rate of frequency decline-based load shedding.  IEEE Transactions on Power Systems, 18(1):174–181, 2003.
  * [150] H. You, V. Vittal, and Z. Yang.  Self-healing in power systems: an approach using islanding and rate of frequency decline-based load shedding.  IEEE Transactions on Power Systems, 18(1):174–181, Feb 2003.
  * [151] L. Yu and C. Ding.  Network community discovery: Solving modularity clustering via normalized cut.  In Proceedings of the Eighth Workshop on Mining and Learning with Graphs, MLG ’10, pages 34–36, New York, NY, USA, 2010. ACM.
  * [152] A. Zocca and B. Zwart.  Optimization of stochastic lossy transport networks and applications to power grids.  Stochastic Systems, 11(1):34–59, Mar. 2021.

##  Appendix A Appendix

###  A.1 Proof of Proposition 2.2

  * (i)

From its definition (1), it is clear that we can rewrite the Laplacian matrix
$L$ as

$L=\sum_{(i,j)\in
E}b_{ij}(\bm{e}_{i}\bm{e}_{i}^{T}+\bm{e}_{j}\bm{e}_{j}^{T}-\bm{e}_{i}\bm{e}_{j}^{T}-\bm{e}_{j}\bm{e}_{i}^{T}).$

Therefore, for any $\bm{x}\in\mathbb{R}^{n}$ we have

$\displaystyle\bm{x}^{T}L\bm{x}$
$\displaystyle=\bm{x}^{T}\Big{(}\sum_{(i,j)\in
E}b_{ij}(\bm{e}_{i}\bm{e}_{i}^{T}+\bm{e}_{j}\bm{e}_{j}^{T}-\bm{e}_{i}\bm{e}_{j}^{T}-\bm{e}_{j}\bm{e}_{i}^{T})\Big{)}\bm{x}=\sum_{(i,j)\in
E}b_{ij}\,\bm{x}^{T}(\bm{e}_{i}\bm{e}_{i}^{T}+\bm{e}_{j}\bm{e}_{j}^{T}-\bm{e}_{i}\bm{e}_{j}^{T}-\bm{e}_{j}\bm{e}_{i}^{T})\bm{x}$
$\displaystyle=\sum_{(i,j)\in
E}b_{ij}\left(x_{i}^{2}-2x_{i}x_{j}+x_{j}^{2}\right)=\sum_{(i,j)\in
E}b_{ij}(x_{i}-x_{j})^{2}\geq 0$

  * (ii)

In (i) we rewrote $\bm{x}^{T}L\bm{x}$ as the quadratic form $\sum_{(i,j)\in
E}b_{ij}(x_{i}-x_{j})^{2}$. This, in combination with the fact that $b_{ij}>0$
for every line $(i,j)\in E$ suffices to conclude that $L$ is positive
semidefinite.

  * (iii)

The row and column property immediately follows from the way the matrix $L$ is
defined, cf. (1). Since the kernel of $L$ contains at least the nontrivial
vector $\bm{1}$, the matrix is singular.

  * (iv)

We claim that a vector $\bm{v}$ is in the null space of $L$ if and only if
$v_{i}=v_{j}$ for all nodes $i,j$ in the same connected component. For any
such pair, there exists a path $\ell_{1},\dots,\ell_{r}$ connecting them and
for all the nodes traversed by this path (including $i$ and $j$) the
corresponding entries of the vector $v$ must be equal, in view of the fact
that $\bm{v}^{T}L\bm{v}=0$ and that $b_{\ell_{1}},\dots,b_{\ell_{r}}>0$. The
reverse implication is trivial. This claim implies that an orthonormal basis
of the null space consists of $k$ orthogonal unit vectors $\bm{v}_{j}$,
$j=1,\dots,k$, whose entries are

$(\bm{v}_{j})_{i}:=\frac{\bm{1}_{\mathcal{I}_{j}}(i)}{\sqrt{|\mathcal{I}_{j}|}},\qquad
i=1,\dots,n,$

where $\mathcal{I}_{1},\dots,\mathcal{I}_{k}$ are the connected components of
the graph $G$. Hence, the null space of $L$ has a dimension of $k$ and,
therefore, $\mathrm{rank}(L)=n-\mathrm{dim}(\mathrm{ker}(L))=n-k$.

Consider now the singular value decomposition of the symmetric real matrix
$L$, that is $L=U\Sigma U^{T}$. The columns of $U$ are the orthonormal
eigenvectors of $L$, namely
$\frac{1}{\sqrt{|\mathcal{I}_{1}|}}\bm{1}_{\mathcal{I}_{1}},\dots,\frac{1}{\sqrt{|\mathcal{I}_{k}|}}\bm{1}_{\mathcal{I}_{k}},\bm{v}_{k+1},\dots,\bm{v}_{n}$.
Then the pseudo-inverse $L^{\dagger}$ is equal to
$L^{\dagger}=U\Sigma^{\dagger}U^{T}$, where $\Sigma^{\dagger}$ is the diagonal
$n\times n$ matrix of rank $n-k$ obtained from $\Sigma$ by replacing each the
nonzero eigenvalues $\lambda_{i}$ of $L$ by its reciprocal $1/\lambda_{i}$.
The first identity

$L^{\dagger}=\sum_{j=k+1}^{n}\frac{1}{\lambda_{j}}\,\bm{v}_{j}\bm{v}_{j}^{T}$
(32)

readily follows from $L^{\dagger}=U\Sigma^{\dagger}U^{T}$ in view of the
orthogonality of the eigenvectors and the structure of the null space
described above. For the second identity, it is enough to show that

$\left(L+\sum_{j=1}^{k}\frac{1}{|\mathcal{I}_{j}|}\bm{1}_{\mathcal{I}_{j}}\bm{1}_{\mathcal{I}_{j}}^{T}\right)^{-1}=L^{\dagger}+\sum_{j=1}^{k}\frac{1}{|\mathcal{I}_{j}|}\bm{1}_{\mathcal{I}_{j}}\bm{1}_{\mathcal{I}_{j}}^{T}=\sum_{j=k+1}^{n}\frac{1}{\lambda_{j}}\bm{v}_{j}\bm{v}_{j}^{T}+\sum_{j=1}^{k}\frac{1}{|\mathcal{I}_{j}|}\bm{1}_{\mathcal{I}_{j}}\bm{1}_{\mathcal{I}_{j}}^{T}.$

We prove that the RHS of the latter equation is the inverse matrix by direct
calculation

$\left(L+\sum_{j=1}^{k}\frac{1}{|\mathcal{I}_{j}|}\bm{1}_{\mathcal{I}_{j}}\bm{1}_{\mathcal{I}_{j}}^{T}\right)\left(\sum_{j=k+1}^{n}\frac{1}{\lambda_{j}}\bm{v}_{j}\bm{v}_{j}^{T}+\sum_{j=1}^{k}\frac{1}{|\mathcal{I}_{j}|}\bm{1}_{\mathcal{I}_{j}}\bm{1}_{\mathcal{I}_{j}}^{T}\right)=UU^{T}=I,$

and the conclusion follows by uniqueness of the matrix inverse. In the special
case in which $G$ is connected, then $k=1$, $V=\mathcal{I}_{1}$, and the above
expression simplifies in view of the fact that
$\frac{1}{|\mathcal{I}_{1}|}\bm{1}_{\mathcal{I}_{1}}\bm{1}_{\mathcal{I}_{1}}^{T}=\frac{1}{n}\bm{1}\bm{1}^{T}$.

  * (v)

All the listed properties of $L^{\dagger}$ can be easily deduced from (ii) and
identity (32).

###  A.2 Proof of Proposition 3.2

(i) We can directly inspect that the $(\ell,\hat{\ell})$-th element of the
PTDF matrix $D$, i.e. $D_{\ell\ell}$, coincides with the
$(\ell,\hat{\ell})$-th element of the matrix $BC^{T}L^{\dagger}C$. More
specifically, using the first equation of Proposition 3.1 and choosing
$\hat{\ell}=(s,t)\in E$, we have

$(BC^{T}L^{\dagger}C)_{\ell\hat{\ell}}=\mathbf{e}_{\ell}^{T}BC^{T}L^{\dagger}C\mathbf{e}_{\hat{\ell}}=b_{\ell}e_{\ell}^{T}C^{T}L^{\dagger}C\mathbf{e}_{\hat{\ell}}=b_{\ell}(\mathbf{e}_{i}-\mathbf{e}_{j})^{T}L^{\dagger}(\mathbf{e}_{s}-\mathbf{e}_{t})=b_{\ell}\left(L^{\dagger}_{is}+L^{\dagger}_{jt}-L^{\dagger}_{it}-L^{\dagger}_{js}\right)=D_{\ell\hat{\ell}}.$

(ii) Let us consider the second expression given in Proposition 3.1 for
$D_{\ell,\ell}$ in the special case where $\hat{\ell}=(s,t)=(i,j)=\ell$. We
obtain

$D_{\ell,\ell}=b_{\ell}\ \frac{\sum_{\mathcal{E}\in
T(\\{i,i\\},\\{j,j\\})}\,\beta(\mathcal{E})\ -\ \sum_{\mathcal{E}\in
T(\\{i,j\\},\\{j,i\\})}\,\beta(\mathcal{E})}{\sum_{\mathcal{E}\in
T}\,\beta(\mathcal{E})}=b_{\ell}\ \frac{\sum_{\mathcal{E}\in
T(\\{i\\},\\{j\\})}\,\beta(\mathcal{E})}{\sum_{\mathcal{E}\in
T}\,\beta(\mathcal{E})},$ (33)

where the last identity follows from the fact that
$T(\\{i,j\\},\\{j,i\\})=\emptyset$. The collection $T=T_{E}$ of all spanning
trees of the graph $G$ can be partitioned into two subsets, depending on
whether the edge $\ell=(i,j)$ belongs to it or not. All the spanning trees
that do contain $\ell$ are in one-to-one correspondence with the spanning
forests in $T(\\{i\\},\\{j\\})$. Indeed, each such spanning tree, once the
edge $\ell$ is removed, yields a spanning forest consisting of two trees, one
containing node $i$ and the other one node $j$. The other subset consisting of
all the spanning trees that do not contain $\ell$ is
$T\\!\setminus\\!\\{\ell\\}$ by definition. In view of these considerations,
we can rewrite the sum of all spanning tree weights as

$\sum_{\mathcal{E}\in T}\,\beta(\mathcal{E})=b_{\ell}\sum_{\mathcal{E}\in
T(\\{i\\},\\{j\\})}\,\beta(\mathcal{E})\ +\ \sum_{\mathcal{E}\in
T\\!\setminus\\!\\{\ell\\}}\,\beta(\mathcal{E}).$

Using this identity to rewrite the denominator appearing in the RHS of (33) we
obtain

$\frac{b_{\ell}\sum_{\mathcal{E}\in
T(\\{i\\},\\{j\\})}\,\beta(\mathcal{E})}{\sum_{\mathcal{E}\in
T}\,\beta(\mathcal{E})}=\frac{b_{\ell}\sum_{\mathcal{E}\in
T(\\{i\\},\\{j\\})}\,\beta(\mathcal{E})}{b_{\ell}\sum_{\mathcal{E}\in
T(\\{i\\},\\{j\\})}\,\beta(\mathcal{E})\ +\ \sum_{\mathcal{E}\in
T\\!\setminus\\!\\{\ell\\}}\,\beta(\mathcal{E})}=1\ -\
\frac{\sum_{\mathcal{E}\in
T\\!\setminus\\!\\{\ell\\}}\,\beta(\mathcal{E})}{\sum_{\mathcal{E}\in
T}\,\beta(\mathcal{E})}.$

Since the collection $T\\!\setminus\\!\\{\ell\\}$ could be empty but it is
always strictly included in $T$, we immediately deduce that
$0<D_{\ell\ell}\leq 1$.

(iii) The two identities readily follow from Proposition 3.1 in the special
case $\ell=(s,t)$ combined with the definition of effective resistance given
in (4).

###  A.3 Proof of Theorem 3.4

We prove the result by contradiction. If $D_{\ell\hat{\ell}}\neq 0$, then at
least one of the two sets $T(\\{i,s\\},\\{j,t\\})$ and
$T(\\{i,t\\},\\{j,s\\})$ of spanning forests appearing in the numerator of the
RHS of (5) is nonempty. Suppose $T(\\{i,s\\},\\{j,t\\})$ is nonempty and take
any spanning forest $F\in T(\\{i,s\\},\\{j,t\\})$. The tree in the forest $F$
that contains buses $i$ and $s$ defines a path from $i$ to $s$, and the other
tree in $F$ that contains $j$ and $t$ defines a path from $j$ to $t$. Clearly
these two paths do not share any vertices. If we add the lines $\ell=(i,j)$
and $\hat{\ell}=(s,t)$ to these two vertex-disjoint paths we obtain a simple
cycle that contains both $\ell$ and $\hat{\ell}$.