IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v538y2020ics0378437119316279.html
   My bibliography  Save this article

Critical node detection problem for complex network in undirected weighted networks

Author

Listed:
  • Chen, Wei
  • Jiang, Manrui
  • Jiang, Cheng
  • Zhang, Jun

Abstract

Detection of critical nodes in complex networks has recently received extensive attention. Currently, studies of the critical nodes problem (CNP) mainly focus on two problem types: “critical nodes problem/positive” (CNP-Pos) and “critical nodes problem/negative” (CNP-Neg). However, to the best of our knowledge, few studies have been conducted on CNP-Neg for weighed networks. In this paper, we investigate CNP-Neg in undirected weighted networks. We first propose a novel metric DFW to evaluate network fragmentation. Then, we formulate a new nonconvex mixed-integer quadratic programming model, named MIQPM, that aims to simultaneously minimize pairwise connectivity and maximize the weights between the nodes. After that, a general greedy algorithm is employed to solve the corresponding optimization problem. Finally, comparison experiments are carried out for several synthetic networks and four real-world networks to demonstrate the effectiveness of the proposed approaches.

Suggested Citation

  • Chen, Wei & Jiang, Manrui & Jiang, Cheng & Zhang, Jun, 2020. "Critical node detection problem for complex network in undirected weighted networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 538(C).
    • Handle: RePEc:eee:phsmap:v:538:y:2020:i:c:s0378437119316279
    DOI: 10.1016/j.physa.2019.122862
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437119316279
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2019.122862?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. Jiang, Cheng & Liu, Zhonghua & Wang, Juyun & Yu, Hua & Guo, Xiaoling, 2017. "An optimal approach for the critical node problem using semidefinite programming," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 471(C), pages 315-324.
    2. R. Mantegna, 1999. "Hierarchical structure in financial markets," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 11(1), pages 193-197, September.
    3. Crucitti, Paolo & Latora, Vito & Marchiori, Massimo & Rapisarda, Andrea, 2004. "Error and attack tolerance of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 340(1), pages 388-394.
    4. Maarten Oosten & Jeroen H. G. C. Rutten & Frits C. R. Spieksma, 2007. "Disconnecting graphs by removing vertices: a polyhedral approach," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 61(1), pages 35-60, February.
    5. Erricos J. Kontoghiorghes & Berç Rustem & Peter Winker (ed.), 2008. "Computational Methods in Financial Engineering," Springer Books, Springer, number 978-3-540-77958-2, November.
    6. Marco Di Summa & Andrea Grosso & Marco Locatelli, 2012. "Branch and cut algorithms for detecting critical nodes in undirected graphs," Computational Optimization and Applications, Springer, vol. 53(3), pages 649-680, December.
    7. Bernardetta Addis & Roberto Aringhieri & Andrea Grosso & Pierre Hosteins, 2016. "Hybrid constructive heuristics for the critical node problem," Annals of Operations Research, Springer, vol. 238(1), pages 637-649, March.
    8. Anna Nagurney & Qiang Qiang, 2008. "Identification of Critical Nodes and Links in Financial Networks with Intermediation and Electronic Transactions," Springer Books, in: Erricos J. Kontoghiorghes & Berç Rustem & Peter Winker (ed.), Computational Methods in Financial Engineering, pages 273-297, Springer.
    9. Jose L. Walteros & Panos M. Pardalos, 2012. "Selected Topics in Critical Element Detection," Springer Optimization and Its Applications, in: Nicholas J. Daras (ed.), Applications of Mathematics and Informatics in Military Science, edition 127, chapter 0, pages 9-26, Springer.
    10. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2014. "An integer programming framework for critical elements detection in graphs," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 233-273, July.
    11. Crucitti, Paolo & Latora, Vito & Marchiori, Massimo & Rapisarda, Andrea, 2003. "Efficiency of scale-free networks: error and attack tolerance," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 320(C), pages 622-642.
    12. Bernardetta Addis & Roberto Aringhieri & Andrea Grosso & Pierre Hosteins, 2016. "Hybrid constructive heuristics for the critical node problem," Annals of Operations Research, Springer, vol. 238(1), pages 637-649, March.
    13. Stephen P. Borgatti, 2006. "Identifying sets of key players in a social network," Computational and Mathematical Organization Theory, Springer, vol. 12(1), pages 21-34, April.
    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. Wu, Gongyu & Li, Meiyan & Li, Zhaojun Steven, 2021. "A Gene Importance based Evolutionary Algorithm (GIEA) for identifying critical nodes in Cyber–Physical Power Systems," Reliability Engineering and System Safety, Elsevier, vol. 214(C).
    2. Meng, Yangyang & Tian, Xiangliang & Li, Zhongwen & Zhou, Wei & Zhou, Zhijie & Zhong, Maohua, 2020. "Exploring node importance evolution of weighted complex networks in urban rail transit," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 558(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. Marco Di Summa & Syed Md Omar Faruk, 2023. "Critical node/edge detection problems on trees," 4OR, Springer, vol. 21(3), pages 439-455, September.
    2. Ventresca, Mario & Harrison, Kyle Robert & Ombuki-Berman, Beatrice M., 2018. "The bi-objective critical node detection problem," European Journal of Operational Research, Elsevier, vol. 265(3), pages 895-908.
    3. Hosseinali Salemi & Austin Buchanan, 2022. "Solving the Distance-Based Critical Node Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1309-1326, May.
    4. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2014. "An integer programming framework for critical elements detection in graphs," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 233-273, July.
    5. Zhou, Yangming & Wang, Gezi & Hao, Jin-Kao & Geng, Na & Jiang, Zhibin, 2023. "A fast tri-individual memetic search approach for the distance-based critical node problem," European Journal of Operational Research, Elsevier, vol. 308(2), pages 540-554.
    6. Jiang, Cheng & Liu, Zhonghua, 2019. "Detecting multiple key players under the positive effect by using a distance-based connectivity approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 534(C).
    7. T. N. Dinh & M. T. Thai & H. T. Nguyen, 2014. "Bound and exact methods for assessing link vulnerability in complex networks," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 3-24, July.
    8. Bernardetta Addis & Roberto Aringhieri & Andrea Grosso & Pierre Hosteins, 2016. "Hybrid constructive heuristics for the critical node problem," Annals of Operations Research, Springer, vol. 238(1), pages 637-649, March.
    9. Ningji Wei & Jose L. Walteros & Foad Mahdavi Pajouh, 2021. "Integer Programming Formulations for Minimum Spanning Tree Interdiction," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1461-1480, October.
    10. Hooshmand, F. & Mirarabrazi, F. & MirHassani, S.A., 2020. "Efficient Benders decomposition for distance-based critical node detection problem," Omega, Elsevier, vol. 93(C).
    11. Bernardetta Addis & Roberto Aringhieri & Andrea Grosso & Pierre Hosteins, 2016. "Hybrid constructive heuristics for the critical node problem," Annals of Operations Research, Springer, vol. 238(1), pages 637-649, March.
    12. Alexander Veremyev & Konstantin Pavlikov & Eduardo L. Pasiliao & My T. Thai & Vladimir Boginski, 2019. "Critical nodes in interdependent networks with deterministic and probabilistic cascading failures," Journal of Global Optimization, Springer, vol. 74(4), pages 803-838, August.
    13. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2019. "Finding Critical Links for Closeness Centrality," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 367-389, April.
    14. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    15. César Yajure & Darihelen Montilla & Jose Emmanuel Ramirez-Marquez & Claudio M Rocco S, 2013. "Network vulnerability assessment via bi-objective optimization with a fragmentation approach as proxy," Journal of Risk and Reliability, , vol. 227(6), pages 576-585, December.
    16. Wei, Ningji & Walteros, Jose L., 2022. "Integer programming methods for solving binary interdiction games," European Journal of Operational Research, Elsevier, vol. 302(2), pages 456-469.
    17. Kashyap, G. & Ambika, G., 2019. "Link deletion in directed complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 631-643.
    18. Zhong, Haonan & Mahdavi Pajouh, Foad & A． Prokopyev, Oleg, 2023. "On designing networks resilient to clique blockers," European Journal of Operational Research, Elsevier, vol. 307(1), pages 20-32.
    19. Jin Qin & Yuxin He & Linglin Ni, 2014. "Quantitative Efficiency Evaluation Method for Transportation Networks," Sustainability, MDPI, vol. 6(12), pages 1-15, November.
    20. Jiang, Cheng & Liu, Zhonghua & Wang, Juyun & Yu, Hua & Guo, Xiaoling, 2017. "An optimal approach for the critical node problem using semidefinite programming," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 471(C), pages 315-324.

    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:phsmap:v:538:y:2020:i:c:s0378437119316279. 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: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    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.