IDEAS home Printed from https://ideas.repec.org/a/eee/chsofr/v126y2019icp283-291.html
   My bibliography  Save this article

Non-backtracking PageRank: From the classic model to hashimoto matrices

Author

Listed:
  • Aleja, David
  • Criado, Regino
  • García del Amo, Alejandro J.
  • Pérez, Ángel
  • Romance, Miguel

Abstract

Non-backtracking centrality was introduced as a way to correct what may be understood as a deficiency in the eigenvector centrality, since the eigenvector centrality in a network can be artificially increased in high-degree nodes (hubs) because a hub is central because its neighbors are central, but these, in turn, are central just because they are hub neighbors. We define the non-backtracking PageRank as a new measure modifying the well-known classic PageRank in order to avoid the possibility of the random walker returning to the node immediately visited (non-backtracking walk). But, as we show, this measure presents a gap and a remarkable difference between the limit of “no penalty for return trips” and the direct calculation of the non-backtracking PageRank. Also, as it is shown in the applications presented, in certain cases this new measure produces notable variations with respect to the classifications obtained by the classic PageRank.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:chsofr:v:126:y:2019:i:c:p:283-291
    DOI: 10.1016/j.chaos.2019.06.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0960077919302292
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.chaos.2019.06.017?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. Agryzkov, Taras & Tortosa, Leandro & Vicent, Jose F., 2016. "New highlights and a new centrality measure based on the Adapted PageRank Algorithm for urban networks," Applied Mathematics and Computation, Elsevier, vol. 291(C), pages 14-29.
    2. 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.
    3. Porta, Sergio & Crucitti, Paolo & Latora, Vito, 2006. "The network analysis of urban streets: A dual approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 369(2), pages 853-866.
    4. L. Šubelj & M. Bajec, 2011. "Robust network community detection using balanced propagation," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 81(3), pages 353-362, June.
    5. Omodei, Elisa & De Domenico, Manlio & Arenas, Alex, 2017. "Evaluating the impact of interdisciplinary research: A multilayer network approach," Network Science, Cambridge University Press, vol. 5(2), pages 235-246, June.
    6. Romance, Miguel & Solá, Luis & Flores, Julio & García, Esther & García del Amo, Alejandro & Criado, Regino, 2015. "A Perron–Frobenius theory for block matrices associated to a multiplex network," Chaos, Solitons & Fractals, Elsevier, vol. 72(C), pages 77-89.
    7. Scholz, Michael & Pfeiffer, Jella & Rothlauf, Franz, 2017. "Using PageRank for non-personalized default rankings in dynamic markets," European Journal of Operational Research, Elsevier, vol. 260(1), pages 388-401.
    8. Manlio De Domenico & Albert Solé-Ribalta & Elisa Omodei & Sergio Gómez & Alex Arenas, 2015. "Ranking in interconnected multilayer networks reveals versatile nodes," Nature Communications, Nature, vol. 6(1), pages 1-6, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Li, Hanwen & Shang, Qiuyan & Deng, Yong, 2021. "A generalized gravity model for influential spreaders identification in complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 143(C).
    2. Criado-Alonso, Ángeles & Battaner-Moro, Elena & Aleja, David & Romance, Miguel & Criado, Regino, 2021. "Enriched line graph: A new structure for searching language collocations," Chaos, Solitons & Fractals, Elsevier, vol. 142(C).
    3. Zhang, Renquan & Wei, Ting & Sun, Yifan & Pei, Sen, 2024. "Influence maximization based on simplicial contagion models," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 645(C).
    4. Criado-Alonso, Ángeles & Aleja, David & Romance, Miguel & Criado, Regino, 2022. "Derivative of a hypergraph as a tool for linguistic pattern analysis," Chaos, Solitons & Fractals, Elsevier, vol. 163(C).

    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. Higham, Kyle & Contisciani, Martina & De Bacco, Caterina, 2022. "Multilayer patent citation networks: A comprehensive analytical framework for studying explicit technological relationships," Technological Forecasting and Social Change, Elsevier, vol. 179(C).
    2. Mirco Nanni & Leandro Tortosa & José F Vicent & Gevorg Yeghikyan, 2020. "Ranking places in attributed temporal urban mobility networks," PLOS ONE, Public Library of Science, vol. 15(10), pages 1-25, October.
    3. 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.
    4. Jiang, Bin, 2007. "A topological pattern of urban street networks: Universality and peculiarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 384(2), pages 647-655.
    5. Boeing, Geoff, 2017. "OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks," SocArXiv q86sd, Center for Open Science.
    6. Antoaneta Serguieva & David Bholat, 2017. "Multichannel contagion vs stabilisation in multiple interconnected financial markets," IFC Bulletins chapters, in: Bank for International Settlements (ed.), Statistical implications of the new financial landscape, volume 43, Bank for International Settlements.
    7. Zhou, Yaoming & Wang, Junwei, 2018. "Efficiency of complex networks under failures and attacks: A percolation approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 658-664.
    8. Lordan, Oriol & Sallan, Jose M., 2019. "Core and critical cities of global region airport networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 513(C), pages 724-733.
    9. Chen, Zhen-Yu & Fan, Zhi-Ping & Sun, Minghe, 2021. "Tensorial graph learning for link prediction in generalized heterogeneous networks," European Journal of Operational Research, Elsevier, vol. 290(1), pages 219-234.
    10. Wagner, Roy, 2008. "On the metric, topological and functional structures of urban networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(8), pages 2120-2132.
    11. Zhang, Tong & Zeng, Zhe & Jia, Tao & Li, Jing, 2016. "Examining the amenability of urban street networks for locating facilities," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 457(C), pages 469-479.
    12. 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).
    13. Lin, Ting (Grace) & Xia, Jianhong (Cecilia) & Robinson, Todd P. & Goulias, Konstadinos G. & Church, Richard L. & Olaru, Doina & Tapin, John & Han, Renlong, 2014. "Spatial analysis of access to and accessibility surrounding train stations: a case study of accessibility for the elderly in Perth, Western Australia," Journal of Transport Geography, Elsevier, vol. 39(C), pages 111-120.
    14. Geoff Boeing, 2020. "Urban Street Network Analysis in a Computational Notebook," REGION, European Regional Science Association, vol. 7, pages 39-51.
    15. Geoff Boeing, 2020. "A multi-scale analysis of 27,000 urban street networks: Every US city, town, urbanized area, and Zillow neighborhood," Environment and Planning B, , vol. 47(4), pages 590-608, May.
    16. Saucan, Emil & Sreejith, R.P. & Vivek-Ananth, R.P. & Jost, Jürgen & Samal, Areejit, 2019. "Discrete Ricci curvatures for directed networks," Chaos, Solitons & Fractals, Elsevier, vol. 118(C), pages 347-360.
    17. Zareie, Ahmad & Sheikhahmadi, Amir, 2019. "EHC: Extended H-index Centrality measure for identification of users’ spreading influence in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 141-155.
    18. Omer Dogan & Jaewon Han & Sugie Lee, 2020. "Analysis of Large-Scale Residential Development on Walking Environments in Surrounding Neighborhoods: A Before-and-After Comparison of Apartment Complex Developments in Seoul, Korea," Sustainability, MDPI, vol. 12(18), pages 1-17, September.
    19. Wang, Shiguang & Zheng, Lili & Yu, Dexin, 2017. "The improved degree of urban road traffic network: A case study of Xiamen, China," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 469(C), pages 256-264.
    20. Zhang, Ting & Zhang, Kun & Lv, Laishui & Bardou, Dalal, 2019. "Co-Ranking for nodes, layers and timestamps in multilayer temporal networks," Chaos, Solitons & Fractals, Elsevier, vol. 125(C), pages 88-96.

    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:chsofr:v:126:y:2019:i:c:p:283-291. 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: Thayer, Thomas R. (email available below). General contact details of provider: https://www.journals.elsevier.com/chaos-solitons-and-fractals .

    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.