Multilinear PageRank
Multilinear PageRank
复制标题
DOI：
10.1137/140985160
复制
发表时间：
2014-09
期刊：
影响因子：
--
通讯作者：
D. Gleich;Lek-Heng Lim;Yongyang Yu
中科院分区：
文献类型：
--
作者：
D. Gleich;Lek-Heng Lim;Yongyang Yu
在本文中，我们首先扩展了著名的PageRank修改高阶马尔可夫链。虽然这个系统具有吸引人的理论性质，它是计算上难以解决的许多有趣的问题。接下来，我们研究一个计算上容易处理的近似高阶PageRank向量，涉及一个系统的多项式方程称为多线性PageRank。这是由一种新颖的“空间随机冲浪者”模型激发的，在这种模型中，冲浪者记住了历史的点点滴滴，并受到这些信息的影响。基本的随机过程是一个顶点强化随机游动的实例。我们发展了一个简单的不动点方法，移位不动点方法，和牛顿迭代在一个特定的参数制度的收敛理论。与马尔可夫链的PageRank向量的情况形成鲜明对比的是，解决方案总是唯一的，并且易于计算，多线性PageRank的参数制度的解决方案不是唯一的，简单的算法不收敛。我们提供了一个存储库，这些非收敛的情况下，我们遇到了通过穷举和随机抽样，我们相信是有用的，为今后的研究问题。
In this paper, we first extend the celebrated PageRank modification to a higher-order Markov chain. Although this system has attractive theoretical properties, it is computationally intractable for many interesting problems. We next study a computationally tractable approximation to the higher-order PageRank vector that involves a system of polynomial equations called multilinear PageRank. This is motivated by a novel “spacey random surfer” model, where the surfer remembers bits and pieces of history and is influenced by this information. The underlying stochastic process is an instance of a vertex-reinforced random walk. We develop convergence theory for a simple fixed-point method, a shifted fixed-point method, and a Newton iteration in a particular parameter regime. In marked contrast to the case of the PageRank vector of a Markov chain where the solution is always unique and easy to compute, there are parameter regimes of multilinear PageRank where solutions are not unique and simple algorithms do not converge. We provide a repository of these non-convergent cases that we encountered through exhaustive enumeration and randomly sampling that we believe is useful for future study of the problem.