Abstract
As a generalization of the conventional PageRank model, the multilinear PageRank model is based on the higher-order Markov chain that uses more histories than only the previous state for ranking nodes. The fixed-point iteration and its variants are most commonly used to compute the multilinear PageRank model. In this paper, based on the fixed-point iteration and the inner–outer iteration proposed by Gleich et al. (2015), we present a two-step iteration (named FPIO) for the computation of the multilinear PageRank model. Then we develop a variant of the FPIO (named MFPIO) by considering the multi-step fixed-point iteration and combining it with the inner–outer iteration for solving the multilinear PageRank problem. In fact, the FPIO iteration can be regarded as a special case of the MFPIO iteration. Furthermore, in order to speed up the multilinear PageRank computations, the fixed-point iteration is improved by introducing the minimal polynomial extrapolation (MPE) acceleration technique, such that a new method named FPMPE is presented. Convergence behaviors of our proposed methods are discussed in detail. Numerical results on several multilinear PageRank problems are used to demonstrate the effectiveness of our methods by comparing with several existing methods.