|
|
Pure Mathematics 2025
基于Anderson加速分裂迭代算法求解多重线性PageRank问题
|
Abstract:
本文针对多重线性PageRank问题，结合松弛技术，提出了一般形式的张量分裂迭代算法，并给出了相应的收敛性分析。进一步，结合Anderson加速技术，提出了新的张量分裂算法。
In this paper, combining relaxation techniques, a general form of tensor splitting iterative algorithm is proposed for the multilinear PageRank problem, and the corresponding convergence analysis is given. Furthermore, a new tensor splitting algorithm is proposed by incorporating Anderson acceleration techniques.
| [1] | Page, L. (1999) The Page Rank Citation Ranking: Bringing Order to the Web. Technical Report. |
| [2] | Freschi, V. (2007) Protein Function Prediction from Interaction Networks Using a Random Walk Ranking Algorithm. 2007 IEEE 7th International Symposium on BioInformatics and BioEngineering, Boston, 14-17 October 2007, 42-48. https://doi.org/10.1109/bibe.2007.4375543 |
| [3] | Gleich, D.F. (2015) Page-Rank beyond the Web. SIAM Review, 57, 321-363. https://doi.org/10.1137/140976649 |
| [4] | Morrison, J.L., Breitling, R., Higham, D.J. and Gilbert, D.R. (2005) Gene-Rank: Using Search Engine Technology for the Analysis of Microarray Experiments. BMC Bioinformatics, 6, Article No. 233. https://doi.org/10.1186/1471-2105-6-233 |
| [5] | Winter, C., Kristiansen, G., Kersting, S., Roy, J., Aust, D., Knösel, T., et al. (2012) Google Goes Cancer: Improving Outcome Prediction for Cancer Patients by Network-Based Ranking of Marker Genes. PLOS Computational Biology, 8, e1002511. https://doi.org/10.1371/journal.pcbi.1002511 |
| [6] | Gleich, D.F., Lim, L. and Yu, Y. (2015) Multilinear Page-Rank. SIAM Journal on Matrix Analysis and Applications, 36, 1507-1541. https://doi.org/10.1137/140985160 |
| [7] | Li, W. and Ng, M.K. (2013) On the Limiting Probability Distribution of a Transition Probability Tensor. Linear and Multilinear Algebra, 62, 362-385. https://doi.org/10.1080/03081087.2013.777436 |
| [8] | Li, W., Liu, D., Vong, S. and Xiao, M. (2020) Multilinear Page-Rank: Uniqueness, Error Bound and Perturbation Analysis. Applied Numerical Mathematics, 156, 584-607. https://doi.org/10.1016/j.apnum.2020.05.022 |
| [9] | Li, W., Liu, D., Ng, M.K. and Vong, S. (2017) The Uniqueness of Multilinear Page-Rank Vectors. Numerical Linear Algebra with Applications, 24, e2107. https://doi.org/10.1002/nla.2107 |
| [10] | Liu, D., Vong, S. and Shen, L. (2022) Improved Uniqueness Conditions of Solution for Multilinear Page-Rank and Its Application. Linear and Multilinear Algebra, 72, 203-233. https://doi.org/10.1080/03081087.2022.2158292 |
| [11] | Fasino, D. and Tudisco, F. (2020) Ergodicity Coefficients for Higher-Order Stochastic Processes. SIAM Journal on Mathematics of Data Science, 2, 740-769. https://doi.org/10.1137/19m1285214 |
| [12] | Meini, B. and Poloni, F. (2018) Perron-Based Algorithms for the Multilinear Page-Rank. Numerical Linear Algebra with Applications, 25, e2177. https://doi.org/10.1002/nla.2177 |
| [13] | Guo, P., Gao, S. and Guo, X. (2018) A Modified Newton Method for Multilinear Page-Rank. Taiwanese Journal of Mathematics, 22, 1161-1171. https://doi.org/10.11650/tjm/180303 |
| [14] | Li, D., Xie, S. and Xu, H. (2017) Splitting Methods for Tensor Equations. Numerical Linear Algebra with Applications, 24, e2102. https://doi.org/10.1002/nla.2102 |
| [15] | Liu, D., Li, W. and Vong, S. (2019) Relaxation Methods for Solving the Tensor Equation Arising from the Higher-Order Markov Chains. Numerical Linear Algebra with Applications, 26, e2260. https://doi.org/10.1002/nla.2260 |
| [16] | Bentbib, A.H., Boubekraoui, M. and Jbilou, K. (2024) Extrapolation Methods for Multilinear Page-Rank. Numerical Algorithms, 98, 1013-1043. |
| [17] | Walker, H.F. and Ni, P. (2011) Anderson Acceleration for Fixed-Point Iterations. SIAM Journal on Numerical Analysis, 49, 1715-1735. https://doi.org/10.1137/10078356x |
| [18] | Liu, D., Li, W. and Vong, S. (2018) The Tensor Splitting with Application to Solve Multi-Linear Systems. Journal of Computational and Applied Mathematics, 330, 75-94. https://doi.org/10.1016/j.cam.2017.08.009 |
| [19] | Anderson, D.G. (1965) Iterative Procedures for Nonlinear Integral Equations. Journal of the ACM, 12, 547-560. https://doi.org/10.1145/321296.321305 |
| [20] | Toth, A. and Kelley, C.T. (2015) Convergence Analysis for Anderson Acceleration. SIAM Journal on Numerical Analysis, 53, 805-819. https://doi.org/10.1137/130919398 |
