IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v420y2022ics009630032100881x.html
   My bibliography  Save this article

Shifted power-GMRES method accelerated by extrapolation for solving PageRank with multiple damping factors

Author

Listed:
  • Shen, Zhao-Li
  • Su, Meng
  • Carpentieri, Bruno
  • Wen, Chun

Abstract

Starting from the seminal paper published by Brin and Page in 1998, the PageRank model has been extended to many fields far beyond search engine rankings, such as chemistry, biology, bioinformatics, social network analysis, to name a few. Due to the large dimension of PageRank problems, in the past decade or so, considerable research efforts have been devoted to their efficient solution especially for the difficult cases where the damping factors are close to 1. However, there exists few research work concerning about the solution of the case where several PageRank problems with the same network structure and various damping factors need to be solved. In this paper, we generalize the Power method to solving the PageRank problem with multiple damping factors. We demonstrate that the solution has almost the equative cost of solving the most difficult PageRank system of the sequence, and the residual vectors of the PageRank systems after running this method are collinear. Based upon these results, we develop a more efficient method that combines this Power method with the shifted GMRES method. For further accelerating the solving phase, we present a seed system choosing strategy combined with an extrapolation technique, and analyze their effect. Numerical experiments demonstrate the potential of the proposed iterative solver for accelerating realistic PageRank computations with multiple damping factors.

Suggested Citation

  • Shen, Zhao-Li & Su, Meng & Carpentieri, Bruno & Wen, Chun, 2022. "Shifted power-GMRES method accelerated by extrapolation for solving PageRank with multiple damping factors," Applied Mathematics and Computation, Elsevier, vol. 420(C).
    • Handle: RePEc:eee:apmaco:v:420:y:2022:i:c:s009630032100881x
    DOI: 10.1016/j.amc.2021.126799
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S009630032100881X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.amc.2021.126799?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Shen, Zhao-Li & Huang, Ting-Zhu & Carpentieri, Bruno & Gu, Xian-Ming & Wen, Chun, 2017. "An efficient elimination strategy for solving PageRank problems," Applied Mathematics and Computation, Elsevier, vol. 298(C), pages 111-122.
    2. Tian, Zhaolu & Liu, Yong & Zhang, Yan & Liu, Zhongyun & Tian, Maoyi, 2019. "The general inner-outer iteration method based on regular splittings for the PageRank problem," Applied Mathematics and Computation, Elsevier, vol. 356(C), pages 479-501.
    3. Massucci, Francesco Alessandro & Docampo, Domingo, 2019. "Measuring the academic reputation through citation networks via PageRank," Journal of Informetrics, Elsevier, vol. 13(1), pages 185-201.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Del Corso, Gianna M. & Romani, Francesco, 2019. "Adaptive nonnegative matrix factorization and measure comparisons for recommender systems," Applied Mathematics and Computation, Elsevier, vol. 354(C), pages 164-179.
    2. Alexander Kuchansky & Andrii Biloshchytskyi & Yurii Andrashko & Svitlana Biloshchytska & Adil Faizullin, 2022. "The Scientific Productivity of Collective Subjects Based on the Time-Weighted PageRank Method with Citation Intensity," Publications, MDPI, vol. 10(4), pages 1-17, October.
    3. Chen, Ying & Koch, Thorsten & Zakiyeva, Nazgul & Liu, Kailiang & Xu, Zhitong & Chen, Chun-houh & Nakano, Junji & Honda, Keisuke, 2023. "Article’s scientific prestige: Measuring the impact of individual articles in the web of science," Journal of Informetrics, Elsevier, vol. 17(1).
    4. Indra Budi & Yaniasih Yaniasih, 2023. "Understanding the meanings of citations using sentiment, role, and citation function classifications," Scientometrics, Springer;Akadémiai Kiadó, vol. 128(1), pages 735-759, January.
    5. Bai, Xiaomei & Zhang, Fuli & Liu, Jiaying & Xia, Feng, 2023. "Quantifying the impact of scientific collaboration and papers via motif-based heterogeneous networks," Journal of Informetrics, Elsevier, vol. 17(2).
    6. Zhang, Ronda J. & Ye, Fred Y., 2020. "Measuring similarity for clarifying layer difference in multiplex ad hoc duplex information networks," Journal of Informetrics, Elsevier, vol. 14(1).
    7. Xiaomei Bai & Fuli Zhang & Jinzhou Li & Zhong Xu & Zeeshan Patoli & Ivan Lee, 2021. "Quantifying scientific collaboration impact by exploiting collaboration-citation network," Scientometrics, Springer;Akadémiai Kiadó, vol. 126(9), pages 7993-8008, September.
    8. Cao, Huiying & Gao, Chao & Wang, Zhen, 2023. "Ranking academic institutions by means of institution–publication networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 629(C).
    9. Wang, Xiaoli & Liang, Wenting & Ye, Xuanting & Chen, Lingdi & Liu, Yun, 2024. "Disruptive development path measurement for emerging technologies based on the patent citation network," Journal of Informetrics, Elsevier, vol. 18(1).
    10. Zhang, Xinyuan & Xie, Qing & Song, Min, 2021. "Measuring the impact of novelty, bibliometric, and academic-network factors on citation count using a neural network," Journal of Informetrics, Elsevier, vol. 15(2).
    11. Aleja, David & Criado, Regino & García del Amo, Alejandro J. & Pérez, Ángel & Romance, Miguel, 2019. "Non-backtracking PageRank: From the classic model to hashimoto matrices," Chaos, Solitons & Fractals, Elsevier, vol. 126(C), pages 283-291.
    12. Tian, Zhaolu & Liu, Yong & Zhang, Yan & Liu, Zhongyun & Tian, Maoyi, 2019. "The general inner-outer iteration method based on regular splittings for the PageRank problem," Applied Mathematics and Computation, Elsevier, vol. 356(C), pages 479-501.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:apmaco:v:420:y:2022:i:c:s009630032100881x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.