Predicting Positive and Negative Links with Noisy Queries: Theory & Practice
Predicting Positive and Negative Links with Noisy Queries: Theory & Practice
复制标题
通过嘈杂的查询预测正向和负向链接：理论
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Vasileios Nakos
中科院分区：
文献类型：
--
作者：
Charalampos E. Tsourakakis;M. Mitzenmacher;Jarosław Błasiok;Benn Lawson;Preetum Nakkiran;Vasileios Nakos
社交网络涉及积极关系和负面关系，可以在签名的图中捕获。 {Em边缘标志预测问题}旨在预测一对节点之间的相互作用是正面还是负面。我们为这个问题提供了理论上的结果，可以激发近期启发式方法的自然改进。
边缘标志预测问题与相关聚类有关。积极的关系意味着处于同一集群中。我们考虑以下两个群集的模型：我们可以查询任何一对节点是否属于同一群集，但是查询的答案被某些概率$ 0 <q <q <frac {1} {2}损坏了。 $。令$ delta = 1-2q $为偏见。我们提供了一种算法，该算法在存在$ o（frac {nlog n} {delta^2}+frac {log^2 n} {delta^6}）的噪声的情况下正确恢复所有符号。这是除了Tiny $ delta $以外的所有问题的最著名的结果，在Mazumdar和Saha Cite {Mazumdar2017Clustering}的最新工作中有所改善。我们还提供了一种执行$ o（frac {nlog n} {delta^4}）$查询的算法，并使用广度首次搜索作为其主要算法原始搜索。尽管该算法的运行时间和查询数量都是亚最佳选择，但我们的结果依赖于新颖的理论技术，并且自然暗示使用边缘 - 偶口路径作为预测在线社交网络中标志的功能。相应地，我们尝试使用短度长度的边缘分离$ S-T $路径作为预测现实世界中签名网络中边缘$（s，t）$的符号的功能。经验发现表明，这种路径的使用提高了分类准确性，尤其是对于没有共同邻居的一对节点。
Social networks involve both positive and negative relationships, which can be captured in signed graphs. The {em edge sign prediction problem} aims to predict whether an interaction between a pair of nodes will be positive or negative. We provide theoretical results for this problem that motivate natural improvements to recent heuristics.
The edge sign prediction problem is related to correlation clustering; a positive relationship means being in the same cluster. We consider the following model for two clusters: we are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability $0<q<frac{1}{2}$. Let $delta=1-2q$ be the bias. We provide an algorithm that recovers all signs correctly with high probability in the presence of noise with $O(frac{nlog n}{delta^2}+frac{log^2 n}{delta^6})$ queries. This is the best known result for this problem for all but tiny $delta$, improving on the recent work of Mazumdar and Saha cite{mazumdar2017clustering}. We also provide an algorithm that performs $O(frac{nlog n}{delta^4})$ queries, and uses breadth first search as its main algorithmic primitive. While both the running time and the number of queries for this algorithm are sub-optimal, our result relies on novel theoretical techniques, and naturally suggests the use of edge-disjoint paths as a feature for predicting signs in online social networks. Correspondingly, we experiment with using edge disjoint $s-t$ paths of short length as a feature for predicting the sign of edge $(s,t)$ in real-world signed networks. Empirical findings suggest that the use of such paths improves the classification accuracy, especially for pairs of nodes with no common neighbors.