technical paper

AAMAS 2020

May 13, 2020

Live on Underline

Manipulating Node Similarity Measures in Networks

DOI: 10.48448/48mt-np02

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. 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 (W1-hard and W2-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 ErdosRenyi models.



Next from AAMAS 2020

technical paper

Encapsulating Reacting Behaviour In Goal-Based Plans For Programming BDI Agents

AAMAS 2020

Alessandro Ricci and 3 other authors

08 May 2020

Similar lecture


Practical Parallel Algorithms for Submodular Maximization subject to a Knapsack Constraint with Nearly Optimal Adaptivity

AAAI 2023

Kai Han and 5 other authors

11 February 2023

Stay up to date with the latest Underline news!


  • All Lectures
  • For Librarians
  • Resource Center
  • Free Trial
Underline Science, Inc.
1216 Broadway, 2nd Floor, New York, NY 10001, USA

© 2023 Underline - All rights reserved