 Modeling and Exact Solution Approaches for the Distance-Based Critical Node and Edge Detection ProblemsGlory Uche Alozie,
Kerem Akartunali () and
Ashwin Arulselvan
Chapter Chapter 7 in Optimization Essentials, 2024, pp 233-256 from Springer Abstract: 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 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. Keywords: Critical node detection problem; Distance-based connectivity; Mixed integer programming; Branch-and-cut; Networks (search for similar items in EconPapers) There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it. Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-981-99-5491-9_7 Ordering information: This item can be ordered from DOI: 10.1007/978-981-99-5491-9_7 Access Statistics for this chapter More chapters in International Series in Operations Research & Management Science from Springer |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.