The spanning centrality of an edge is the fraction of the graph's spanning trees that contain it — a principled measure of how structurally critical the edge is. It is valuable for network robustness analysis and graph sparsification, but computing it exactly involves effective resistances, which are prohibitively expensive on large graphs.

The contribution

This work builds approximation algorithms that combine random spanning-tree sampling and random-walk-based estimators with tight variance control, delivering accuracy guarantees at a small fraction of the cost of prior methods. Careful algorithm engineering — landmark selection, loop-erased walk reuse — pushes the practical scale to graphs with hundreds of millions of edges.

Takeaway

Spanning centrality no longer needs to be a small-graph luxury: with these estimators, edge-importance analysis runs on social-network-scale graphs on a single machine, with error bounds you can set in advance.