System-wide Metrics

2017-09-29

Jonas Kersulis

Introduction

M6.1.2

M6.1.3

Goals

• Perform graph analysis of many networks.
• Corroborate unusual characteristics identified by community.
• Combine data spread with outside knowledge to develop easy-to-use set of checks (similar to parameter checks).

Set of networks

41 networks total:

• 33 community test cases from NESTA
• 5 PEGASE networks
• 4 RTE networks
• 3 Polish grid scenarios
• 2 IEEE RTS cases
• 5 IEEE power flow test cases
• 6 small publication test cases
• 4 recent RTE test cases
• 4 synthetic test cases from Overbye group

Previous work made translation to GRG format in pu easy.

Networks by size

Categories: tiny (<20 nodes), small (20-1k), medium (1k-5k), large (5k+)

Derivation of metrics

• Stick with unweighted for now; no electrical information.
• Graph theory still provides insight.
• Straightforward warnings highlight unusual connectivity and density patterns.

A. Degree distribution

Description

$$\text{Pr}(k=x)=\frac{n_k}{n},$$ where $n_k$ is the number of nodes with degree $k$.

Results

Results: 1k - 7k nodes

B. Maximum node degree

Description

• Substations rarely have >10 connections.
• High max node degree suggests network reduction.

Results

• High max degree of large PEGASE cases has been pointed out.
• case89 has max degree unusual for its size.
• Size trend is only valid for smaller networks; substation connections do not grow arbitrarily numerous with network size.

Warning thresholds

• 10 or higher: warning
• Above $y=4.22\log n + 3.87$: error

C. Mean node degree

Description

• Related to $n-1$ security
• Between 2 and 3 for most networks

Results

• Clump around 2.4: RTE + Polish
• Clump around 2.7: PEGASE + IEEE

Warning thresholds

• Mean degree > 3: warning (less than 15% of networks)
• Mean degree > 4: error (just PEGASE 89)

How many buses are driving up the mean degree?

D. Median node degree

Description

Can only identify extreme outliers.

E. Degree assortativity coefficient

Description

Extent to which nodes of like degree connect to each other. $$ r = \frac{\sum_{xy}xy(e_{xy} - a_xa_y)}{\sigma_a^2} $$

• $x$, $y$: node degree values
• $e_{xy}$: fraction of all edges connecting a node with degree $x$ to a node with degree $y$
• $a_x$: fraction of all edges that start or end at nodes with degree $x$
• $\sigma_a$: standard deviation of node degree distribution

$r$ is between -1 (perfect disassortativity) and 1 (perfect assortativity).

Illustration

• case9: each node connected only to others with different degree; highly disassortative
• case6: two edges between degree-2 nodes, one between degree-3 nodes; less disassortative

Results

• Slight disassortative trend
• Just 3 networks with $|r|>0.5$
• No discernible size dependence

Results

Reproducing figure from literature (with more data points)

Paul Cuffe wrote a letter to Transactions noting the assortativity anomaly of the large PEGASE network.

Warning thresholds

Use 1 and 2 standard deviations as guidelines:

• $r\notin [-0.37,~0.18]$: warning
• $r\notin [-0.64,~0.45]$: error

F. Rich club coefficient

Description

• For each degree $k$, divide number of edges between nodes of degree $\geq k$ by number of potential edges between those nodes.
• Example: 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$.

Results

Warning thresholds

Important: how many nodes are involved in the rich club? Dozens, or just two? Sensible starting point:

• Consider the set $K_{0.8}$ of degrees with rich club coeff. $\geq 0.8$. Issue warning when there are at least 10 nodes with degree $k\in K_{0.8}$.

Application of metrics

• Running the code
• Output from checking all test cases

Running the code

Compute and check metrics on GRG-format networks in a directory:

              
    import grg_metrics
    metrics = grg_metrics.compute_metrics('path/to/folder/')
    msg = grg_metrics.analyze_metrics(metrics)
            
          

            
    >>> msg.loc['nesta_case240_wecc']
    max_degree
    mean_degree
    median_degree           Warning: 'nesta_case240_wecc' has median degre...
    degree_assortativity
    rich_club
            
          

            
    >>> msg.loc['nesta_case240_wecc'].median_degree
    "Warning: 'nesta_case240_wecc' has median degree 3, which is rare for networks larger than 200 buses."
          
        

Applying checks to test networks

Use the checks on the test networks used to develop them.

Discussion

• Other potential metrics we investigated
• Future work

Other potential metrics

Spectral graph analysis

No electrical data

• Algebraic connectivity (Fiedler value): second-smallest Laplacian Eigenvalue
• Adjacency spectral radius: largest Eigenvalue of adjacency matrix

With electrical data

• Admittance matrix spectrum
• Injection shift factor spectrum

Interesting data...

Weighted graph analysis

Electrical distance information is rich:

Tough to distill into intuitive, actionable metrics.

Clique analysis

• A clique is a fully-connected subgraph.
• Cliques can overlap.

Future work

Our metrics can detect unusual connectivity patterns and modeling errors, but we'd really like metrics that predict computational behavior.