Multilinear PageRank
From MaRDI portal
graphshigher-order Markov chainshigher-order PageRankhypermatrixmultilinear PageRankPageRankspacey random surfertensortensor PageRank
Hypergraphs (05C65) Random walks on graphs (05C81) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Multilinear algebra, tensor calculus (15A69) Stochastic matrices (15B51) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Numerical computation of solutions to systems of equations (65H10) Programming involving graphs or networks (90C35)
Abstract: 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, which is a type of tensor PageRank vector. It 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.
Recommendations
Cites work
- An inner-outer iteration for computing PageRank
- Bounded-rank tensors are defined in bounded degree
- Eigenvalues of a real supersymmetric tensor
- Google's PageRank and beyond. The science of search engine rankings
- scientific article; zbMATH DE number 1256666 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 3215568 (Why is no real title available?)
- PageRank beyond the web
- Perron-Frobenius theorem for nonnegative multilinear forms and extensions
- Perron-Frobenius theorem for nonnegative tensors
- Semidefinite relaxations for best rank-1 tensor approximations
- Shifted power method for computing tensor eigenpairs
- Solving sparse non-negative tensor equations: algorithms and applications
- The Spacey Random Walk: A Stochastic Process for Higher-Order Data
- Traps and Pitfalls of Topic-Biased PageRank
- Vertex-reinforced random walk
- Vertex-reinforced random walks and a conjecture of Pemantle
- When are overcomplete topic models identifiable? Uniqueness of tensor Tucker decompositions with structured sparsity
Cited in
(66)- Continuation methods for computing Z-/H-eigenpairs of nonnegative tensors
- Fast computation of stationary joint probability distribution of sparse Markov chains
- A modified Newton iteration for finding nonnegative \(Z\)-eigenpairs of a nonnegative tensor
- Markov chains with memory, tensor formulation, and the dynamics of power iteration
- Uniqueness and perturbation bounds for sparse non-negative tensor equations
- A modified Newton method for multilinear PageRank
- A survey of Shanks' extrapolation methods and their applications
- A general preconditioner accelerated SOR-type iterative method for multi-linear systems with \(\mathcal{Z}\)-tensors
- Triangular decomposition of CP factors of a third-order tensor with application to solving nonlinear systems of equations
- New uniqueness conditions for the stationary probability matrix of transition probability tensors
- A new modified Newton iteration for computing nonnegative Z-eigenpairs of nonnegative tensors
- An SDP relaxation method for Perron pairs of a nonnegative tensor
- Some inequalities on the spectral radius of nonnegative tensors
- Multilinear PageRank: uniqueness, error bound and perturbation analysis
- Computing the largest H-eigenvalue of large-scale tensors generated from directed hypergraphs
- Generalized tensor equations with leading structured tensors
- Ergodicity of $p$-majorizing nonlinear Markov operators on the finite dimensional space
- Non-backtracking PageRank
- Vector Aitken extrapolation method for multilinear PageRank computations
- PageRank beyond the web
- Computing eigenvalues of large scale sparse tensors arising from a hypergraph
- A necessary and sufficient condition for existence of a positive Perron vector
- Perron-based algorithms for the multilinear PageRank
- Seeded PageRank solution paths
- The uniqueness of multilinear PageRank vectors.
- Quadratic decomposable submodular function minimization: theory and practice
- Nonlocal pagerank
- Three hypergraph eigenvector centralities
- Convergence of the fixed‐point iteration for multilinear PageRank
- Ergodicity Coefficients for Higher-Order Stochastic Processes
- Higher-order power methods with momentum for solving the limiting probability distribution vector of higher-order Markov chains
- Computing tensor Z-eigenvectors with dynamical systems
- On identifiability of higher order block term tensor decompositions of rank \(L_r \otimes\) rank-1
- A residual-based error bound for the multilinear PageRank vector
- Nonnegative tensors revisited: plane stochastic tensors
- The Spacey Random Walk: A Stochastic Process for Higher-Order Data
- Higher Order Extended Dynamic Mode Decomposition Based on the Structured Total Least Squares
- Nonlinear Perron--Frobenius Theorems for Nonnegative Tensors
- Spectral computation with third-order tensors using the t-product
- Semidefinite Relaxation Methods for Tensor Absolute Value Equations
- Network Capacity Bound for Personalized PageRank in Multimodal Networks
- What Are Higher-Order Networks?
- Multi-linear pseudo-PageRank for hypergraph partitioning
- On classification of states in higher order Markov chains
- Truncated and sparse power methods with partially updating for large and sparse higher-order PageRank problems
- Improved uniqueness conditions of solution for multilinear pagerank and its application
- The MFPIO iteration and the FPMPE method for multilinear PageRank computations
- Extrapolation methods for multilinear PageRank
- On limiting probability distributions of higher order Markov chains
- Accelerating the computation of tensor Z-eigenvalues
- Low-dimensional subspace regularization through structured tensor priors
- A linearized alternating direction method of multipliers for solving complex semi-symmetric tensor equations and its applications
- The projected Newton iteration approach for computing the nonnegative Z-eigenpairs of nonnegative tensors
- Influence of the automorphism group of a graph on its PageRank scores of vertices
- Spliting iteration method for solving multilinear PageRank problem
- Preconditioned iterative methods with Anderson acceleration for solving multilinear PageRank and applications
- On certain classes of nonlinear matrix equations: theory, applications, and numerical solution
- Krylov subspace methods for large multidimensional eigenvalue computation
- Extrapolated splitting methods for multilinear PageRank computations
- On the Perron–Frobenius theory for tensors with negative entries and its applications
- On the spectrum of two-layer approach and multiplex PageRank
- Fast computation of eigenvector centralities for multilayer networks with nonnegative tensor train
- Can a higher-order Markov chain be treated as a first-order Markov chain?
- On computations of limiting probability distributions of higher order Markov chains
- Further study on tensor absolute value equations
- Multivariate polynomial perturbations of algebraic equations
This page was built for publication: Multilinear PageRank
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3456870)
