# Efficient Algorithms for Computing Random Walk Centrality

arXiv: https://arxiv.org/abs/2510.20604 · HTML: https://mlsanity.com/paper/2510.20604/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 77 references that are in the map.
- First posted on arXiv 23 Oct 2025.

## Builds on (most cited first, 14 of 14)

- [SNAP: A General Purpose Network Analysis and Graph Mining Library](https://mlsanity.com/paper/1606.07550/) (2016)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [Axioms for Centrality](https://mlsanity.com/paper/1308.2140/) (2013)
- [Vital nodes identification in complex networks](https://mlsanity.com/paper/1607.01134/) (2016)
- [Robust and Practical Solution of Laplacian Equations by Approximate Elimination](https://mlsanity.com/paper/2303.00709/) (2023)
- [Efficient Approximation Algorithms for Spanning Centrality](https://mlsanity.com/paper/2305.16086/) (2023)
- [Absorbing random-walk centrality: Theory and algorithms](https://mlsanity.com/paper/1509.02533/) (2015)
- [Consistency and differences between centrality measures across distinct classes of networks](https://mlsanity.com/paper/1805.02375/) (2018)
- [On the limiting behavior of parameter-dependent network centrality measures](https://mlsanity.com/paper/1312.6722/) (2013)
- [Computing Effective Resistances on Large Graphs Based on Approximate Inverse of Cholesky Factor](https://mlsanity.com/paper/2303.03617/) (2023)
- [Efficient Centrality Maximization with Rademacher Averages](https://mlsanity.com/paper/2306.03651/) (2023)
- [Estimating Current-Flow Closeness Centrality with a Multigrid Laplacian Solver](https://mlsanity.com/paper/1607.02955/) (2016)
- [Estimating the Percolation Centrality of Large Networks through Pseudo-dimension Theory](https://mlsanity.com/paper/1910.00494/) (2019)
- [Means of Hitting Times for Random Walks on Graphs: Connections, Computation, and Optimization](https://mlsanity.com/paper/2412.11160/) (2024)

## Built on by (most cited first, 1 of 1)

- [What Makes a Desired Graph for Relational Deep Learning?](https://mlsanity.com/paper/2606.08491/) (2026)

## Abstract (arXiv)

Random walk centrality is a fundamental metric in graph mining for quantifying node importance and influence, defined as the weighted average of hitting times to a node from all other nodes. Despite its ability to capture rich graph structural information and its wide range of applications, computing this measure for large networks remains impractical due to the computational demands of existing methods. In this paper, we present a novel formulation of random walk centrality, underpinning two scalable algorithms: one leveraging approximate Cholesky factorization and sparse inverse estimation, while the other sampling rooted spanning trees. Both algorithms operate in near-linear time and provide strong approximation guarantees. Extensive experiments on large real-world networks, including one with over 10 million nodes, demonstrate the efficiency and approximation quality of the proposed algorithms.