Adversarial link deception against the link prediction in complex networks

Currently, the link prediction tool has been extensively used in kinds of complex networks for the use of friend, commodity, or service recommendations. However, many adversaries may maliciously or intentionally perturb a part of social links to deceive the link prediction method to suggest some unexpected missing links (referred to as targets) to users. In this work, from the attacker perspective, we propose to promote the prediction probability of given targets via adding a tiny number of new links into the network to deceive the common neighbor based link prediction method. We first define the link deception process as a similarity score maximizing problem. Secondly, we propose to use a greedy algorithm referred to as GreedyAdd to greedily adding a budget limited number of links into the network. Thirdly, considering the high time complexity of the GreedyAdd, we propose a heuristic link addition method referred to as HeuristicAdd to improve the computing efficiency. Finally, we do experiments on many real social graphs to confirm the effectiveness and efficiency of the HeuristicAdd method. The results show that the HeuristicAdd algorithm can mostly deceive the link prediction with less time consumptions than the GreedyAdd. This work considers the security problem of complex systems from a new perspective and has potential applications.