Difference between revisions of "Leskovecl et al., 2010,Predicting Positive and Negative Linksin Online Social Networks"

From Cohen Courses
Jump to navigationJump to search
Line 13: Line 13:
 
== Models ==
 
== Models ==
  
−
=== Logistic Regression ===  
+
=== [[UsesMethod:: Logistic Regression]] ===  
−
The above continuous model isn't truly continuous has it has to be simulated using increment on the variable t.  This process requires long run time for testing.  For this reason, the authors present a discrete time model which assumes that the probability of a user influencing his neighbors his constant over a certain window of time after an action.
+
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 ==
 
== Experiments and Evaluation ==
  
−
The different models are evaluated with a ROC curve with true positive rate and false positive rate varying for different threshold values. The threshold value controls how much influence a user need to have from his neighbors in order to do the action (e.g., join a group).  The result show that the static model fail to perform as well as the two temporally aware models, which probably indicates that influence does vary over time in social networks.  Also, although discrete and continuous time models show similar performance, the discrete model has a faster run time.
+
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:
  
−
[[File:Result_learning_influence_probabilities.jpg]] Source: the original paper
+
[[File:Result_predicting_negative.jpg]] Source: the original paper

Revision as of 00:24, 25 March 2011

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 to evaluate the quality of their approach.

Key Contributions

Ways of predicting negative relations in social networks.

Models

Logistic Regression

The task of predicting edge sign (positive or negative) is accomplished by a logistic regression model that uses the following features:

  1. signed degree of a node (i.e., how many positive edges it has)
  2. "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:

File:Result predicting negative.jpg Source: the original paper

Retrieved from "http://curtis.ml.cmu.edu/w/courses/index.php?title=Leskovecl_et_al.,_2010,Predicting_Positive_and_Negative_Linksin_Online_Social_Networks&oldid=4471"