Abstract
During last decades, contingency analysis has been facing challenges from significant load demand increase and high penetrations of intermittent renewable energy, fluctuant responsive loads and non-linear power electronic interfaces. It requires an advanced approach for high-performance contingency analysis as a safeguard of the power system operation. In this paper, a graph-based method is employed for N-1 contingency analysis (CA) fast screening. At first, bi-directional breadth-first search (BFS) is proposed and adopted on graph model to detect the potential shedding component in contingency analysis. It implements hierarchical parallelism of the graph traverse and speedup its process. Then, the idea of evolving graph is introduced in this paper to improve computation performance. For each contingency scenario, N-1 contingency graph quickly derives from system graph in basic status, and parallelly analyzes each contingency scenario using graph computing. The efficiency and effectiveness of the proposed approach have been tested and verified by IEEE 118-bus system and a practical case SC 2645-bus system.
Introduction
In modern power systems, Contingency Analysis (CA) serves as a critical "what-if" simulation tool, ensuring grid stability by modeling the failure of individual components, such as transmission lines. This process, known as "N-1" analysis, is becoming increasingly complex as grids integrate volatile renewable energy sources and sophisticated power electronics.
Traditional CA methods rely heavily on matrix algebra, specifically LU decomposition, to evaluate network connectivity. However, these numerical methods are computationally expensive and often struggle to meet the real-time operational requirements of expanding modern grids. This paper proposes a shift from static matrix-based calculations to a dynamic graph computing framework, treating the power grid as an evolving graph to achieve high-performance screening.
Methodology
Graph Modeling and Data Representation
The foundation of the proposed approach is the direct mapping of power system data into a graph database. Unlike traditional relational databases that store data in isolated tables, a graph database represents buses as vertices and transmission lines as edges. This structure allows for "constant time" complexity when accessing neighboring components, which is vital for rapid traversal.
Bi-Directional Breadth-First Search (BFS)
To identify if a specific line failure results in an "island" (a disconnected segment of the grid), the researchers implemented a bi-directional BFS. Instead of a standard one-way traversal, the algorithm initiates a search from both ends of the failed component simultaneously. If the two search fronts meet, connectivity is confirmed; if they fail to intersect, an island is detected. This hierarchical parallelism significantly reduces the search space and accelerates the detection process.
Evolving Graphs and Parallel Processing
Rather than rebuilding the entire grid model for every N-1 scenario, the framework utilizes an "evolving graph" concept. It maintains a master base-case graph and derives sub-graphs for each contingency by applying temporary "deltas" or updates. This minimizes memory overhead and redundant computations. Furthermore, the system employs the Bulk Synchronous Parallel (BSP) model, treating each node as an independent computing agent to process thousands of failure scenarios concurrently.
Experimental Results
The proposed method was validated using the standard IEEE 118-bus system (179 branches) and a large-scale practical case, the SC 2645-bus system (3,226 branches), representing the power grid of Sichuan Province, China.
The graph-based approach demonstrated exceptional performance:
- IEEE 118-bus system: Complete N-1 screening was achieved in just 86.54 ms.
- SC 2645-bus system: The system processed over 3,000 scenarios in 286.21 ms, averaging only 0.08 ms per scenario.
These results represent a significant improvement over previous graph-algebraic methods, which required substantially more time for much smaller systems.
Conclusion and Future Work
By transitioning from global matrix calculations to localized graph-based agent interactions, the proposed framework achieves millisecond-level contingency screening. While highly effective for N-1 connectivity checks, future research will focus on extending this logic to "N-k" (multiple simultaneous) failures. Additionally, the researchers aim to integrate more complex AC power flow analysis into the graph framework to enhance the severity ranking of detected contingencies.
Summary updated