Adversarial link deception against the link prediction in complex networks

Zhongyuan Jiang, Xiaoke Tang, Yong Zeng, Jinku Li and Jianfeng Ma

Physica A: Statistical Mechanics and its Applications, 2021, vol. 577, issue C

Abstract: 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.

Keywords: Linking deception; Link prediction; Link addition; Complex network (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437121003472
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:577:y:2021:i:c:s0378437121003472

DOI: 10.1016/j.physa.2021.126074

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().