Manipulating Node Similarity Measures in Network
Manipulating Node Similarity Measures in Network
复制标题
DOI：
--
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
P. Dey;Sourav Medya
中科院分区：
文献类型：
--
作者：
P. Dey;Sourav Medya
节点相似性度量量化网络中一对节点的相似程度。这些相似性度量被证明是许多现实世界应用的重要基础工具，如网络中的链接预测、推荐系统等。局部相似性度量是一类重要的相似性度量。如果两个节点在其相邻节点集之间有很大的重叠，则在局部相似性度量下它们被认为是相似的。通过去除边来处理节点相似性度量是一个重要的问题。例如，这种类型的操纵阻碍了恐怖分子网络中链接预测的有效性。幸运的是，所有围绕操纵相似性度量而形成的流行计算问题都被证明是NP难的。在这篇文章中，我们通过参数复杂性的透镜，给出了这些问题的细粒度复杂性结果。特别地，我们证明了这些问题中的一些关于各种自然参数是固定参数可处理的(FPT)，而另一些问题仍然是W[1]-困难的，特别是W[2]-困难的)。最后，我们在真实数据集以及使用Barabasi-Albert和Erdos-Renyi模型生成的合成网络上展示了我们所提出的FPT算法的有效性。
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.