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

Vulnerability of complex networks under path-based attacks

Author

Listed:
  • Pu, Cun-Lai
  • Cui, Wei

Abstract

We investigate vulnerability of complex networks including model networks and real-world networks subject to path-based attacks. Specifically, we remove approximately the longest simple path from a network iteratively until there are no paths left in the network. We propose two algorithms, the random augmenting approach (RPA) and the Hamilton-path based approach (HPA), for finding the approximately longest simple path in a network. Results demonstrate that steps of longest-path attacks increase with network density linearly for random networks, while exponentially increasing for scale-free networks. The more homogeneous the degree distribution is, the more fragile the network, which is different from the previous results of node or edge attacks. HPA is generally more efficient than RPA in the longest-path attacks of complex networks. These findings further help us understand the vulnerability of complex systems, better protect complex systems, and design more tolerant complex systems.

Suggested Citation

  • Pu, Cun-Lai & Cui, Wei, 2015. "Vulnerability of complex networks under path-based attacks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 622-629.
  • Handle: RePEc:eee:phsmap:v:419:y:2015:i:c:p:622-629
    DOI: 10.1016/j.physa.2014.10.038
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437114008760
    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.2014.10.038?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. Karimi, Fariba & Holme, Petter, 2013. "Threshold model of cascades in empirical temporal networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(16), pages 3476-3483.
    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. Tian, Meng & Dong, Zhengcheng & Wang, Xianpei, 2021. "Reinforcement learning approach for robustness analysis of complex networks with incomplete information," Chaos, Solitons & Fractals, Elsevier, vol. 144(C).
    2. Fei Ma & Fei Liu & Kum Fai Yuen & Polin Lai & Qipeng Sun & Xiaodan Li, 2019. "Cascading Failures and Vulnerability Evolution in Bus–Metro Complex Bilayer Networks under Rainstorm Weather Conditions," IJERPH, MDPI, vol. 16(3), pages 1-30, January.
    3. Abedi, Amin & Gaudard, Ludovic & Romerio, Franco, 2019. "Review of major approaches to analyze vulnerability in power system," Reliability Engineering and System Safety, Elsevier, vol. 183(C), pages 153-172.
    4. Alexander Shiroky & Andrey Kalashnikov, 2023. "Influence of the Internal Structure on the Integral Risk of a Complex System on the Example of the Risk Minimization Problem in a “Star” Type Structure," Mathematics, MDPI, vol. 11(4), pages 1-18, February.
    5. Zhang, Weitong & Zhang, Rui & Shang, Ronghua & Li, Juanfei & Jiao, Licheng, 2019. "Application of natural computation inspired method in community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 515(C), pages 130-150.
    6. Wang, Jianwei & Wang, Siyuan & Wang, Ziwei, 2022. "Robustness of spontaneous cascading dynamics driven by reachable area," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 585(C).
    7. Lekha, Divya Sindhu & Balakrishnan, Kannan, 2020. "Central attacks in complex networks: A revisit with new fallback strategy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 549(C).
    8. Zhou, Hong-Li & Zhang, Xiao-Dong, 2018. "Dynamic robustness of knowledge collaboration network of open source product development community," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 490(C), pages 601-612.
    9. Kashin Sugishita & Yasuo Asakura, 2021. "Vulnerability studies in the fields of transportation and complex networks: a citation network analysis," Public Transport, Springer, vol. 13(1), pages 1-34, March.
    10. Wang, Haibo, 2024. "Assessing resilience to systemic risks across interbank credit networks using linkage-leverage analysis: Evidence from Japan," International Review of Financial Analysis, Elsevier, vol. 94(C).
    11. Viljoen, Nadia M. & Joubert, Johan W., 2016. "The vulnerability of the global container shipping network to targeted link disruption," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 462(C), pages 396-409.
    12. Zhou, Hongli & Zhang, Xiaodong & Hu, Yang, 2020. "Robustness of open source product innovation community’s knowledge collaboration network under the dynamic environment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 540(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. Fariba Karimi & Matthias Raddant, 2016. "Cascades in Real Interbank Markets," Computational Economics, Springer;Society for Computational Economics, vol. 47(1), pages 49-66, January.
    2. Tian, Yang & Tian, Hui & Cui, Yajuan & Zhu, Xuzhen & Cui, Qimei, 2023. "Influence of behavioral adoption preference based on heterogeneous population on multiple weighted networks," Applied Mathematics and Computation, Elsevier, vol. 446(C).
    3. Xianliang Liu & Zishen Yang & Wei Wang, 2021. "The t-latency bounded strong target set selection problem in some kinds of special family of graphs," Journal of Combinatorial Optimization, Springer, vol. 41(1), pages 105-117, January.
    4. Hu, Ping & Geng, Dongqing & Lin, Tao & Ding, Li, 2021. "Coupled propagation dynamics on multiplex activity-driven networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 561(C).
    5. Mitja Steinbacher & Matthias Raddant & Fariba Karimi & Eva Camacho Cuena & Simone Alfarano & Giulia Iori & Thomas Lux, 2021. "Advances in the agent-based modeling of economic and social behavior," SN Business & Economics, Springer, vol. 1(7), pages 1-24, July.
    6. Kobayashi, Teruyoshi & Ogisu, Yoshitaka & Onaga, Tomokatsu, 2023. "Unstable diffusion in social networks," Journal of Economic Dynamics and Control, Elsevier, vol. 146(C).
    7. Xiaole Wan & Zhen Zhang & Chi Zhang & Qingchun Meng, 2020. "Stock Market Temporal Complex Networks Construction, Robustness Analysis, and Systematic Risk Identification: A Case of CSI 300 Index," Complexity, Hindawi, vol. 2020, pages 1-19, July.
    8. Lee, Sang Hoon & Holme, Petter, 2019. "Navigating temporal networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 513(C), pages 288-296.
    9. Zhu, Shu-Shan & Zhu, Xu-Zhen & Wang, Jian-Qun & Zhang, Zeng-Ping & Wang, Wei, 2019. "Social contagions on multiplex networks with heterogeneous population," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 516(C), pages 105-113.
    10. Goel, Rahul & Singh, Anurag & Ghanbarnejad, Fakhteh, 2019. "Modeling Competitive Marketing Strategies in Social Networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 518(C), pages 50-70.
    11. Teruyoshi Kobayashi & Tomokatsu Onaga, 2023. "Dynamics of diffusion on monoplex and multiplex networks: a message-passing approach," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 76(1), pages 251-287, July.

    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:419:y:2015:i:c:p:622-629. 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.