Source-linked AI summary
Graph measures and network robustness
W. Ellens, R. E. Kooij
TL;DR
Quantifying network robustness matters for comparing and improving networks, but proposed measures need to capture the structural properties associated with robustness. This paper surveys graph measures and assesses their functionality, finding that some measures have important limitations and that effective graph resistance accounts for backup possibilities.
Problem
Assessing whether a network is robust requires quantitative measures, but capturing backup possibilities and alternative paths mathematically is challenging.
Source: §1.1 · p. 1Method
The paper surveys fourteen measures for simple, undirected, unweighted graphs, spanning connectivity, distance, betweenness, clustering, and Laplacian eigenvalues.
Source: §5 · p. 10Results
The fourteen measures order some small example graphs as expected, but several cannot distinguish graphs or respond consistently to added edges, and effective graph resistance considers backup possibilities.
Source: §5 · p. 10Takeaways & Limitations
The survey provides a basis for comparing networks, improving existing networks, and designing robust new networks using graph measures.
Source: §5 · p. 10Some measures ignore backup paths or may not increase when an edge is added; algebraic connectivity also lacks strict edge-addition monotonicity.
Source: §2.2 · p. 3, §2.3 · p. 4, §3.1 · p. 7
Abstract
from arXiv · showhide
Network robustness research aims at finding a measure to quantify network robustness. Once such a measure has been established, we will be able to compare networks, to improve existing networks and to design new networks that are able to continue to perform well when it is subject to failures or attacks. In this paper we survey a large amount of robustness measures on simple, undirected and unweighted graphs, in order to offer a tool for network administrators to evaluate and improve the robustness of their network. The measures discussed in this paper are based on the concepts of connectivity (including reliability polynomials), distance, betweenness and clustering. Some other measures are notions from spectral graph theory, more precisely, they are functions of the Laplacian eigenvalues. In addition to surveying these graph measures, the paper also contains a discussion of their functionality as a measure for topological network robustness.
1 Introduction
The introduction frames network robustness as continued performance under failures or attacks and motivates quantitative measures that can support its assessment. It surveys graph-based approaches and evaluates them against criteria the authors consider important for robustness and practical use.
1.1 The field of network robustness research
- Robustness is the ability to continue performing well under failures or attacks, while measuring it requires capturing backup possibilities and alternative paths.The authors also prioritize measures that respond to added edges and have intuitively clear meanings.Source: §1.1 · pp. 1–2
- The survey focuses on topological graph measures, which describe network structure while neglecting processes running on top of the network.Unless stated otherwise, graphs are simple, undirected, connected, unweighted, finite, and deterministic.Source: §1.1 · p. 2
1.2 Outline
- Section 2 reviews classical graph measures and reliability polynomials, while Section 3 covers three measures based on the Laplacian spectrum.Section 2 asks whether classical measures can characterize robustness; the three spectral measures are algebraic connectivity, spanning-tree count, and effective graph resistance.Source: §1.2 · p. 2
- Section 4 evaluates fourteen measures on selected small graphs against edge-addition sensitivity, backup possibilities, and intuitive interpretability.The conclusion recapitulates earlier findings and suggests a direction for further research.Source: §1.2 · p. 2
2 Classical graph measures
Section 2 surveys classical graph measures considered for network robustness, including connectivity, distance, betweenness, clustering, and reliability polynomials. It discusses both how these measures indicate robustness and where their evaluations are limited.
2.1 Connectivity
- Higher vertex or edge connectivity is treated as indicating greater robustness; vertex connectivity counts the minimum vertex removals needed to disconnect an incomplete graph.For complete graphs, vertex connectivity is defined as n − 1 so that κv ≤ κe ≤ δmin still holds.Source: §2.1 · p. 3
2.2 Distance
- Average distance strictly decreases when edges are added, unlike diameter, but neither measure accounts for backup paths.Efficiency can be used for unconnected networks, but it shares the alternative-path limitation.Source: §2.2 · pp. 3–4
2.3 Betweenness
- Betweenness can identify bottlenecks under shortest-path traffic, but it ignores alternative paths; average betweenness rankings also depend on graph size conditions.Average distance and average vertex betweenness agree for graphs with the same number of vertices; all three averages agree when both vertex and edge counts match.Source: §2.3 · p. 4
- Maximum edge betweenness can increase when an edge is added, conflicting with the view that added links improve robustness.Figure 1 gives edge betweenness values for the example graphs.Source: Figure 1 · p. 4, §2.3 · p. 5
2.4 Clustering
- A high clustering coefficient indicates high robustness because more triangles correspond to more alternative paths.The coefficient measures how often vertices sharing a neighbour are themselves connected.Source: §2.4 · p. 5
2.5 Reliability polynomials
- The reliability polynomial gives the probability that a graph remains connected when each edge independently exists with probability p; choosing p is difficult, and graph rankings can depend on it.For p close to one, lower edge connectivity implies lower reliability; among graphs with equal edge connectivity, the count of minimum disconnecting edge sets can distinguish reliability.Source: §2.5 · pp. 5–6
- For p close to one, reliability and edge connectivity give the same robustness evaluation; the reliability polynomial can also be defined for vertex deletion.In the vertex-deletion case, its evaluation near p = 1 agrees with vertex connectivity.Source: §2.5 · p. 6
3 Spectral graph measures
The section surveys three Laplacian-based robustness measures: algebraic connectivity, spanning-tree count, and effective graph resistance. It relates these measures to the Laplacian spectrum and discusses their properties as robustness indicators.
3.1 Algebraic connectivity
- Algebraic connectivity is the second-smallest Laplacian eigenvalue and is zero exactly when a graph is disconnected.For an incomplete graph, it is no greater than vertex connectivity.Source: §3.1 · p. 6
- Algebraic connectivity is not strictly increasing when an edge is added, and using any fixed number of Laplacian eigenvalues does not guarantee that property.Figure 3 illustrates graphs with identical algebraic connectivity.Source: §3.1 · p. 7, Figure 3 · p. 7
3.2 Number of spanning trees
- The spanning-tree count ξ is a Laplacian-eigenvalue function and ranks graphs like the reliability polynomial for p sufficiently close to zero.A spanning tree contains n−1 edges and no cycles.Source: §3.2 · p. 7
3.3 Effective resistance
- Effective graph resistance R sums pairwise effective resistances and can be expressed using the non-zero Laplacian eigenvalues.It is also called total effective resistance or the Kirchhoff index.Source: §3.3 · p. 8
- Effective graph resistance strictly decreases when an edge is added, and small values indicate robustness.Pairwise effective resistance reflects both the number of paths between vertices and their length.Source: §3.3 · p. 8
4 An evaluation of robustness measures
Across five four-vertex examples, the measures generally rank graphs in the expected order of decreasing robustness, though several cannot distinguish every graph. The criteria evaluation favors measures that reflect added edges and alternative paths, with effective graph resistance best capturing robustness but difficult to interpret in practice.
4.1 Examples
- All measures rank the five example graphs in the expected decreasing-robustness order, although some cannot distinguish every graph.The examples are complete, cycle, star, path, and empty graphs, each with four vertices.Source: §4.1 · p. 8, Figure 4 · p. 8, Table 1 · p. 9
- Clustering coefficient and connectedness share values for four of five graphs, while connectivity measures, reliability polynomial, and spanning-tree count are constant across trees.Only graph efficiency and clustering coefficient distinguish the unconnected graphs in these examples.Source: §4.1 · pp. 8–9
- Average distance, average vertex betweenness, and average edge betweenness seem useful, but consider only shortest paths rather than longer alternatives.Maximum edge betweenness performs well in these examples but fails in other situations; algebraic connectivity also does not always detect an added edge.Source: §4.1 · p. 9
4.2 Criteria control
- Strict increase when an edge is added leaves only average distance and related average betweenness measures, graph efficiency, reliability polynomial, spanning-tree count, and effective graph resistance.Reliability polynomial rankings depend on edge-failure probability; near one, it corresponds to edge connectivity, which does not strictly increase with added edges.Source: §4.2 · p. 9
- Effective graph resistance best captures robustness because it accounts for alternative paths, unlike shortest-path measures, but its practical meaning is not directly clear.The section identifies average distance and graph efficiency as measures that omit the number and length of alternative paths.Source: §4.2 · p. 9, §4.1 · p. 9
5 Conclusion
The paper surveys fourteen measures for simple, undirected, unweighted graphs and assesses their functionality as robustness measures. All order small example graphs as intuition would, but several have important limitations, including scope restrictions and sensitivity to added edges.
5 Conclusion
- The survey covers eleven measures based on connectivity, distance, betweenness, or clustering, plus three functions of Laplacian eigenvalues.It discusses their functionality as robustness measures.Source: §5 · p. 10
- All fourteen measures order small example graphs as intuition would, though four connectivity measures, clustering coefficient, and spanning-tree count cannot distinguish the given graphs.The four connectivity measures include the reliability polynomial.Source: §5 · p. 10
- Several measures may not reflect an added edge as increased robustness: some remain unchanged, while maximum edge betweenness can increase and indicate lower robustness.The measures that may remain unchanged are connectivity measures, diameter, clustering coefficient, and algebraic connectivity.Source: §5 · p. 10
- Only graph efficiency and clustering coefficient can be used for networks with multiple unconnected components, such as social networks or networks under attack.Source: §5 · p. 10
- The reliability polynomial is realistic for very small failure probabilities but then relates to insensitive edge connectivity; for large probabilities it relates to spanning-tree count.Algebraic connectivity and effective graph resistance are difficult to explain to administrators, while effective graph resistance alone considers backup possibilities.Source: §5 · p. 10
- The analysis is scoped to simple, undirected, unweighted graphs; some measures generalize to weighted networks, and defining measures for flow networks remains a stated need.Flow networks are described as having a traffic matrix and edge capacities.Source: §5 · p. 10