Graph Vulnerability and Robustness: A Survey

Abstract

The study of network robustness is a critical tool in the characterization and sense making of complex interconnected systems such as infrastructure, communication and social networks. While significant research has been conducted in all of these areas, gaps in the surveying literature still exist. Answers to key questions are currently scattered across multiple scientific fields and numerous papers. In this survey, we distill key findings across numerous domains and provide researchers crucial access to important information by--(1) summarizing and comparing recent and classical graph robustness measures; (2) exploring which robustness measures are most applicable to different categories of networks (e.g., social, infrastructure; (3) reviewing common network attack strategies, and summarizing which attacks are most effective across different network topologies; and (4) extensive discussion on selecting defense techniques to mitigate attacks across a variety of networks. This survey guides researchers and practitioners in navigating the expansive field of network robustness, while summarizing answers to key questions. We conclude by highlighting current research directions and open problems.

arXiv commentAccepted into Transactions on Knowledge and Data Engineering (TKDE) 2022

References in corpus (36)

• Emergence of scaling in random networks
• Power-law distributions in empirical data
• Error and attack tolerance of complex networks
• Catastrophic cascade of failures in interdependent networks
• The large-scale organization of metabolic networks
• Network robustness and fragility: Percolation on random graphs
• Spatial Networks
• Cascade-based attacks on complex networks
• Attack vulnerability of complex networks
• Subgraph Centrality in Complex Networks
• A model for cascading failures in complex networks
• Growing Scale-Free Networks with Tunable Clustering
• Mitigation of Malicious Attacks on Networks
• Scale-free topology of e-mail networks
• Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition
• Modeling Cascading Failures in the North American Power Grid
• Robustness of a Network of Networks
• Cascade of failures in coupled network systems with multiple support-dependent relations
• Vulnerability and Protection of Critical Infrastructures
• Resilience of public transport networks against attacks
• Spectral Measures of Bipartivity in Complex Networks
• Complex network analysis of water distribution systems
• Optimization of Robustness of Complex Networks
• Enhancing network robustness for malicious attacks
• Suppressing Epidemics with a Limited Amount of Immunization Units
• Adversarial Attack on Graph Structured Data
• Spectral Scaling in Complex Networks
• Robustness of Interdependent Networks: The case of communication networks and the power grid
• Approximating Spectral Impact of Structural Perturbations in Large Networks
• Graph measures and network robustness
• Two distinct transitions in spatially embedded multiplex networks
• Reliability and Survivability Analysis of Data Center Network Topologies
• Robustness and stability of enterprise intranet social networks: The impact of moderators
• Approximation Algorithms for Reducing the Spectral Radius to Control Epidemic Spread
• Node Immunization with Non-backtracking Eigenvalues
• D2M: Dynamic Defense and Modeling of Adversarial Movement in Networks

Cited by in corpus (10)

• Trustworthy Graph Neural Networks: Aspects, Methods and Trends
• Structural Robustness of Complex Networks: A Survey of A Posteriori Measures
• SPP-CNN: An Efficient Framework for Network Robustness Prediction
• Exploring Robust Architectures for Deep Artificial Neural Networks
• Cyber Network Resilience against Self-Propagating Malware Attacks
• Minimizing the effective graph resistance by adding links is NP-hard
• Measures and Optimization for Robustness and Vulnerability in Disconnected Networks
• Efficient Algorithms for Minimizing the Kirchhoff Index via Adding Edges
• Weighted cycle-based identification of influential node groups in complex networks
• Identifying Central Nodes in Multiplex Networks by Embracing Layer-Specific Heterogeneity via DomiRank