An Efficient and Scalable Algorithm for Estimating Kemeny's Constant of a Markov Chain on Large Graphs
An Efficient and Scalable Algorithm for Estimating Kemeny's Constant of a Markov Chain on Large Graphs
复制标题
DOI：
10.1145/3447548.3467431
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Shiju Li;Xin Huang;Chul-Ho Lee
中科院分区：
文献类型：
--
作者：
Shiju Li;Xin Huang;Chul-Ho Lee
图上的马尔可夫链从任意节点到根据其平稳分布随机选择的目标节点的平均命中时间称为Kemeny常数，它是网络分析的一个重要度量，具有广泛的应用。然而，计算Kemeny常数仍然是昂贵的，特别是当它涉及到一个大的图时，因为它需要计算相应的转移矩阵或其归一化拉普拉斯矩阵的谱。在本文中，我们提出了一种简单而计算效率高的逼近Kemeny常数的蒙特卡罗算法，该算法配备了一个ε，δ)近似估计量。由于其固有的算法并行性，我们能够在GPU上开发其并行实现以加快计算速度。我们在13个真实世界的图形上提供了广泛的实验结果，以证明我们的算法的计算效率和可扩展性，它比最先进的算法实现了高达500倍的加速。我们进一步介绍了它的实际增强，使我们的算法准备好在现实环境中实际使用。
The mean hitting time of a Markov chain on a graph from an arbitrary node to a target node randomly chosen according to its stationary distribution is called Kemeny's constant, which is an important metric for network analysis and has a wide range of applications. It is, however, still computationally expensive to evaluate the Kemeny's constant, especially when it comes to a large graph, since it requires the computation of the spectrum of the corresponding transition matrix or its normalized Laplacian matrix. In this paper, we propose a simple yet computationally efficient Monte Carlo algorithm to approximate the Kemeny's constant, which is equipped with an ε,δ)-approximation estimator. Thanks to its inherent algorithmic parallelism, we are able to develop its parallel implementation on a GPU to speed up the computation. We provide extensive experiment results on 13 real-world graphs to demonstrate the computational efficiency and scalability of our algorithm, which achieves up to 500x speed-up over the state-of-the-art algorithm. We further present its practical enhancements to make our algorithm ready for practical use in real-world settings.