论文标题
在快速计算有向图的laplacian伪插入
On Fast Computation of Directed Graph Laplacian Pseudo-Inverse
论文作者
论文摘要
laplacian矩阵及其用于强烈连接的有向图的伪内部符号对于计算有向图的许多属性至关重要。示例包括随机步行中心性和中间度量，平均打击时间和通勤时间以及其他连接度量。这些措施在分析许多社会和计算机网络时产生。在这篇简短的论文中，我们展示了如何在边缘数量中求解涉及拉普拉斯式的线性系统，这取决于图的可分离性。这直接导致了整个laplacian伪为iNVERSE的列列计算，以节点数量，即每个矩阵输入的恒定时间。该方法基于保证全局线性收敛的“现成”迭代方法，而无需求助于任何矩阵消除算法。
The Laplacian matrix and its pseudo-inverse for a strongly connected directed graph is fundamental in computing many properties of a directed graph. Examples include random-walk centrality and betweenness measures, average hitting and commute times, and other connectivity measures. These measures arise in the analysis of many social and computer networks. In this short paper, we show how a linear system involving the Laplacian may be solved in time linear in the number of edges, times a factor depending on the separability of the graph. This leads directly to the column-by-column computation of the entire Laplacian pseudo-inverse in time quadratic in the number of nodes, i.e., constant time per matrix entry. The approach is based on "off-the-shelf" iterative methods for which global linear convergence is guaranteed, without recourse to any matrix elimination algorithm.
