Supaporn LONAPALAWONG, Jiangzhe YAN, Jiayu LI, Deshi YE,Wei CHEN, Yong TANG, Yanhao HUANG, Can WANG?

1State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310058, China

2College of Computer Science and Technology, Zhejiang University, Hangzhou 310058, China

3School of Mathematical Science, Zhejiang University, Hangzhou 310058, China

4State Key Laboratory of Power Grid Safety and Energy Conservation,China Electric Power Research Institute, Beijing 100192, China

Abstract:Analyzing network robustness under various circumstances is generally regarded as a challenging problem.Robustness against failure is one of the essential properties of large-scale dynamic network systems such as power grids, transportation systems, communication systems, and computer networks. Due to the network diversity and complexity, many topological features have been proposed to capture specific system properties. For power grids,a popular process for improving a network’s structural robustness is via the topology design. However, most of existing methods focus on localized network metrics, such as node connectivity and edge connectivity, which do not encompass a global perspective of cascading propagation in a power grid. In this paper, we use an informative global metric algebraic connectivity because it is sensitive to the connectedness in a broader spectrum of graphs.Our process involves decreasing the average propagation in a power grid by minimizing the increase in its algebraic connectivity. We propose a topology-based greedy strategy to optimize the robustness of the power grid. To evaluate the network robustness, we calculate the average propagation using MATCASC to simulate cascading line outages in power grids. Experimental results illustrate that our proposed method outperforms existing techniques.

Key words: Network robustness; Cascading failure; Average propagation; Algebraic connectivity; Power grid

1 Introduction

Several important infrastructures,such as transportation systems, telecommunication systems, and electric power grids, are modeled as networks (Pizzuti et al., 2020). Such representations allow us to specify how the components are related to each other through interconnections, and allow us to study many system properties such as robustness, different partitions,and consensus problems,among other areas of interest(Tang et al., 2018).

Examining network robustness under various situations such as internal failures or external attacks is regarded as a difficult research topic, due to the diversity and complexity of networks in general.Several publications discuss how a network’s topology can be used to analyze and measure its robustness(Gu et al.,2020;Wang JX et al.,2020). Various network topological features have been proposed for measuring some network properties. These include simple network metrics(such as mean shortest paths,degree centrality,and clustering coefficient)and network connectivity properties inferred from spectral graph theory. Many of these metrics have been studied in large-scale networks such as power grids(Anghel et al., 2007), which are commonly modeled as complex networks as shown in Fig. 1. Power grid robustness is typically evaluated based on abnormal events such as a cascading failure of the transmission lines, which is the consequence of the collective dynamics of a power grid(Ko? et al.,2014). Because a power grid cascading failure starts from the propagation of a single local failure, the network topology can help us effectively analyze the robustness of the power grid.

However,power grid complexity goes beyond its topology. Analysis based solely on topological features may lead to inaccurate results, because it fails to capture some of the peculiarities of power networks described by Kirchoff’s laws (Cuadra et al.,2015). Consequently, evaluation and validation of real cascading failure data are necessary to verify the effectiveness of topological methods. However,because cascading failures are rare events in a power grid,analyzing the system’s properties directly from cascading failure data is impractical. Existing studies commonly rely on simulation tools to inspect how a power grid will behave in case of such rare events.There are several tools that simulate cascading failures and are capable of returning detailed information that is useful for understanding how cascades propagate,such as DCSIMSEP(Eppstein and Hines,2012; Rezaei et al., 2015), OPA (Carreras et al.,2002), MATCASC (Ko? et al., 2013), and COSMIC(Song et al., 2016). However, it should be noted that although these tools can give detailed simulation results, they cannot provide any insight into how the topology of a power grid affects the system’s robustness.

In recent years, many studies have devoted efforts to optimizing a network’s structural robustness by designing network topology (Liu W et al., 2009;Liu ZY et al., 2012; Laszka et al., 2013; Peng and Wu, 2016). Several different optimization models have been presented to generate robust networks that could withstand random failures and attacks.A lot of research has focused on localized networks,node connectivity, and edge connectivity, but these areas do not tell the whole story of cascade propagation phenomena, which encompasses the entire power grid network. There are much more variables that can be considered. For example, algebraic connectivity is considered an essential indicator of a network’s resilience, and it was used by Liu W et al.(2009)to quantify the importance of network nodes and lines. Laszka et al. (2013)proposed a new metric called persistence, which was used to mitigate attacks by controlling node deployment,resulting in more robust network topologies for wireless sensor networks. Liu ZY et al. (2012) converted the optimal sensor network design problem into a multiobjective optimization problem to obtain a balanced result among the rigidity and efficiency of the connections and resilience to node disconnections. A statistical model called the branching process(Dobson et al., 2005, 2010; Qi et al., 2013; Dey et al.,2016) was explored in later studies to help analyze system dynamics. It gives an accurate result of the average propagation even for a smaller number of simulations. Despite this progress, the following challenges still need to be grappled when designing robust power grid topology: (1) Due to the large number of nodes in real-world power grids, a highly scalable algorithm is required; (2) Although various methods for evaluating robustness exist,there is no widely acknowledged robustness metric and using different metrics often leads to different optimized networks.

To address these issues,a global power grid perspective,rather than a local view,should be adopted when designing a robust topology. Because the edges are sparse in real-world power grids,removing existing edges often has undesirable effects. It is natural to optimize the topology by adding edges. However,adding edges to real-world power grids is quite diffi-cult due to resource constraints,and design planning in advance is required. We propose a topology-based power grid optimization strategy for selecting transmission lines to add to the network,which optimizes the grid’s robustness. We use a more informative metric, algebraic connectivity of the power grid, because it is sensitive to connectivity in a broader spectrum of graphs(Liu W et al.,2009;Dey et al.,2016).Because graph theory does not fully address a power system’s physical characteristics,power grid robustness is currently evaluated mainly by power flow simulation(Azzolin et al.,2018)and verified by cascading failure simulator based power flow equations. Average propagation is calculated to evaluate network robustness using MATCASC to simulate cascading failures. Our experimental results show that generally,the larger the algebraic connectivity is,the more severe the propagation will be. We propose a greedy algorithm to determine the optimal way to add lines to the grids so the increase in the algebraic connectivity is minimized after new connections are added.As a result, cascading failure propagation after the addition can also be expected to be low. Finally, we compare our approach with existing strategies. To evaluate our approach,we conduct case studies with real-world datasets. The results proved the usefulness and effectiveness of our proposed strategy.

The contributions of this study are as follows:

1. We optimize edge addition using a modified greedy algorithm to increase the efficiency of the process and reduce the computational time complexity.

2. We perform empirical analysis of cascading failures in several power grids based on algebraic connectivity, using average propagation as the main evaluation criterion.

2 Related works

Our work is related to the study of topological analysis of networks and algebraic connectivity, as well as cascading power grid failures. Here,we briefly review the related works in these fields of research.

2.1 Topological analysis of network and algebraic connectivity

The study of applied graph theory, also known as complex network theory (Correa-Henao and Yusta-Loyo, 2015), is characterized by its theoretical representation of a system as a network topology. This facilitates study of the impacts of topology changes on the robustness of the system with topological measurements. Examples of these measurements include the degree of connections (Holme et al.,2002;Correa-Henao et al.,2013),betweenness(Guan et al., 2011; Marsden, 2015), and centrality and mean shortest paths(Dey et al.,2016). According to Bigdeli et al.(2009),the betweenness,degree,and clustering coefficient are all defined on a single node. To evaluate the robustness of the entire network, these metrics need to be calculated on every node, which may result in an inefficient computation process. The above metrics explicitly use the graph topology to quantify connectivity. In addition to these metrics, there exists another group of indicators, called spectrum-based measurements, which are derived from the adjacency matrix and Laplacian matrix of a network(van Mieghem,2010;Ellens et al., 2011). Spectrum-based measurements have been shown to be associated with the inherent interconnectedness, partition ability, propagation range,and convergence rates of dynamic network processes,and thus have been widely used to quantify network robustness.

Major progress in spectral analysis was presented by Fiedler (1973), who introduced a metric of graph connectedness called algebraic connectivity, which is the second smallest eigenvalue of the Laplacian matrix of a graph. He showed that the greater the algebraic connectivity, the more difficult it is to cut the graph into smaller components. Existing studies indicate that high algebraic connectivity results in robust networks,and attempt to maximize the algebraic connectivity by adding edges(lines)to the grid (Jamakovic and Uhlig, 2007; Sydney et al.,2013). Many strategies have been proposed to optimize a network’s algebraic connectivity, including edge addition(Jiang et al., 2011;Wei P et al., 2014;Ji et al., 2016), edge deletion (Wei P et al., 2014),and edge rewiring (Sydney et al., 2013). Sydney et al. (2013) studied edge rewiring on three kinds of complex networks and compared edge rewiring to edge addition. Wei P et al. (2014) introduced the flight route addition/deletion problem and compared three different methods to analyze and optimize the algebraic connectivity of air transportation networks. In recent years, some new efforts were also witnessed in network optimization in industrial sectors, such as air transportation and satellite networks (Zheng et al., 2017), and also in businesses where sensor networks are used(Liu ZY et al.,2012;Laszka et al., 2013). Due to limiting factors such as computational complexity, most researchers employ the algebraic connectivity of a network to quantify the importance of a node or an edge in a localized view rather than in a global view.

2.2 Cascading failure and network topology

Extensive literature exists on cascading failures.Large-scale cascading failures are usually the results of propagation from a single local failure into the whole network(Ko? et al.,2014). The existing works can be divided into two basic categories: the evolutionary approach and the holistic approach (Li and Xue, 2019). The evolutionary approach focuses mainly on the causes and consequences of cascading failures (Chen J et al., 2005; Bompard et al., 2016).Flow analysis (Rei et al., 2000) and Markov chains(Wang ZF et al., 2012) were adopted in such studies. The holistic approach focuses on the topology and operation of power grids. This approach typically evaluates vulnerabilities to locate weak points in power systems(Chen Q and Mili,2013;Wang YZ and Baldick, 2014). Furthermore, with the development of system engineering, cascading failures can be analyzed based on complex network theory(Saleh et al., 2018), which is used to model a power grid’s ability to handle cascading outages from a macroscopic perspective (Carreras et al., 2004).

Most of the existing models for cascading failures in power grids are basic topological models.Hardly any attention has been paid to quantifying network robustness against cascading failure in terms of network’s topological properties. Some researchers studied both the topological features and effect of flow dynamics on network robustness in cascading failures. Ko? et al. (2014) proposed a topological metric that uses effective graph resistance to relate power grid robustness to cascading failures.Dey et al. (2016) proposed a novel approach to investigate the relationship between the average propagation of failures and the topological variations occurring in the grid. Pahwa et al.(2012)studied how topological changes can affect the robustness of the network against attacks and failures. However, due to power grid complexity, there are still insufficient network optimization techniques to design typologies that are robust against cascading failures. As most power grids are usually sparsely connected and normal changes to the topology can involve the addition of new power lines, we consider to optimize the robustness of a power grid against cascading failures with edge additions.

3 Empirical analysis of cascading failures in power grids

In this section, we present empirical analysis of the relationship between cascading failures in a power grid and its topology. To examine the effects that topology has on a cascading system, it is necessary to develop a cascade model as a complex network, where the generation, transmission, and load buses are modelled as nodes while the transmission lines are represented as edges in accordance to the circuit laws. We then explain how to use these models to run simulations of cascading failures on power grids. This is followed by a detailed explanation of average propagation.

Some existing research has already analyzed power grid networks by attacking critical power lines in the topology. The results often simulate the worstcase scenarios by causing critical power lines to fail(Pizzuti et al., 2020). In the real world, cascading failures can be caused by several factors, not just the failure of critical power lines. This means that the results from the existing research reflect only one kind of cascading failures(caused by critical line failures). In this paper, we applied a random attack method to obtain a better overall view of the impact of the cascade. The results based on random attacks on power lines are more acceptable than the results from attacking critical lines. A comparison of different attack strategies and their effects on the robustness levels of the tested networks was proposed in Ko? et al.(2013).

3.1 Cascading failure simulation

A cascading failure occurs when the failure of one part of an interconnected system results in the failure of more parts, and eventually the whole system. The concept is comparable to a set of falling dominoes. In a power grid,each line has a relay that protects it from permanent damage due to events such as excessive current. To avoid permanently damaging the line, an overcurrent relay notifies a circuit breaker to trip a line when the line’s current exceeds its capacity limit and this violation lasts long enough. As stated in Ko? et al. (2014), we assume that the capacityClof a transmission linelis proportional to its initial power flowLl(0) (when there is no failure in the network):

whereαlis the tolerance level of linel. Traditionally,power grid researchers have focused on the robustness of a grid for a specific grid tolerance level of the grid. The study of effects of using different tolerance levels is important in identifying the robustness and vulnerability of real-life networks;Wang JW and Rong (2009) showed that tolerance could be used negatively to cause damage by spreading rumors or positively to control epidemics.

For simplicity,we assume a deterministic model for the line tripping mechanism, where the circuit breaker for a line trips at the moment the flow of the line exceeds its capacity. When isolated islands are created by the failure, the cascading failure continues in each island in which generators or loads are separately shed,to attain a supply-demand balance.The cascade of failures continues until no more components are overloaded.

Following the notation of Dobson et al. (2006),we assume that the cascading failure is started by∈0＞0 initial failures in stage 0 and continues to produce further failures∈1,∈2,...in stages 1, 2, ...,respectively. The simulation is repeatedKtimes with different initial failures to produceKindependent instances of cascading failures.

We defineY(k)nas the total number of failures including stagenin thekthsimulation as

We apply MATCASC, a MATLAB-based cascading failure analysis tool from Ko? et al.(2013),to solve the power flow equations and analyze cascading line outages in power grids.

3.2 Average propagation

To deduce the growth of outages after they are initiated,it is necessary to have an estimator to predict the blackout severity. We use average propagation (AP), which was proposed by Dobson et al.(2006)to evaluate the scale of the cascading failure.For cascading data obtained fromKsimulations using the methods described in Section 3.1, AP is expressed as

With a triggering event leading to more outages,the chances that the entire system will collapse are rare. Rather, small independent islands will form,indicating that a few lines are still intact. Therefore,in the above equation,s(k) depends on the saturationS(Dobson et al.,2006):

We can see that the cascading failure simulation stops when the number of failures in any stage is zero or the total number of failures becomes at leastS.

AP can be divided into the following cases:

(1) AP＜1: In this case, the cascade tends to die after a certain number of stages. (2) AP＞1:Here,the cascade either ceases after some stages with certain probability or proceeds until the system is saturated.

3.3 Impact of tolerance level and saturation

We use simulations to evaluate the impact of tolerance level and saturation. We set the initial failure to be random attacks, where four randomly chosen transmission lines(edges)are removed.Fig.2a shows the impact of the tolerance level on AP for the IEEE 39 network. Data is obtained with[αmin=1,αmax=4] subdivided with Δα= 0.1.The impact of the tolerance level in Fig.2a suggests that AP decreases asαincreases. The larger the value ofα,the slower the decrease in AP.Therefore,network robustness is positively correlated withαas measured by AP. However, in reality, due to economic considerations,the safety margins are limited and will not be very high. Fig. 2b shows the effect of saturation in a cascading failure in terms of AP.We found that the increase in saturation causes a decrease in AP. It can be seen from the figure that when the ratio of saturation to the total number of edges reaches 0.6,AP decreases much more slowly as the saturation continues to increase.

We design a line capacity tolerance and saturation level to control the scale of failure(Anghel et al.,2007;Moussawi et al.,2017;Spiewak et al.,2018). In our numerical evaluations in Sections 3.4 and 5, we set the saturationSto 60% of the total number of transmission lines in the system and the tolerance levelαto 1.3 for each line.

3.4 Correlation between average propagation and algebraic connectivity

The relationship between algebraic connectivity and robustness is somewhat counter-intuitive. Dey et al. (2016)reported that after the removal of a line,the system tends to be less connected, thus increasing the network sparsity. Links tend to act independently of one another, which effectively reduces failure propagation. A system that has low algebraic connectivity tends to be less connected and there is a decrease in AP. Intuitively, a densely connected network will result in more severe propagation. As new connections typically characterize a power grid’s evolution, cascading failure is an increasing concern for the power grid as it grows in size. From the summary given above, our understanding is that in a sparsely connected network, if network connectivity is increased, it may become more prone to failure propagation. Thus, we need to find an optimal method to increase the network robustness by edge addition,with minimum increase in the failure propagation rate.

We conducted simulations on the IEEE 39 network and IEEE 118 network to test and identify the impact of algebraic connectivity on propagation. As explained in Section 3.2, several simulations were performed to estimate AP using Eq. (3). In each simulation, several random edges were added to the grid. After the addition of edges,the connectivity of the system is increased. Edges tend to act independently of one another,which effectively increases the failure propagation range. We again used random attacks to generate initial failures. The relationship between the algebraic connectivity and AP is shown in Fig.3. The correlation in Table 1 shows that when the network becomes more connected (that is, has higher algebraic connectivity), AP of failures is also increased. From these results, we can see an obvious positive correlation between algebraic connectivity and propagation spread. Because the cascading spread is also affected by some factors that are not captured by topological metrics, some discrepancies exist between algebraic connectivity and AP,but the general tendency of correlation is obvious.

Table 1 Correlation between the algebraic connectivity and average propagation for the IEEE 39 network and the IEEE 118 network obtained in 20 simulations

Fig. 2 Impact of the tolerance level on the average propagation(AP) for the IEEE 39 network (a) and impact of the saturation S on AP for the IEEE 39 network (b), where M is the ratio of S to the total number of edges

Fig. 3 Relationship between the algebraic connectivity and the average propagation (AP) in 20 simulations for the IEEE 39 network (a) and the IEEE 118 network (b)

4 Cascading failure reduction via algebraic connectivity

In real life, there are few chances to construct a totally new power grid network, either in a local area or for a whole country. Instead,experts and engineers are tasked with maintaining or finding ways to improve the robustness of an existing network.The actions of these engineers and experts are restricted by a budget (e.g., adding a fixed number of edges), having to follow government regulations,and other constrictions. These issues and concerns are the major motivations of this work.

4.1 Problem formulation

In this study, we aim to optimize the algebraic connectivity of power grid networks to improve robustness by minimizing AP. Consider the electrical network’s physical structure. Electric power is transferred from the generation buses to distribution substations through the transmission buses, interconnected by transmission lines. The graph of a power grid network can be described byG(V,E0), where node setVrepresents the generators, substations, and transformers in the power grid, and edge setE0contains the power transmission lines. Letndenote the size ofVandmdenote the size ofE0. The second smallest eigenvalue of the Laplacian matrix of a graph is called its algebraic connectivityλ2(L), and the corresponding normalized eigenvector is called the Fiedler vector (Fiedler, 1973). According to Ghosh and Boyd (2006), the Laplacian matrixLcan be represented by the dot product summation of edge vectors. For an edgeeconnecting two nodesiandj, we define the edge vectorhe∈Rnashe(i) = 1,he(j) =-1, and all other entries equal to 0. Then the Laplacian matrixLofGis ann×nmatrix:

The objective of this study is to reduce propagation of a cascading failure by minimizing the increase in algebraic connectivity after a fixed number of edge additions.

All possible edges that can be added are given in a pre-determined setP. We denote the edges chosen to be added as a set ΔE. Thus, the edge addition problem can be formulated as

4.2 Minimizing algebraic connectivity using greedy edge addition

Ghosh and Boyd (2006) presented a greedy local heuristic, where they addedkedges to the grid based on the Fiedler vector. In a sparsely connected network, addingkedges all at once may not produce an optimal result. By extending their method,we present an algorithm called modified greedy edge addition (MGEA) to reduce the propagation range by addingkedges using a selection criterion and minimizing the increase in algebraic connectivity.

According to Mohar et al. (1991), the algebraic connectivity can be computed by

whereyis ann×1 non-zero vector and it is orthogonal to the all-one vector 1. Furthermore, Eq. (7)can be transformed into

where we can replace vectorywith the normalized vectorv=y/‖y‖and we have Eq. (9):

The normalized vectorvin Eq. (9)is the Fiedler vector,because

MultiplyingvTto the left of both sides of Eq. (10)yields

Because vectorvis normalized,

Therefore,ifvis a Fiedler vector,the minimum in Eq. (9)can be achieved:

Based on Eq. (5), the Laplacian matrix after edge addition is

whereIfvis a Fiedler vector, we can obtain the algebraic connectivity as

So,minimizingλ2(Lnew)can be relaxed to minimizingλ2(L′). Note that ΔE ?P,and minimizingλ2(G′) is equivalent to selecting edges fromPthat have the smallest impact onλ2(LP). IfGis a large graph with many edges,adding one edge has only an insignificant impact on its second eigenvector. According to Eq. (13), we have

Because (vi-vj)2≥0, we can see that adding an edge can never decrease the algebraic connectivity. Fig. 4 shows 200 random instances of edge addition for the IEEE 118 network and the IEEE 2383 network. From the result, we can see that there is a strong positive correlation between the value of(vi-vj)2of an edge and the increase in the algebraic connectivity (λ2) after edge addition. Therefore, we believe that it is appropriate to apply our method to increase the robustness of the system, because it leads to small algebraic connectivity after edge addition, thus reducing the failure propagation range.

Fig. 4 Relationship between the value of (vi - vj)2 and the increase in algebraic connectivity after edge addition for the IEEE 118 network (a) and the IEEE 2383 network (b)

In summary, the MGEA algorithm picks one edge from the candidate set with the minimum(vi-vj)2at each iteration, whereviandvjare theithandjthitems of the Fiedler vectorvof the current Laplacian matrixL,respectively. The complete algorithm is listed in Algorithm 1.

Algorithm 1 Modified greedy edge addition 1: Given graph G(V,E0) and candidate edge set P 2: Let E = E0 3: for 1 to k do 4: Calculate λ2(G(V,E)) and its Fiedler vector v 5: eij = arg mineij ∈P (vi-vj)2 6: E = E+eij 7: P = P -eij 8: end for 9: Output G(V,E)

5 Experiments and results

Determining the optimal location of a new edge is challenging. The added edges should increase the power grid’s robustness by minimizing failure propagation. In this section, we review the results from the experiments that we conducted to evaluate the greedy edge addition algorithm’s ability to improve the robustness of power grid networks. Our study is intended to examine the following question:Does MGEA outperform the other four baseline strategies?

5.1 Experimental protocol

5.1.1 Datasets

Four datasets, IEEE 39, IEEE 57, IEEE 118,and IEEE 2383, are used in our experiments. Some properties of the datasets are presented in Table 2.We will evaluate the performance of our algorithm in terms of(1)minimizing the algebraic connectivity increase and (2) reducing the average propagation rate. Considering the issue of protecting the grid against random failures or targeted attacks, in our experiments,cascading failures are triggered by random attacks, where four randomly chosen transmission lines (edges) are removed. For the IEEE 2383 dataset, which has a total of 2896 edges, we remove 10 lines instead, to compensate for the large number of edges compared with the other three datasets.Because different initial attacks can lead to different results, we performed 200 iterations when calculating AP (i.e.,K=200 in Eq. (3)).

Table 2 Numbers of nodes and edges in each dataset

The number of lines removed randomly in each cycle was determined by experiments. Based onN-kcontingency analysis(Wei XG et al.,2019),we narrowed down the initial powerline removal number to be between 2 and 20. We found that removing 4 edges in a small network and 10 edges in an extensive network satisfied the needs for computational efficiency,while preserving the experimental results’trends. In real-world networks,most changes are restricted by limitations and budgets,such as limits on the number of powerlines that can be added and the need to comply with government regulations,among other restrictions. Based on real-world power grid topologies, our simulations return the top 20 edges that can be added to the original network,which can help simplify a human engineer’s decision making to improve the grid’s robustness. How those edges are chosen in each strategy is explained below.

5.1.2 Baseline strategies

Here, we compare MGEA with the baseline strategies. Table 3 summarizes the strategies and their corresponding computational complexities.

Table 3 Summary of the strategies and their computational complexities

1. Random(RD)

The random addition strategy simply chooses anedge from the candidate set at random. It is often selected as a reference to be compared with other edge addition strategies.

2. Degree product(DP) (Marsden,2015)

The degree of a node is the simplest centrality metric that reflects a node’s importance in its locality(Marsden,2015). For an undirected network,the degree of a node is equal to the number of edges connected to it. The edge in the candidate set with the lowest degree product is added.

3. Betweenness (BT) (Guan et al., 2011; Jiang et al., 2011)

Betweenness is one of the most important metrics to evaluate the routing strategy performance of a network (Jiang et al., 2011). We define the betweenness product of an edge (i,j) in the candidate set as (CB(i)+1)(CB(j)+1), whereCB(v) is the betweenness centrality of nodevas defined in Guan et al.(2011). Note that one is added to the betweenness before calculating the product because the betweenness for some nodes can be 0. The edge in the candidate set with the lowest betweenness product is added.

4. Effective resistance (ER) (van Mieghem,2010;Ko? et al.,2014)

According to Ohm’s law,the effective resistanceRijis the potential difference between nodesiandjwhen a unit current is injected at nodeiand withdrawn at nodej(van Mieghem, 2010). The edge in the candidate set with the highest effective resistance is added.

Note that each algorithm is repeated multiple times, adding one edge each time, until the target number of edge additions is reached. For all the experiments performed in this study,the candidate set is chosen to be the set of all possible edge additions that do not lead to self-loops or parallel edges.

5.2 Performance comparison

Tables 4—7 present the values of AC and AP for each algorithm on the four datasets we used. Overall,we can see that the random,degree product,and effective resistance algorithms are far inferior to the MGEA algorithm proposed in this study. The performance of the betweenness algorithm is similarly to that of our algorithm when the first few edges are added. However, after more edges are added,our algorithm surpasses the betweenness algorithm substantially.

Table 4 Algebraic connectivity (AC) and average propagation (AP) after edge addition for the IEEE 39 network

Table 5 Algebraic connectivity (AC) and average propagation (AP) after edge addition for the IEEE 57 network

Table 6 Algebraic connectivity (AC) and average propagation (AP) after edge addition for the IEEE 118 network

Table 7 Algebraic connectivity (AC) and average propagation (AP) after edge addition for the IEEE 2383 network

5.2.1 Algebraic connectivity

As shown in Figs.5a,6a,7a,and 8a,the results suggest that the MGEA algorithm performs better than the other baseline methods in all four datasets in terms of minimizing the increase in AC. Fig. 5a shows that the results of the betweenness algorithm are relatively close to those of our algorithm initially.

However, after 10 edges are added, the distinction becomes clear, with our algorithm having the best results. Therefore, for the IEEE 39 network,we can say that the performance of the MGEA algorithm is the best among the five we tested. In addition, we find that the topology of the IEEE 39 network and some grid-related parameters are relatively close to those of the IEEE 118 network,so it is reasonable for the IEEE 39 to be similar to the IEEE 118 in experimental results.

For the IEEE 2383 network, Fig. 8a shows that the performance of the MGEA algorithm is also better than those of the baseline algorithms. We can conclude that each of the five algorithms tested adds different lines to the network,and each added line influences the topology’s overall strength in a different way. The MGEA algorithm appears to be the most successful one among the five tested in improving the overall robustness of the whole network.

5.2.2 Average propagation

We can see from the results that among all the strategies tested, the MGEA algorithm yields the most robust network configuration against cascading failures, as measured by AP. However, as shown in Fig. 6b, the results of the DP algorithm are comparable to those of our algorithm except for the last few edges, where the performance of the DP algorithm deteriorates. Electric power is transmitted from the generation buses to the load buses through intermediate(transmission)components,which deliver electric power from generators to consumers. We believe that this may be because the DP algorithm adds only edges from one of the two nodes in the initial grid with very small degrees to the other nodes. When these edges fail, there are more neighboring lines around the edges that can carry the fault. The load makes the edges of the surrounding nodes less prone to overloading and failure, so AP of the cascading failure is relatively small. Another possible reason is that after studying the IEEE 57 network, we findthat its topology is slightly different from those of other networks. The generators are concentrated in one area, and the generator degrees are very low.When a new line is added to a generator, AP of the cascading failure may be smaller if the new line is added in a network with a different topology. For the IEEE 2383 network,the difference among the algorithms is not very obvious when adding the first10 edges, due to the large number of existing edges.Also, because the electrical characteristics of power grids are not captured in the algorithms, the tendency of the results is not uniform. However, after the addition of a significant number of edges,the performance of the MGEA algorithm shows superiority against the other algorithms tested.

Fig. 5 Algebraic connectivity (AC) (a) and average propagation (AP) (b) after edge addition for the IEEE 39 network

Fig. 6 Algebraic connectivity (AC) (a) and average propagation (AP) (b) after edge addition for the IEEE 57 network

Fig. 7 Algebraic connectivity (AC) (a) and average propagation (AP) (b) after edge addition for the IEEE 118 network

Fig. 8 Algebraic connectivity (AC) (a) and average propagation (AP) (b) after edge addition for the IEEE 2383 dataset

6 Conclusions

In this study, we studied topology-based design optimization strategies for selecting transmission lines to add a power grid’s topology to a power grid, to increase its robustness in terms of average propagation. Experimental results on four power grid datasets showed that our proposed MGEA algorithm outperforms all the compared algorithms.We expect our algorithm to help experts better design new power grid topologies and maintain power grid systems in the future.

At the same time,it is noted that algebraic connectivity is a topological measurement that is widely used to assess network characteristics. Although a topological approach is appropriate to evaluate the power distribution grid, purely topological metrics fail to capture some inherent electrical characteristics of power grids. In our work,the network modeled does not fully distinguish different types of buses in the system because buses in a power grid can be categorized into different categories such as generation,transmission,or load buses. We will leave that to the future work to incorporate more electrical properties in a power grid model.

Furthermore, power grids of the same structure can also display different robustness in practice.Among existing studies, the robustness of a power grid network can be related to various factors, such as consumers’accessibility to generators(Zhang and Tse,2015),tolerance factors(Liu J et al.,2019),and electrical properties such as resistance and power flow (Ko? et al., 2014). Discovering such relationships is an important direction for future research.

Contributors

Supaporn LONAPALAWONG designed the study and addressed the problems. Supaporn LONAPALAWONG and Jiangzhe YAN processed the data and designed the algorithms. Jiayu LI and Deshi YE helped deduce the mathematical models and algorithms. Supaporn LONAPALAWONG drafted the manuscript. Yong TANG and Yanhao HUANG helped with the technical information. Wei CHEN supported with the resources. Can WANG helped organize the manuscript. Supaporn LONAPALAWONG, Jiangzhe YAN,and Can WANG revised and finalized the paper.

Compliance with ethics guidelines

Supaporn LONAPALAWONG, Jiangzhe YAN, Jiayu LI, Deshi YE, Wei CHEN, Yong TANG, Yanhao HUANG,and Can WANG declare that they have no conflict of interest.