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