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

Research output: Chapter in Book/Report/Conference proceedingChapter

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.
Original languageEnglish
Title of host publicationOptimization Essentials
Subtitle of host publicationTheory, Tools, and Applications
EditorsFaiz Hamid
Chapter7
Pages233-256
Number of pages24
Volume353
Edition1
ISBN (Electronic)9789819954919
DOIs
Publication statusPublished - 11 Jan 2025

Publication series

NameInternational Series in Operations Research & Management Science
PublisherSpringer
ISSN (Print)0884-8289
ISSN (Electronic)2214-7934

Keywords

  • optimization techniques
  • modeling

Fingerprint

Dive into the research topics of 'Modeling and exact solution approaches for the distance-based critical node and edge detection problems'. Together they form a unique fingerprint.

Cite this