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. 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.
    7. 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.
    8. 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).
    9. Gabrielle Demange, 2018. "Contagion in Financial Networks: A Threat Index," Management Science, INFORMS, vol. 64(2), pages 955-970, February.
    10. Fazal Hayat & Daniele Ettore Otera, 2024. "Maximizing Closeness in Bipartite Networks: A Graph-Theoretic Analysis," Mathematics, MDPI, vol. 12(13), pages 1-13, June.
    11. Zhepeng Li & Xiao Fang & Xue Bai & Olivia R. Liu Sheng, 2017. "Utility-Based Link Recommendation for Online Social Networks," Management Science, INFORMS, vol. 63(6), pages 1938-1952, June.
    12. Ferreira, D.S.R. & Ribeiro, J. & Oliveira, P.S.L. & Pimenta, A.R. & Freitas, R.P. & Dutra, R.S. & Papa, A.R.R. & Mendes, J.F.F., 2022. "Spatiotemporal analysis of earthquake occurrence in synthetic and worldwide data," Chaos, Solitons & Fractals, Elsevier, vol. 165(P2).
    13. Qinghu Liao & Wenwen Dong & Boxin Zhao, 2023. "A New Strategy to Solve “the Tragedy of the Commons” in Sustainable Grassland Ecological Compensation: Experience from Inner Mongolia, China," Sustainability, MDPI, vol. 15(12), pages 1-24, June.
    14. Dequiedt, Vianney & Zenou, Yves, 2017. "Local and consistent centrality measures in parameterized networks," Mathematical Social Sciences, Elsevier, vol. 88(C), pages 28-36.
    15. Luca Colombo & Paola Labrecciosa & Agnieszka Rusinowska, 2025. "A dynamic analysis of criminal networks," Post-Print hal-04850675, HAL.
    16. Jianhong Chen & Hongcai Ma & Shan Yang, 2023. "SEIOR Rumor Propagation Model Considering Hesitating Mechanism and Different Rumor-Refuting Ways in Complex Networks," Mathematics, MDPI, vol. 11(2), pages 1-22, January.
    17. Pawanesh Pawanesh & Charu Sharma & Niteesh Sahni, 2025. "Analyzing Communicability and Connectivity in the Indian Stock Market During Crises," Papers 2502.08242, arXiv.org.
    18. ,, 2014. "A ranking method based on handicaps," Theoretical Economics, Econometric Society, vol. 9(3), September.
    19. Ernest Liu & Aleh Tsyvinski, 2021. "Dynamical Structure and Spectral Properties of Input-Output Networks," Working Papers 2021-13, Princeton University. Economics Department..
    20. Daniel Reisinger & Fabian Tschofenig & Raven Adam & Marie Lisa Kogler & Manfred Füllsack & Fabian Veider & Georg Jäger, 2024. "Patterns of stability in complex contagions," Journal of Computational Social Science, Springer, vol. 7(2), pages 1895-1911, 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.