IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0053095.html
   My bibliography  Save this article

Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks

Author

Listed:
  • Mahendra Piraveenan
  • Mikhail Prokopenko
  • Liaquat Hossain

Abstract

A number of centrality measures are available to determine the relative importance of a node in a complex network, and betweenness is prominent among them. However, the existing centrality measures are not adequate in network percolation scenarios (such as during infection transmission in a social network of individuals, spreading of computer viruses on computer networks, or transmission of disease over a network of towns) because they do not account for the changing percolation states of individual nodes. We propose a new measure, percolation centrality, that quantifies relative impact of nodes based on their topological connectivity, as well as their percolation states. The measure can be extended to include random walk based definitions, and its computational complexity is shown to be of the same order as that of betweenness centrality. We demonstrate the usage of percolation centrality by applying it to a canonical network as well as simulated and real world scale-free and random networks.

Suggested Citation

  • Mahendra Piraveenan & Mikhail Prokopenko & Liaquat Hossain, 2013. "Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks," PLOS ONE, Public Library of Science, vol. 8(1), pages 1-14, January.
    • Handle: RePEc:plo:pone00:0053095
    DOI: 10.1371/journal.pone.0053095
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0053095
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0053095&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0053095?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
    ---><---

    References listed on IDEAS

    as
    1. Barabási, Albert-László & Albert, Réka & Jeong, Hawoong, 2000. "Scale-free characteristics of random networks: the topology of the world-wide web," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 281(1), pages 69-77.
    2. Gert Sabidussi, 1966. "The centrality index of a graph," Psychometrika, Springer;The Psychometric Society, vol. 31(4), pages 581-603, December.
    3. Dorogovtsev, S.N. & Mendes, J.F.F., 2003. "Evolution of Networks: From Biological Nets to the Internet and WWW," OUP Catalogue, Oxford University Press, number 9780198515906.
    4. M. E. J. Newman & D. J. Watts, 1999. "Scaling and Percolation in the Small-World Network Model," Working Papers 99-05-034, Santa Fe Institute.
    5. Cristopher Moore & M. E. J. Newman, 2000. "Epidemics and Percolation in Small-World Networks," Working Papers 00-01-002, Santa Fe Institute.
    6. R. Kinney & P. Crucitti & R. Albert & V. Latora, 2005. "Modeling cascading failures in the North American power grid," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 46(1), pages 101-107, July.
    7. M. Piraveenan & M. Prokopenko & A. Y. Zomaya, 2009. "Assortativeness and information in scale-free networks," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 67(3), pages 291-300, February.
    8. M. Piraveenan & M. Prokopenko & A. Y. Zomaya, 2009. "Local assortativity and growth of Internet," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 70(2), pages 275-285, July.
    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. Anita Mezzetti & Loic Mar'echal & Dimitri Percia David & William Lacube & S'ebastien Gillard & Michael Tsesmelis & Thomas Maillart & Alain Mermoud, 2022. "TechRank," Papers 2210.07824, arXiv.org.
    2. Mahdi Jalili & Ali Salehzadeh-Yazdi & Yazdan Asgari & Seyed Shahriar Arab & Marjan Yaghmaie & Ardeshir Ghavamzadeh & Kamran Alimoghaddam, 2015. "CentiServer: A Comprehensive Resource, Web-Based Application and R Package for Centrality Analysis," PLOS ONE, Public Library of Science, vol. 10(11), pages 1-8, November.
    3. Mira A. Kantemirova & Mira A. Kantemirova & Zaur L. Dzakoev & Zara R. Alikova & Sergei R. Chedgemov & Sergei R. Chedgemov & Zarina V. Soskieva & Zarina V. Soskieva, 2018. "Percolation approach to simulation of a sustainable network economy structure," Entrepreneurship and Sustainability Issues, VsI Entrepreneurship and Sustainability Center, vol. 5(3), pages 502-513, March.
    4. Mira A. Kantemirova & Zaur L. Dzakoev & Zara R. Alikova & Sergei R. Chedgemov & Zarina V. Soskieva, 2018. "Percolation approach to simulation of a sustainable network economy structure," Post-Print hal-01773587, HAL.
    5. Sheryl Le Chang & Mahendra Piraveenan & Mikhail Prokopenko, 2019. "The Effects of Imitation Dynamics on Vaccination Behaviours in SIR-Network Model," IJERPH, MDPI, vol. 16(14), pages 1-31, July.
    6. Víctor Martínez & Fernando Berzal & Juan-Carlos Cubero, 2019. "NOESIS: A Framework for Complex Network Data Analysis," Complexity, Hindawi, vol. 2019, pages 1-14, October.
    7. Kovalenko, K. & Romance, M. & Vasilyeva, E. & Aleja, D. & Criado, R. & Musatov, D. & Raigorodskii, A.M. & Flores, J. & Samoylenko, I. & Alfaro-Bittner, K. & Perc, M. & Boccaletti, S., 2022. "Vector centrality in hypergraphs," Chaos, Solitons & Fractals, Elsevier, vol. 162(C).
    8. Belik, Ivan & Jörnsten, Kurt, 2014. "Centrality Computation in Weighted Networks Based on Edge-Splitting Procedure," Discussion Papers 2014/40, Norwegian School of Economics, Department of Business and Management Science.
    9. King, Maia, 2020. "The probabilities of node-to-node diffusion in fixed networks," SocArXiv dfq8y, Center for Open Science.
    10. Nasirian, Farzaneh & Mahdavi Pajouh, Foad & Balasundaram, Balabhaskar, 2020. "Detecting a most closeness-central clique in complex networks," European Journal of Operational Research, Elsevier, vol. 283(2), pages 461-475.
    11. Ullah, Farman & Lee, Sungchang, 2017. "Identification of influential nodes based on temporal-aware modeling of multi-hop neighbor interactions for influence spread maximization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 486(C), pages 968-985.
    12. Feng, Yuhao & Wu, Shufan & Wu, Peixin & Su, Shiliang & Weng, Min & Bian, Meng, 2018. "Spatiotemporal characterization of megaregional poly-centrality: Evidence for new urban hypotheses and implications for polycentric policies," Land Use Policy, Elsevier, vol. 77(C), pages 712-731.
    13. Elhem Ben Fatma & Ezzeddine Ben Mohamed & Léo-Paul Dana & Sami Boudabbous, 2021. "Does entrepreneurs’ psychology affect their business venture success? Empirical findings from North Africa," International Entrepreneurship and Management Journal, Springer, vol. 17(2), pages 921-962, June.
    14. Zádor, Zsófia & Zhu, Zhen & Smith, Matthew & Gorgoni, Sara, 2022. "A weighted and normalized Gould–Fernandez brokerage measure," Greenwich Papers in Political Economy 37794, University of Greenwich, Greenwich Political Economy Research Centre.

    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. Marc Barthélémy & Michele Campagna & Alessandro Chessa & Andrea De Montis & Alessandro Vespignani, 2005. "Emergent topological and dynamical properties of a real inter-municipal commuting network - perspectives for policy-making and planning," ERSA conference papers ersa05p607, European Regional Science Association.
    2. Floortje Alkemade & Carolina Castaldi, 2005. "Strategies for the Diffusion of Innovations on Social Networks," Computational Economics, Springer;Society for Computational Economics, vol. 25(1), pages 3-23, February.
    3. I. Vieira & R. Cheng & P. Harper & V. Senna, 2010. "Small world network models of the dynamics of HIV infection," Annals of Operations Research, Springer, vol. 178(1), pages 173-200, July.
    4. Huang, Wei & Chen, Shengyong & Wang, Wanliang, 2014. "Navigation in spatial networks: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 393(C), pages 132-154.
    5. Hüseyin İkizler, 2019. "Contagion of network products in small-world networks," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 14(4), pages 789-809, December.
    6. Kumar, Ajay & Swarnakar, Pradip & Jaiswal, Kamya & Kurele, Ritika, 2020. "SMIR model for controlling the spread of information in social networking sites," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 540(C).
    7. Zhong, Li-Xin & Xu, Wen-Juan & Chen, Rong-Da & Qiu, Tian & Shi, Yong-Dong & Zhong, Chen-Yang, 2015. "Coupled effects of local movement and global interaction on contagion," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 436(C), pages 482-491.
    8. Zhang, Xiaohang & Cui, Huiyuan & Zhu, Ji & Du, Yu & Wang, Qi & Shi, Wenhua, 2017. "Measuring the dissimilarity of multiplex networks: An empirical study of international trade networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 467(C), pages 380-394.
    9. Cristopher Moore & M. E. J. Newman, 2000. "Exact Solution of Site and Bond Percolation on Small-World Networks," Working Papers 00-01-007, Santa Fe Institute.
    10. Silva, S.L. & Ferreira, J.A. & Martins, M.L., 2007. "Epidemic spreading in a scale-free network of regular lattices," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 377(2), pages 689-697.
    11. Jaideep Ghosh & Avinash Kshitij, 2017. "Examining the Emergence of Large-scale Structures in Collaboration Networks: Methods in Sociological Analysis," Sociological Methods & Research, , vol. 46(4), pages 821-863, November.
    12. Yang, Jianmei & Zhuang, Dong & Xie, Weicong & Chen, Guangrong, 2013. "A study of design approach of spreading schemes for viral marketing based on human dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(24), pages 6494-6505.
    13. Scabini, Leonardo F.S. & Ribas, Lucas C. & Neiva, Mariane B. & Junior, Altamir G.B. & Farfán, Alex J.F. & Bruno, Odemir M., 2021. "Social interaction layers in complex networks for the dynamical epidemic modeling of COVID-19 in Brazil," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 564(C).
    14. Jaideep Ghosh & Avinash Kshitij & Sandeep Kadyan, 2015. "Functional information characteristics of large-scale research collaboration: network measures and implications," Scientometrics, Springer;Akadémiai Kiadó, vol. 102(2), pages 1207-1239, February.
    15. De Masi, G. & Giovannetti, G. & Ricchiuti, G., 2013. "Network analysis to detect common strategies in Italian foreign direct investment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(5), pages 1202-1214.
    16. Zhao, Star X. & Rousseau, Ronald & Ye, Fred Y., 2011. "h-Degree as a basic measure in weighted networks," Journal of Informetrics, Elsevier, vol. 5(4), pages 668-677.
    17. Fogel, Kathy & Jandik, Tomas & McCumber, William R., 2018. "CFO social capital and private debt," Journal of Corporate Finance, Elsevier, vol. 52(C), pages 28-52.
    18. Champagne, Claudia, 2014. "The international syndicated loan market network: An “unholy trinity”?," Global Finance Journal, Elsevier, vol. 25(2), pages 148-168.
    19. Ya-Chun Gao & Zong-Wen Wei & Bing-Hong Wang, 2013. "Dynamic Evolution Of Financial Network And Its Relation To Economic Crises," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 24(02), pages 1-10.
    20. 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).

    More about this item

    Statistics

    Access and download statistics

    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:plo:pone00:0053095. 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: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    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.