Critical nodes for distance‐based connectivity and related problems in graphs
Abstract
This study considers a class of critical node detection problems that involves minimization of a distance‐based connectivity measure of a given unweighted graph via the removal of a subset of nodes (referred to as critical nodes) subject to a budgetary constraint. The distance‐based connectivity measure of a graph is assumed to be a function of the actual pairwise distances between nodes in the remaining graph (e.g., graph efficiency, Harary index, characteristic path length, residual closeness) rather than simply whether nodes are connected or not, a typical assumption in the literature. We derive linear integer programming (IP) formulations, along with additional enhancements, aimed at improving the performance of standard solvers. For handling larger instances, we develop an effective exact algorithm that iteratively solves a series of simpler IPs to obtain an optimal solution for the original problem. The edge‐weighted generalization is also considered, which results in some interesting implications for distance‐based clique relaxations, namely, ‐clubs. Finally, we conduct extensive computational experiments with real‐world and randomly generated network instances under various settings that reveal interesting insights and demonstrate the advantages and limitations of the proposed approach. In particular, one important conclusion of our work is that vulnerability of real‐world networks to targeted attacks can be significantly more pronounced than what can be estimated by centrality‐based heuristic methods commonly used in the literature. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 170–195 2015
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jul 22, 2015
- Source ID
- 10.1002/net.21622
Entities
People
- Alexander Veremyev
- Eduardo Pasiliao
- Oleg A. Prokopyev
Organizations
- Air Force Office of Scientific Research
- Air Force Research Laboratory
- National Research Council
- United States Air Force
- University of Florida
- University of Pittsburgh