Predicting Positive and Negative Links with Noisy Queries: Theory & Practice

Understand

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.