Predicting positive and negative links in online social networks

Jure LeskovecDaniel HuttenlocherJon Kleinberg

article2010WWW1,715 citations

Demonstrates how machine learning models can accurately predict friendly and antagonistic relationships across diverse online networks by leveraging classical social psychology theories of balance and status.

Listen

Online social platforms depend heavily on recommendation algorithms to suggest new connections, manage trust, and curate content. Most social network analyses exclusively study positive relationships, such as friendships or follows, ignoring negative attitudes like distrust, disapproval, or antagonism. Failing to account for negative ties introduces significant risks of recommending unwanted or adversarial connections to users, undermining user experience and trust. To resolve this, the article investigates how negative relationships interact with positive ties and evaluates whether the sentiment of a hidden link can be accurately inferred from the surrounding social network structure.

The article demonstrates a supervised machine-learning framework using logistic regression to predict whether a given relationship is positive or negative, while simultaneously testing fundamental social-psychology theories of structural balance and status. The researchers evaluated their approach across three diverse, large-scale online communities where users explicitly record positive and negative ties: Epinions (distrust and trust ratings), Slashdot (foe and friend tags), and Wikipedia (negative and positive promotion votes for administrator roles), spanning networks ranging from over 7,000 to nearly 120,000 nodes where positive links comprise roughly 77% to 85% of all connections.

The analysis yielded several critical findings. First, local structural features—specifically the user's incoming and outgoing link counts and the configuration of shared three-node triads—predict edge signs with high accuracy, achieving 90% to 95% accuracy on full datasets and error rates as low as roughly 6.6% on balanced benchmarks, significantly outperforming prior propagation methods. Second, the predictive models generalize remarkably well across platforms; models trained on Wikipedia, for example, accurately predict link sentiments on Slashdot and Epinions with almost no performance loss. Third, negative ties provide critical context for standard network tasks: incorporating negative link data boosted the accuracy of predicting latent positive relationships by up to a factor of 1.5 over random baseline guessing compared to using positive links alone. Finally, while local relationships reflect a mix of structural balance (such as shared allies) and status hierarchies, global network analysis reveals an approximate overarching status hierarchy (satisfying 80% to 85% of edges) but finds virtually no evidence of global division into two polarized factions.

These findings prove that positive and negative interactions are deeply intertwined and must be modeled together rather than treated as independent features. In practical social computing applications, organizations can leverage local network topology to reliably estimate user sentiment and filter out hostile recommendations without needing complex global analyses. However, decision-makers should note that prediction performance is lower on Wikipedia (around 80% accuracy) than on Epinions or Slashdot (over 92%), showing that public, high-stakes decisions depend more heavily on external qualitative information than casual social interactions do.

Stakeholders and platform designers should integrate negative edge data into recommender systems and community moderation tools to improve recommendation quality and avoid recommending antagonistic interactions. Teams seeking immediate baseline improvements can leverage simple heuristic rules based on out-degree or status differentials, though full triad-based models deliver superior precision. For future initiatives, organizations should invest in pilot programs to test sentiment-prediction algorithms on implicit sentiment data (such as textual interactions or unlabeled web links) and further investigate the theoretical bridge between local social dynamics and macroscopic network behavior.

Cornell University Stanford University social aspect social computing online communities edge sign prediction link prediction online social networks

arXiv: 1003.2429 snap-stanford/snap

Paper: The link prediction problem for social networks, David Liben-Nowell et al. (2003). This paper establishes the foundational topological proximity measures and evaluation framework for link prediction in social networks that the source builds upon for signed graphs.
Paper: Hierarchical structure and the prediction of missing links in networks, Aaron Clauset et al. (2008). This work introduces techniques for predicting missing links using hierarchical and structural network patterns, providing key conceptual foundations for network link estimation.
Paper: SimRank: a measure of structural-context similarity, Glen Jeh et al. (2002). This paper introduces structural-context similarity over graph topologies, which underpins the node-relation scoring mechanisms adapted in social network prediction.
Paper: Group formation in large social networks: membership, growth, and evolution, Lars Backstrom et al. (2006). This study analyzes how local triad structures and social neighbor connectivity drive tie formation, directly informing the structural balance and triad features used in the source paper.
Paper: Mining knowledge-sharing sites for viral marketing, Matthew Richardson et al. (2002). This research provides empirical grounding in online trust network datasets like Epinions that are subsequently leveraged to study signed positive and negative ties.

Paper: Link Prediction in Complex Networks: A Survey, Linyuan Lu et al. (2010). This comprehensive survey categorizes and contextualizes link prediction algorithms across complex networks, extending the specific findings of signed link classification into broader network theory.
Paper: Recommender systems with social regularization, Hao Ma et al. (2011). This paper applies signed and trust network relationships to regularize matrix factorization models for recommender systems.
Paper: A Three-Way Model for Collective Learning on Multi-Relational Data, Maximilian Nickel et al. (2011). This work generalizes the prediction of multiple relational edge types and link signs through collective tensor factorization.
Paper: Link Prediction Based on Graph Neural Networks, Muhan Zhang et al. (2018). This study advances link prediction beyond handcrafted heuristic and balance features by using graph neural networks to learn predictive patterns directly from enclosing subgraphs.
Paper: node2vec: Scalable Feature Learning for Networks, Aditya Grover et al. (2016). This work develops scalable representation learning methods that automatically learn low-dimensional feature vectors to predict edges and relationship properties in complex networks.
Paper: Graph Neural Networks for Social Recommendation, Wenqi Fan et al. (2019). This paper uses graph neural networks to integrate user opinion polarities and social network links to improve consumer rating predictions on datasets like Epinions.
Paper: KONECT: the Koblenz network collection, Jérôme Kunegis (2013). This paper establishes a large-scale repository and algebraic analysis suite for network graphs, formalizing signed and directed relationships across benchmark datasets.

Cover for Predicting positive and negative links in online social networks

Abstract

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.

Topics

social aspect social computing online communities network architecture social relations social network services social graphs cognitive science

Keywords

edge sign prediction link prediction online social networks social balance triad features common neighbors Wikipedia network

1 Introduction
2 Dataset Description
3 Predicting edge sign
3.1 A Machine-Learning Formulation
3.2 Connections to Theories of Balance and Status
3.3 Generalization across datasets
3.4 Heuristic Predictors
4 Global structure of signed networks
5 Predicting positive edges
6 Conclusion
References

Knowls

Knowl 1 — Local Feature Formulation and Logistic Regression for Edge Sign Prediction
model/method
The edge sign prediction problem requires inferring the hidden sign $s(u, v) \in \{-1, +1\}$ of a directed edge from node $u$ to node $v$ in a signed directed graph $G = (V, E)$ , using information from the rest of the network. A 23-dimensional feature representation $x = (x_1, \dots, x_{23})$ is extracted using only the local one-step neighborhood of the edge:
1. Degree Features (7 features):
  - $d_{\text{out}}^+(u)$ : number of positive outgoing edges from $u$ .
  - $d_{\text{out}}^-(u)$ : number of negative outgoing edges from $u$ .
  - $d_{\text{in}}^+(v)$ : number of positive incoming edges to $v$ .
  - $d_{\text{in}}^-(v)$ : number of negative incoming edges to $v$ .
  - Total out-degree: $d_{\text{out}}(u) = d_{\text{out}}^+(u) + d_{\text{out}}^-(u)$ .
  - Total in-degree: $d_{\text{in}}(v) = d_{\text{in}}^+(v) + d_{\text{in}}^-(v)$ .
  - Embeddedness $C(u, v)$ : number of common undirected neighbors $w$ linked by an edge in either direction to both $u$ and $v$ .
2. Triad Features (16 features): Counts of two-step paths connecting $u$ and $v$ via intermediate nodes $w$ . Each triad type is indexed as $[F|B][F|B][p|m][p|m]$ , encoding the direction (Forward $F$ or Backward $B$ ) and sign ( $p$ for $+1$ , $m$ for $-1$ ) of the edge between $u$ and $w$ , followed by the direction and sign of the edge between $w$ and $v$ . There are $2 \times 2 \times 2 \times 2 = 16$ distinct triad configurations.
The edge sign probability is estimated using a logistic regression model: $P(s(u, v) = +1 \mid x) = \frac{1}{1 + \exp\left(-\left(b_0 + \sum_{i=1}^{n} b_i x_i\right)\right)}$ where $b_0, \dots, b_n$ are regression coefficients fitted via maximum likelihood on training data.
Knowl 2 — Global Node Ordering in Status-Consistent Signed Tournaments
theoretical result
Let $G = (V, E)$ be a signed, directed tournament (a directed graph where every distinct pair of nodes is connected by exactly one directed edge with a positive or negative sign). Suppose every subset of three nodes in $G$ is status-consistent: that is, for every triple $\{u, v, w\}$ , there exists an assignment of distinct real status values $\sigma(u), \sigma(v), \sigma(w) \in \mathbb{R}$ such that every positive directed edge points from a node of lower status to higher status ( $s(x, y) = +1 \implies \sigma(x) < \sigma(y)$ ) and every negative directed edge points from higher status to lower status ( $s(x, y) = -1 \implies \sigma(x) > \sigma(y)$ ).

Theorem: If all sets of three nodes in $G$ are status-consistent, then there exists a global total ordering of the vertices $v_1, v_2, \dots, v_n$ such that:
1. Every positive directed edge $(v_i, v_j) \in E$ satisfies $i < j$ .
2. Every negative directed edge $(v_i, v_j) \in E$ satisfies $i > j$ .
Knowl 3 — Cartwright-Harary Structural Balance Theorem for Complete Signed Graphs
theoretical result
Let $G = (V, E)$ be a signed, undirected complete graph where every edge $e = \{u, v\}$ has sign $s(u, v) \in \{+1, -1\}$ . A triangle on vertices $u, v, w$ is balanced if the product of its three edge signs is positive ( $s(u, v) s(v, w) s(u, w) = +1$ ), meaning it has either 3 positive edges or 1 positive and 2 negative edges.

Theorem (Cartwright-Harary): If every triangle in a signed complete undirected graph $G$ is balanced, then the vertex set $V$ can be partitioned into two disjoint subsets $A$ and $B$ (where one subset may be empty) such that:
1. Every edge with both endpoints within $A$ is positive ( $s(u, v) = +1$ for all $u, v \in A$ ).
2. Every edge with both endpoints within $B$ is positive ( $s(u, v) = +1$ for all $u, v \in B$ ).
3. Every edge with one endpoint in $A$ and the other in $B$ is negative ( $s(u, v) = -1$ for all $u \in A, v \in B$ ).

Knowl 4 — Empirical Comparison of Global Balance vs. Global Status Structure

empirical result

To evaluate whether real online signed social networks exhibit global structural balance (partition into two opposing factions) or global status hierarchy (topological ordering where positive edges point forward and negative edges point backward), local search optimization heuristics were evaluated against two baseline models:

Permuted-signs baseline: Preserves graph topology while randomly shuffling edge signs.
Rewired-edges baseline: Preserves individual signed in- and out-degrees ( $d_{\text{in}}^+, d_{\text{in}}^-, d_{\text{out}}^+, d_{\text{out}}^-$ ) while randomizing edge endpoints.

Model / Baseline	Epinions	Slashdot	Wikipedia
Balance Partition (Fraction Satisfied)
Real Network	0.8344	0.8105	0.7809
Permuted Signs	0.8562	0.7779	0.7866
Rewired Edges	0.8993	0.8310	0.8316
Status Ordering (Fraction Satisfied)
Real Network	0.7905	0.8221	0.8538
Permuted Signs	0.7241	0.7568	0.7767
Rewired Edges	0.6377	0.6644	0.6321

Findings:

Balance: The fraction of edges satisfied by a 2-faction partition in real networks (78.1–83.4%) is no higher than the background rate of positive edges (~80%) and is lower than the rewired baseline (83.1–89.9%). Thus, signed social networks show no significant evidence of global 2-faction structural balance.
Status: The fraction of satisfied edges under a linear node ordering (79.1–85.4%) substantially exceeds the 50% expected by chance, the permuted baseline (72.4–77.7%), and the rewired baseline (63.2–66.4%), demonstrating strong evidence of global status hierarchy.

Knowl 5 — Triad Sign Predictions: Balance Theory, Status Theory, and Learned Regression Models

empirical result

Directed triads connecting target edge $(u,v)$ through intermediate node $w$ are compared across Structural Balance Theory, Status Theory, and empirical logistic regression weights across Epinions, Slashdot, and Wikipedia. Triad notation $[F|B][F|B][p|m][p|m]$ indicates edge directions ( $F$ : forward, $B$ : backward) and signs ( $p$ : $+1$ , $m$ : $-1$ ) along paths $u-w$ and $w-v$ .

Triad Type	Balance	Status	Epinions	Slashdot	Wikipedia
const	–	–	-0.1656	0.0180	-0.2150
FFpp	+1	+1	+0.4869	+0.8504	+0.2849
FFpm	-1	0	-0.5166	-0.9008	-0.4337
FFmp	-1	0	-0.4476	-1.0513	-0.3092
FFmm	+1	-1	-0.7331	-0.5874	-0.7680
FBpp	+1	0	+0.3416	+0.4385	+0.0544
FBpm	-1	+1	-0.0147	-0.1439	-0.0131
FBmp	-1	-1	-0.8598	-1.1887	-0.1986
FBmm	+1	0	+0.0436	-0.0719	-0.0325
BFpp	+1	0	+0.0814	+0.3593	+0.1160
BFpm	-1	-1	-1.3097	-1.0838	-0.3527
BFmp	-1	+1	-0.1228	-0.2480	+0.0527
BFmm	+1	0	+0.0788	-0.0240	-0.0968
BBpp	+1	-1	-0.0855	-0.0873	-0.0065
BBpm	-1	0	-0.0536	-0.2736	-0.0168
BBmp	-1	0	-0.0382	-0.2788	+0.0507
BBmm	+1	+1	-0.0242	+0.2275	-0.1616

Key Findings:

Failure of "Enemy of my Enemy": The empirical coefficient for $FFmm$ ( $u \to^- w \to^- v$ ) is strongly negative across all datasets ( $-0.7331, -0.5874, -0.7680$ ), directly contradicting balance theory ( $+1$ ) and supporting status theory ( $-1$ , as $u > w > v \implies u > v$ ).
Directional Asymmetry: Forward paths ( $FF$ ) and mixed paths ( $FBmp, BFpm$ ) have much higher coefficient magnitudes than backward paths ( $BB$ ).
Status Agreement on $BBpp$ : For $BBpp$ ( $u \leftarrow^+ w \leftarrow^+ v$ ), balance predicts positive, but status predicts negative ( $v > w > u \implies v > u$ ); the learned regression coefficient is negative across all three datasets.

Knowl 6 — Reduced 4-Dimensional Models for Balance and Status Theories

empirical result

To evaluate balance and status theories at their natural level of abstraction, 4-dimensional logistic regression models were trained on reduced feature sets:

Undirected Balance Model: Treats edges as undirected, counting common neighbors $w$ forming undirected triad sign pairs ( $pp, pm, mp, mm$ ).
Canonicalized Status Model: Reverses every negative edge $(x, y)$ to a positive edge $(y, x)$ with identical status interpretation, counting triads over relative status relations ( $u < w < v$ , $u > w > v$ , $u < w > v$ , $u > w < v$ ).

Model / Feature	Theory Sign	Epinions	Slashdot	Wikipedia
Undirected (Balance)
const	0	+0.4321	+1.4973	+0.0395
pp	+1	+0.0470	+0.0395	+0.0553
pm	-1	-0.1154	-0.2464	-0.1632
mp	-1	-0.2125	-0.3476	-0.1432
mm	+1	-0.0149	-0.0262	-0.0465
Canonicalized (Status)
const	0	-0.6873	-1.3915	-0.3039
$u < w < v$	+1	+0.1165	+0.0463	+0.0258
$u > w > v$	-1	-0.1002	-0.1140	-0.1941
$u < w > v$	0	+0.0572	+0.1558	+0.0300
$u > w < v$	0	-0.0064	+0.0382	+0.0543

Findings:

In the undirected model, learned weights strictly match balance theory for $pp$ , $pm$ , and $mp$ , but consistently assign negative weights to $mm$ . This supports Davis's weak balance theory, which excludes the $mm \to +1$ assumption.
In the canonicalized model, learned signs perfectly match status theory predictions for all status-determining configurations ( $u < w < v \implies +$ , $u > w > v \implies -$ ) across all three domains.

Knowl 7 — Cross-Dataset Generalization of Edge Sign Classifiers

data/table

Logistic regression models trained on 23 local features ( $All23$ ) and reduced 4-feature balance/status representations transfer across distinct social networks (Epinions, Slashdot, Wikipedia) with negligible loss in predictive accuracy. Evaluated on balanced test sets (50% positive, 50% negative) for edges with embeddedness $C(u, v) \ge 25$ .

Model	Training Dataset	Evaluation Dataset Accuracy
		Epinions	Slashdot	Wikipedia
All23	Epinions	0.9342	0.9289	0.7722
	Slashdot	0.9249	0.9351	0.7717
	Wikipedia	0.9272	0.9260	0.8021
BalanceLrn	Epinions	0.9027	0.9166	0.7319
	Slashdot	0.9020	0.9203	0.7439
	Wikipedia	0.8985	0.9145	0.7558
StatusLrn	Epinions	0.8313	0.7514	0.6410
	Slashdot	0.7682	0.7847	0.6094
	Wikipedia	0.7592	0.6598	0.7163

Insights:

The 23-feature model generalizes across domains: training on Wikipedia (where adminship votes are public and contentious) yields accuracy on Epinions (0.9272) and Slashdot (0.9260) comparable to within-dataset training (0.9342 and 0.9351).
Learned balance properties (BalanceLrn) generalize consistently across all three networks, whereas learned status properties (StatusLrn) show domain-specific degradation when evaluated out-of-domain.

Knowl 8 — Predicting Unobserved Positive Edges Using Negative Link Information

empirical result

The presence or absence of unobserved positive edges between node pairs $(a, b)$ can be predicted more accurately when information about negative edges is available. In a balanced binary classification task matching true positive edges $(a, b)$ with non-edges $(c, d)$ of identical embeddedness ( $C(a, b) = C(c, d)$ ):

Positive-only Model: Uses 4 features counting directed paths formed purely of positive edges ( $FFpp, FBpp, BFpp, BBpp$ ).
Positive and Negative Model: Uses 16 features counting all 16 directed signed triad types.

Results: Incorporating negative edges improves classification accuracy by 3.0 to 3.7 percentage points on Epinions and Slashdot, representing an approximate 50% relative increase in improvement over random guessing (baseline 0.50).

Knowl 9 — Heuristic Baselines for Signed Edge Prediction
algorithm
Four rule-based heuristic predictors determine baseline accuracy for predicting the sign $s(u, v) \in \{-1, +1\}$ of edge $(u, v)$ :
Input: Directed signed graph G = (V, E), edge (u, v)
Output: Predicted sign s_hat in {-1, +1}
Procedure BalanceHeuristic(u, v):
    pos_count = count of triads (u, w, v) balanced if s(u, v) = +1
    neg_count = count of triads (u, w, v) balanced if s(u, v) = -1
    if pos_count >= neg_count then return +1 else return -1
Procedure StatusHeuristic(u, v):
    sigma(u) = d_in^+(u) + d_out^-(u) - d_out^+(u) - d_in^-(u)
    sigma(v) = d_in^+(v) + d_out^-(v) - d_out^+(v) - d_in^-(v)
    if sigma(u) <= sigma(v) then return +1 else return -1
Procedure OutSignHeuristic(u):
    if d_out^+(u) >= d_out^-(u) then return +1 else return -1
Procedure InSignHeuristic(v):
    if d_in^+(v) >= d_in^-(v) then return +1 else return -1
Properties:
- The out-degree initiator heuristic (OutSign) substantially outperforms the in-degree recipient heuristic (InSign) on Epinions and Slashdot, demonstrating that the initiator's tendency to trust/distrust carries greater predictive signal than the target's popularity.
- Triad-based heuristics (Balance and StatusDifference) improve as embeddedness increases from 0 to 15, but their performance plateaus or declines at very high embeddedness due to sparsity in available triads.
Knowl 10 — Dataset Characteristics and Edge Sign Prediction Performance
empirical result
Edge sign prediction was evaluated across three online networks:
1. Epinions: Product review trust network (119,217 nodes, 841,200 edges, 85.0% positive).
2. Slashdot Zoo: User friend/foe tagging network (82,144 nodes, 549,202 edges, 77.4% positive).
3. Wikipedia RfA: Adminship election voting network (7,118 nodes, 103,747 edges, 78.7% positive).
Evaluation Protocol: 10-fold cross-validation on a balanced dataset formed by pairing each negative edge $(u,v)$ with a randomly sampled positive edge, yielding a random guessing baseline of 50.0% accuracy (or ~80% on the full unweighted dataset).

Prediction Performance by Feature Set (at embeddedness $C(u, v) \ge 25$ ):
- Epinions: Degree features achieve 88.55% accuracy (11.45% error rate); 16 triad features achieve 93.36% accuracy (6.64% error); all 23 features combined achieve 93.42% accuracy (6.58% error). This substantially outperforms the matrix-exponentiation propagation model of Guha et al. (lowest error 14.7%).
- Slashdot: All 23 features achieve 93.51% accuracy (AUC ~90% balanced, ~95% full dataset).
- Wikipedia: All 23 features achieve 80.21% accuracy. Wikipedia accuracy is noticeably lower across all models, reflecting the public, deliberative, and candidate-history-dependent nature of administrator elections.

Coverage note — None was omitted; all key contributions—including the 23-feature logistic regression framework, theoretical and empirical analyses of balance and status theories, global structure heuristics and theorems, cross-dataset transfer experiments, positive link prediction using negative edges, and baseline heuristics—are represented.

References

1.T. Antal, P. Krapivsky, and S. Redner. Social balance on networks. Physica D, 224(130), 2006.
2.M. J. Brzozowski, T. Hogg, and G. Szabó. Friends and foes: ideological social networking. In Proc. 26th CHI, 2008.
3.M. Burke and R. Kraut. Mopping up: Modeling wikipedia promotion decisions. In Proc. CSCW, 2008.
4.D. Cartwright and F. Harary. Structure balance: A generalization of Heider’s theory. Psych. Rev., 63, 1956.
5.M. Chudnovsky, P. Seymour, and B. D. Sullivan. Cycles in dense digraphs. Combinatorica, 28(1):1–18, 2008.
6.D. Cosley, D. Frankowski, S. B. Kiesler, L. G. Terveen, and J. Riedl. How oversight improves member-maintained communities. In Proc. 23rd CHI, pages 11–20, 2005.
7.J. A. Davis. Structural balance, mechanical solidarity, and interpersonal relations. Am. J. Soc., 68:444–462, 1963.
8.R. V. Guha, R. Kumar, P. Raghavan, and A. Tomkins. Propagation of trust and distrust. In Proc. 13th WWW, 2004.
9.V. Guruswami, R. Manokaran, and P. Raghavendra. Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In Proc. 49th IEEE FOCS, 2008.
10.Z. Gyöngyi, H. Garcia-Molina, and J. Pedersen. Combating web spam with trustrank. In VLDB ’04, 2004.
11.F. Heider. Attitudes and cognitive organization. J. Psych., 21:107–112, 1946.
12.S. D. Kamvar, M. T. Schlosser, and H. G. Molina. The eigentrust algorithm for reputation management in p2p networks. In Proc. 12th WWW, pages 640–651. ACM, 2003.
13.J. Kunegis, A. Lommatzsch, and C. Bauckhage. The Slashdot Zoo: Mining a social network with negative edges. In Proc. 18th WWW, pages 741–750, 2009.
14.C. Lampe, E. Johnston, and P. Resnick. Follow the reader: filtering comments on slashdot. In Proc. 25th CHI, 2007.
15.J. Leskovec, D. Huttenlocher, and J. Kleinberg. Signed networks in social media. In Proc. 28th CHI, 2010.
16.D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. J. Amer. Soc. Inf. Sci. and Tech., 58(7):1019–1031, 2007.
17.S. Marvel, S. Strogatz, and J. Kleinberg. Energy landscape of social balance. Physical Review Letters, 103, 2009.
18.P. Massa and P. Avesani. Controversial users demand local trust metrics: an experimental study on epinions.com community. In AAAI ’05, pages 121–126. AAAI Press, 2005.
19.M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167–256, 2003.
20.B. Pang and L. Lee. Opinion Mining and Sentinment Analysis. Number 2(1-2) in Foundations and Trends in Information Retrieval. Now Publishers, 2008.
21.P. Resnick and H. R. Varian. Recommender systems. Comm. ACM, 40(3):56–58, 1997.
22.M. Richardson, R. Agrawal, and P. Domingos. Trust management for the semantic web. In Intl. Semantic Web Conference, 2003.
23.S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge Univ. Pr., 1994.
24.F. Wu and B. A. Huberman. How public opinion forms. In Proc. 4th WINE, pages 334–341, 2008.
25.L. Xiong and L. Liu. Peertrust: supporting reputation-based trust for peer-to-peer electronic communities. IEEE Trans. Knowl. Data Engr., 16(7):843–857, 2004.

Citation

MLA

Leskovec, J., et al. “Predicting Positive and Negative Links in Online Social Networks”. WWW 2010: ACM WWW International Conference on World Wide Web, 2010, 2010, http://arxiv.org/abs/1003.2429v1.

APA

Leskovec, J., Huttenlocher, D., & Kleinberg, J. (2010). Predicting Positive and Negative Links in Online Social Networks. WWW 2010: ACM WWW International Conference on World Wide Web, 2010. http://arxiv.org/abs/1003.2429v1

Chicago

Leskovec, J., D. Huttenlocher, and J. Kleinberg. 2010. “Predicting Positive and Negative Links in Online Social Networks”. WWW 2010: ACM WWW International Conference on World Wide Web, 2010. http://arxiv.org/abs/1003.2429v1.

Harvard

Leskovec, J., Huttenlocher, D. and Kleinberg, J. (2010) “Predicting Positive and Negative Links in Online Social Networks”, WWW 2010: ACM WWW International conference on World Wide Web, 2010 [Preprint]. Available at: http://arxiv.org/abs/1003.2429v1.

Vancouver

1. Leskovec J, Huttenlocher D, Kleinberg J (2010) Predicting Positive and Negative Links in Online Social Networks. WWW 2010: ACM WWW International conference on World Wide Web, 2010

BibTeX

@article{leskovec2010predicting,
  title = {Predicting Positive and Negative Links in Online Social Networks},
  author = {Leskovec, Jure and Huttenlocher, Daniel and Kleinberg, Jon},
  year = {2010},
  journal = {WWW 2010: ACM WWW International conference on World Wide Web, 2010},
  url = {http://arxiv.org/abs/1003.2429v1},
  eprint = {1003.2429}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Feature Set	Epinions	Slashdot	Wikipedia
Positive edges only	0.5612	0.5579	0.6983
Positive and negative edges	0.5911	0.5953	0.7114

Predicting positive and negative links in online social networks

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Local Feature Formulation and Logistic Regression for Edge Sign Prediction

Knowl 2 — Global Node Ordering in Status-Consistent Signed Tournaments

Knowl 3 — Cartwright-Harary Structural Balance Theorem for Complete Signed Graphs

Knowl 4 — Empirical Comparison of Global Balance vs. Global Status Structure

Knowl 5 — Triad Sign Predictions: Balance Theory, Status Theory, and Learned Regression Models

Knowl 6 — Reduced 4-Dimensional Models for Balance and Status Theories

Knowl 7 — Cross-Dataset Generalization of Edge Sign Classifiers

Knowl 8 — Predicting Unobserved Positive Edges Using Negative Link Information

Knowl 9 — Heuristic Baselines for Signed Edge Prediction

Knowl 10 — Dataset Characteristics and Edge Sign Prediction Performance

References

Citation

BibTeX

Source Code

Access the Paper