Title: Attacking Similarity-Based Link Prediction in Social Networks,
Abstract: Link prediction is one of the fundamental problems in computational social
science. A particularly common means to predict existence of unobserved links
is via structural similarity metrics, such as the number of common neighbors;
node pairs with higher similarity are thus deemed more likely to be linked.
However, a number of applications of link prediction, such as predicting links
in gang or terrorist networks, are adversarial, with another party incentivized
to minimize its effectiveness by manipulating observed information about the
network. We offer a comprehensive algorithmic investigation of the problem of
attacking similarity-based link prediction through link deletion, focusing on
two broad classes of such approaches, one which uses only local information
about target links, and another which uses global network information. While we
show several variations of the general problem to be NP-Hard for both local and
global metrics, we exhibit a number of well-motivated special cases which are
tractable. Additionally, we provide principled and empirically effective
algorithms for the intractable cases, in some cases proving worst-case
approximation guarantees.