Efficient Algorithms for Computing Random Walk Centrality
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918167793631232 |
|---|---|
| author | Liu, Changan Xie, Zixuan Zehmakan, Ahad N. Zhang, Zhongzhi |
| author_facet | Liu, Changan Xie, Zixuan Zehmakan, Ahad N. Zhang, Zhongzhi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_20604 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Algorithms for Computing Random Walk Centrality Liu, Changan Xie, Zixuan Zehmakan, Ahad N. Zhang, Zhongzhi Artificial Intelligence 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. |
| title | Efficient Algorithms for Computing Random Walk Centrality |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2510.20604 |