Graph Database and Graph Computing for Power System Analysis

Renchang Dai, PhD, is a Consulting Analyst and Project Manager for Puget Sound Energy, Washington, USA. He is a founding member of GE Energy Consluting Smart Grid CoE and an IEEE Senior Member, and has worked and published extensively on graph based power system analysis software. Guangyi Liu, PhD, is Chief Scientist and Smart Grid CoE at Envision Digital, USA. He is an IEEE Senior member and has extensive experience developing software for graph-based power system analysis across numerous applications.

• About the Authors xiiiPreface xvAcknowledgments xviiPart I Theory and Approaches 11 Introduction 31.1 Power System Analysis 61.1.1 Power Flow Calculation 61.1.2 State Estimation 61.1.3 Contingency Analysis 71.1.4 Security-Constrained Automatic Generation Control 71.1.5 Security-Constrained ED 81.1.6 Electromechanical Transient Simulation 91.1.7 Photovoltaic Power Generation Forecast 101.2 Mathematical Model 101.2.1 Direct Methods of Solving Large-Scale Linear Equations 101.2.2 Iterative Methods of Solving Large-Scale Linear Equations 111.2.3 High-Dimensional Differential Equations 111.2.4 Mixed Integer-Programming Problems 111.3 Graph Computing 121.3.1 Graph Modeling Basics 131.3.2 Graph Parallel Computing 14References 142 Graph Database 172.1 Database Management Systems History 172.2 Graph Database Theory and Method 182.2.1 Graph Database Principle and Concept 182.2.1.1 Defining a Graph Schema 192.2.1.2 Creating a Loading Job 202.2.1.3 Graph Query Language 212.2.2 System Architecture 252.2.3 Graph Computing Platform 252.3 Graph Database Operations and Performance 262.3.1 Graph Database Management System 262.3.1.1 Parallel Processing by MapReduce 272.3.1.2 Graph Partition 292.3.2 Graph Database Performance 35References 383 Graph Parallel Computing 413.1 Graph Parallel Computing Mechanism 413.2 Graph Nodal Parallel Computing 443.3 Graph Hierarchical Parallel Computing 463.3.1 Symbolic Factorization 473.3.2 Elimination Tree 513.3.3 Node Partition 563.3.4 Numerical Factorization 573.3.5 Forward and Backward Substitution 58References 594 Large-Scale Algebraic Equations 614.1 Iterative Methods of Solving Nonlinear Equations 614.1.1 Gauss–Seidel Method 614.1.2 PageRank Algorithm 624.1.2.1 PageRank Algorithm Mechanism 634.1.2.2 Iterative Method 664.1.2.3 Algebraic Method 674.1.2.4 Convergence Analysis 694.1.3 Newton–Raphson Method 724.2 Direct Methods of Solving Linear Equations 754.2.1 Introduction 754.2.2 Basic Concepts 764.2.2.1 Data Structures of Sparse Matrix 764.2.2.2 Matrices and Graphs 784.2.3 Historical Development 804.2.4 Direct Methods 814.2.4.1 Solving Triangular Systems 814.2.4.2 Symbolic Factorization 824.2.4.3 Fill-Reducing Ordering 824.3 Indirect Methods of Solving Linear Equations 834.3.1 Stationary Methods 834.3.1.1 Jacobi Method 834.3.1.2 Gauss–Seidel Method 854.3.1.3 SOR Method 864.3.1.4 SSOR Method 864.3.2 Nonstationary Methods 884.3.2.1 CG Method 884.3.2.2 Gmres 894.3.2.3 BCG (bi-CG) 90References 915 High-Dimensional Differential Equations 955.1 Integration Methods 955.1.1 An Overview of Integration Methods and their Accuracy 955.1.1.1 One-Step Methods 965.1.1.2 Linear Multistep Methods 995.1.2 Integration Methods for Power System Transient Simulations 1005.1.3 Transient Analysis Accuracy 1005.1.4 Transient Analysis Stability 1015.1.4.1 Absolute Stability 1015.1.4.2 Stiff Stability 1025.2 Time Step Control 1035.2.1 Adaptive Time Step 1045.2.1.1 Change by Iteration Number 1055.2.1.2 Change by Estimated Truncation Error 1055.2.1.3 Change by State Variable Derivative 1065.2.2 Multiple Time Step 1065.2.3 Break Points 1095.3 Initial Operation Condition 1105.4 Graph-Based Transient Parallel Simulation 1155.5 Numerical Case Study 1175.6 Summary 123References 1246 Optimization Problems 1256.1 Optimization Theory 1256.2 Linear Programming 1256.2.1 The Simplex Method 1276.2.1.1 Basic Feasible Solution 1276.2.1.2 The Simplex Iteration 1286.2.2 Interior-Point Methods 1326.3 Nonlinear Programming 1386.3.1 Unconstrained Optimization Approaches 1396.3.1.1 Line Search 1406.3.1.2 Trust Region Optimization 1416.3.1.3 Quasi-Newton Method 1416.3.1.4 Double Dogleg Optimization 1426.3.1.5 Conjugate Gradient Optimization 1436.3.2 Constrained Optimization Approaches 1456.3.2.1 Karush–Kuhn–Tucker Conditions 1456.3.2.2 Linear Approximations of Nonlinear Programming with Linear Constraints 1456.3.2.3 Linear Approximations of Nonlinear Programming with Nonlinear Constraints 1476.4 Mixed Integer Optimization Approach 1476.4.1 Branch-and-Bound Approach 1486.4.2 Machine Learning for Branching 1506.5 Optimization Problems Solution by Graph Parallel Computing 1516.5.1 Simplex Method Based on Graph Parallel Computing 1516.5.2 Interior-Point Method Based on Graph Parallel Computing 154References 1567 Graph-Based Machine Learning 1597.1 State of Art on PV Generation Forecasting 1597.2 Graph Machine Learning Model 1607.3 Convolutional Graph Auto-Encoder 1627.3.1 Auto-Encoder 1627.3.2 Auto-Encoder on Graphs 1637.3.3 Probability Distribution Function Approximation 1647.3.4 Convolutional Graph Auto-Encoder 1677.3.5 Graph Feature Extraction Artificial Neural Network (R(G)) 1697.3.6 Encoder (Q) and Decoder (P) 1707.3.7 Estimation of P(V∗/ π) 171References 171Part II Implementations and Applications 1758 Power Systems Modeling 1778.1 Power System Graph Modeling 1778.2 Physical Graph Model and Computing Graph Model 1788.3 Node-Breaker Model and Graph Representation 1808.4 Bus-Branch Model and Graph Representation 1898.5 Graph-Based Topology Analysis 1908.5.1 Substation-Level Topology Analysis 1908.5.2 System-Level Network Topology Analysis 196References 1989 State Estimation Graph Computing 1999.1 Power System State Estimation 1999.2 Graph Computing-Based State Estimation 2019.2.1 State Estimation Graph Computing Algorithm 2019.2.1.1 Build Node-Based State Estimation 2019.2.1.2 Graph-Based State Estimation Parallel Algorithm 2039.2.2 Numerical Example 2099.2.3 Graph-Based State Estimation Implementation 2159.2.3.1 Graph-Based State Estimation Graph Schema 2159.2.3.2 Nodal Gain Matrix Formation 2169.2.3.3 Build RHS 2199.2.4 Graph-Based State Estimation Computation Efficiency 2209.3 Bad Data Detection and Identification 2239.3.1 Chi-Squares Test 2249.3.2 Advanced Bad Data Detection 2249.3.3 Bad Data Identification 2289.3.3.1 Normalized Residual 2289.3.3.2 Largest Normalized Residual for Bad Data Identification 2299.4 Graph-Based Bad Data Detection Implementation 229References 23110 Power Flow Graph Computing 23310.1 Power Flow Mathematical Model 23310.2 Gauss–Seidel Method 23410.3 Newton–Raphson Method 24210.3.1 Build Jacobian Graph 24510.3.2 Graph-Based Symbolic Factorization 24710.3.3 Graph-Based Elimination Tree Creation and Node Partition 24910.3.4 Graph Numerical Factorization 25110.3.5 Build Right-Hand Side 25310.3.6 Graph Forward and Backward Substitution 25410.3.7 Graph-Based Newton–Raphson Power Flow Calculation 25510.4 Fast Decoupled Power Flow Calculation 25710.4.1 Build B_P and B_PP Graphs 25910.5 Ill-Conditioned Power Flow Problem Solution 26110.5.1 Introduction 26110.5.2 Determine the Feasibility of the Power Flow 26210.5.3 Problem Formulation for Determining the Feasibility of Power Flow 26310.5.4 Power Flow Feasibility Verification 26410.5.5 Find a Feasible Solution for the Power Flow Problem 266References 27111 Contingency Analysis Graph Computing 27311.1 dc Power Flow 27311.2 Bridge Search 27611.3 Conjugate Gradient for Postcontingency Power Flow Calculation 28211.4 Contingency Analysis Using Convolutional Neural Networks 29411.4.1 Convolutional Neural Network 29511.4.2 Convolutional Neural Network Components 29711.4.2.1 Convolutional Neural Network Input 29711.4.2.2 Convolutional Neural Network Output 29711.4.2.3 Convolutional Neural Network Convolutional Layer 29711.4.2.4 CNN Pooling Layer 29811.4.2.5 CNN Fully Connected Layer 29911.4.3 Evaluation Metrics 29911.4.3.1 Accuracy 29911.4.3.2 Precision 30011.4.3.3 Recall 30011.4.4 Implementation of Convolutional Neural Network 30011.5 Contingency Analysis Graph Computing Implementation 302References 30612 Economic Dispatch and Unit Commitment 30912.1 Classic Economic Dispatch 30912.1.1 Thermal Unit Economic Dispatch 30912.1.2 Hydrothermal Power Generation System Economic Dispatch 31512.2 Security-Constrained Economic Dispatch 32012.2.1 Generation Shift Factor Matrix 32312.2.2 Graph-Based SCED Modeling 32512.2.3 Graph-Based SCED 32712.2.3.1 Buildup Simplex Graph 32812.2.3.2 Graph-Based Simplex Method 33112.2.3.3 Update Power Flow 33112.2.3.4 Graph-Based SCED Implementation 33312.3 Security-Constrained Unit Commitment 33412.3.1 SCUC Model 33412.3.2 Graph-Based SCUC 33512.4 Numerical Case Study 33612.4.1 Graph-Based SCED Modeling 33612.4.2 Basic Feasible Solution 34012.4.3 Economic Dispatch Optimal Solution 342References 34213 Automatic Generation Control 34513.1 Classic Automatic Generation Control 34513.1.1 Speed Governor Control 34513.1.2 Speed Droop Function 34713.1.3 Frequency Supplementary Control 35313.1.4 Fundamentals of Automatic Generation Control 35513.2 Network Security-Constrained Automatic Generation Control 35813.3 Security-Constrained AGC Graph Computing 361References 36414 Small-Signal Stability 36514.1 Small-Signal Stability of a Dynamic System 36514.2 System Linearization 36614.3 Small-Signal Stability Mode 36714.4 Single-Machine Infinite Bus System 36714.4.1 Classical Generator Model 36714.4.2 Third-Order Generator Model 36914.4.3 Numerical Case Study 37314.4.3.1 Stable Case 37314.4.3.2 Instable Case 37614.5 Small-Signal Oscillation Stabilization 37814.6 Eigenvalue Calculation 37914.6.1 Graph-Based Small-Signal Stability Analysis 38214.6.2 Buildup Small-Signal Stability Graph 38314.6.3 Numerical Example 383References 38815 Transient Stability 39115.1 Transient Stability Theory 39115.1.1 Stability Region and Boundary 39115.1.2 Energy Function Method 39115.1.2.1 Controlling UEP Method 39215.1.2.2 Stability-Region-Based Controlling UEP Method 39315.2 Transient Simulation Model 39315.2.1 Generator Rotor Model 39315.2.2 Generator Electro-Magnetic Model 39415.2.3 Excitation System Model 39415.2.4 Governor Model 39615.2.5 PSS Model 39715.3 Transient Simulation Approach 39715.3.1 Transient Simulation Algorithm 39815.3.2 Steady-State Equilibrium Condition 39815.3.3 Generator Injection Current 40015.4 Transient Simulation by Graph Parallel Computing 40115.4.1 Transient Simulation Graph 40115.4.2 Loading Data into Graph 40315.4.3 Graph-Based Transient Simulation Implementation 40615.5 Numerical Example 40615.5.1 Power Flow Data 40615.5.2 Dynamic Data 40615.5.3 Power Flow Results 40915.5.4 Steady-State Equilibrium Point 41015.5.5 Generator Injection Current Calculation 41515.5.6 Calculate Bus Voltage 41615.5.7 Simulation Results 416References 42116 Graph-Based Deep Reinforcement Learning on Overload Control 42516.1 Introduction 42516.2 DDPG Algorithm 42616.2.1 Terminology 42616.2.2 Q Function 42716.2.3 Q Value Approximation 42716.2.4 Policy Gradient 42816.3 Branch Overload Control 42916.3.1 States 42916.3.2 Actions 43016.3.3 Rewards 43016.4 Graph-Based Deep Reinforcement Learning Implementation 430References 43317 Conclusions 435Appendix 437Index 481