Source-linked AI summary
Predicting Positive and Negative Links in Online Social Networks
Jure Leskovec, Daniel Huttenlocher, Jon Kleinberg
TL;DR
Online social networks contain both positive and negative relationships, but their sign patterns and broader configurations require systematic study. The paper formulates sign prediction, applies machine-learning models across Epinions, Slashdot, and Wikipedia, and compares the results with balance and status theories. The models generalize across domains, improve on previous approaches, and reveal global status ordering without corresponding global factional organization.
Problem
The paper asks how a link’s positive or negative sign relates to surrounding signed relationships and how such patterns generalize across online domains.
Method
The authors hide an edge sign, infer it from the remaining network using machine-learning models, and compare the learned models with balance and status theories across three signed datasets.
Results
The models generalize across domains, significantly improve on previous approaches, and yield up to a factor of 1.5 improvement over random choice on two of three datasets when negative links aid positive-link prediction.
Takeaways & Limitations
Local sign patterns show aspects of both balance and status, while global structure provides evidence for approximate status ordering but essentially no evidence for opposing factions.
Takeaways & Limitations
The framework considers primarily directed links, although it can also be applied to undirected links.
Abstract
from arXiv · showhide
We study online social networks in which relationships can be either positive (indicating relations such as friendship) or negative (indicating relations such as opposition or antagonism). Such a mix of positive and negative links arise in a variety of online settings; we study datasets from Epinions, Slashdot and Wikipedia. We find that the signs of links in the underlying social networks can be predicted with high accuracy, using models that generalize across this diverse range of sites. These models provide insight into some of the fundamental principles that drive the formation of signed links in networks, shedding light on theories of balance and status from social psychology; they also suggest social computing applications by which the attitude of one user toward another can be estimated from evidence provided by their relationships with other members of the surrounding social network.
1. INTRODUCTION
The paper formulates prediction of positive and negative link signs across three online networks, using learned structural models and comparisons with balance and status theories. It finds cross-domain generalization, improved prediction, and distinct local and global patterns in signed networks.
- Motivation: Most online social-network research considered positive relationships, despite online interactions also expressing disapproval, disagreement, distrust, and antagonism.
- Problem and approach: The edge sign prediction problem hides one edge sign and infers it from the rest of the signed network, supporting estimation of unobserved user attitudes.
- Problem and approach: Machine-learning models evaluate which structural features predict signs and significantly improve performance over earlier propagation-based approaches.
- Findings: The learned models can be compared directly with balance and status theories, revealing characteristic agreements and disagreements that persist across datasets.
- Findings: Sign prediction generalizes across Epinions, Slashdot, and Wikipedia, with only slight performance degradation when training and testing across domains despite different link meanings.
- Additional tasks: Up to a factor of 1.5 improvement over random choice occurs on two of three datasets when negative links are visible for predicting hidden positive links.
- Global structure: Global analysis finds evidence for an approximate status ordering but essentially no evidence for opposing factions, contrasting with local evidence for aspects of both theories.
2. DATASET DESCRIPTION
The study uses three large online networks with explicitly signed links: trust and distrust on Epinions, friends and foes on Slashdot, and votes on Wikipedia admin promotions. Across the networks, approximately 80% of edges are positive.
- Datasets: The datasets are Epinions, Slashdot, and Wikipedia, each containing links explicitly labeled positive or negative.
- Epinions: Epinions records trust or distrust relationships connected to product-review authority, covering 119,217 nodes and 841,000 edges from 1999 through August 12, 2003.
- Slashdot: Slashdot’s 2002 friend-or-foe network contains 82,144 users and 549,202 edges, with 77.4% positive edges.
- Wikipedia: Wikipedia’s network contains 7,118 users and 103,747 signed votes from 2,794 administrator elections, with 78.7% positive votes.
- Cross-dataset pattern: Approximately 80% of edges are positive in all three networks.
3. PREDICTING EDGE SIGN
Machine-learning models predict hidden edge signs from local structural features and outperform earlier results, while revealing systematic relationships to balance and status theories. Performance and theory alignment vary across datasets, with cross-domain balance properties more robust than status properties.
- Prediction performance: 6.58% error was achieved using all 23 features on Epinions, improving over the earlier 14.7% lowest error rate.Degree features achieved 11.45% error, while 16 triad features achieved 6.64%.
- Prediction performance: Local one-step neighborhood features can predict edge signs without modeling propagation from distant parts of the network.The learned features use local properties around the edge being inferred.
- Prediction performance: Triad features are weaker for low-embeddedness edges but become more effective as embeddedness increases.Greater embeddedness provides more triadic information for prediction.
- Prediction performance: Wikipedia prediction accuracy is lower than on Epinions and Slashdot, even for edges with large embeddedness.The passage contrasts Wikipedia’s publicly visible, consequential, information-based evaluations with the other datasets.
- Connections to theories: Balance and status theories agree with learned models on more than half of the triad types where they predict, generally reaching agreement on at least three-quarters.Balance aligns better with learned models on Epinions and Slashdot than on Wikipedia.
- Connections to theories: Balance consistently disagrees with learned models on the “enemy of my enemy” pattern, while weak balance avoids predicting that case.For all other triad types in the reported comparison, learned coefficients match balance predictions across datasets.
- Connections to theories: Learned coefficients match status predictions for both triad types on which status theory makes predictions across all three datasets.The reduced-form analysis places balance at the undirected-graph level and status after canonicalizing edge signs and directions.
- Generalization across datasets: Learned balance properties generalize well across datasets, whereas learned status properties are more dataset-specific and can underperform the baseline status model.The comparison includes learned and nonlearned Balance and Status models.
4. GLOBAL STRUCTURE OF SIGNED NETWORKS
The paper tests whether local theories of balance and status produce global structural predictions in signed networks. Across datasets, the networks show evidence of approximate status ordering but not global factional balance.
- Local status consistency implies a total node ordering in which positive edges point left-to-right and negative edges point right-to-left.
- Balance theory predicts two opposed factions, while status theory predicts an ordering with positive edges forward and negative edges backward.
- The balance heuristic maximizes positive within-group and negative between-group edges, starting from random two-set partitions and improving them iteratively.
- The status heuristic reverses negative edges, then searches for an ordering that maximizes edges pointing from earlier to later nodes.
- Global balance scores are comparable to the trivial baseline, whereas real networks show status performance above randomized baselines.
- Overall, the datasets support approximate global status ordering but not significant global factional partitioning, contrasting with local evidence for both theories.
5. PREDICTING POSITIVE EDGES
The paper asks whether negative links improve prediction of unobserved positive links. It compares models using positive-only versus signed-network features and finds that negative-link information improves performance in these experiments.
- The task is to predict whether a positive edge exists between two individuals, comparing models that use only positive edges with models using both signs.
- The models use logistic regression with directed-triad features computed from either positive-only or signed networks.
- 0.56 accuracy is achieved on Epinions and Slashdot using positive-edge features, while Wikipedia reaches almost 0.70.
- 0.59 accuracy is achieved on Epinions and Slashdot, and 0.71 on Wikipedia, when features include both positive and negative edges.
- Negative relationships can improve prediction of positive-edge existence, so positive and negative links should often be treated as inter-related.
6. CONCLUSION
The paper finds generalizable mechanisms in signed-link formation, connects them to balance and status theories, and shows that negative relationships can aid positive-link prediction. It also identifies future work on stronger models, local-global connections, and implicitly signed links.
- The study identifies sign-formation principles that generalize across multiple domains and connect to theories of balance and status.
- Sign-prediction methods significantly improve performance over previous approaches.
- All datasets show evidence for approximate global status ordering but essentially no evidence for global opposing factions, suggesting stronger local than global balance.
- Negative relationships can help predict positive edges, showing that the two link types may be inter-related.
- Future directions include better sign-prediction methods, stronger local-global connections, and studying relationships that are not explicitly tagged as positive or negative.