提出两种高效算法，快速计算超大规模网络的节点重要性。
Efficient Algorithms for Computing Random Walk Centrality
- 基于近似乔列斯基分解和稀疏逆估计，实现近线性时间计算。
- 在超过1000万节点的网络上，计算效率显著优于传统方法。
- 适合需要快速分析大规模图结构的应用场景。
随机游走中心性是图挖掘中衡量节点重要性和影响力的基石指标，定义为从其他所有节点到达目标节点的命中时间的加权平均。尽管该指标能捕捉丰富的图结构信息且应用广泛，但现有方法在大规模网络上的计算开销巨大，难以实用。本文提出一种新的随机游走中心性公式，据此设计了两种可扩展算法：一种基于近似乔列斯基分解与稀疏逆估计，另一种基于采样有根生成树。两种算法均在近线性时间内运行，并提供严格的近似保证。在多个大规模真实网络上的实验，包括一个超过1000万节点的网络，验证了所提算法在效率与近似质量方面的优越性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。