IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i14p2521-d867103.html
   My bibliography  Save this article

Intrinsic Correlation with Betweenness Centrality and Distribution of Shortest Paths

Author

Listed:
  • Yelai Feng

    (College of Electronic Engineering, National University of Defense Technology, Hefei 230000, China
    College of Computer, National University of Defense Technology, Changsha 410000, China)

  • Huaixi Wang

    (College of Electronic Engineering, National University of Defense Technology, Hefei 230000, China)

  • Chao Chang

    (College of Electronic Engineering, National University of Defense Technology, Hefei 230000, China)

  • Hongyi Lu

    (College of Computer, National University of Defense Technology, Changsha 410000, China)

Abstract

Betweenness centrality evaluates the importance of nodes and edges in networks and is one of the most pivotal indices in complex network analysis; for example, it is widely used in centrality ordering, failure cascading modeling, and path planning. Existing algorithms are based on single-source shortest paths technology, which cannot show the change of betweenness centrality with the growth of paths, and prevents deep analysis. We propose a novel algorithm that calculates betweenness centrality hierarchically and accelerates computing via GPUs. Based on the novel algorithm, we find that the distribution of shortest path has an intrinsic correlation with betweenness centrality. Furthermore, we find that the betweenness centrality indices of some nodes are 0, but these nodes are not edge nodes, and they characterize critical significance in real networks. Experimental evidence shows that betweenness centrality is closely related to the distribution of the shortest paths.

Suggested Citation

  • Yelai Feng & Huaixi Wang & Chao Chang & Hongyi Lu, 2022. "Intrinsic Correlation with Betweenness Centrality and Distribution of Shortest Paths," Mathematics, MDPI, vol. 10(14), pages 1-18, July.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:14:p:2521-:d:867103
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/14/2521/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/14/2521/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Duncan J. Watts & Steven H. Strogatz, 1998. "Collective dynamics of ‘small-world’ networks," Nature, Nature, vol. 393(6684), pages 440-442, June.
    2. Shohei Tokito & Shigemi Kagawa & Tesshu Hanaka, 2022. "Hypothetical extraction, betweenness centrality, and supply chain complexity," Economic Systems Research, Taylor & Francis Journals, vol. 34(1), pages 111-128, January.
    3. Xing, Lizhi & Dong, Xianlei & Guan, Jun & Qiao, Xiaoyong, 2019. "Betweenness centrality for similarity-weight network and its application to measuring industrial sectors’ pivotability on the global value chain," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 516(C), pages 19-36.
    4. Xianyong Li & Ying Tang & Yajun Du & Yanjie Li, 2021. "Key Node Discovery Algorithm Based on Multiple Relationships and Multiple Features in Social Networks," Mathematical Problems in Engineering, Hindawi, vol. 2021, pages 1-12, October.
    5. Ding, Jie & Wen, Changyun & Li, Guoqi, 2017. "Key node selection in minimum-cost control of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 486(C), pages 251-261.
    6. Daniel Gómez & Javier Castro & Inmaculada Gutiérrez & Rosa Espínola, 2021. "A New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection," Mathematics, MDPI, vol. 9(21), pages 1-29, October.
    7. Leo Katz, 1953. "A new status index derived from sociometric analysis," Psychometrika, Springer;The Psychometric Society, vol. 18(1), pages 39-43, March.
    8. Dangalchev, Chavdar, 2006. "Residual closeness in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 365(2), pages 556-564.
    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. Alexey V. Yakovlev & Vladimir V. Alekseev & Maria V. Volchikhina & Sergey V. Petrenko, 2022. "A Combinatorial Model for Determining Information Loss in Organizational and Technical Systems," Mathematics, MDPI, vol. 10(19), pages 1-12, September.

    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. Lin, Dan & Wu, Jiajing & Xuan, Qi & Tse, Chi K., 2022. "Ethereum transaction tracking: Inferring evolution of transaction networks via link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 600(C).
    2. Lee, Yan-Li & Dong, Qiang & Zhou, Tao, 2021. "Link prediction via controlling the leading eigenvector," Applied Mathematics and Computation, Elsevier, vol. 411(C).
    3. Mishra, Shivansh & Singh, Shashank Sheshar & Kumar, Ajay & Biswas, Bhaskar, 2022. "ELP: Link prediction in social networks based on ego network perspective," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 605(C).
    4. Wang, Xiaojie & Su, Yanyuan & Zhao, Chengli & Yi, Dongyun, 2016. "Effective identification of multiple influential spreaders by DegreePunishment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 461(C), pages 238-247.
    5. Marcus Engsig & Alejandro Tejedor & Yamir Moreno & Efi Foufoula-Georgiou & Chaouki Kasmi, 2024. "DomiRank Centrality reveals structural fragility of complex networks via node dominance," Nature Communications, Nature, vol. 15(1), pages 1-12, December.
    6. Huan Wang & Chuang Ma & Han-Shuang Chen & Ying-Cheng Lai & Hai-Feng Zhang, 2022. "Full reconstruction of simplicial complexes from binary contagion and Ising data," Nature Communications, Nature, vol. 13(1), pages 1-10, December.
    7. Vinayak, & Raghuvanshi, Adarsh & kshitij, Avinash, 2023. "Signatures of capacity development through research collaborations in artificial intelligence and machine learning," Journal of Informetrics, Elsevier, vol. 17(1).
    8. Supriya Tiwari & Pallavi Basu, 2024. "Quasi-randomization tests for network interference," Papers 2403.16673, arXiv.org, revised Oct 2024.
    9. Anzhi Sheng & Qi Su & Aming Li & Long Wang & Joshua B. Plotkin, 2023. "Constructing temporal networks with bursty activity patterns," Nature Communications, Nature, vol. 14(1), pages 1-10, December.
    10. Thomas J. Sargent & John Stachurski, 2022. "Economic Networks: Theory and Computation," Papers 2203.11972, arXiv.org, revised Jul 2022.
    11. Karimi, Fatemeh & Lotfi, Shahriar & Izadkhah, Habib, 2021. "Community-guided link prediction in multiplex networks," Journal of Informetrics, Elsevier, vol. 15(4).
    12. D’Errico, Marco & Battiston, Stefano & Peltonen, Tuomas & Scheicher, Martin, 2018. "How does risk flow in the credit default swap market?," Journal of Financial Stability, Elsevier, vol. 35(C), pages 53-74.
    13. Samrachana Adhikari & Beau Dabbs, 2018. "Social Network Analysis in R: A Software Review," Journal of Educational and Behavioral Statistics, , vol. 43(2), pages 225-253, April.
    14. Liu, Xiaodong & Patacchini, Eleonora & Zenou, Yves & Lee, Lung-Fei, 2011. "Criminal Networks: Who is the Key Player?," Research Papers in Economics 2011:7, Stockholm University, Department of Economics.
    15. Wang, Xiaojie & Slamu, Wushour & Guo, Wenqiang & Wang, Sixiu & Ren, Yan, 2022. "A novel semi local measure of identifying influential nodes in complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 158(C).
    16. Agnieszka Rusinowska & Rudolf Berghammer & Harrie de Swart & Michel Grabisch, 2011. "Social networks: Prestige, centrality, and influence (Invited paper)," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) hal-00633859, HAL.
    17. Gabrielle Demange, 2018. "Contagion in Financial Networks: A Threat Index," Management Science, INFORMS, vol. 64(2), pages 955-970, February.
    18. Zhu, Qingyuan & Xu, Chengzhen & Pan, Yinghao & Wu, Jie, 2024. "Identifying critical transmission sectors, paths, and carbon communities for CO2 mitigation in global supply chains," Renewable and Sustainable Energy Reviews, Elsevier, vol. 191(C).
    19. Fazal Hayat & Daniele Ettore Otera, 2024. "Maximizing Closeness in Bipartite Networks: A Graph-Theoretic Analysis," Mathematics, MDPI, vol. 12(13), pages 1-13, June.
    20. Yao Hongxing & Lu Yunxia, 2017. "Analyzing the Potential Influence of Shanghai Stock Market Based on Link Prediction Method," Journal of Systems Science and Information, De Gruyter, vol. 5(5), pages 446-461, October.

    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:gam:jmathe:v:10:y:2022:i:14:p:2521-:d:867103. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.