Graph Metrics
Quantitative measures that describe the structure of a graph or the role of individual vertices and edges within it.
Centrality
How important is a vertex?
| Metric | Complexity | What it measures |
|---|---|---|
O(VE) unweighted; O(VE + V(V+E) log V) weighted |
How often a vertex lies on shortest paths between other vertices. High betweenness = bridge or bottleneck. |
|
O(V) per vertex given a pre-computed distance map |
Reciprocal of the sum of shortest distances to all other vertices. High closeness = can reach everyone quickly. |
|
O(1) per vertex |
Number of connections (in, out, or total). Simple but effective for many networks. |
|
O(V + E) per iteration |
Importance based on incoming links (recursive: a link from an important page counts more). Used by web search engines. |
Distance and structure
| Metric | What it measures |
|---|---|
Maximum distance from a vertex to any other. The minimum eccentricity across all vertices is the graph’s radius; the maximum is the diameter. |
|
Mean shortest-path distance from a vertex. Low mean = centrally located. |
|
Fraction of a vertex’s neighbor pairs that are also connected to each other. High clustering = tight-knit local community. |
|
Sparse-matrix metrics used to evaluate vertex orderings for numerical solvers. |
Graph-level statistics
| Metric | What it measures |
|---|---|
k-core decomposition: assigns each vertex the largest k such that it belongs to a subgraph where every vertex has degree >= k. Useful for identifying dense substructures. A weighted variant is available. |
Most distance-based metrics (eccentricity, geodesic_distance,
closeness_centrality) consume a pre-computed distance map and therefore
don’t fit a single complexity figure — the cost is dominated by the
shortest-paths run (Dijkstra
per vertex, Floyd-Warshall,
or Johnson) that
you run first.
|