Leskovecl et al., 2010,Predicting Positive and Negative Linksin Online Social Networks
Contents
Online version
An online version of this paper is available here.
Summary
Machine learning has previously been used as a way of Determining Social Network Attributes. This paper follows this path and addresses a sub-problem: predicting negative links in social networks. Certain social networks allow you to express negative relations with other users, such as Slashdot (foes), Epinions (distrust) and Wikipedia (voting down). This paper introduces ways of predicting these negative relations, and propose explanations for the models that are based on psychology theory. Finally, they use a SlashDot dataset, which contains "friends" and "foes" tag to evaluate the quality of their approach. They also use Wikipedia and Epinions to further validate their model.
Key Contributions
Ways of predicting negative relations in social networks.
Background
The authors refer to two main theories that have been proposed in psychology to explain the possible causes of negative links: balance and status. Balance is a concept that includes transitional relationships (e.g., "the friend of my friend is my friend"), as well as other variants (e.g., "the friend of my enemy is my enemy"). This balance might explain how negative links are created in social networks (e.g., especially if relationships are public). The concept of status is that every human conceives other humans as having either a higher or lower status. Such idea can be represented with (u,v) links, where the existence of such links means that u considers v of higher status. Once again, these status relations might influence the characterization of "friend" or "enemy" (e.g., one prefers to be friend with another of higher status).
Models
Logistic Regression
The task of predicting edge sign (positive or negative) is accomplished by a logistic regression model that uses the following features:
- signed degree of a node (i.e., how many positive edges it has)
- "type" of triads formed by (u,v and w) in a way that the node w has an edge to both u and v. For example, a negative/negative relations exists if w foe with both u and v (thus u and v might be friends, as explained below). There are 16 types of such triads.
Experiments and Evaluation
The model is compared to a random approach, where positive and negative are randomly selected. For this approach to be valid, the authors sample from the SlashDot dataset to obtain 50% of positive and negative. The effects of the different features on the logistic regression are shown in the following results graph:
Source: the original paper
In this graph, A corresponds to predicting Epinions "distrust" relationships, B corresponds to SlashDot "foes" relationship and C corresponds to a user voting down another user for adminship in Wikipedia. The results indicate that it is possible to predicting the polarity of a link with high accuracy compared to a random baseline. This results seems to generalize to multiple dataset.
