Adversarial Link Prediction in Spatial Networks
Adversarial Link Prediction in Spatial Networks
复制标题
DOI：
10.5555/3545946.3598846
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
M. T. Godziszewski;Yevgeniy Vorobeychik;Tomasz P. Michalak
中科院分区：
文献类型：
--
作者：
M. T. Godziszewski;Yevgeniy Vorobeychik;Tomasz P. Michalak
社交网络是人与人之间复杂互动的结果，而同质性在这一过程中起着重要作用。如果我们将同质性视为网络形成中的主导力量，并将每个节点与一组特征相关联，那么这个过程就会产生空间网络，边缘的可能性是其事件节点之间特征相似性的递增函数。这样的空间网络中的链路预测问题则相当于根据该边缘似然函数来确定节点对是否足够接近。我们进行了这个问题的对抗方面的第一个算法研究，其中对手操纵网络上的节点子集的特征，以防止预测目标边缘。我们表明，这个问题是NP-困难的，即使边缘似然函数是凸的。另一方面，如果这个函数是凸的，我们证明了当对手需要操纵的节点集是固定的时，这个问题可以用凸规划来解决。此外，如果边缘似然函数是线性的，我们提出了近似算法的情况下，当功能是二进制的，我们希望只隐藏一个边缘，和的情况下，当功能是实值的，但我们需要隐藏任意收集的边缘。
Social networks arise as a result of complex interactions among people, and homophily plays an important role in this process. If we view homophily as a dominant force in network formation and associate each node with a collection of features, this process gives rise to spatial networks, with likelihood of an edge an increasing function of feature similarity among its incident nodes. A link prediction problem in such spatial networks then amounts to determining whether the pair of nodes are sufficiently close according to this edge likelihood function. We undertake the first algorithmic study of the adversarial side of this problem in which the adversary manipulates features of a subset of nodes on the network to prevent predicting target edges. We show that this problem is NP-hard, even if the edge likelihood function is convex. On the other hand, if this function is convex, we show that the problem can be solved with convex programming when the set of nodes that the adversary needs to manipulate is fixed. Furthermore, if the edge likelihood function is linear, we present approximation algorithms for the case when the features are binary, and we wish to hide only a single edge, and for the case when the features are real-valued but we need to hide an arbitrary collection of edges.