Robustness of solutions to critical node detection problems with imperfect data: a computational study

Abstract

A class of critical node detection problems based upon the metric of communication efficiency is considered. While both exact integer programming and heuristic centrality-based methods exist for the solution of these problems, previous work has been mostly focused on the case where perfect information about the network is available. In this paper we suppose that some level of misinformation about nodes or edges has been inflicted on the observer's perception of the network, that is, there are hidden elements or fake additional elements. An extensive computational study is conducted to ascertain whether the exact integer-programming-based solutions perform better under imperfect information than heuristic methods. For large networks, exact methods cannot produce a solution in a reasonable amount of time, hence an approximation of the exact method is also considered for such instances. The obtained approximate solutions are again compared to centrality-based heuristics under the presence of imperfect data.

Keywords:

• critical node detection
• distance-based metrics
• graph efficiency
• network interdiction
• mixed integer programming
• robustness
• sensitivity

Acknowledgements

The US Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of AFRL/RW or the US Government. The authors would also like to thank the Associate Editor and the anonymous reviewers for their comments, which improved the clarity and exposition of the manuscript.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The first and third authors were supported by the DTRA grant HDTRA1-14-1-0065 and AFOSR grant FA2386-12-1-3032. This research is also partially supported by the US Air Force Research Laboratory (AFRL) Mathematical Modeling and Optimization Institute and sponsored by AFRL/RW under agreement number FA8651-14-2-0002.