Efficient Algorithms for Computing Random Walk Centrality
Changan Liu, Zixuan Xie, Ahad N. Zehmakan, and Zhongzhi Zhang · 2025
Read Efficient Algorithms for Computing Random Walk Centrality by Changan Liu, Zixuan Xie, Ahad N. Zehmakan, and Zhongzhi Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20604.txt.
Description
Changan Liu and three co-authors present efficient algorithms for computing random walk centrality, a graph measure that averages hitting times to a node from all other nodes. The measure captures rich structural information and has wide uses in graph mining, but existing computation methods are too demanding for large networks. A novel formulation of the centrality underpins both of their scalable algorithms.
One algorithm uses approximate Cholesky factorization with sparse inverse estimation, while the other samples rooted spanning trees. Both run in near-linear time and carry strong approximation guarantees, two properties that rarely come together for this measure. Extensive experiments on large real-world networks, including one with over ten million nodes, demonstrate the efficiency and approximation quality of the pair.
Catalog record
| CREATOR | Changan Liu, Zixuan Xie, Ahad N. Zehmakan, and Zhongzhi Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-20604