Topological Graph Metrics for Detecting Grid Anomalies and Improving Algorithms

Power system reliability and security session, PSCC session 27

June 14, 2018

Jonas A. Kersulis, Ian A. Hiskens

Electrical Engineering and Computer Science

University of Michigan

Ann Arbor, MI, USA

Carleton Coffrin

Advanced Network Science Initiative

Los Alamos National Laboratory

Los Alamos, NM, USA

Daniel K. Molzahn

Energy Systems Division

Argonne National Laboratory

Argonne, IL, USA

Work supported by US ARPA-E GRID DATA program

Why graph structure?

  • Key reliability consideration
  • Quickly detect unusual connectivity patterns
  • Algorithm performance implications

Detecting structural anomalies

Ingredients

  • Many potential graph-theoretical metrics
  • Context provided by broad network set
  • Literature on known unusual topologies

Results

  • Systematic identification of anomalous structure
  • Effective set of topological graph metrics; intuitive warnings
  • SDP OPF solver performance implications

Networks

41 networks spanning a broad size range, and divided into four categories by horizontal lines.
41 networks spanning a broad size range, and divided into four categories by horizontal lines.
  • 33 community test cases from NESTA [1]
  • 5 PEGASE variants [2]
  • 4 RTE networks from recent partnership
  • 4 synthetic test cases from Overbye group [3]

Metrics

  • Degree distribution
    • Max, median, mean
  • Degree assortativity
  • Rich-club coefficient
  • Clique composition
    • Maximum clique size
  • Adjacency matrix spectral radius
  • Fiedler value
  • Sensitivity matrix analysis
    • Admittance matrix
    • Injection shift factors
  • Thevenin impedance distances

Reduce to set of fast, intuitive checks

Maximum node degree

The size trend should not be extrapolated for arbitrarily large networks.
The size trend should not be extrapolated for arbitrarily large networks.
  • High max degree of large PEGASE cases has been pointed out [4]
  • case89 max degree is unusual for its size

Degree assortativity

  • Extent to which nodes of like degree connect to each other
  • Coefficient r ∈ ( − 1, 1)

Power grids tend to be disassortative.
Power grids tend to be disassortative.

Just 3 networks with |r| > 0.5 (2 PEGASE + trivial example)

Rich-club effect

  • If a graph has 90% of all possible edges between nodes of degree 10 or greater, the rich club coefficient for k = 10 is 0.9.
  • Detects “hub of hubs” suggested by high r.

All rich clubs with more than 80% of potential edges and at least 3 nodes:

Nodes involved Degree
case9241 pegase 28 >25
case13659 pegase 19 >29
case89 pegase 11 >11
case2869 pegase 5 >13
case3 lmbd 3 >0

Four PEGASE cases and one trivial case

Maximum clique size

The vast majority of maximal cliques contain just two nodes, with the maximum clique having three.
The vast majority of maximal cliques contain just two nodes, with the maximum clique having three.

All four outliers are PEGASE cases.

Adjacency matrix spectral radius

A more computationally expensive way to expose anomalous structure.
A more computationally expensive way to expose anomalous structure.

Again, reasonable spread with PEGASE outliers

Summary

  • Corroboration, contextualization of grid quirks; reference dataset
  • Computationally efficient, intuitive graph metrics
  • Tool that analyzes networks and generates messages

Improving SDP OPF performance

  • OPF relaxation: replace power flow constraints with semidefinite constraint
  • Promising despite computational intensity [5]
  • Use matrix completion theorem [6] to replace big constraint with one small constraint per maximal clique
  • Greedily merge some cliques together to eliminate overlap [7]

Tradeoff: many linking constraints vs large constraint matrices

What is the optimal decomposition?

Clique merge

  1. Form a chordal graph extension
  2. Identify maximal cliques (linear-time algorithm)
  3. Merge cliques according to overlap (eliminate linking constraints)
  4. Stop merging cliques before submatrix size grows too large

What clique merge looks like

Minimize the effective number of variables by stopping at the white rectangle.
Minimize the effective number of variables by stopping at the white rectangle.

Potential for improvement

  • Effective problem size is minimized before solution time
  • Solution time is minimized roughly when the last clique is merged into another group

Main takeaways

  1. Topological graph metrics are powerful in the right settings
  2. Context highlights network reduction in PEGASE networks
  3. Clique composition tied to SDP OPF solver performance
  4. Potential for finding better semidefinite constraint decompositions

References

[1] C. Coffrin, D. Gordon, and P. Scott, “NESTA, The NICTA Energy System Test Case Archive,” arXiv:1411.0359 [cs], Nov. 2014.

[2] C. Josz, S. Fliscounakis, J. Maeght, and P. Panciatici, “AC Power Flow Data in MATPOWER and QCQP Format: iTesla, RTE Snapshots, and PEGASE,” arXiv:1603.01533 [math], Mar. 2016.

[3] A. B. Birchfield, T. Xu, K. M. Gegner, K. S. Shetye, and T. J. Overbye, “Grid Structural Characteristics as Validation Criteria for Synthetic Networks,” IEEE Trans. Power Syst., vol. PP, no. 99, pp. 1–1, 2016.

[4] P. Cuffe, “Assortativity Anomalies in a Large Test System,” IEEE Trans. Power Syst., vol. 31, no. 5, pp. 4169–4170, Sep. 2016.

[5] B. C. Lesieutre, D. K. Molzahn, A. R. Borden, and C. L. DeMarco, “Examining the limits of the application of semidefinite programming to power flow problems,” in 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2011, pp. 1492–1499.

[6] R. A. Jabr, “Exploiting Sparsity in SDP Relaxations of the OPF Problem,” IEEE Transactions on Power Systems, vol. 27, no. 2, pp. 1138–1139, May 2012.

[7] D. K. Molzahn, J. T. Holzer, B. C. Lesieutre, and C. L. DeMarco, “Implementation of a Large-Scale Optimal Power Flow Solver Based on Semidefinite Programming,” IEEE Transactions on Power Systems, vol. 28, no. 4, pp. 3987–3998, Nov. 2013.

[8] E. Cotilla-Sanchez, P. D. H. Hines, C. Barrows, and S. Blumsack, “Comparing the Topological and Electrical Structure of the North American Electric Power Infrastructure,” IEEE Systems Journal, vol. 6, no. 4, pp. 616–626, Dec. 2012.

[9] G. A. Pagani and M. Aiello, “The Power Grid  as a complex network: A survey,” Physica A: Statistical Mechanics and its Applications, vol. 392, no. 11, pp. 2688–2700, Jun. 2013.