CBDI: Combined Banzhaf & diversity index for finding critical nodes

Critical node discovery plays a vital role in assessing the vulnerability of a network to an abrupt change, such as an adversarial attack or human intervention. In this paper, we propose a new metric to characterize the criticality of a node in an arbitrary network which we refer to as the Combined Banzhaf & Diversity Index (CBDI). The metric utilizes a diversity index which is based on the variability of a node's attributes relative to its neighbors and the Banzhaf Power Index which characterizes the degree of participation of a node in forming shortest paths. The Banzhaf power index is inspired from the theory of voting games in game theory. We evaluate the performance of the new metric using simulations. Our results indicate that in a number of network topologies, the proposed metric outperforms other proposals which have appeared in the literature. The proposed CBDI index chooses more critical nodes which, when removed, degrade network performance to a greater extent than if critical nodes based on other criticality metrics were removed.