Scalable Approximation of Global Graph Centrality

27 concepts22 papers1 proposal

Graph centrality metrics are fundamental tools for understanding networks, allowing us to identify influential nodes, critical bridges, and community bottlenecks. However, traditional global metrics—such as betweenness, closeness, and effective resistance—suffer from a severe scalability bottleneck. Computing them exactly typically requires solving the All-Pairs Shortest Paths (APSP) problem or performing full matrix inversions, both of which scale cubically ($O(n^3)$) or quadratically ($O(n^2)$) with the number of nodes. As Timothy M. Chan et al. demonstrate in Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths, many of these classic graph problems are computationally bound to the complexity of APSP, making exact calculations impossible for modern networks with millions or billions of edges.

To bypass this computational wall, a powerful paradigm has emerged: scalable centrality approximation. Instead of computing exact global values, we can leverage randomized algorithms, nearly-linear time Laplacian solvers, and structural proxies to estimate these metrics in near-linear time ($O(m)$). This approach turns intractable matrix operations into rapid, scalable computations by exploiting key mathematical insights.

Bypassing Matrix Inversion with Laplacian Solvers

Many advanced centrality metrics, such as information centrality or effective resistance, rely on the pseudo-inverse of the graph Laplacian matrix ($L^\dagger$). The entries of this inverse matrix reveal how "current" or information flows through all possible paths in a network, not just the shortest ones. Unfortunately, explicitly calculating $L^\dagger$ takes $O(n^3)$ time.

The key intuition behind scaling these metrics is that we rarely need the entire explicit matrix; we only need its action on specific vectors or its diagonal entries. By reframing complex matrix operations as linear systems ($Lx = b$), we can use high-performance, nearly-linear time Laplacian solvers.

For instance, Wanyue Xu et al. show in Fast Evaluation for Relevant Quantities of Opinion Dynamics that social metrics like polarization and conflict can be reframed as vector norm estimations, allowing networks with millions of nodes to be analyzed in seconds. Similarly, Liren Shan et al. demonstrate in Improving Information Centrality of a Node in Complex Networks by Adding Edges that combining nearly-linear time Laplacian solvers with Monte-Carlo trace estimation allows for the optimization of network centrality without incurring the cubic complexity of exact matrix inversion.

Dimensionality Reduction and Random Projections

Even with fast solvers, evaluating centrality for every node or edge individually can still be too expensive. To scale further, researchers combine Laplacian solvers with dimensionality reduction techniques, most notably the Johnson-Lindenstrauss (JL) lemma.

The JL lemma guarantees that a set of high-dimensional vectors can be projected into a much lower-dimensional space while preserving their pairwise distances with high probability. In network analysis, this means we can approximate global distance-based or flow-based metrics by running a small number of random trials rather than computing the full network state.

For example, Liren Shan et al. integrate randomized Laplacian solvers with the JL lemma in Current Flow Group Closeness Centrality for Complex Networks? to approximate the marginal gain of adding a node to a group, reducing the complexity from cubic to nearly-linear time. This same combination of random projections and fast solvers enables Liren Shan et al. to compute Biharmonic Distance Related Centrality for Edges in Weighted Networks for millions of edges with high empirical accuracy.

Beyond projections, randomized sampling and hypergraph sketches offer another route to efficiency. As highlighted by Wei Wang et al. in Data Science for Social Good - 2014 KDD Highlights, using hypergraph sketches allows complex metrics like betweenness centrality and PageRank to be estimated in near-linear time by compressing the graph's path structure into lightweight probabilistic summaries.

Bridging Local and Global Scales

Another core intuition behind scalable approximation is that global network properties are often heavily influenced by local structures. We can avoid exploring the entire graph by combining exact local scans with strategic global sampling or geometric bounds.

Consider closeness centrality, which measures the average distance from a node to all others. Edith Cohen et al. achieve near-linear time estimation on graphs with billions of edges in Computing Classic Closeness Centrality, at Scale by combining random sampling with a "pivoting" technique rooted in the triangle inequality. Instead of measuring every pairwise distance, they measure distances to a small set of pivot nodes and bound the rest.

For edge-level metrics like spanning centrality, Renchi Yang et al. introduce a hybrid algorithm in Efficient Approximation Algorithms for Spanning Centrality that uses deterministic graph traversals for nearby nodes and strategic random walks for distant ones, processing over 100 million edges in minutes. Similarly, Dayong Zhang et al. show in Identifying and quantifying potential super-spreaders in social networks that balancing local neighborhood scans with targeted global assessments avoids the high complexity of traditional global metrics while maintaining structural accuracy.

In some cases, global spectral properties can be replaced entirely by simple local or geometric proxies. Luoyi Fu et al. prove in On the Similarity between von Neumann Graph Entropy and Structural Information: Interpretation, Computation, and Applications that structural information based purely on node degrees serves as a highly accurate proxy for von Neumann graph entropy, shifting the computational complexity from cubic to linear time. In community detection, Didong Li et al. simplify complex discrete curvature formulas into a linear-time calculation via lower-bound approximations in Lower Ricci Curvature for Efficient Community Detection.

Greedy Optimization via Submodularity

When the goal is not just to compute centrality, but to maximize it (e.g., finding the most influential group of nodes), the search space grows exponentially. However, many global centrality metrics exhibit a mathematical property known as submodularity (or supermodularity), which reflects a law of diminishing returns: adding a node to a small set provides a larger centrality boost than adding it to a larger set.

Submodularity allows researchers to use simple greedy algorithms that provide provable approximation guarantees (typically within $(1 - 1/e)$ of the optimal solution). Eugenio Angriman et al. exploit this property in Group Centrality Maximization for Large-scale Graphs for their walk-based group centrality measure, GED-Walk, developing a "lazy greedy" algorithm that scales linearly with the number of edges and vertices. By combining submodularity with fast marginal gain estimation, complex group selection problems become solvable on an industrial scale.

For directed graphs, where symmetric Laplacian solvers do not directly apply, Haisong Xia demonstrates in Fast Computation of Kemeny's Constant for Directed Graphs that optimized Monte Carlo simulations can provide efficient approximations for random walk metrics with rigorous theoretical error guarantees, reducing processing time from hours to seconds.

Key Foundational Work

Identifying high betweenness centrality nodes in large social networks (2013) — contributed 1 concept elements to this direction.
Limited Attention and Centrality in Social Networks (2013) — contributed 1 concept elements to this direction.
Multi-Scale Link Prediction (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scalable_centrality_approximation_c4cf443f,
  title = {scalable centrality approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-centrality-approximation/rdr_c4cf443f395e4d43b074ef392ecbd85b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_scalable_centrality_approximation_c4cf443f_v1,
  title = {scalable centrality approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scalable-centrality-approximation/rdr_c4cf443f395e4d43b074ef392ecbd85b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake