Modeling and exact solution approaches for the distance-based critical node and edge detection problems

Alozie, Glory and Akartunali, Kerem and Arulselvan, Ashwin; Hamid, Faiz, ed. (2025) Modeling and exact solution approaches for the distance-based critical node and edge detection problems. In: Optimization Essentials. International Series in Operations Research & Management Science (1). Springer Singapore. ISBN 9789819954919 (In Press) (https://doi.org/10.1007/978-981-99-5491-9_7)

[thumbnail of Modeling and Exact Solution Approaches for the Distance-Based Critical Node and Edge Detection Problems] Text. Filename: DCNDP_Book_Chapter_Final.pdf
Accepted Author Manuscript
Restricted to Repository staff only until 1 January 2099.
License: Strathprints license 1.0
Download (543kB) | Request a copy

Abstract

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 optimal performance of the system. With respect to network connectivity as a performance metric, such components are termed critical nodes and edges. The optimisation problem associated with identifying critical nodes of a network is termed the critical node detection problem (CNDP). The CNDP has gained 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 are modelled by pre-defined distance-based connectivity measure. 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 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 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 context studied using the proposed models and algorithm. The Chapter concludes with directions for future research.

ORCID iDs

Alozie, Glory ORCID logoORCID: https://orcid.org/0000-0001-8750-6394, Akartunali, Kerem ORCID logoORCID: https://orcid.org/0000-0003-0169-3833 and Arulselvan, Ashwin ORCID logoORCID: https://orcid.org/0000-0001-9772-5523; Hamid, Faiz
CORE (COnnecting REpositories)