2022/03/25 by Jeremie Fish, Fish, Jeremie, Mahesh K. Banavar +3
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Distributed systems and fault tolerance #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Opportunistic and Delay-Tolerant Networks #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.2203.13943
openalex publication_date 2022/03/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graphs are pervasive in our everyday lives, with relevance to biology, the internet, and infrastructure, as well as numerous other applications. It is thus necessary to have an understanding as to how quickly a graph disintegrates, whether by random failure or by targeted attack. While much of the interest in this subject has been focused on targeted removal of nodes, there has been some recent interest in targeted edge removal. Here, we focus on how robust a graph is against edge removal. We define a measure of network fragility that relates the fraction of edges removed to the largest connected component. We construct a class of graphs that is robust to edge removal. Furthermore, it is demonstrated that graphs generally disintegrate faster than would be anticipated by greedy targeted attack. Finally it is shown that our fragility measure as demonstrated real and natural networks.