Predicting Signed Edges with O(n^1+o(1) logn) Queries

2016/09/02 by Michael Mitzenmacher, Mitzenmacher, Michael, Charalampos E. Tsourakakis +1
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Social and Information Networks (cs.SI)

paper · pdf · doi:10.48550/arxiv.1609.00750

openalex publication_date 2016/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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, which aims to predict whether an interaction between a pair of nodes will be positive or negative, is an important graph mining task for which many heuristics have recently been proposed \citeleskovec2010predicting,leskovec2010signed. Motivated by social balance theory, 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 0

Related

• Predicting Positive and Negative Links with Noisy Queries: Theory & Practice
• On the Troll-Trust Model for Edge Sign Prediction in Social Networks
• Prediction and Clustering in Signed Networks: A Local to Global Perspective
• A Model of Consistent Node Types in Signed Directed Social Networks
• Interpretable Signed Link Prediction with Signed Infomax Hyperbolic Graph