Model And Algorithm For Higher-order Markov Chains With Applications

In this thesis,we propose some fast and efficient algorithms for a limiting probability distribution problem of a higher-order Markov chain,and then these methods are used for multilinear PageRank problems.The details are given as follows:The first chapter is the introduction of this thesis,which introduces the limiting probability distribution problem of a higher-order Markov chain,and the main results obtained in this thesis.In the second chapter,we propose and develop an Aitken extrapolation method to calculate a limiting probability distribution vector of a transition probability tensor P arising from a higher-order Markov chain.In the model,the computation of such limiting probability distribution vector x can be formulated as a Z-eigenvalue problem of a transition probability tensor.The implementation of Aitken extrapolation is well studied.Numerical experiments show that the new methods are feasible and faster than original approaches.In the third chapter,the higher-order Markov chain problem is a natural generalization of the first order Markov chain,which can be regarded as the problem of the tensor equation with constraints.Currently used for a limiting probability distribution problem of a higher-order Markov chain is the most classical algorithm of higher-order power method,but in some cases,a power method of convergence speed is slow.We first reformulate the constrained transition probability tensor equations as a least squares problem,then we propose the projection of Gauss-Newton method to solve the least squares problem.Numerical results show that the proposed algorithm converges faster than the power method.Furthermore,the higher-order Markov chain is introduced to the multilinear PageRank in a directed graph,then using the Aitken extrapolation method and the least squares method to calculate the multilinear PageRank vector.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.Numerical results show that the proposed algorithm converges faster than the fixed-point iteration.