Fast Computation of Kemeny's Constant for Directed Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929492291747840 |
|---|---|
| author | Xia, Haisong Zhang, Zhongzhi |
| author_facet | Xia, Haisong Zhang, Zhongzhi |
| contents | Kemeny's constant for random walks on a graph is defined as the mean hitting time from one node to another selected randomly according to the stationary distribution. It has found numerous applications and attracted considerable research interest. However, exact computation of Kemeny's constant requires matrix inversion, which scales poorly for large networks with millions of nodes. Existing approximation algorithms either leverage properties exclusive to undirected graphs or involve inefficient simulation, leaving room for further optimization. To address these limitations for directed graphs, we propose two novel approximation algorithms for estimating Kemeny's constant on directed graphs with theoretical error guarantees. Extensive numerical experiments on real-world networks validate the superiority of our algorithms over baseline methods in terms of efficiency and accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_05471 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast Computation of Kemeny's Constant for Directed Graphs Xia, Haisong Zhang, Zhongzhi Social and Information Networks Kemeny's constant for random walks on a graph is defined as the mean hitting time from one node to another selected randomly according to the stationary distribution. It has found numerous applications and attracted considerable research interest. However, exact computation of Kemeny's constant requires matrix inversion, which scales poorly for large networks with millions of nodes. Existing approximation algorithms either leverage properties exclusive to undirected graphs or involve inefficient simulation, leaving room for further optimization. To address these limitations for directed graphs, we propose two novel approximation algorithms for estimating Kemeny's constant on directed graphs with theoretical error guarantees. Extensive numerical experiments on real-world networks validate the superiority of our algorithms over baseline methods in terms of efficiency and accuracy. |
| title | Fast Computation of Kemeny's Constant for Directed Graphs |
| topic | Social and Information Networks |
| url | https://arxiv.org/abs/2409.05471 |