Enhancing network robustness for malicious attacks

Abstract

In a recent work [Proc. Natl. Acad. Sci. USA 108, 3838 (2011)], the authors proposed a simple measure for network robustness under malicious attacks on nodes. With a greedy algorithm, they found the optimal structure with respect to this quantity is an onion structure in which high-degree nodes form a core surrounded by rings of nodes with decreasing degree. However, in real networks the failure can also occur in links such as dysfunctional power cables and blocked airlines. Accordingly, complementary to the node-robustness measurement ($R_n$), we propose a link-robustness index ($R_l$). We show that solely enhancing $R_n$ cannot guarantee the improvement of $R_l$. Moreover, the structure of $R_l$-optimized network is found to be entirely different from that of onion network. In order to design robust networks resistant to more realistic attack condition, we propose a hybrid greedy algorithm which takes both the $R_n$ and $R_l$ into account. We validate the robustness of our generated networks against malicious attacks mixed with both nodes and links failure. Finally, some economical constraints for swapping the links in real networks are considered and significant improvement in both aspects of robustness are still achieved.

6 pages, 6 figures

References in corpus (27)

• Emergence of scaling in random networks
• Community structure in social and biological networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Efficient Behavior of Small-World Networks
• Maps of random walks on complex networks reveal community structure
• Catastrophic cascade of failures in interdependent networks
• Statistical physics of social dynamics
• Synchronization in complex networks
• Identification of influential spreaders in complex networks
• Network robustness and fragility: Percolation on random graphs
• Defining and identifying communities in networks
• Resilience of the Internet to random breakdowns
• Mitigation of Malicious Attacks on Networks
• Detecting rich-club ordering in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Robustness of interdependent networks under targeted attack
• Designing optimal transport networks
• Suppressing Epidemics with a Limited Amount of Immunization Units
• How to make a fragile network robust and vice versa
• Onion structure and network robustness
• Removing spurious interactions in complex networks
• Stochastic Opinion Formation in Scale-Free Networks
• Enhancing synchronization by directionality in complex networks
• Optimal Tree for Both Synchronizability and Converging Time
• Scaling properties in spatial networks and its effects on topology and traffic dynamics
• Optimal synchronization on strongly connected directed networks

Cited by in corpus (18)

• Percolation of Partially Interdependent Scale-free Networks
• Immunization and targeted destruction of networks using explosive percolation
• Graph Vulnerability and Robustness: A Survey
• Smart Rewiring for Network Robustness
• Structural Robustness of Complex Networks: A Survey of A Posteriori Measures
• A Learning Convolutional Neural Network Approach for Network Robustness Prediction
• Knowledge-Based Prediction of Network Controllability Robustness
• Towards Optimal Robustness of Network Controllability: An Empirical Necessary Condition
• Synchrony-optimized networks of Kuramoto oscillators with inertia
• Improving information filtering via network manipulation
• SPP-CNN: An Efficient Framework for Network Robustness Prediction
• The Robustness of Graph k-shell Structure under Adversarial Attacks
• Tutte polynomial of pseudofractal scale-free web
• Identifying vital edges in Chinese air route network via memetic algorithm
• Robustness and Directed Structures in Ecological Flow Networks
• Link Cascades in Complex Networks: A Mean-field Approach
• Predicting the cascading dynamics in complex networks via the bimodal failure size distribution
• Mandala Networks: ultra-robust, ultra-small-world and highly sparse graphs