扩大电气紧密中心性计算的规模

《IEEE Transactions on Knowledge and Data Engineering》：Scaling up Electrical Closeness Centrality Computation

电近邻中心性计算成本高，本文通过连接拉普拉斯子矩阵逆的新方法，结合spanning trees和loop-erased random walks理论，提出高效近似算法，实验验证其速度和精度显著提升。

　　

摘要：

电气接近中心性（Electrical Closeness Centrality）是一种经典且稳健的图中心性度量方法。然而，现有的计算电气接近中心性的算法在处理大型图时往往计算成本较高，因为这些算法需要确定图拉普拉斯矩阵（L?）的伪逆的对角元素。为了解决这一挑战，我们提出了新的方法来近似计算L?，通过建立与拉普拉斯子矩阵Lv的逆之间的联系来实现。该子矩阵是通过从原始拉普拉斯矩阵L中移除第v行和第v列得到的。这种联系的一个关键优势是L?1具有多种富有洞察力的组合学解释。具体来说，我们基于生成树和消除环的随机游走（loop-erased random walks）提出了两种对L?1的新解释方法，这些方法有助于开发高效的采样算法。基于这些理论见解，我们设计了两种用于高效近似计算电气接近中心性的算法，并在五个真实世界数据集上对其性能进行了广泛评估。实验结果表明，我们的方法在运行时间和估计精度方面都显著优于现有的最先进方法，优势达到了几个数量级。