  A fundamental challenge in networked systems is detection and removal of
suspected malicious nodes. In reality, detection is always imperfect, and the
decision about which potentially malicious nodes to remove must trade off false
positives (erroneously removing benign nodes) and false negatives (mistakenly
failing to remove malicious nodes). However, in network settings this
conventional tradeoff must now account for node connectivity. In particular,
malicious nodes may exert malicious influence, so that mistakenly leaving some
of these in the network may cause damage to spread. On the other hand, removing
benign nodes causes direct harm to these, and indirect harm to their benign
neighbors who would wish to communicate with them.
  We formalize the problem of removing potentially malicious nodes from a
network under uncertainty through an objective that takes connectivity into
account. We show that optimally solving the resulting problem is NP-Hard. We
then propose a tractable solution approach based on a convex relaxation of the
objective. Finally, we experimentally demonstrate that our approach
significantly outperforms both a simple baseline that ignores network
structure, as well as a state-of-the-art approach for a related problem, on
both synthetic and real-world datasets.
