标题： 返回概率和k步度量 显示英文标题

标题： Return probability and k-step measures

摘要： 返回概率的概念——最著名的是由乔治·波利亚在d维格子上研究的——在分析网络方面具有潜力。我们提出了一种有效的方法来寻找连通无向图的返回概率分布。我们认为返回概率的区分能力与现有的k步度量方法相同——特别是负β中心性、图论功率指数（GPI）和子图中心性。我们将我们的算法运行时间与β中心性和子图中心性进行比较，发现它要快得多。当返回概率用于测量与β中心性相同的现象时，其运行时间为线性时间——O(n+m)，其中n和m分别为节点数和边数——这比计算β中心性的精确或近似形式所需的矩阵求逆或一系列矩阵乘法要快得多。我们将这种形式的返回概率称为波利亚幂指数（PPI）。计算子图中心性需要对邻接矩阵进行昂贵的特征分解；在2000节点的网络上，返回概率的运行时间是特征分解的一半。这些性能改进很重要，因为计算效率高的度量是分析大型网络所必需的。 显示英文摘要

摘要： The notion of return probability -- explored most famously by George P\'{o}lya on d-dimensional lattices -- has potential as a measure for the analysis of networks. We present an efficient method for finding return probability distributions for connected undirected graphs. We argue that return probability has the same discriminatory power as existing k-step measures -- in particular, beta centrality (with negative beta), the graph-theoretical power index (GPI), and subgraph centrality. We compare the running time of our algorithm to beta centrality and subgraph centrality and find that it is significantly faster. When return probability is used to measure the same phenomena as beta centrality, it runs in linear time -- O(n+m), where n and m are the number of nodes and edges, respectively -- which takes much less time than either the matrix inversion or the sequence of matrix multiplications required for calculating the exact or approximate forms of beta centrality, respectively. We call this form of return probability the P\'{o}lya power index (PPI). Computing subgraph centrality requires an expensive eigendecomposition of the adjacency matrix; return probability runs in half the time of the eigendecomposition on a 2000-node network. These performance improvements are important because computationally efficient measures are necessary in order to analyze large networks.