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. 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. 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.
    3. 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.
    4. 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.
    5. 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.
    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 & 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).
    3. 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).

    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. Batac, Rene C. & Cirunay, Michelle T., 2022. "Shortest paths along urban road network peripheries," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 597(C).
    6. Yang, Chao & Chen, Zhuoran & Qian, Jianghai & Han, Dingding & Zhao, Kaidi, 2023. "Simultaneous improvement of multiple transportation performances on link-coupled networks by global dynamic routing," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 616(C).
    7. Guanwen Yin & Tianzi Liu & Yanbin Chen & Yiming Hou, 2022. "Disparity and Spatial Heterogeneity of the Correlation between Street Centrality and Land Use Intensity in Jinan, China," IJERPH, MDPI, vol. 19(23), pages 1-23, November.
    8. Boeing, Geoff, 2017. "OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks," SocArXiv q86sd, Center for Open Science.
    9. 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.
    10. Xue Jiang & Han Zhang & Xiongwen Quan & Zhandong Liu & Yanbin Yin, 2017. "Disease-related gene module detection based on a multi-label propagation clustering algorithm," PLOS ONE, Public Library of Science, vol. 12(5), pages 1-17, May.
    11. Blagus, Neli & Šubelj, Lovro & Bajec, Marko, 2012. "Self-similar scaling of density in complex real-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(8), pages 2794-2802.
    12. Xiaokun Su & Chenrouyu Zheng & Yefei Yang & Yafei Yang & Wen Zhao & Yue Yu, 2022. "Spatial Structure and Development Patterns of Urban Traffic Flow Network in Less Developed Areas: A Sustainable Development Perspective," Sustainability, MDPI, vol. 14(13), pages 1-18, July.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. Li, Zhitao & Tang, Jinjun & Zhao, Chuyun & Gao, Fan, 2023. "Improved centrality measure based on the adapted PageRank algorithm for urban transportation multiplex networks," Chaos, Solitons & Fractals, Elsevier, vol. 167(C).
    18. Sergio Porta & Vito Latora & Fahui Wang & Salvador Rueda & Emanuele Strano & Salvatore Scellato & Alessio Cardillo & Eugenio Belli & Francisco CÃ rdenas & Berta Cormenzana & Laura Latora, 2012. "Street Centrality and the Location of Economic Activities in Barcelona," Urban Studies, Urban Studies Journal Limited, vol. 49(7), pages 1471-1488, May.
    19. Karolina Dudzic-Gyurkovich, 2023. "Study of Centrality Measures in the Network of Green Spaces in the City of Krakow," Sustainability, MDPI, vol. 15(18), pages 1-30, September.
    20. Feng, Huifang & Bai, Fengshan & Xu, Youji, 2019. "Identification of critical roads in urban transportation network based on GPS trajectory data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 535(C).

    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.