Journal
PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS
Volume 577, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.physa.2021.126074
Keywords
Linking deception; Link prediction; Link addition; Complex network
Categories
Funding
- Fundamental Research Funds for the Central Universities of China [JB211501]
- Natural Science Basis Research Plan in Shaanxi Province of China [2020JM-203]
- National Natural Science Foundation of China [61502375]
- Key R&D Program of Shaanxi Province of China [2019ZDLGY12-06]
Ask authors/readers for more resources
This work introduces a link deception method from the attacker's perspective, aiming to enhance the prediction probability of given targets by adding a small number of new links. The research first defines the link deception process and proposes greedy and heuristic algorithms to efficiently achieve the deception goal.
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. (C) 2021 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available