Measuring the Vulnerability in Networks: A Heuristic Approach

Abstract

The integrity of a graph $G=(V,E)$ is defined as $I(G)=min\{|S|+m(G-S):S\subseteq V(G)\}$, where $m(G-S)$ denotes the order of the largest component in the graph $G-S$. This is a better parameter to measure the stability of a network, as it takes into account both the amount of work done to damage the network and how badly the network is damaged. Computationally, it belongs to the class of intractable problems known as NP-hard. In this paper, we develop a heuristic algorithm to determine the integrity of a graph. Extensive computational experience on $88$ randomly generated graphs ranging from $20\mathrm{\%}$ to $90\mathrm{\%}$ densities and from $100$ to $200$ vertices has shown that the proposed algorithm is very effective.