Efficient Algorithms for Computing Random Walk Centrality
By: Changan Liu , Zixuan Xie , Ahad N. Zehmakan and more
Potential Business Impact:
Finds important people in huge groups faster.
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.
Similar Papers
Network Centrality Metrics Based on Unrestricted Paths, Walks and Cycles Compared to Standard Centrality Metrics
Social and Information Networks
Finds better ways to measure importance in networks.
Fully personalized PageRank and algebraic methods to distribute a random walker
Social and Information Networks
Changes how important websites appear online.
The Derivative of Kemeny's Constant as a Centrality Measure in Undirected Graphs
Numerical Analysis
Finds important roads in networks.