(Universiti Teknikal Malaysia Melaka, Malaysia)(2) Ahmad Naim Che Pee
(Universiti Teknikal Malaysia Melaka, Malaysia)(3) Sarni Suhaila Rahim
(Universiti Teknikal Malaysia Melaka, Malaysia)(4) * Aji Prasetya Wibawa
(Universitas Negeri Malang, Indonesia)*corresponding author
AbstractComputation ranking algorithms are widely used in several informatics fields. One of them is the PageRank algorithm, recognized as the most popular search engine globally. Many researchers have improvised the ranking algorithm in order to get better results. Recent research using Rayleigh Quotient to speed up PageRank can guarantee the convergence of the dominant eigenvalues as a key value for stopping computation. Bolzano's method has a convergence character on a linear function by dividing an interval into two intervals for better convergence. This research aims to implant the Bolzano algorithm into Rayleigh for faster computation. This research produces an algorithm that has been tested and validated by mathematicians, which shows an optimization speed of a maximum 7.08% compared to the sole Rayleigh approach. Analysis of computation results using statistics software shows that the degree of the curve of the new algorithm, which is Rayleigh with Bolzano booster (RB), is positive and more significant than the original method. In other words, the linear function will always be faster in the subsequent computation than the previous method.
KeywordsPageRank; Optimization; Bolzano method; Rayleigh quotient; Eigenvalue
|
DOIhttps://doi.org/10.26555/ijain.v8i1.718 |
Article metricsAbstract views : 675 | PDF views : 223 |
Cite |
Full Text Download
|
References
[1] V. Kuleshov, “Fast algorithms for sparse principal component analysis based on Rayleigh quotient iteration,” 30th Int. Conf. Mach. Learn. ICML 2013, vol. 28, no. 3, pp. 2468–2475, 2013. Available: Google Scholar.
[2] D. Siahaan and Z. Arifin, “Implementing quotient rayleigh in power method to improve the computation speed of Pagerank,” Asian J. Inf. Technol., vol. 8, no. 4, pp. 104–111, 2009. Available: Google Scholar.
[3] J. H. Kim, “Efficient Node Proximity and Node Significance Computations in Graphs,” ProQuest Diss. Theses, p. 198, 2017, [Online]. Available: https://search.proquest.com/docview/1957948842?accountid=188395.
[4] D. Silvestre, J. Hespanha, and C. Silvestre, “A PageRank Algorithm based on Asynchronous Gauss-Seidel Iterations,” 2018 Annu. Am. Control Conf., vol. 2018-June, pp. 484–489, Jun. 2018, doi: 10.23919/ACC.2018.8431212.
[5] Z.-L. Luo, W.-D. Cai, Y.-J. Li, and D. Peng, “A PageRank-Based Heuristic Algorithm for Influence Maximization in the Social Network,” in Lecture Notes in Electrical Engineering, vol. 157, pp. 485–490, 2012, doi: 10.1007/978-3-642-28798-5_65.
[6] P. Berkhin, “A Survey on PageRank Computing,” Internet Math., vol. 2, no. 1, pp. 73–120, Jan. 2005, doi: 10.1080/15427951.2005.10129098.
[7] K. Sugihara, “Beyond Google’s PageRank: Complex Number-based Calculations for Node Ranking,” Glob. J. Comput. Sci. Technol., vol. 19, no. 3E, pp. 1–12, Oct. 2019, doi: 10.34257/GJCSTEVOL19IS3PG1.
[8] D. F. Gleich, L.-H. Lim, and Y. Yu, “Multilinear PageRank,” SIAM J. Matrix Anal. Appl., vol. 36, no. 4, pp. 1507–1541, Jan. 2015, doi: 10.1137/140985160.
[9] X. Wang, J. Ma, K. Bi, and Z. Li, “A Improved PageRank Algorithm Based on Page Link Weight,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8630, no. 1, pp. 720–727, 2014, doi: 10.1007/978-3-319-11197-1_57.
[10] S. Luo, “Distributed PageRank Computation: An Improved Theoretical Study,” Proc. AAAI Conf. Artif. Intell., vol. 33, pp. 4496–4503, Jul. 2019, doi: 10.1609/aaai.v33i01.33014496.
[11] A. N. Langville and C. D. Meyer, Google’s PageRank and beyond: The science of search engine rankings. 2011. Available: Google Scholar.
[12] H.-F. Zhang, T.-Z. Huang, C. Wen, and Z.-L. Shen, “FOM accelerated by an extrapolation method for solving PageRank problems,” J. Comput. Appl. Math., vol. 296, no. C, pp. 397–409, Apr. 2016, doi: 10.1016/j.cam.2015.09.027.
[13] A. K. Srivastava, M. Srivastava, R. Garg, and P. K. Mishra, “An Aitken-extrapolated Gauss-Seidel method for computing PageRank,” J. Stat. Manag. Syst., vol. 22, no. 2, pp. 199–222, Feb. 2019, doi: 10.1080/09720510.2019.1580901.
[14] G. Liu, “An adaptive improvement on PageRank algorithm,” Appl. Math. J. Chinese Univ., vol. 28, no. 1, pp. 17–26, Mar. 2013, doi: 10.1007/s11766-013-3123-9.
[15] J. Lei and H.-F. Chen, “Distributed Randomized PageRank Algorithm Based on Stochastic Approximation,” IEEE Trans. Automat. Contr., vol. 60, no. 6, pp. 1641–1646, Jun. 2015, doi: 10.1109/TAC.2014.2359311.
[16] N. Chen, N. Litvak, and M. Olvera‐Cravioto, “Generalized PageRank on directed configuration networks,” Random Struct. Algorithms, vol. 51, no. 2, pp. 237–274, Sep. 2017, doi: 10.1002/rsa.20700.
[17] C. Gu, F. Xie, and K. Zhang, “A two-step matrix splitting iteration for computing PageRank,” J. Comput. Appl. Math., vol. 278, pp. 19–28, Apr. 2015, doi: 10.1016/j.cam.2014.09.022.
[18] D. F. Gleich, “PageRank Beyond the Web,” SIAM Rev., vol. 57, no. 3, pp. 321–363, Jan. 2015, doi: 10.1137/140976649.
[19] V. Dinh, L. S. T. Ho, D. Nguyen, and B. T. Nguyen, “Fast learning rates with heavy-tailed losses,” Adv. Neural Inf. Process. Syst., pp. 505–513, Sep. 2016, [Online]. Available: http://arxiv.org/abs/1609.09481.
[20] M. I. Ortega, R. N. Slaybaugh, P. N. Brown, T. S. Bailey, and B. Chang, “A Rayleigh quotient method for criticality eigenvalue problems in neutron transport,” Ann. Nucl. Energy, vol. 138, p. 107120, Apr. 2020, doi: 10.1016/j.anucene.2019.107120.
[21] B. J. Yang, “Dominant eigenvector and eigenvalue algorithm in sparse network spectral clustering,” Lat. Am. Appl. Res. - An Int. J., vol. 48, no. 4, pp. 323–328, Oct. 2018, doi: 10.52292/j.laar.2018.248.
[22] P. I. Frazier, S. G. Henderson, and R. Waeber, “Probabilistic Bisection Converges Almost as Quickly as Stochastic Approximation,” Math. Oper. Res., vol. 44, no. 2, pp. 651–667, May 2019, doi: 10.1287/moor.2018.0938.
[23] M. Mahrudinda, D. Munandar, and S. Purwani, “Efficiency and Convergence of Bisection, Secant, and Newton Raphson Methods in Estimating Implied Volatility,” World Sci. News, vol. 153, no. 2, pp. 157–168, 2021, [Online]. Available: http://psjd.icm.edu.pl/psjd/element/bwmeta1.element.psjd-a6a50cb9-4815-4ac7-b8ea-c69cf6790fbb.
[24] Q. Yang and X. Peng, “An Exact Method for Calculating the Eigenvector Sensitivities,” Appl. Sci., vol. 10, no. 7, p. 2577, Apr. 2020, doi: 10.3390/app10072577.
[25] D. Ruiz, J. C. Bellido, and A. Donoso, “Eigenvector sensitivity when tracking modes with repeated eigenvalues,” Comput. Methods Appl. Mech. Eng., vol. 326, pp. 338–357, Nov. 2017, doi: 10.1016/j.cma.2017.07.031.
[26] G. H. Yoon, A. Donoso, J. Carlos Bellido, and D. Ruiz, “Highly efficient general method for sensitivity analysis of eigenvectors with repeated eigenvalues without passing through adjacent eigenvectors,” Int. J. Numer. Methods Eng., vol. 121, no. 20, p. nme.6442, Jun. 2020, doi: 10.1002/nme.6442.
[27] S. Noschese and L. Reichel, “Eigenvector sensitivity under general and structured perturbations of tridiagonal Toeplitz‐type matrices,” Numer. Linear Algebr. with Appl., vol. 26, no. 3, May 2019, doi: 10.1002/nla.2232.
[28] A. H.-D. Cheng, “Multiquadric and its shape parameter—A numerical investigation of error estimate, condition number, and round-off error by arbitrary precision computation,” Eng. Anal. Bound. Elem., vol. 36, no. 2, pp. 220–239, Feb. 2012, doi: 10.1016/j.enganabound.2011.07.008.
[29] J. H. Wilkinson, “Error analysis of floating-point computation,” Numer. Math., vol. 2, no. 1, pp. 319–340, Dec. 1960, doi: 10.1007/BF01386233.
[30] L. Page, S. Brin, R. Motwani, and T. Winograd, “The PageRank Citation Ranking: Bringing Order to the Web,” World Wide Web Internet Web Inf. Syst., vol. 54, no. 1999–66, pp. 1–17, 1998, doi: 10.1.1.31.1768.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
___________________________________________________________
International Journal of Advances in Intelligent Informatics
ISSN 2442-6571 (print) | 2548-3161 (online)
Organized by UAD and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
W: http://ijain.org
E: info@ijain.org (paper handling issues)
andri.pranolo.id@ieee.org (publication issues)
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0