Modeling and Exact Solution Approaches for the Distance-Based Critical Node and Edge Detection Problems

The performance of many networked systems including energy, telecommunication, and transport networks is dependent on the functionality of a few components of these systems whose malfunction compromises the optimal performance of the system. With respect to network connectivity as a performance metric, such components are termed critical nodes and edges. The optimization problem associated with identifying critical nodes of a network is termed the critical node detection problem (CNDP). The CNDP has gained a significant amount of research owing to its applicability in diverse real-life problems including disaster management, social network analysis, and disease epidemiology, as well as its computational complexity. However, traditional models, whose underlying objective is to maximize network fragmentation fail to capture cohesiveness and extent of connectivity within the resultant network. Therefore, a new variant of the problem termed the distance-based critical node detection problem (DCNDP) was proposed to address this gap. The DCNDP takes into account pairwise distances between nodes as part of its network connectivity objective, which is modeled by pre-defined distance-based connectivity measures. Distance-based connectivity plays an important part in everyday life. For instance, our choice of route of travel and the cost of a flight ticket are influenced by the duration of travel and number of stopovers involved. Therefore, while a source-destination route might exist, if the duration of a trip via the route precludes the attainment of a time-bound activity, then such is a practical disconnection. Similarly, in communication and telecommunication networks, speed and coverage are key operational issues for assessing connectivity which are both related to pairwise distances in the network. In this chapter, we study a generalization of the DCNDP on weighted networks, where the distance between any source-destination (s-t) pair is not limited to hop distance (number of edges along an s-t path). We present a new model with fewer entities than the models in previous studies. Moreover, we show that the proposed model admits different distance-based connectivity measures, hence is valid for all existing classes of the distance-based critical node detection problem. We introduce a new version of the problem, in which edges rather than nodes are to be deleted. This version is useful for application contexts where it is impractical or too expensive to delete nodes. Furthermore, we study social and transportation networks, where we also demonstrate practical aspects of the problem. Some computational experiments on instances of different real-world networks are presented for the different application contexts studied using the proposed models and algorithm. The Chapter concludes with directions for future research.