The general tensor regular splitting iterative method for multilinear PageRank problem

Shuting Tang; Xiuqin Deng; Rui Zhan; Shuting Tang; Xiuqin Deng; Rui Zhan

doi:10.3934/math.2024071

AIMS Mathematics

2024, Volume 9, Issue 1: 1443-1471. doi: 10.3934/math.2024071

Previous Article Next Article

Research article Special Issues

The general tensor regular splitting iterative method for multilinear PageRank problem

School of Mathematics and Statistics, Guangdong University of Technology, Guangzhou, 510006, China

Received: 08 October 2023 Revised: 17 November 2023 Accepted: 30 November 2023 Published: 11 December 2023
MSC : 65F10, 65H10

The paper presents an iterative scheme called the general tensor regular splitting iterative (GTRS) method for solving the multilinear PageRank problem, which is based on a (weak) regular splitting technique and further accelerates the iterative process by introducing a parameter. The method yields familiar iterative schemes through the use of specific splitting strategies, including fixed-point, inner-outer, Jacobi, Gauss-Seidel and successive overrelaxation methods. The paper analyzes the convergence of these solvers in detail. Numerical results are provided to demonstrate the effectiveness of the proposed method in solving the multilinear PageRank problem.
- multilinear PageRank,
- tensor,
- regular splitting,
- convergence
Citation: Shuting Tang, Xiuqin Deng, Rui Zhan. The general tensor regular splitting iterative method for multilinear PageRank problem[J]. AIMS Mathematics, 2024, 9(1): 1443-1471. doi: 10.3934/math.2024071

Related Papers:

Abstract

The paper presents an iterative scheme called the general tensor regular splitting iterative (GTRS) method for solving the multilinear PageRank problem, which is based on a (weak) regular splitting technique and further accelerates the iterative process by introducing a parameter. The method yields familiar iterative schemes through the use of specific splitting strategies, including fixed-point, inner-outer, Jacobi, Gauss-Seidel and successive overrelaxation methods. The paper analyzes the convergence of these solvers in detail. Numerical results are provided to demonstrate the effectiveness of the proposed method in solving the multilinear PageRank problem.

References

[1]	L. Page, S. Brin, R. Motwani, T. Winograd, The PageRank citation ranking: bringing order to the web, Proceedings of ASIS, 98 (1998), 161–172.
[2]	P. Boldi, M. Santini, S. Vigna, PageRank as a function of the damping factor, Proceedings of the 14th international conference on World Wide Web, 2005,557–566. https://doi.org/10.1145/1060745.1060827
[3]	Y. Ding, E. Yan, A. Frazho, J. Caverlee, PageRank for ranking authors in co-citation networks, J. Am. Soc. Inf. Sci. Tec., 60 (2009), 2229–2243. https://doi.org/10.1002/asi.21171 doi: 10.1002/asi.21171
[4]	F. Chung, A brief survey of PageRank algorithms, IEEE Trans. Netw. Sci. Eng., 1 (2014), 38–42. https://doi.org/10.1109/TNSE.2014.2380315 doi: 10.1109/TNSE.2014.2380315
[5]	Q. Liu, B. Xiang, N. Yuan, E. Chen, H. Xiong, Y. Zheng, et al., An influence propagation view of PageRank, ACM Trans. Knowl. Discov. D., 11 (2017), 30. https://doi.org/10.1145/3046941 doi: 10.1145/3046941
[6]	Y. Gao, X. Yu, H. Zhang, Overlapping community detection by constrained personalized PageRank, Expert Syst. Appl., 173 (2021), 114682. https://doi.org/10.1016/j.eswa.2021.114682 doi: 10.1016/j.eswa.2021.114682
[7]	P. Zhang, T. Wang, J. Yan, PageRank centrality and algorithms for weighted, directed networks, Physica A, 586 (2022), 126438. https://doi.org/10.1016/j.physa.2021.126438 doi: 10.1016/j.physa.2021.126438
[8]	Z. Hua, L. Fei, X. Jing, An improved risk prioritization method for propulsion system based on heterogeneous information and PageRank algorithm, Expert Syst. Appl., 212 (2023), 118798. https://doi.org/10.1016/j.eswa.2022.118798 doi: 10.1016/j.eswa.2022.118798
[9]	D. Gleich, L. Lim, Y. Yu, Multilinear PageRank, SIAM J. Matrix Anal. Appl., 36 (2015), 1507–1541. https://doi.org/10.1137/140985160 doi: 10.1137/140985160
[10]	S. Hu, L. Qi, Convergence of a second order Markov chain, Appl. Math. Comput., 241 (2014), 183–192. https://doi.org/10.1016/j.amc.2014.05.011 doi: 10.1016/j.amc.2014.05.011
[11]	A. Langville, C. Meyer, Google's PageRank and beyond: the science of search engine rankings, Princeton: Princeton University Press, 2006. https://doi.org/10.1515/9781400830329
[12]	W. Li, D. Liu, M. Ng, S. Vong, The uniqueness of multilinear PageRank vectors, Numer. Linear Algebr., 24 (2017), 2107. https://doi.org/10.1002/nla.2107 doi: 10.1002/nla.2107
[13]	W. Li, D. Liu, S. Vong, M. Xiao, Multilinear PageRank: uniqueness, error bound and perturbation analysis, Appl. Math. Comput., 156 (2020), 584–607. https://doi.org/10.1016/j.apnum.2020.05.022 doi: 10.1016/j.apnum.2020.05.022
[14]	J. Huang, G. Wu, Convergence of the fixed-point iteration for multilinear PageRank, Numer. Linear Algebr., 28 (2021), 2379. https://doi.org/10.1002/nla.2379 doi: 10.1002/nla.2379
[15]	D. Fasino, F. Tudisco, Ergodicity coefficients for higher-order stochastic processes, SIAM J. Math. Data Sci., 2 (2020), 740–769. https://doi.org/10.1137/19M1285214 doi: 10.1137/19M1285214
[16]	D. Liu, S. Vong, L. Shen, Improved uniqueness conditions of solution for multilinear PageRank and its application, Linear Multilinear A., in press. https://doi.org/10.1080/03081087.2022.2158292
[17]	B. Meini, F. Poloni, Perron-based algorithms for the multilinear PageRank, Numer. Linear Algebr., 25 (2018), 2177. https://doi.org/10.1002/nla.2177 doi: 10.1002/nla.2177
[18]	P. Guo, S. Gao, X. Guo, A modified Newton method for multilinear PageRank, Taiwan. J. Math., 22 (2018), 1161–1171. https://doi.org/10.11650/tjm/180303 doi: 10.11650/tjm/180303
[19]	D. Liu, W. Li, S. Vong, Relaxation methods for solving the tensor equation arising from the higher-order Markov chains, Numer. Linear Algebr., 26 (2019), 2260. https://doi.org/10.1002/nla.2260 doi: 10.1002/nla.2260
[20]	S. Cipolla, M. Redivo-Zaglia, F. Tudisco, Extrapolation methods for fixed-point multilinear PageRank computations, Numer. Linear Algebr., 27 (2020), 2280. https://doi.org/10.1002/nla.2280 doi: 10.1002/nla.2280
[21]	A. Bucci, F. Poloni, A continuation method for computing the multilinear PageRank, Numer. Linear Algebr., 29 (2022), 2432. https://doi.org/10.1002/nla.2432 doi: 10.1002/nla.2432
[22]	M. Boubekraoui, A. Bentbib, K. Jbilou, Vector Aitken extrapolation method for multilinear PageRank computations, J. Appl. Math. Comput., 69 (2023), 1145–1172. https://doi.org/10.1007/s12190-022-01786-z doi: 10.1007/s12190-022-01786-z
[23]	F. Lai, W. Li, X. Peng, Y. Chen, Anderson accelerated fixed-point iteration for multilinear PageRank, Numer. Linear Algebr., 30 (2023), 2499. https://doi.org/10.1002/nla.2499 doi: 10.1002/nla.2499
[24]	D. Liu, W. Li, S. Vong, The tensor splitting with application to solve multi-linear systems, J. Appl. Math. Comput., 330 (2018), 75–94. https://doi.org/10.1016/j.cam.2017.08.009 doi: 10.1016/j.cam.2017.08.009
[25]	L. Cui, W. Hu, J. Yuan, Iterative refinement method by higher-order singular value decomposition for solving multi-linear systems, Appl. Math. Lett., 146 (2023), 108819. https://doi.org/10.1016/j.aml.2023.108819 doi: 10.1016/j.aml.2023.108819
[26]	Z. Jiang, J. Li, A new preconditioned AOR-type method for M-tensor equation, Appl. Numer. Math., 189 (2023), 39–52. https://doi.org/10.1016/j.apnum.2023.03.013 doi: 10.1016/j.apnum.2023.03.013
[27]	L. Cui, X. Zhang, Bounds of H-eigenvalues of interval tensors, Comp. Appl. Math., 42 (2023), 280. https://doi.org/10.1007/s40314-023-02418-3 doi: 10.1007/s40314-023-02418-3
[28]	R. Varga, Matrix iterative analysis, Berlin: Springer, 2000. https://doi.org/10.1007/978-3-642-05156-2
[29]	Z. Tian, Y. Liu, Y. Zhang, Z. Liu, M. Tian, The general inner-outer iteration method based on regular splittings for the PageRank problem, Appl. Math. Comput., 356 (2019), 479–501. https://doi.org/10.1016/j.amc.2019.02.066 doi: 10.1016/j.amc.2019.02.066
[30]	A. Raftery, S. Tavaré, Estimation and modelling repeated patterns in high order Markov chains with the mixture transition distribution model, J. R. Stat. Soc. C-Appl., 43 (1994), 179–199. https://doi.org/10.2307/2986120 doi: 10.2307/2986120
[31]	W. Li, M. Ng, On the limiting probability distribution of a transition probability tensor, Linear Multilinear A., 62 (2014), 362–385. https://doi.org/10.1080/03081087.2013.777436 doi: 10.1080/03081087.2013.777436

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)