Truncated and sparse power methods with partially updating for large and sparse higher-order PageRank problems

DOI10.1007/S10915-023-02146-0zbMATH Open1515.65080arXiv2105.03874OpenAlexW4323567536MaRDI QIDQ6159014FDOQ6159014

Authors: Jun Huang, Gang Wu 

Publication date: 20 June 2023

Published in: Journal of Scientific Computing (Search for Journal in Brave)

Abstract: A commonly used technique for the higher-order PageRank problem is the power method that is computationally intractable for large-scale problems. The truncated power method proposed recently provides us with another idea to solve this problem, however, its accuracy and efficiency can be poor in practical computations. In this work, we revisit the higher-order PageRank problem and consider how to solve it efficiently. The contribution of this work is as follows. First, we accelerate the truncated power method for high-order PageRank. In the improved version, it is neither to form and store the vectors arising from the dangling states, nor to store an auxiliary matrix. Second, we propose a truncated power method with partial updating to further release the overhead, in which one only needs to update some important columns of the approximation in each iteration. On the other hand, the truncated power method solves a modified high-order PageRank model for convenience, which is not mathematically equivalent to the original one. Thus, the third contribution of this work is to propose a sparse power method with partial updating for the original higher-order PageRank problem. The convergence of all the proposed methods are discussed. Numerical experiments on large and sparse real-world and synthetic data sets are performed. The numerical results show the superiority of our new algorithms over some state-of-the-art ones for large and sparse higher-order PageRank problems.

Full work available at URL: https://arxiv.org/abs/2105.03874

Recommendations

• Higher-order power methods with momentum for solving the limiting probability distribution vector of higher-order Markov chains
• Two-splitting iteration method for computing higher-order PageRank
• An improved approach to the PageRank problems
• Multilinear PageRank
• Fast PageRank Computation via a Sparse Linear System

zbMATH Keywords

higher-order Markov chaintruncated power methodhigher-order PageRankmultilinear pagerankpartially updating strategy

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Cites Work

• Higher-order multivariate Markov chains and their applications
• Higher-order Markov chain models for categorical data sequences
• Title not available (Why is that?)
• Linear and nonlinear functional analysis with applications. With 401 problems and 52 figures
• On the limiting probability distribution of a transition probability tensor
• Google's PageRank and beyond. The science of search engine rankings
• Solving sparse non-negative tensor equations: algorithms and applications
• Probability, Markov chains, queues, and simulation. The mathematical basis of performance modeling.
• PageRank beyond the web
• A preconditioned and shifted GMRES algorithm for the PageRank problem with multiple damping factors
• A modified Newton method for multilinear PageRank
• Title not available (Why is that?)
• Multilinear PageRank
• Stationary distributions of continuous-time Markov chains: a review of theory and truncation-based approximations
• The uniqueness of multilinear PageRank vectors.
• Fast computation of stationary joint probability distribution of sparse Markov chains
• Extrapolation methods for fixed‐point multilinear PageRank computations
• Relaxation methods for solving the tensor equation arising from the higher‐order Markov chains
• Perron vector analysis for irreducible nonnegative tensors and its applications
• Perron-based algorithms for the multilinear PageRank
• Multilinear PageRank: uniqueness, error bound and perturbation analysis
• Convergence of the fixed‐point iteration for multilinear PageRank
• A residual-based error bound for the multilinear PageRank vector

Cited In (4)

• Higher-order power methods with momentum for solving the limiting probability distribution vector of higher-order Markov chains
• The MFPIO iteration and the FPMPE method for multilinear PageRank computations
• Shifted power-GMRES method accelerated by extrapolation for solving pagerank with multiple damping factors
• Multi-linear pseudo-PageRank for hypergraph partitioning

This page was built for publication: Truncated and sparse power methods with partially updating for large and sparse higher-order PageRank problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6159014)