A Metric to Compare Vulnerability of the Graphs of Different Sizes

Abstract Node immunization and estimation of vulnerability are essential for a number of applications from safe guarding computer networks against virus attacks to protecting human population from highly contagious biological viruses. The concepts of node immunization can be used in the fast diffusion of information on a network and viral marketing. In this article, normalized eigenvalue based measure to compare vulnerability of Graphs of different sizes is proposed. The measure is based on largest eigenvalue of the adjacency matrix of the graph. Erdos-Renyi Random Graphs of different size and connectivity been used for experimental verification using susceptible infected (SI) model. It has been found that the proposed metric is good to compare vulnerability of graphs when graphs are moderately or highly connected, or when contagion strength is not too weak.