Manipulating Node Similarity Measures in Networks
arXiv:1910.11529
Abstract
Node similarity measures quantify how similar a pair of nodes are in a network. These similarity measures turn out to be an important fundamental tool for many real world applications such as link prediction in networks, recommender systems etc. An important class of similarity measures are local similarity measures. Two nodes are considered similar under local similarity measures if they have large overlap between their neighboring set of nodes. Manipulating node similarity measures via removing edges is an important problem. This type of manipulation, for example, hinders effectiveness of link prediction in terrorists networks. Fortunately, all the popular computational problems formulated around manipulating similarity measures turn out to be NP-hard. We, in this paper, provide fine grained complexity results of these problems through the lens of parameterized complexity. In particular, we show that some of these problems are fixed parameter tractable (FPT) with respect to various natural parameters whereas other problems remain intractable W[1]-hard and W[2]-hard in particular). Finally we show the effectiveness of our proposed FPT algorithms on real world datasets as well as synthetic networks generated using Barabasi-Albert and Erdos-Renyi models.
To appear as a full paper in AAMAS 2020
References in corpus (8)
- Emergence of scaling in random networks
- Predicting Missing Links via Local Information
- Recommender Systems for Online and Mobile Social Networks: A survey
- Attacking Similarity-Based Link Prediction in Social Networks
- Target Defense Against Link-Prediction-Based Attacks via Evolutionary Perturbations
- Attack Tolerance of Link Prediction Algorithms: How to Hide Your Relations in a Social Network
- Influence Minimization Under Budget and Matroid Constraints: Extended Version
- K-Core Minimization: A Game Theoretic Approach