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. ACM 978-1-60558-799-8/10/04. fundamental question is then the following: How does the sign of a given link interact with the pattern of link signs in its local vicinity, or more broadly throughout the network? Moreover, what are the plausible configurations of link signs in real social networks? Answers to these questions can help us reason about how negative relationships are used in online systems, and answers that generalize across multiple domains can help to illuminate some of the underlying principles. Effective answers to such questions can also help inform the design of social computing applications in which we attempt to infer the (unobserved) attitude of one user toward another, using the positive and negative relations that have been observed in the vicinity of this user. Indeed, a common task in online communities is to suggest new relationships to a user, by proposing the formation of links to other users with whom one shares friends, interests, or other properties. The challenge here is that users may well have pre-existing attitudes and opinions -both positive and negative -towards others with whom they share certain characteristics, and hence before arbitrarily making such suggestions to users, it is important to be able to estimate these attitudes from existing evidence in the network. For example, if A is known to dislike people that B likes, this may well provide evidence about A's attitude toward B. Edge Sign Prediction. With this in mind, we begin by formulating a concrete underlying task -the edge sign prediction problem -for which we can directly evaluate and compare different approaches. The edge sign prediction problem is defined as follows. Suppose we are given a social network with signs on all its edges, but the sign on the edge from node u to node v, denoted s(u, v), has been "hidden." How reliably can we infer this sign s(u, v) using the information provided by the rest of the network? Note that this problem is both a concrete formulation of our basic questions about the typical patterns of link signs, and also a way of approaching our motivating application of inferring unobserved attitudes among users of social computing sites. There is an analogy here to the link prediction problem for social networks [16] ; in the same way that link prediction is used to to infer latent relationships that are present but not recorded by explicit links, the sign prediction problem can be used to estimate the sentiment of individuals toward each other, given information about other sentiments in the network. In studying the sign prediction problem, we are following an experimental framework articulated by Guha et al. in their study of trust and distrust on Epinions [8] . We extend their approach in a number of directions. First, where their goal was to evaluate propagation algorithms based on exponentiating the adjacency matrix, we approach the problem using a machine-learning framework that enables us to evaluate which of a range of structural features are most informative for the prediction task. Using this framework, we also obtain significantly improved performance on the task itself.
Leskovec et al. REF first introduce status theory and balance theory to predict positive or negative link in signed networks.
Predicting positive and negative links in online social networks
WWW '10
Mathematics Computer Science Physics