Leskovec et al 2010

Online Version

An electronic version of this paper can be downloaded from here: [1]

Summary

In this paper, the authors study several problems of online social networks with both positive and negative connection links: 1) Sign Prediction: Infer the signs of edges that are unknown given the rest of the edges with known signs in the network; 2) Sign prediction in cross-datasets setting: Train the model proposed in 1) on one dataset, and test on another to evaluate the generalization performance of the algorithm; 3) Connections to theories of balance and status: Empirically evaluate the consistency between the learned models and social psychology theories of balance and status; 4) Predicting positive edges: Examine how given the negative edges could help improve prediction of positive edges. For edge sign prediction, a logistic regression classifier is applied to features of two classes, one based on the degrees of the nodes (degree features) and the other based on the joint relationships with third parties (triad features).

Results

There are three datasets used throughout the experiments: Epinions, Slashdot and Wikipedia. For all three datasets, the proportion of positive edges is ~80%, so the authors also create a balanced dataset with equal number of positive and negative edges using the methodology of Guha et al. Below are some key results from the experiments on the above 4 tasks:

1) Link prediction: When combining both classes of features, the learned models significantly outperform Guha et al. that uses a propagation model exploiting global properties. Another interesting result is that models trained using the triad features only do not perform as well as ones trained using degree features only.

2) Generalization across datasets: As it turns out, when applying the trained models to a different dataset, the performance does not decrease significantly, implying good generalization ability of their method.

3) Connections to theories of balance and status: At the local level, the learned models seem to be consistent with both balance and status theories, but this is not the case at the global level, where no significant evidence for balance theory is found.

4) Predicting positive edges: two cases are considered in this experiment, using only information about positive edges and using information about both positive and negative edges. Results on the three datasets show some significant improvement by incorporating also the information about negative edges.

Related Papers

R. V. Guha, R. Kumar, P. Raghavan, and A. Tomkins. Propagation of trust and distrust. In Proc. 13th WWW, 2004. This is one of the first papers that deals with both positive and negative links in a social network.

J. Leskovec, D. Huttenlocher, and J. Kleinberg. Signed networks in social media. In Proc. 28th CHI, 2010. This is an earlier work by the same authors on analyzing the balance and status theories in social media sites.

F. Heider. Attitudes and cognitive organization. J. Psych., 21:107–112, 1946. A very early paper on the theory of balance and status in social psychology.

Study Plan

• Read related material on balance and status theories.

• Further understand the network properties captured by the features used.