Identification of critical nodes for cascade faults of grids based on electrical PageRank

0 Introduction

In recent years, the occurrence of large-scale power outages in the world has caused enormous economic losses to local areas.On November 21, 2020, Jilin city, Jilin province suffered a snowstorm weather trip fault, affecting 300,000 users.In the early morning of February 14, 2021, a 7.3-magnitude earthquake occurred in Japan, resulting in a total of 860,000 power outages within the jurisdiction of Tokyo Electric Power Company.These accidents have gained the interest of many researchers worldwide.The mechanisms of these accidents show that the failure of power grid nodes causes transfer of the power flow in different scenarios and cascading failures, which may eventually lead to the disintegration or even collapse of the power system.Therefore, accurate and rapid identification of the critical nodes and lines that contribute to cascading failures in a power grid [1], [2] can effectively prevent the occurrence of cascading failures.Achieving these objectives will also play a very important role in guiding the planning and construction of a power grid and improving the stability of the power system.Finding a method to accurately identify the critical nodes triggering cascading failures in a power grid and exploring the evaluation method of critical node identification in a power grid are prominent research areas.

Numerous methods are available for identifying the critical nodes in power systems; however, they can be further improved.In [3], the vulnerability of a power system was evaluated based on information such as its operating mode and the line currents of the power distribution.In [4], a method combining a weighted network model and the heterogeneity of grid topology and distribution was proposed for the identification of hazardous lines during power transmission.Because the consequences of a fault chain also have an impact on grid assessment, in [5], they were rationally assigned as indicators of the vulnerability of grid branches based on the game results, using a cooperative game framework.In [6], an assessment method based on a fuzzy integrated evaluation of the entropy group of utility risk was proposed.In [7], a critical vulnerability line identification method based on weighted power flow margin intermittency and dynamic power flow transmission integrated entropy was suggested.Identification of the vulnerable nodes of power systems based on weighted networks was reported in [8]-[11].Moreover, the concept of an exchange graph was extended in [12] for improving PageRank to identify vulnerable lines.The load of nodes and the topology of the network also affect the importance of nodes, and in [13], the PageRank algorithm was improved to identify the important nodes of a grid.However, the type of node also affects the importance of nodes; therefore, in [14]-[16], the method was considered for edge nodes.To better evaluate nodes, [17] investigated the average load oscillation level of other nodes by considering one node as the attacked indicator node.In addition, [18] improved the PageRank algorithm for identifying critical lines based on electrical intermittency, load deviation rate, and voltage shock rate.However, the consequences of cascading faults also serve as important reference factors, and [19] and [20] considered this aspect to identify the critical nodes in a grid.Although the proposed methods are suitably improved based on some of the characteristics of a grid, and some possible deviations can be avoided, the strategies are still lacking.

The previous studies did not consider the state of the power system after node failure.Therefore, inspired by the above research results, based on the PageRank algorithm and complex network knowledge, we propose a critical node identification method for a power grid by combining the cascading failure model and the PageRank algorithm.This method fully considers the impact of a node failure on the power system of a grid.The loss caused by the chain reaction due to a node failure is used as a weight to improve PageRank.

The main study is as follows:

(1) The Google matrix is modified based the topology of a grid combined with the tidal direction.

(2) Based on cascading failures, the losses of each node to the entire grid after failure are calculated and the corresponding loss rate of each node is determined.

(3) The PageRank algorithm is improved and called the electrical PageRank (EPR) algorithm.

(4) The effectiveness of the method is verified in terms of the average load loss, system connectivity, and network transmission efficiency and compared with those of other identification methods.The comparison results show that the proposed method is superior to other methods.

The contributions of this study are as follows：

(1) The impact of cascading faults on the power system of a grid is considered.

(2) The PageRank algorithm is improved based on the characteristics of the power system; therefore, it can accurately evaluate the critical nodes in the power system.It can focus on protecting the evaluated critical nodes.

1 Cascading Fault Analysis

A cascading fault of the power system of a power grid occurs when the power grid is tripped by natural disasters [21], manmade intentional damage, and other causes.Consequently, some loads inside the power system are transferred to other nodes, resulting in a successive overload of the power system lines and tripping of the protection devices, causing large-scale blackouts and even power grid disintegration.Cascading faults in power systems cause significant losses to the lives of people and affect social development.

In a complex power grid, a small effect may lead to a cascading failure and even large-scale paralysis of the power system.The existing cascading failure models mainly include the CASCADE model and the hidden failure model [22].In this paper, the cascading fault method refers to the CASCADE model.Based on the CASCADE model, the load loss caused by a node exit is also considered.This model is used to calculate the load loss of the power system of a power grid caused by an attack on it and by the withdrawal of some devices, which lays the foundation for the proposed EPR algorithm.

The cascaded fault method uses the optimal power flow [23]-[25] to obtain various types of power grid data.The optimal power flow model is as follows:

where x is a state variable, u is a control variable, and objective function f and some constraints in inequality constraints h and equality constraints g are nonlinear functions of these variables.are the lower and upper bounds of the active power output in the inequality constraints, respectively.

The specific workflow of the cascading failure model modeling is as follows:

(1) Power system modeling is conducted using the MATPOWER toolbox.

(2) Based on the optimal power flow equation, the power of the transmission lines in the power system of a power grid is calculated.If the power flow calculation converges, then step 3 is proceeded.If the calculation flow does not converge, load shedding is conducted, and subsequently step 2 is continued.

(3) Based on the optimal power flow, the line transmission power value of the power system is obtained to determine the occurrence of line overload.The overloaded parameter in the cascading failure model is set as β.If the transmission power value of a line exceeds β times of its rated value, severe overload of the line is determined, and the line is removed, and step 4 is proceeded.

(4) The entire power grid is tested to examine whether a line is removed owing to overload or other causes.If a line being cut, then the power system parameters are updated and step 5 is proceeded.If all lines in the power system are not removed, step 6 is proceeded.

(5) Based on the topology parameters of the power system, the existence of an island in the power grid is examined.If there is no island in the grid, then step 6 is executed.If there is an island in the power grid, load shedding of the island is conducted.Subsequently the optimal power flow is calculated and the power system data are updated.

(6) If all nodes are attacked, step 7 is executed.Otherwise, step 2 is executed.

(7) The load loss, P(i), of the power system in a cascading failure and the number of node losses, J(i), caused by the cascading failure after each node is attacked are calculated to determine the system loss index.

(8) The load loss is normalized and defined as the load loss rate.The load loss rate equation is as follows:

where P(i) is the load loss load of the power system after node i is attacked and P is the total load of the power system.

The average load loss and the average node loss are as follows:

where n is the number of nodes and J(i) is the number of nodes lost after node i is attacked.

Because island processing is highly complex, to reduce the amount of calculation, an isolated area without balanced nodes is set to determine the island, and the corresponding operation is conducted.

The calculated load loss rate, average load loss, and average node loss caused by the cascading failure lay the foundation for the EPR algorithm as well as provide the basis for verifying its superiority to other methods.

2 EPR

The PageRank algorithm is a method proposed by Google to efficiently identify the most influencing nodes in a network.The equation of PageRank is as follows:

where PR(x) is the PageRank value of web page x, PR(j) is the PageRank value of web page j, web page j is connected to web page x via a number of links out of web page j, i.e., Lout(j), and σ is the damping coefficient.If the damping coefficient is large, the level of the web page is high, and in general, it is 0.85 [26].Based on the PageRank equation, a large value of PR(j) indicates high importance and a large PageRank value of page x.

The PageRank algorithm is simple, fast, and robust, and it can rapidly and accurately identify influencing pages.However, compared with the Internet, a power system has its own unique characteristics, and problems can be easily caused when the PageRank algorithm is directly used in a power grid.In the iterative process of the PageRank algorithm, the PageRank values of a node is evenly distributed to the node that a given node points to.However, after the operation of a power grid, in the power system, the relationship between the lines varies, and the average distribution shows large errors.

Therefore, in view of the above problems, this paper proposes the EPR algorithm based on the direction and size of the line power flow and the load loss rate.Because a power system network is highly complex, to facilitate our research on a power grid, we need to simplify the power system.A power system is composed of power plants, transmission lines, and electrical loads.In a grid, power plants and substations are transformed into nodes, and transmission lines are transformed into the edges of the graph.Because a grid is directional, the edges formed by the grid are also directional, and the direction can be calculated using the optimal power flow.The simplified grid can be represented by a directed adjacency matrix.If the grid contains n nodes, the power network is represented by an n×n adjacency matrix G.

The element, gij, in the grid adjacency matrix is defined as follows:

Because the PageRank algorithm does not consider the characteristics of a power grid but those in the power system, all grid nodes are different and cannot follow the average weight distribution of the PageRank algorithm.The weight distribution must be based on the characteristics of the node power grid.Therefore, we improve the PageRank algorithm according to the adjacency matrix of the power system, number of nodes in and out of the node, and load loss after a node is destroyed.The improved algorithm is called the EPR algorithm.The calculated results are the EPR values.

The improvements to PageRank are as below.

First, the distribution ratio, α(j→i), of the EPR values of a grid node considers the influence of the transmission power of the grid node on the node importance and the influence of the node load on the node importance.The equation of α(j→i) is as follows:

where α(j→i) represents the EPR weight assigned to node j, Y represents the set of out-link points of node j, and EPR(i) represents the EPR value of node i.

Subsequently, γ(i) represents the weight of node i and considers the load loss caused by the node attack.The equation is as follows:

In Equations (9) and (11), A represents the set of grid nodes, Y represents the set of out-link points of node j, Li-in represents the number of in-link points of node i, Li-out represents the number of out-link points of node i, and y represents an element of the set of out-link points of node j.The number of in-link points and out-link points of each node can be obtained using the adjacency matrix, G.Pji represents the power supplied by node j to node i and Pj represents the total power supplied by node j to its out-link node.The load loss rate, S(i), is obtained using Equation (3).

Finally, combining α(j→i) and γ(i) to improve the PageRank algorithm, the improved EPR algorithm equation is as follows:

Based on Equation (12), the EPR values of each node in the power grid are calculated and sorted to find the critical nodes in the power grid.

3 Identification Algorithm Process of Critical Nodes in Power Grid

The critical node identification of a cascading failure in a directed weighted power grid based on the EPR algorithm is presented in Algorithm 1.

Algorithm 1 EPR algorithm 1: Calculate optimal tide using (1) and (2)2: Calculate link matrix of grid using (7) and (8)3: Update α(j → i ) based on (9) and (10)4: Update γ(i) based on (11)5: if EPRi(j) - EPRi(j +1) ≤ 10-6 then 6: Calculate EPR(i) using (12)7: end if 8: return EPR(i)

The MATPOWER toolbox is used to calculate the optimal power flow of the grid.

(1) Based on the grid data calculated in step 1, the power flow direction of the grid is determined and the adjacency matrix, G, of the power grid is established.

(2) Based on the cascading failure model of the power grid, the load loss, Si, of the attacked node, i, is calculated.

(3) Using the grid directed adjacency matrix, line power flow, and load loss Si, γ(i) is calculated using Equation (11) and α(j→i) is calculated using Equation (9).

(4) The initial values for all nodes and the threshold for iterative convergence of the EPR algorithm are set.The threshold is set as EPRi( j )-EPRi( j+1 )≤10-6 or the maximum number of iterations is set as 50 based on experience.

(5) The EPR values of all nodes are iteratively calculated using Equation (12), and the nodes with large EPR values are of high importance.

4 Simulation results analysis

This section takes the IEEE39 node as the simulation object to verify the effectiveness and accuracy of the EPR algorithm.The IEEE39 bus system is shown in Fig.1.The simulation object contains 10 generators, 12 transformers, and 46 lines.The data of the IEEE39 bus system are obtained using the MATPOWER toolbox.Based on the method proposed in Reference [27], when the line load rate is 2.5 times greater than the rated value, i.e., β = 2.5, the line overload is considered [28].

Based on the cascading failure model established in this study, the IEEE39 standard system is used for simulation.

First, in the process of cascading failure simulation of the IEEE39 standard system, from No.1 attack node to No.39 node, in the power flow calculation of the system, the balance node ensures the power flow convergence.Therefore, the cascading failure model does not attack No.31 balance node, and the load loss of each node after the attack is obtained.

Subsequently, normalization is conducted using Equation (3), as shown in Fig.2.In Fig.2, we can see that the load loss rates of nodes 2 and 6 are very high.Following this, the corresponding weights are calculated using Equations (9) and (11).Subsequently, the numbers of in-link and out-link points of each node are obtained using the adjacency matrix, G, and the results are summarized in Table 1.

Finally, the obtained L(i), Li-out, and Li-in as well as the weights α(j→i) and γ(i) input are used to calculate the EPR values of all IEEE39 nodes and sort them.The top ten critical nodes obtained by the EPR method are 16, 39, 6, 9, 27, 15, 24, 8, 4, and 26, respectively, as listed in Table 2.

Remark 1: In the simulation of cascading faults, a large loss of a single node does not fully indicate its importance.This is because, in the EPR algorithm, various factors such as S(i) and topology are considered.For example, although node 34 after being destroyed causes a large loss, it is not particularly important in the entire power system.In comparison, node 27 after destruction causes a loss that is not as large as that caused by node 34; however, it is still important in the entire power system.This is because the nodes around node 27 are also important.This is a common process, which partly depends on the simulation, to analyze the cascading faults for identifying important nodes or lines.

To verify the effectiveness and advantages of the EPR algorithm proposed in this paper, three experimental schemes are set.

Table 1 Number of access chain points of IEEE39 node

Node number Number of in-links Number of out-links 1 1 1 2 2 2 3 1 2 4 3 0 5 1 2 6 2 2 7 1 1 8 2 1 9 1 1 10 1 2 11 2 1 12 1 1 13 1 2 14 1 2 15 2 0 16 3 2 17 1 2 18 2 0 19 1 2 20 2 0 21 1 1 22 1 2 23 2 1 24 1 1 25 1 2 26 3 1 27 2 0 28 1 1 29 1 2 30 0 1 31 0 1 32 0 1 33 0 1 34 0 1 35 0 1 36 0 1 37 0 1 38 0 1 39 2 0

Table 2 Critical node EPR values for IEEE39 nodes

Sort Node number EPR value (10-5)1 16 4.9258 2 39 4.9070 3 6 3.2978 4 9 3.0953 5 27 3.0924 6 15 2.7090 7 24 2.3411 8 8 2.2413 9 4 2.1871 10 26 1.9885

Fig.1 IEEE39 bus system

Fig.2 IEEE39 node loss rate

(1) The EPR algorithm is compared with the PageRank algorithm.Because one attack does not involve numerous nodes, the average load loss and average node loss of the first five nodes evaluated by the EPR and PageRank methods are calculated in this study.The first five nodes of the IEEE39 node identified by the EPR and PageRank algorithms are listed in Table 4.The critical nodes identified by the PageRank algorithm are 39, 16, 27, 9, and 8, whereas by the method proposed in this paper are 16, 39, 6, 9, and 27.The reason for the different critical nodes is that the method proposed in this paper combines the characteristics of the direction and size of the line power flow and the load loss rate.In comparison, the PageRank algorithm does not consider these characteristics.The average load loss calculated using Equation (4) and the average node loss calculated using Equation (5) are listed in Table 3.

Table 3 Average loss comparison

Attacking method Average lo 1564.ad loss Average node loss Electrical PageRank 6 10.4 PageRank 991.2 3.2

Table 4 Important nodes ranked with evaluation methods

Sort EPR M.1 [14] M.2 [15] M.3 [29] M.4 [30]1 16 8 2 15 16 2 39 4 1 16 17 3 6 16 5 3 3 4 9 27 4 8 4 5 27 15 6 27 14

It can be seen from the data in Table 3 that the average load loss after attacking the first five nodes obtained by the EPR algorithm is 1564.6 MW and the average number of loss nodes is 10.4.Compared to attacking the critical nodes obtained by the PageRank algorithm, the loss caused by attacking those obtained by the EPR algorithm is larger.By comparing the load loss index, the EPR method has more advantages than the PageRank method.It can be seen that the proposed directed weighted power grid cascading failure method based on EPR has high accuracy in evaluating power grid nodes.

(2) To further verify the superiority of the proposed method to other methods, we use a random attack and the top five critical nodes evaluated in the attack literature in [14], [15], [29], and [30].The attack sequence is summarized in Table 4.The first five nodes are selected respectively, and the maximum load, R, is chosen as the vulnerability index.The fundamental role of a power grid is to provide sufficient and reliable power supply for the load demand.This indicator is the maximum load that can be supported by the existing power grid, and it is an important indicator to evaluate the vulnerability of the power grid as follows:

where P represents the total load of the power system and Pload represents the load that the system can support after the attack.Fig.3 compares the vulnerability indicators after six attacks.

Fig.3 illustrates the vulnerability of the power grid when the power system nodes are gradually attacked.After the five nodes are subjected to random attacks in succession, the load that the power grid can withstand is only reduced by approximately 20%, which indicates that the grid is more robust to random attacks than to intentional attacks.The grid is significantly more robust to intentional attacks by methods such as M.1 than EPR attacks, indicating that the EPR method is more accurate in identifying critical nodes.

Fig.3 Load index under node attack

Fig.4 System connectivity under node attack

(3) In addition, system connectivity Q is used to test whether the grid can maintain normal power supply, particularly after a node attack that results in a cascade failure that creates an island, as follows:

where Sm represents the set of nodes of the subsystem after islanding, M represents the number of subsystems, and N represents the number of nodes in the system before the attack.

From Fig.4, it can be seen that a random attack has little effect on the system connectivity compared with a deliberate attack.Moreover, after attacking the first five nodes in turn, it can be found that an EPR attack and an M.4 method attack decrease the system connectivity by 25%, and the performance of the EPR and M.4 methods are similar in terms of system connectivity.However, based on the attack of the first four nodes, the EPR attack is superior to the M.4 method.

(4) Network transmission efficiency reflects the shortest path from the generator node to the load node.It is obtained as follows:

where G and L denote the generator node and the load node, respectively; dij denotes the shortest transmission path from the generator node to the load node; and G0, L0, and dij0 represent the parameters of the grid before it is attacked.

Fig.5 Network transmission efficiency under node attack

As can be seen from Fig.5, for random attacks, the network transmission efficiency slightly decreases, whereas for deliberate attacks, particularly EPR attacks, it decreases significantly, even by 70%.It can be noted that the EPR method is significantly better than the other methods in terms of identification.

5 Conclusion

This paper presents an EPR grid critical node identification method based on EPR.In identifying the importance of the nodes of a grid, the connection characteristics of the grid, electrical topology relationship between individual and neighboring nodes, and direction of the power flow are considered.In addition, the importance of individual nodes in complex grids can be obtained and the critical nodes of large grids can be accurately identified.The effectiveness of the proposed method is verified by comparison with other evaluation methods in terms of performance, such as connectivity.It can be seen that the proposed method effectively improves the identification of cascading faults of the critical nodes in power systems and can effectively prevent such cascading faults and avoid power outages.However, new energy sources are not considered in this study.New energy sources are intermittent and unstable and can pose a major challenge to a grid.In the future, we will improve this method from the aspect of grid connection of new energy sources to make it more extensively applicable.

Acknowledgement

This study was supported by the National Natural Science Foundation of China (61873057).

Declaration of Competing Interest

We declare that we have no conflict of interest.