Non-backtracking PageRank
Non-backtracking PageRank
复制标题
非回溯PageRank
DOI：
10.1007/s10915-019-00981-8
复制
发表时间：
2019
影响因子：
2.5
通讯作者：
Arrigo F
中科院分区：
文献类型：
--
作者：
Arrigo F
20多年来，PageRank算法一直在为网络带来秩序，它计算的是经典的随机行走加隐形传送的稳定状态。这里，我们考虑PageRank的一个变体，它使用非回溯随机游走。要做到这一点，我们首先根据关联的折线图重新表示PageRank。然后，自然地出现了一个非回溯模拟。比较得到的稳态，我们发现，即使对于无向图，非回溯通常会导致节点的不同排名。然后我们将重点放在计算问题上，推导出新算法的显式表示，该算法可以利用底层网络中的结构和稀疏性。最后，我们在一些实际网络上评估了该方法的有效性和效率。
The PageRank algorithm, which has been “bringing order to the web” for more than 20 years, computes the steady state of a classical random walk plus teleporting. Here we consider a variation of PageRank that uses a non-backtracking random walk. To do this, we first reformulate PageRank in terms of the associated line graph. A non-backtracking analog then emerges naturally. Comparing the resulting steady states, we find that, even for undirected graphs, non-backtracking generally leads to a different ranking of the nodes. We then focus on computational issues, deriving an explicit representation of the new algorithm that can exploit structure and sparsity in the underlying network. Finally, we assess effectiveness and efficiency of this approach on some real-world networks.