Measures

graph_tiger.measures.algebraic_connectivity(graph, **kwargs)

The larger the algebraic connectivity, the more robust the graph. This is due to it’s close connection to edge connectivity, where it serves as a lower bound: 0 < \(u_2\) < node connectivity < edge connectivity. This means that a network with larger algebraic connectivity is harder to disconnect [7, 12].

Parameters

graph – undirected NetworkX graph

Returns

a float

graph_tiger.measures.average_clustering_coefficient(graph, **kwargs)

The global clustering coefficient is based on the number of triplets of nodes in the graph, and provides an indication of how well nodes tend to cluster together. The larger the average global clustering coefficient, the more robust the graph i.e., more triangles –> better connected –> more robust graph [7].

Parameters

graph – undirected NetworkX graph

Returns

a float

graph_tiger.measures.avg_distance(graph, **kwargs)

The average distance between all pairs of nodes in the graph. The smaller the average shortest path distance, the more robust the graph. This can be viewed through the lens of network connectivity i.e., smaller avg. distance –> better connected graph [7].

Undefined for disconnected graphs.

Parameters

graph – undirected NetworkX graph

Returns

a float

graph_tiger.measures.avg_edge_betweenness(graph, k=inf, **kwargs)

Similar to vertex betweenness, edge betweenness is defined as the number of shortest paths that pass through an edge e out of the total possible shortest paths. The smaller the average edge betweenness, the more robust the graph. We can view this as the load of the network being better distributed and less dependent on a few edges [7].

Parameters
  • graph – undirected NetworkX graph

  • k – the number of nodes used to approximate betweenness centrality (k=10% of nodes is usually good)

Returns

a float

graph_tiger.measures.avg_inverse_distance(graph, **kwargs)

The average inverse distance between all pairs of nodes in the graph. The larger the average inverse shortest path distance, the more robust the graph. This can be viewed through the lens of network connectivity i.e., larger average inverse distance –> better connected graph –> more robust graph [7].

Resolves the issue of not working for disconnected graphs in the avg_distance() function.

Parameters

graph – undirected NetworkX graph

Returns

a float

graph_tiger.measures.avg_vertex_betweenness(graph, k=inf, **kwargs)

The average vertex betweenness of a graph is the summation of vertex betweenness for every node in the graph. The smaller the average vertex betweenness, the more robust the graph. We can view this as the load of the network being better distributed and less dependent on a few nodes [7].

Parameters
  • graph – undirected NetworkX graph

  • k – the number of nodes used to approximate betweenness centrality (k=10% of nodes is usually good)

Returns

a float

graph_tiger.measures.diameter(graph, **kwargs)

The diameter of a connected graph is the longest shortest path between all pairs of nodes. The smaller the diameter the more robust the graph i.e., smaller diameter –> better connected graph –> more robust graph [7].

Parameters

graph – undirected NetworkX graph

Returns

an integer

graph_tiger.measures.edge_connectivity(graph, **kwargs)

Measures the minimal number of edges that can be removed to disconnect the graph. Larger edge connectivity –> harder to disconnect graph –> more robust graph [9].

Parameters

graph – undirected NetworkX graph

Returns

an integer

graph_tiger.measures.effective_resistance(graph, k=inf, **kwargs)

This measure views a graph as an electrical circuit where an edge \((i, j)\) corresponds to a resister of \(r_{ij} = 1\) Ohm and a node i corresponds to a junction. We say the effective graph resistance R is the sum of resistances for all distinct pairs of vertices The smaller the effective resistance, the more robust the graph [7, 8, 13].

Parameters

graph – undirected NetworkX graph

Returns

a float

graph_tiger.measures.generalized_robustness_index(graph, k=30, use_gpu=False, **kwargs)

This can be considered a fast approximation of spectral scaling. The smaller the value, the more robust the graph. Also helps determine if a graph has many bridges (bad for robustness) [16].

Parameters
  • graph – undirected NetworkX graph

  • use_gpu – defaults to False; set to True to use GPU (if available)

Returns

a float

graph_tiger.measures.get_measures()

Returns a list of strings representing all of the available graph robustness measures

Returns

list of strings

graph_tiger.measures.largest_connected_component(graph, **kwargs)

This measure provides an indication of a graph’s connectivity by measuring the fraction of nodes contained in the largest connected component. The larger the value, the more robust the graph.

Parameters

graph – undirected NetworkX graph

Returns

a float

graph_tiger.measures.natural_connectivity(graph, k=inf, use_gpu=False, **kwargs)

Natural connectivity has a physical and structural interpretation that is tied to the connectivity properties of a network, identifying alternative pathways in a network through the weighted number of closed walks. The larger the natural connectivity (average eigenvalue of adjacency matrix), the more robust the graph [4].

Parameters
  • graph – undirected NetworkX graph

  • use_gpu – defaults to False; set to True to use GPU (if available)

Returns

a float

graph_tiger.measures.node_connectivity(graph, **kwargs)

Measures the minimal number of vertices that can be removed to disconnect the graph. Larger vertex (node) connectivity –> harder to disconnect graph –> more robust graph [9].

Parameters

graph – undirected NetworkX graph

Returns

an integer

graph_tiger.measures.num_spanning_trees(graph, k=inf, **kwargs)

The number of spanning trees T is the number of unique spanning trees that can be found in a graph. The larger the number of spanning trees, the more robust the graph. This can be viewed from the perspective of network connectivity, where a larger set of spanning trees means more alternative pathways in the network [1, 7].

Parameters

graph – undirected NetworkX graph

Returns

a float

graph_tiger.measures.odd_subgraph_centrality(i, lam, u)

Calculates the number of odd length closed walks that a node participates in [11]. Used in the calculation of spectral scaling and generalized robustness index.

Parameters
  • i – node index

  • lam – largest eigenvalue

  • u – largest eigenvector

Returns

a float

graph_tiger.measures.run_measure(graph, measure, k=inf, use_gpu=False)

Evaluates graph robustness according to a specified measure

Parameters
  • graph – undirected NetworkX graph to measure

  • measure – string containing the robustness measure to evaluate

  • k – an integer for fast approximation of certain robustness measures. small k = fast, large k = precise

  • timeout – allows the user to stop running the measure after ‘x’ seconds.

Returns

a float representing the robustness of the graph, or None if it times out or an error occurs

graph_tiger.measures.spectral_gap(graph, use_gpu=False, **kwargs)

The difference between the largest and second largest eigenvalues of the adjacency matrix (\(\lambda_1 - \lambda_2\)) is called the spectral gap \(\lambda_d\). The larger the spectral gap, the more robust the graph. Has an advantage over spectral radius since it accounts for undesirable bridges in the network [3, 16].

Parameters
  • graph – undirected NetworkX graph

  • use_gpu – defaults to False; set to True to use GPU (if available)

Returns

a float

graph_tiger.measures.spectral_radius(graph, use_gpu=False, **kwargs)

The largest eigenvalue \(\lambda_1\) of an adjacency matrix A is called the spectral radius. The larger the spectral radius, the more robust the graph. This can be viewed from its close relationship to the “path” or “loop” capacity in a network [5, 19].

Parameters
  • graph – undirected NetworkX graph

  • use_gpu – defaults to False; set to True to use GPU (if available)

Returns

a float

graph_tiger.measures.spectral_scaling(graph, k=inf, use_gpu=False, **kwargs)

Spectral scaling is a combination of the spectral gap and subgraph centrality. Spectral scaling takes into account if a graph has many bridges. The smaller the value, the more robust the graph [10].

Parameters
  • graph – undirected NetworkX graph

  • use_gpu – defaults to False; set to True to use GPU (if available)

Returns

a float