Networks · 2015 · 99 citations · 60 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationCombinatorial OptimizationGraph AlgorithmsGraph TheoryInteger ProgrammingNetwork ConnectivityNetwork OptimizationClique AlgorithmsConnectivity AlgorithmsEfficiencyGraph ConnectivityGraph OptimizationGraph RelaxationInteger Linear ProgrammingLinear Integer Optimization
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
60
Collective dynamics of ‘small-world’ networks
Duncan J. Watts, Steven H. Strogatz · Nature · 1998 · 43.2K citations
Statistical mechanics of complex networks
Réka Albert, Albert-Ĺaszló Barabási · Reviews of Modern Physics · 2002 · 20.6K citations · Full text
The Structure and Function of Complex Networks
Michael Newman · SIAM Review · 2003 · 18.7K citations · Full text
Network Flows: Theory, Algorithms, and Applications.
David K. Smith, Ravindra K. Ahuja, Thomas L. Magnanti et al. · Journal of the Operational Research Society · 1994 · 8.2K citations · Full text
Error and attack tolerance of complex networks