# Research on Local Topology Tracking of Power Grid Based on Graph Theory

Authors: Sujing Zhou
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Power network topology identification, judgment, and tracking are the basic functional components of power system guarantee system and security management system. They can provide basic network structure data for other application software programs of power system. However, the traditional power grid topology method is not easy to implement and provides less relevant data that can be accurately analyzed, so that relevant personnel cannot fully understand the state of the power grid and give accurate commands, resulting in serious power accidents. Therefore, this paper proposes the research of power grid local topology tracking based on graph theory and constructs the power grid local topology tracking algorithm based on graph theory. The experimental results show that the local topology tracking algorithm based on graph theory can track the local topology of power grid quickly and effectively. Compared with the traditional method based on priority search, although the first power grid topology takes a relatively long time, it greatly improves the search and processing time after each time and has high efficiency in local topology. This shows that the local topology tracking algorithm based on graph theory needs less computation when carrying out the local topology of power grid. At the same time, the theory of power grid local topology tracking algorithm based on graph theory is relatively simple and easy to time, which is more practical than the traditional method.


---

## Body

## 1. Introduction

In power system, power network topology identification, judgment, and tracking are the basic functions of energy management and distribution management system, and the analytical mathematical model transformed into it can provide corresponding basic network structural data for power system state estimation, fault analysis, and reactive power optimization [1]. In the power system, the bus is the collection of physical nodes connected by closed circuit breakers and disconnectors, and the electrical island is the collection of buses connected by lines, transformers, and other branches [2]. In the real-time state of the power system, there are often cuts, loads, and other situations. At this time, the relevant nodes corresponding to the bus section in the substation will change, which is likely to cause problems such as open-loop, closed-loop, and parallel power grid [3]. The purpose of topology analysis and tracking of the store network is to obtain the state of the bus and electrical island according to the corresponding judgment and calculation results when the switching state of the network changes, so as to further monitor the network status, security, and stability of the power system [4]. However, the database of traditional power grid topology contains less relevant information, which means that it does not have enough accurate data for corresponding state analysis and estimation [5]. This makes the network topology analysis able to only be implemented and judged in a single substation and unable to be connected with other substations. When the substation AC is blocked, the relevant personnel of power grid operation cannot accurately obtain the operation data of power grid, and even serious power accidents may be caused by issuing wrong instructions [6].With the continuous development and in-depth research of information and measurement technology, it provides technical support for power system protection and control and also makes the power grid topology identification and tracking model have a new development direction [7]. How to search, identify, and track the power grid in a short time has become a research hotspot. Therefore, this paper proposes a research on power grid local topology tracking based on graph theory, which is mainly divided into three parts. The first part describes the development and current situation of graph theory and power grid topology tracking. The second part introduces the related concepts and algorithms of graph theory and introduces the grid local topology tracking algorithm based on graph theory. In the third part, the simulation experiment and algorithm performance related experiment of power grid local topology tracking algorithm based on graph theory are carried out, and the data are collected and the experimental results are analyzed.


### 1.1. Our Contribution Is Threefold

(1)
This paper proposes the research of power grid local topology tracking based on graph theory and constructs the power grid local topology tracking algorithm based on graph theory.(2)
Experiments show that the local topology tracking algorithm based on graph theory has less computation in solving local topology of power grid. Moreover, the local topology tracking algorithm based on graph theory is relatively simple, easy to time, and more practical than the traditional method.(3)
Experimental results show that the local topology tracking algorithm based on graph theory can quickly and effectively track the local topology of power grid, greatly improves the search and processing time after each time, and has high efficiency for local topology.The remainder of this paper is organized as follows. Section2 introduces the related work. Section 3 discusses the method. Section 4 discusses the experiment and analysis. Section 5 presents the conclusions of the study.


## 1.1. Our Contribution Is Threefold

(1)
This paper proposes the research of power grid local topology tracking based on graph theory and constructs the power grid local topology tracking algorithm based on graph theory.(2)
Experiments show that the local topology tracking algorithm based on graph theory has less computation in solving local topology of power grid. Moreover, the local topology tracking algorithm based on graph theory is relatively simple, easy to time, and more practical than the traditional method.(3)
Experimental results show that the local topology tracking algorithm based on graph theory can quickly and effectively track the local topology of power grid, greatly improves the search and processing time after each time, and has high efficiency for local topology.The remainder of this paper is organized as follows. Section2 introduces the related work. Section 3 discusses the method. Section 4 discusses the experiment and analysis. Section 5 presents the conclusions of the study.


## 2. Related Work

Graph theory is a branch of mathematics. Compared with the development time of mathematics, the development time of graph theory is quite short. According to relevant literature, people took a paper published by Euler in 1736 as the beginning of the formal proposal of graph theory. It can be seen that the development of graph theory has only a history of more than 300 years [8]. However, graph theory itself is easy to understand. Even though it still has many difficulties and problems in practical application, it still begins to develop rapidly. In the 1930s, the publication of the first monograph on graph theory laid the foundation for its theoretical knowledge to a certain extent and began to basically form an independent branch of mathematics [9]. With the continuous development and popularization of science and technology and computer technology, mathematics has got a very huge application space in many fields and achieved good results. This makes graph theory get more and more opportunities to be applied in different fields. Many problems are effectively analyzed and solved through the abstract mathematical model of graph theory. In recent years, graph theory has shown its good performance in the fields of transportation, computer, military, Internet, and social science. At the same time, it not only solves the practical problems in these fields but also greatly accelerates the development of graph theory’s own theoretical system. For example, the coloring theory in graph theory has developed into an important module in graph theory [10].In the rapid development of human society, power system occupies a very important position. As the basis of power system analysis and application software, the accuracy of power grid topology has a direct impact on the operation state and security and stability detection of power system and has an impact on the use effect of power system fault judgment, estimation, analysis, and other programs by relevant staff [11]. Since the early 1980s, the relationship between power network topology and power system has attracted the attention of some scholars and began to be studied in this area. In order to better use the simultaneous establishment of linear equations to describe the branch electrical quantities existing in the power network, its resistance, inductance, and capacitance are abstracted, and the complex correlation relationship between them is represented by the correlation table constructed by points and lines, which replaces the original power grid [12]. When the power grid topology changes, the association table can be modified to track the topology. Since the mid-1990s, switching changes often occur in the actual operation of power system, but few people take them into account. Therefore, corresponding tracking technology is integrated into the regular plant station wiring analysis, so that it can modify the local topology when the switching state changes. This way is not only simple and convenient, but also easy to implement. In addition, some scholars use object-oriented technology to build the model of plant station and power grid topology tracking through class and other data structures and realize the integrated operation of data and graphics [1]. Some scholars have introduced the breadth first search network topology method based on the graphical model, which can solve the problem of repeatedly searching the same node to some extent, so as to improve the real-time performance and accuracy of the model [13]. Other scholars consider that the analysis of internal bus and the analysis of electrical island between stations should be carried out and completed in the control center, so they have constructed a hierarchical and distributed topology modeling method, which can analyze the bus of different stations at the same time. Finally, the data is uploaded to the control center through the smart grid for power grid topology analysis between plants and stations [14]. With the development of cities and countries, the power system has to bear more and more pressure. Therefore, the power grid topology analysis has gradually developed from local analysis to comprehensive real-time analysis, which is also the direction of power grid topology development.To make the grid smart, an advanced communication infrastructure is required to transmit sensing, control, and automation information in a timely, reliable, and efficient manner. Reusing the power lines themselves to implement (in part) this infrastructure is an obvious choice, with a long and successful track record in power utilities. Reference [15] suggests that taking advantage of the fact that the nodes of a power line communication (PLC) network are stationary, messages can be transmitted quickly and efficiently through a route composed of a series of communication links. Specifically, we use the location information of PLC nodes to route messages along favorable paths. This geographical or geographic routing is particularly useful. Reference [16] proposed a unified controller for rural electrified DC nanogrid based on Cuk converter-assisted variable speed wind turbine driven self-excited motor (SEIG). The Cuk converter-based SEIG Wind Energy Conversion System (WECS) is considered as the primary source of nanogrids, which can operate in grid-connected and island-operated modes.


## 3. Methodology

### 3.1. Graph Theory Concept and Its Algorithm

Graph theory is a graph model that can describe the mathematical model with pairwise relationship. It has three necessary elements: node, edge, and edge weight. The node can be any concrete individual or abstract individual, and the edge in the graph is an abstract description of the pairwise relationship between the individuals represented by the node. LetGv,ε,w represent the graph model, where v is the node and its set is v=v1,v2,…,vn , ε is the edge and its set is ε=e1,e2,…,eε , and w is the edge weight and w=w1,w2,…,wε. When the node set, edge set, and edge weight are determined at the same time, a graph can be determined. Graph model is generally divided into directed graph with specific direction on each edge and undirected graph without specific direction on each edge. In this paper, undirected graph is selected. When the node set is a given condition, there are usually three ways to build a graph. One is the whole graph; that is, all nodes in the graph and other nodes are connected. The second is the KNN graph; that is, each node in the graph has k nearest neighbors, and the node is only connected to these K nodes. The third is the graph; that is, all nodes in the graph are connected and the nodes with a distance less than ε.Generally, there are three edge weighting methods. The first is 0–1 weighting method; that is, the edge weight between unconnected nodes is set to 0, while the edge weight between connected nodes is set to 1. The second is Gaussian weighting; that is, when two nodesxi and xj are connected, their edge weights are expressed as exp−xi−xj2/2σ2 , where σ represents the standard deviation of Gaussian kernel function, i.e., kernel width. If two nodes are not connected, the edge weight is 0. The third is cosine weighting; that is, if nodes xi and xj are connected, the edge weight is wij=1−xiTxj/xixj , and if two nodes are not connected, the edge weight is 0.As shown in Figure1, it is a simple schematic diagram of the diagram model. It can be seen from the diagram that it contains 6 nodes, i.e., v=v1,v2,v3,v4,v5,v6, and 8 edges, i.e., ε=e1v1,v2,e2v1,v3,e3v2,v3,e4v3,v4,e5v3,v5,e6v4,v5,e7v4,v6,e8v5,v6. The edge weight corresponding to each edge is w=w1=1,w2=0.5,w3=0.1,w4=1,w5=1.5,w6=1,w7=1,w8=0.8.Figure 1
Simple model diagram.For convenience, generally, the edges and edge weights in the graph model are expressed in matrix form:(1)E=111000111000111110001111001111000111,W=110.5000110.10000.50.1111.50001111001.511100010.81where 0 indicates no connected state and 1 indicates connected state. It can be seen from the figure that the nonzero elements of E and W have the same position, except that the nonzero elements of E are 1. Therefore, it can be deduced that when the relevant information of W is known, the corresponding E can be obtained, and this adjacency matrix is called graph, which only represents the node relationship, and weight of W is represented by Gv,w.WhenGv,w is known, let the degree of the node be expressed as voli, and its value is shown in formula (2):(2)voli=∑j=1nWij.Let the degree matrixD of a graph be a diagonal matrix; the, it means that the i -th diagonal element is the corresponding degree of node vi. At this time, Dii=voli is the Laplace matrix of graph G. Let L−=D−1/2LD−1/2 be the normalized form of Laplace matrix and S=D−1/2WD−1/2 be the normalized adjacency matrix, where the spectral radius is ρS≤1. P=D−1W represents the random walk matrix of figure Gv,w, and its relationship with S is(3)S=D1/2PD−1/2C,where P and S have similar phases and are characterized by a range of [−1, 1]. When tracking the local topology of power grid, a lot of search work needs to be carried out, and artificial intelligence technology has certain advantages in search, but in practical application, the efficiency is not high in both breadth and depth of search. Therefore, this paper combines a fast popular sorting matrix algorithm to improve the efficiency. As shown in formula (4), it is a general popularity matrix:(4)R=I−αS−1,where α∈0,1. The key point is the similarity of matrix S. It should be noted here that(5)Wij=exp−xi−xj22σ2=exp−xi22σ2exp−xj22σ2expxiTxjσ2.Letqi=−xi2/2σ2. The adjacency matrix is shown in formula (6):(6)W=QTEQ,where Q represents a diagonal matrix and its diagonal elements are expressed as Qii=qi, Eii=0 on the diagonal of matrix E, and Eij=expxiTxj/σ2 when it is nondiagonal. As shown in formula (7), it is the Taylor expansion of multivariable function in x0:(7)fx=fx0+∇fx0Tx−x0+12x−x0THx−x0+Ox−x02,where ∇fx0=∂f/∂x|x=x0 is expressed as a gradient vector and H=∂2f/∂x∂xT|x=x0 is expressed as Hessian matrix. Let fx,z=expxTz/σ2 and expand its origin, as shown in formula (8):(8)fx,z=1+xTzσ2+Ox2,z2.Then,Eij is as shown in formula (9):(9)Eij=1+xiTxjσ2+Oxi2,xj2,i≠j0,i=j.If formula (9) is combined with formula (6) and the higher-order term is omitted, the original adjacency matrix is shown in formula (10):(10)W∼=QeeT−I+1σ2XTX−Q∼QT,where Q∼ is expressed as a diagonal matrix and its diagonal elements are expressed as Q∼ii=xi2, vector e=1,1,…,1T, and the degree of node xi is shown in formula (11):(11)voli=∑jWij≈∑jqiqj1+xiTxjσ2−qi21+xiTxiσ2=qi∑jqj+qiσ2xiT∑j=1nqjxj−qi2−qi2Q∼iiσ2=qiC−qi2+qiσ2xiTy−qiQ∼ii,where C=∑j=1nqj,y=∑j=1nqjxj. At this time, the approximation of normalized S=D−1/2WD−1/2 can be as shown in formula (12):(12)S∼=D−1/2W∼D−1/2=D−1/2QeeT−I+2σ2XTX−Q∼QTD−1/2=D−1/2QeeTQTD−1/2−D−1/2QQTD−1/2+1σ2D−1/2QXTXQTD−1/2−D−1/2QQ∼QTD−1/2=D−1/2QeeTQTD−1/2+1σ2D−1/2QXTXQTD−1/2−D−1/2QQTD−1/2+1σ2D−1/2QQ∼QTD−1/2=ppT+1σ2XT∼X∼−T,where the diagonal matrix D represents the approximation matrix and Dii=voli, the matrix T=D−1/2QQTD−1/2+D−1/2QQ∼QTD−1/2/σ2, and p=D−1/2Qe,X∼=XQD−1/2.If the matrixM is n×d+1 and M=p1/σXT∼, the normalized adjacency matrix of formula (12) is shown in formula (13):(13)S∼=MMT−T.The inverse formula of Woodbury matrix is as shown in formula (14):(14)AAT+D−1=D−1−D−1AI+ATD−1A−1ATD−1.WhenD is relatively easy to obtain the inverse, and the matrix represented by A is a high matrix and ATA matrix is smaller than matrix AAT, it can be considered that the inversion of large matrix becomes a relatively easy inversion of D and a small matrix, as shown in formula (15):(15)I−αS∼−1=K−1+αK−1MId+1−αMTK−1M−1MTK−1,where K=I+αT represents a diagonal matrix and Ik represents the matrix as k×k. The simplified formula is(16)R≈K−1+GαI−α2MTG−1GT,where G=K−1M.


### 3.2. Grid Local Topology Tracking Algorithm Based on Graph Theory

According to the corresponding topology concept in graph theory, the main wiring diagram in substation can be transformed into abstract topology diagramG=<N,Bst>N, represented as a collection of all nodes in the substation, and Bst represents the state vector of the open element at time t. Topology graph G has different connection modes, so the topology can be represented by the corresponding node switch incidence matrix, and the definition of matrix M is(17)Mij=1,node i is connected to switch j,0,node i and switch j are not connected.The node adjacency matrix in the substation can represent its connectivity. Therefore, when the switch displacement occurs in the station, it is necessary to judge the on event or on event of the switch first and then modify the adjacency matrix, so as to quickly track the topology change in the station.When the change event in the substation is a closing event, the specific tracking steps are as follows: first, set the nodes at both ends of the closing switch in the adjacency matrix as 1, and arbitrarily select the row vectorAi containing the most element 1.Third, if vectorsAi and Bj are not equal, calculate as in formula (18):(18)C=Uk=1naikIbjk,Where C represents the temporary variable, aik and bjk represent the elements of vectors Ai and Bj in the column k, respectively, U represents the “or” operation, I represents the “and” operation, and n represents the dimension. When C=1 , it indicates that rows i and j contain nodes that can be connected, so Ai=Bj=AiUBj. Let j=1 and return to step 2. When C=0, it indicates that there are no nodes that can be connected in rows i and j. If j=n, Ai is recorded in the completed derivation array. If j<n, j=j+1 and return to step 2.Fourth, ifAi=Bj and j<n, make j=j+1 and return to step 2. If j=n, Ai is recorded in the completed derivation array.Fifth, if the vectorBj contained in the adjacency matrix is still not derived, let Ai=Bj and return to step 2. If the vectors in the adjacency matrix have been derived, the nodes are grouped again according to the new adjacency matrix and mapped into power grid topology nodes, so as to complete the topology tracking in the station.When the change event in the substation is off, set the nodes at both ends of the switch generating displacement in the initial adjacency matrix to 0, and the other steps are the same as above.


## 3.1. Graph Theory Concept and Its Algorithm

Graph theory is a graph model that can describe the mathematical model with pairwise relationship. It has three necessary elements: node, edge, and edge weight. The node can be any concrete individual or abstract individual, and the edge in the graph is an abstract description of the pairwise relationship between the individuals represented by the node. LetGv,ε,w represent the graph model, where v is the node and its set is v=v1,v2,…,vn , ε is the edge and its set is ε=e1,e2,…,eε , and w is the edge weight and w=w1,w2,…,wε. When the node set, edge set, and edge weight are determined at the same time, a graph can be determined. Graph model is generally divided into directed graph with specific direction on each edge and undirected graph without specific direction on each edge. In this paper, undirected graph is selected. When the node set is a given condition, there are usually three ways to build a graph. One is the whole graph; that is, all nodes in the graph and other nodes are connected. The second is the KNN graph; that is, each node in the graph has k nearest neighbors, and the node is only connected to these K nodes. The third is the graph; that is, all nodes in the graph are connected and the nodes with a distance less than ε.Generally, there are three edge weighting methods. The first is 0–1 weighting method; that is, the edge weight between unconnected nodes is set to 0, while the edge weight between connected nodes is set to 1. The second is Gaussian weighting; that is, when two nodesxi and xj are connected, their edge weights are expressed as exp−xi−xj2/2σ2 , where σ represents the standard deviation of Gaussian kernel function, i.e., kernel width. If two nodes are not connected, the edge weight is 0. The third is cosine weighting; that is, if nodes xi and xj are connected, the edge weight is wij=1−xiTxj/xixj , and if two nodes are not connected, the edge weight is 0.As shown in Figure1, it is a simple schematic diagram of the diagram model. It can be seen from the diagram that it contains 6 nodes, i.e., v=v1,v2,v3,v4,v5,v6, and 8 edges, i.e., ε=e1v1,v2,e2v1,v3,e3v2,v3,e4v3,v4,e5v3,v5,e6v4,v5,e7v4,v6,e8v5,v6. The edge weight corresponding to each edge is w=w1=1,w2=0.5,w3=0.1,w4=1,w5=1.5,w6=1,w7=1,w8=0.8.Figure 1
Simple model diagram.For convenience, generally, the edges and edge weights in the graph model are expressed in matrix form:(1)E=111000111000111110001111001111000111,W=110.5000110.10000.50.1111.50001111001.511100010.81where 0 indicates no connected state and 1 indicates connected state. It can be seen from the figure that the nonzero elements of E and W have the same position, except that the nonzero elements of E are 1. Therefore, it can be deduced that when the relevant information of W is known, the corresponding E can be obtained, and this adjacency matrix is called graph, which only represents the node relationship, and weight of W is represented by Gv,w.WhenGv,w is known, let the degree of the node be expressed as voli, and its value is shown in formula (2):(2)voli=∑j=1nWij.Let the degree matrixD of a graph be a diagonal matrix; the, it means that the i -th diagonal element is the corresponding degree of node vi. At this time, Dii=voli is the Laplace matrix of graph G. Let L−=D−1/2LD−1/2 be the normalized form of Laplace matrix and S=D−1/2WD−1/2 be the normalized adjacency matrix, where the spectral radius is ρS≤1. P=D−1W represents the random walk matrix of figure Gv,w, and its relationship with S is(3)S=D1/2PD−1/2C,where P and S have similar phases and are characterized by a range of [−1, 1]. When tracking the local topology of power grid, a lot of search work needs to be carried out, and artificial intelligence technology has certain advantages in search, but in practical application, the efficiency is not high in both breadth and depth of search. Therefore, this paper combines a fast popular sorting matrix algorithm to improve the efficiency. As shown in formula (4), it is a general popularity matrix:(4)R=I−αS−1,where α∈0,1. The key point is the similarity of matrix S. It should be noted here that(5)Wij=exp−xi−xj22σ2=exp−xi22σ2exp−xj22σ2expxiTxjσ2.Letqi=−xi2/2σ2. The adjacency matrix is shown in formula (6):(6)W=QTEQ,where Q represents a diagonal matrix and its diagonal elements are expressed as Qii=qi, Eii=0 on the diagonal of matrix E, and Eij=expxiTxj/σ2 when it is nondiagonal. As shown in formula (7), it is the Taylor expansion of multivariable function in x0:(7)fx=fx0+∇fx0Tx−x0+12x−x0THx−x0+Ox−x02,where ∇fx0=∂f/∂x|x=x0 is expressed as a gradient vector and H=∂2f/∂x∂xT|x=x0 is expressed as Hessian matrix. Let fx,z=expxTz/σ2 and expand its origin, as shown in formula (8):(8)fx,z=1+xTzσ2+Ox2,z2.Then,Eij is as shown in formula (9):(9)Eij=1+xiTxjσ2+Oxi2,xj2,i≠j0,i=j.If formula (9) is combined with formula (6) and the higher-order term is omitted, the original adjacency matrix is shown in formula (10):(10)W∼=QeeT−I+1σ2XTX−Q∼QT,where Q∼ is expressed as a diagonal matrix and its diagonal elements are expressed as Q∼ii=xi2, vector e=1,1,…,1T, and the degree of node xi is shown in formula (11):(11)voli=∑jWij≈∑jqiqj1+xiTxjσ2−qi21+xiTxiσ2=qi∑jqj+qiσ2xiT∑j=1nqjxj−qi2−qi2Q∼iiσ2=qiC−qi2+qiσ2xiTy−qiQ∼ii,where C=∑j=1nqj,y=∑j=1nqjxj. At this time, the approximation of normalized S=D−1/2WD−1/2 can be as shown in formula (12):(12)S∼=D−1/2W∼D−1/2=D−1/2QeeT−I+2σ2XTX−Q∼QTD−1/2=D−1/2QeeTQTD−1/2−D−1/2QQTD−1/2+1σ2D−1/2QXTXQTD−1/2−D−1/2QQ∼QTD−1/2=D−1/2QeeTQTD−1/2+1σ2D−1/2QXTXQTD−1/2−D−1/2QQTD−1/2+1σ2D−1/2QQ∼QTD−1/2=ppT+1σ2XT∼X∼−T,where the diagonal matrix D represents the approximation matrix and Dii=voli, the matrix T=D−1/2QQTD−1/2+D−1/2QQ∼QTD−1/2/σ2, and p=D−1/2Qe,X∼=XQD−1/2.If the matrixM is n×d+1 and M=p1/σXT∼, the normalized adjacency matrix of formula (12) is shown in formula (13):(13)S∼=MMT−T.The inverse formula of Woodbury matrix is as shown in formula (14):(14)AAT+D−1=D−1−D−1AI+ATD−1A−1ATD−1.WhenD is relatively easy to obtain the inverse, and the matrix represented by A is a high matrix and ATA matrix is smaller than matrix AAT, it can be considered that the inversion of large matrix becomes a relatively easy inversion of D and a small matrix, as shown in formula (15):(15)I−αS∼−1=K−1+αK−1MId+1−αMTK−1M−1MTK−1,where K=I+αT represents a diagonal matrix and Ik represents the matrix as k×k. The simplified formula is(16)R≈K−1+GαI−α2MTG−1GT,where G=K−1M.


## 3.2. Grid Local Topology Tracking Algorithm Based on Graph Theory

According to the corresponding topology concept in graph theory, the main wiring diagram in substation can be transformed into abstract topology diagramG=<N,Bst>N, represented as a collection of all nodes in the substation, and Bst represents the state vector of the open element at time t. Topology graph G has different connection modes, so the topology can be represented by the corresponding node switch incidence matrix, and the definition of matrix M is(17)Mij=1,node i is connected to switch j,0,node i and switch j are not connected.The node adjacency matrix in the substation can represent its connectivity. Therefore, when the switch displacement occurs in the station, it is necessary to judge the on event or on event of the switch first and then modify the adjacency matrix, so as to quickly track the topology change in the station.When the change event in the substation is a closing event, the specific tracking steps are as follows: first, set the nodes at both ends of the closing switch in the adjacency matrix as 1, and arbitrarily select the row vectorAi containing the most element 1.Third, if vectorsAi and Bj are not equal, calculate as in formula (18):(18)C=Uk=1naikIbjk,Where C represents the temporary variable, aik and bjk represent the elements of vectors Ai and Bj in the column k, respectively, U represents the “or” operation, I represents the “and” operation, and n represents the dimension. When C=1 , it indicates that rows i and j contain nodes that can be connected, so Ai=Bj=AiUBj. Let j=1 and return to step 2. When C=0, it indicates that there are no nodes that can be connected in rows i and j. If j=n, Ai is recorded in the completed derivation array. If j<n, j=j+1 and return to step 2.Fourth, ifAi=Bj and j<n, make j=j+1 and return to step 2. If j=n, Ai is recorded in the completed derivation array.Fifth, if the vectorBj contained in the adjacency matrix is still not derived, let Ai=Bj and return to step 2. If the vectors in the adjacency matrix have been derived, the nodes are grouped again according to the new adjacency matrix and mapped into power grid topology nodes, so as to complete the topology tracking in the station.When the change event in the substation is off, set the nodes at both ends of the switch generating displacement in the initial adjacency matrix to 0, and the other steps are the same as above.


## 4. Result Analysis and Discussion

### 4.1. Simulation Experiment of Power Grid Local Topology Tracking Based on Graph Theory

As shown in Figure2, it is an example of power grid simulation, including five stations, and the wiring modes include single bus section, double bus, and 3/2 wiring mode. In the simulation experiment, the current simulation operation of the system is set as two kinds; that is, switch 1811 is closed and switch 1101 is open.Figure 2
Example diagram of power grid simulation.As shown in Figure3, the station topology and network topology after initialization are shown.Figure 3
Station topology and network topology after initialization.When switch 1811 is closed, fast grid topology tracking is carried out; that is, whether there is a losingg event for the switch in station 2 is judged first. Then the adjacency matrix of node 2 is modified and the station topology is tracked. The third is to judge that nodes 1 to 8 are connected, and then map them to the corresponding power grid topology code 3. Fourth, before the switch is closed, the corresponding nodes 3 of nodes 1, 5, 7, and 8 in the station belong to No. 1 electric island, and the corresponding nodes of nodes 2 to 4 and 6 belong to No. 2 electric island. The closing state of the switch leads to the merger of the two electric islands. Fifth, take node code 3 corresponding to the closing switch in No. 1 electric island in Figure3 as the number of the new node, and update the node attributes of No. 2 electric island accordingly. At the same time, the node trees of the two electric islands are merged into the node tree of the new electric island, and the topology tracking is completed. The topology tracking model after switch 1811 is closed is shown in Figure 4.Figure 4
Topology tracking model after 1811 switch is closed.The tracking process after 1101 switch is on is as follows: first, judge the switch on event in 1 station. The second is to modify the initial borrowing point adjacency matrix occupied by No. 1 and track the topology changes in the station. Third, according to the judgment result of the modified adjacency matrix, there is no connection between node 1 and node 2. Fourth, after searching the node tree of the electrical island, according to the judgment results, nodes 1 and 2 are not connected and do not belong to the same electrical island. Fifthly, the node tree of the new electric island is constructed and its corresponding node attributes are updated to complete topology tracking, as shown in Figure5.Figure 5
Topology tracking results after switch 1101 is turned on.


### 4.2. Experimental Verification of Power Grid Local Topology Tracking Based on Graph Theory

The initial state of the experiment is composed of five electrical islands, a total of 91 stations and 354 bus sections, including 665 switches and 118 lines, and the number of electrical nodes is 98. In order to better test the grid local topology tracking algorithm based on graph theory, this paper selects the traditional method based on priority search for corresponding performance comparison and analysis. Figures6–8 show the performance comparison results of the two topology methods. From the comparison results in Figure 6, it can be seen that the power grid local topology tracking algorithm based on graph theory takes longer to carry out the first power grid topology analysis than the traditional method based on priority search. This is mainly because the grid local topology tracking algorithm based on graph theory needs to build the node adjacency matrix in each plant and station and the node tree of the electrical island, which needs a relatively long calculation time at the first time. However, after the first analysis, during the actual implementation and continuous operation of the power grid local topology tracking algorithm based on graph theory, the subsequent analysis is slightly modified on the basis of the first time, which can greatly reduce the number of nodes to be searched and reduce the time required for power grid topology tracking, so as to improve the efficiency and real-time performance of the algorithm.Figure 6
The average time of the first topological analysis of the two methods.Figure 7
The comparison results of the number of nodes and edges searched by the two methods.Figure 8
Comparison of average processing time between the two methods.Figure7 is a comparison of the results of the first average topology search nodes and edges of the two methods. Although the first topology time of the grid local topology tracking algorithm based on graph theory is longer than that of the traditional method based on priority search, the number of nodes and edges in the first average topology search is less than that of the method based on priority search. This shows that the local topology tracking algorithm based on graph theory can effectively alleviate the problem of repeated search of the same node and shorten the search time.As shown in Figure8, the average processing time results of the two methods are compared. It can be seen from the results in the figure that the average processing time of power grid local topology tracking algorithm based on graph theory is less than that of the traditional method based on priority search. This shows that the power grid local topology tracking algorithm based on graph theory has efficient search efficiency in power grid local topology processing and tracking and greatly reduces the search time. At the same time, this also shows that the grid local topology tracking algorithm based on graph theory needs relatively less calculation and has strong practical value.


## 4.1. Simulation Experiment of Power Grid Local Topology Tracking Based on Graph Theory

As shown in Figure2, it is an example of power grid simulation, including five stations, and the wiring modes include single bus section, double bus, and 3/2 wiring mode. In the simulation experiment, the current simulation operation of the system is set as two kinds; that is, switch 1811 is closed and switch 1101 is open.Figure 2
Example diagram of power grid simulation.As shown in Figure3, the station topology and network topology after initialization are shown.Figure 3
Station topology and network topology after initialization.When switch 1811 is closed, fast grid topology tracking is carried out; that is, whether there is a losingg event for the switch in station 2 is judged first. Then the adjacency matrix of node 2 is modified and the station topology is tracked. The third is to judge that nodes 1 to 8 are connected, and then map them to the corresponding power grid topology code 3. Fourth, before the switch is closed, the corresponding nodes 3 of nodes 1, 5, 7, and 8 in the station belong to No. 1 electric island, and the corresponding nodes of nodes 2 to 4 and 6 belong to No. 2 electric island. The closing state of the switch leads to the merger of the two electric islands. Fifth, take node code 3 corresponding to the closing switch in No. 1 electric island in Figure3 as the number of the new node, and update the node attributes of No. 2 electric island accordingly. At the same time, the node trees of the two electric islands are merged into the node tree of the new electric island, and the topology tracking is completed. The topology tracking model after switch 1811 is closed is shown in Figure 4.Figure 4
Topology tracking model after 1811 switch is closed.The tracking process after 1101 switch is on is as follows: first, judge the switch on event in 1 station. The second is to modify the initial borrowing point adjacency matrix occupied by No. 1 and track the topology changes in the station. Third, according to the judgment result of the modified adjacency matrix, there is no connection between node 1 and node 2. Fourth, after searching the node tree of the electrical island, according to the judgment results, nodes 1 and 2 are not connected and do not belong to the same electrical island. Fifthly, the node tree of the new electric island is constructed and its corresponding node attributes are updated to complete topology tracking, as shown in Figure5.Figure 5
Topology tracking results after switch 1101 is turned on.


## 4.2. Experimental Verification of Power Grid Local Topology Tracking Based on Graph Theory

The initial state of the experiment is composed of five electrical islands, a total of 91 stations and 354 bus sections, including 665 switches and 118 lines, and the number of electrical nodes is 98. In order to better test the grid local topology tracking algorithm based on graph theory, this paper selects the traditional method based on priority search for corresponding performance comparison and analysis. Figures6–8 show the performance comparison results of the two topology methods. From the comparison results in Figure 6, it can be seen that the power grid local topology tracking algorithm based on graph theory takes longer to carry out the first power grid topology analysis than the traditional method based on priority search. This is mainly because the grid local topology tracking algorithm based on graph theory needs to build the node adjacency matrix in each plant and station and the node tree of the electrical island, which needs a relatively long calculation time at the first time. However, after the first analysis, during the actual implementation and continuous operation of the power grid local topology tracking algorithm based on graph theory, the subsequent analysis is slightly modified on the basis of the first time, which can greatly reduce the number of nodes to be searched and reduce the time required for power grid topology tracking, so as to improve the efficiency and real-time performance of the algorithm.Figure 6
The average time of the first topological analysis of the two methods.Figure 7
The comparison results of the number of nodes and edges searched by the two methods.Figure 8
Comparison of average processing time between the two methods.Figure7 is a comparison of the results of the first average topology search nodes and edges of the two methods. Although the first topology time of the grid local topology tracking algorithm based on graph theory is longer than that of the traditional method based on priority search, the number of nodes and edges in the first average topology search is less than that of the method based on priority search. This shows that the local topology tracking algorithm based on graph theory can effectively alleviate the problem of repeated search of the same node and shorten the search time.As shown in Figure8, the average processing time results of the two methods are compared. It can be seen from the results in the figure that the average processing time of power grid local topology tracking algorithm based on graph theory is less than that of the traditional method based on priority search. This shows that the power grid local topology tracking algorithm based on graph theory has efficient search efficiency in power grid local topology processing and tracking and greatly reduces the search time. At the same time, this also shows that the grid local topology tracking algorithm based on graph theory needs relatively less calculation and has strong practical value.


## 5. Conclusion

With the continuous development of the country and cities, the power system needs more and more load pressure, and its guarantee system technology and safety and stability supervision technology need continuous development and improvement. Power network plays a very important role in power system. It is a basic functional part of energy management and distribution management system. At the same time, it provides corresponding basic network structural data for many power system analysis and guarantee technologies. However, the traditional power grid topology methods often have large errors in power grid topology analysis due to the lack of information data in its database. Moreover, the traditional power grid topology analysis method can only be used in a single plant and station and cannot exchange data and information with other plants and stations, which makes the relevant staff unable to fully control the actual situation of the power grid. In addition, the traditional power grid topology analysis method has a long search time, and the local modification method is difficult and difficult to implement. Therefore, this paper proposes the research of power grid local topology tracking based on graph theory and introduces graph theory into power grid local topology tracking algorithm to improve the search efficiency of the algorithm. The experimental results show that the grid local topology tracking algorithm based on graph theory can successfully analyze the experimental target in the simulation experiment and has better performance than the traditional priority search method. Although the time consumed in the first power grid topology analysis is greater than that consumed by the traditional priority search method, it is mainly due to the fact that the local topology tracking algorithm based on graph theory needs to build the node adjacency matrix and the node tree of the electrical island when searching for the first time. However, in the subsequent power grid topology, local modifications are made on the basis of the first results, which greatly reduces the search time and improves the search efficiency. From the results of average processing time, it can be seen that the power grid local topology tracking algorithm based on graph theory takes less time, requires relatively less calculation when carrying out local topology and tracking, has fast judgment speed, and is easy to implement and more valuable in practice. However, there are still many problems in the grid local topology tracking algorithm based on graph theory, which need to be further improved, and there are few comparison methods in this paper, and the corresponding performance data need to be added for further comparison and analysis.



---

*Source: 7027907-2021-11-12.xml*