Paper Info
Title
Predicting Signed Edges with O(n log n) Queries.
Abstract
Social networks and interactions in social media involve both positive and negative relationships. Signed graphs capture both types of relationships: positive edges correspond to pairs of friends, and negative edges to pairs of foes. The {em edge sign prediction problem} is an important graph mining task for which many heuristics have recently been proposed cite{leskovec2010predicting,leskovec2010signed}. In this paper we model the edge sign prediction problem as a noisy correlation clustering problem with two clusters. We are allowed to query each pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability $0u003cqu003cfrac{1}{2}$. We provide an algorithm that recovers the clustering with high probability in the presence of noise with $O(n log{n})$ queries if that gap $frac{1}{2}-q$ is constant. Finally, we provide a novel generalization to $k geq 3$ clusters and prove that our techniques can recover the clustering if the gap is constant in this generalized setting.
Year
Venue
Field
2016
arXiv: Data Structures and Algorithms
Cluster (physics),Graph,Discrete mathematics,Combinatorics,Correlation clustering,Heuristics,Time complexity,Cluster analysis,Mathematics
DocType
Volume
Citations 
Journal
abs/1609.00750
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Michael Mitzenmacher17386730.89
Charalampos E. Tsourakakis2100351.15