We present very efficient active learning algorithms for link classification in signed networks. Our algorithms are motivated by a stochastic model in which edge labels are obtained through perturbations of a initial sign assignment consistent with a two-clustering of the nodes. We provide a theoretical analysis within this model, showing that we can achieve an optimal (to whithin a constant factor) number of mistakes on any graph G = (V, E) such that |E| = Ω(|V|~(3/2)) by querying O(|V|~(3/2)) edge labels. More generally, we show an algorithm that achieves optimality to within a factor of O(k) by querying at most order of |V| + (|V|/k)~(3/2) edge labels. The running time of this algorithm is at most of order |E| + |V| log |V|.
展开▼
机译：我们提出了用于签名网络中的链接分类的非常有效的主动学习算法。我们的算法是由随机模型驱动的，在该模型中，通过对初始符号分配的扰动来获得边缘标签，该初始符号分配与节点的两次聚类一致。我们在该模型中提供了理论分析，表明在任何图形G =（V，E）上，我们都能获得最优的错误数目（以恒定因子表示），从而使| E |达到最佳。通过查询O（| V |〜（3/2））边缘标签=Ω（| V |〜（3/2））。更一般而言，我们展示了一种算法，该算法通过查询最多| V |的阶数来达到O（k）内的最优性。 +（| V | / k）〜（3/2）边缘标签。该算法的运行时间最多为| E |。 + | V |记录| V |。
展开▼
