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

CREATORChangan Liu, Zixuan Xie, Ahad N. Zehmakan, and Zhongzhi Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-20604

Browse the full library · About the Tower of Babel