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

Generalized k-cores of networks under attack with limited knowledge

Author

Listed:
  • Shang, Yilun

Abstract

Network theory has been used as an effective approach for understanding and controlling many real-world large-scale systems. A significant aspect of network operation is its robustness against failures and attacks. Here, we develop a theoretical framework for two classes of network attack with limited knowledge, namely, min−n and max−n attacks, where only n nodes are observed and a node with smallest or largest degree is removed at a time until a fraction 1−p of nodes are attacked. We study the effect of these attacks on the generalized k-core (Gk-core) of the network, which is obtained by implementing a k-leaf pruning process, removing progressively nodes with degree smaller than k alongside their nearest neighbors. This removal process can be viewed as a generation of the ordinary k-core decomposition. It is found that the G2-core undergoes a continuous phase transition with respect to p while Gk-core shows a first-order percolation transition for k≥3 under both types of attacks for all n. We reveal that knowing one more node during attacks, improving from n=1 to n=2, turns out to be most beneficial in terms of changing the robustness of Gk-core in both directions. Moreover, it is shown that degree heterogeneity plays a role in robustness as prioritizing attack on small-degree nodes in heterogeneous networks may help consolidate the Gk-core, but also in stability where hub nodes act like anchors stabilizing the Gk-core structure. Our results offer insight into the design of resilient complex systems and evaluation of network robustness and stability.

Suggested Citation

  • Shang, Yilun, 2021. "Generalized k-cores of networks under attack with limited knowledge," Chaos, Solitons & Fractals, Elsevier, vol. 152(C).
    • Handle: RePEc:eee:chsofr:v:152:y:2021:i:c:s0960077921006597
    DOI: 10.1016/j.chaos.2021.111305
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0960077921006597
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.chaos.2021.111305?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. Ramon Ferrer i Cancho & Christiaan Janssen & Ricard V. Solé, 2001. "The Topology of Technology Graphs: Small World Patterns in Electronic Circuits," Working Papers 01-05-029, Santa Fe Institute.
    2. Yin, Yong & Liu, Qiong & Zhang, Chaoyong & Zhou, Jian, 2019. "Survivability analysis of weighted-edge attacks on complex networks with incomplete information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 531(C).
    3. Réka Albert & Hawoong Jeong & Albert-László Barabási, 2000. "Error and attack tolerance of complex networks," Nature, Nature, vol. 406(6794), pages 378-382, July.
    4. Anna D. Broido & Aaron Clauset, 2019. "Scale-free networks are rare," Nature Communications, Nature, vol. 10(1), pages 1-10, December.
    5. Xiao-Long Ren & Niels Gleinig & Dijana Tolić & Nino Antulov-Fantulin, 2018. "Underestimated Cost of Targeted Attacks on Complex Networks," Complexity, Hindawi, vol. 2018, pages 1-15, January.
    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. Tu, Haicheng & Xia, Yongxiang & Chen, Xi, 2022. "Vulnerability analysis of cyber physical systems under the false alarm cyber attacks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 599(C).
    2. Rong, Qingnan & Zhang, Jun & Sun, Xiaoqian & Wandelt, Sebastian, 2022. "On the estimation of percolation thresholds for real networks," Chaos, Solitons & Fractals, Elsevier, vol. 158(C).
    3. Wu, Rui-Jie & Kong, Yi-Xiu & Di, Zengru & Zhang, Yi-Cheng & Shi, Gui-Yuan, 2022. "Analytical solution to the k-core pruning process," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 608(P1).
    4. Zhou, Lili & Liao, Haibin & Tan, Fei & Yin, Jun, 2024. "Robustness analysis of multi-dependency networks: k-core percolation and deliberate attacks," Chaos, Solitons & Fractals, Elsevier, vol. 188(C).
    5. Dong, Gaogao & Luo, Yanting & Liu, Yangyang & Wang, Fan & Qin, Huanmei & Vilela, André L.M., 2022. "Percolation behaviors of a network of networks under intentional attack with limited information," Chaos, Solitons & Fractals, Elsevier, vol. 159(C).
    6. Qi, Mingze & Tan, Suoyi & Chen, Peng & Duan, Xiaojun & Lu, Xin, 2023. "Efficient network intervention with sampling information," Chaos, Solitons & Fractals, Elsevier, vol. 166(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. Laurienti, Paul J. & Joyce, Karen E. & Telesford, Qawi K. & Burdette, Jonathan H. & Hayasaka, Satoru, 2011. "Universal fractal scaling of self-organized networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(20), pages 3608-3613.
    2. Shen, Xiaoda & Wang, Zhigang & Deng, Ye & Wu, Jun, 2024. "Spatial network disintegration with heterogeneous cost," Chaos, Solitons & Fractals, Elsevier, vol. 187(C).
    3. Selen Onel & Abe Zeid & Sagar Kamarthi, 2011. "The structure and analysis of nanotechnology co-author and citation networks," Scientometrics, Springer;Akadémiai Kiadó, vol. 89(1), pages 119-138, October.
    4. Nie, Tingyuan & Fan, Bo & Wang, Zhenhao, 2022. "Complexity and robustness of weighted circuit network of placement," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 598(C).
    5. Cárdenas, J.P. & Mouronte, M.L. & Moyano, L.G. & Vargas, M.L. & Benito, R.M., 2010. "On the robustness of Spanish telecommunication networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(19), pages 4209-4216.
    6. Dan Braha & Yaneer Bar-Yam, 2007. "The Statistical Mechanics of Complex Product Development: Empirical and Analytical Results," Management Science, INFORMS, vol. 53(7), pages 1127-1145, July.
    7. Liu, Linqing & Shen, Mengyun & Sun, Da & Yan, Xiaofei & Hu, Shi, 2022. "Preferential attachment, R&D expenditure and the evolution of international trade networks from the perspective of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 603(C).
    8. Yilun Shang, 2020. "Multi-Hop Generalized Core Percolation On Complex Networks," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 23(01), pages 1-15, March.
    9. Luka Naglić & Lovro Šubelj, 2019. "War pact model of shrinking networks," PLOS ONE, Public Library of Science, vol. 14(10), pages 1-14, October.
    10. Kim, Seyun & Yoon, Yoonjin, 2019. "On node criticality of the Northeast Asian air route network," Journal of Air Transport Management, Elsevier, vol. 80(C), pages 1-1.
    11. Lucas Cuadra & Sancho Salcedo-Sanz & Javier Del Ser & Silvia Jiménez-Fernández & Zong Woo Geem, 2015. "A Critical Review of Robustness in Power Grids Using Complex Networks Concepts," Energies, MDPI, vol. 8(9), pages 1-55, August.
    12. Feng, Zhidan & Song, Huimin & Qi, Xingqin, 2024. "A novel algorithm for the generalized network dismantling problem based on dynamic programming," Chaos, Solitons & Fractals, Elsevier, vol. 180(C).
    13. Hao, Yucheng & Jia, Limin & Wang, Yanhui, 2020. "Edge attack strategies in interdependent scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 540(C).
    14. Ding, Sihua, 2022. "Link investment substitutability: A factor influencing network formation," Games and Economic Behavior, Elsevier, vol. 136(C), pages 340-359.
    15. Goldrosen, Nicholas, 2024. "Is corrections officers' use of illegal force networked? Network structure, brokerage, and key players in the New York City Department of Correction," Journal of Criminal Justice, Elsevier, vol. 92(C).
    16. Sanjeev Goyal & Fernando Vega-Redondo, 2000. "Learning, Network Formation and Coordination," Econometric Society World Congress 2000 Contributed Papers 0113, Econometric Society.
    17. 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).
    18. Quayle, A.P. & Siddiqui, A.S. & Jones, S.J.M., 2006. "Preferential network perturbation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 371(2), pages 823-840.
    19. Chen, Lei & Yue, Dong & Dou, Chunxia, 2019. "Optimization on vulnerability analysis and redundancy protection in interdependent networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 1216-1226.
    20. Bálint Mészáros & István Simon & Zsuzsanna Dosztányi, 2009. "Prediction of Protein Binding Regions in Disordered Proteins," PLOS Computational Biology, Public Library of Science, vol. 5(5), pages 1-18, May.

    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:chsofr:v:152:y:2021:i:c:s0960077921006597. 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: Thayer, Thomas R. (email available below). General contact details of provider: https://www.journals.elsevier.com/chaos-solitons-and-fractals .

    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.