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

From Cohen Courses
Jump to navigationJump to search
(Created page with '== Online version == An online version of this paper is available at the [[http://portal.acm.org/ft_gateway.cfm?id=1718518&type=pdf&CFID=7653019&CFTOKEN=17876787 ACM digital lib…')
 
Line 1: Line 1:
 
== Online version ==
 
== Online version ==
  
−
An online version of this paper is available at the [[http://portal.acm.org/ft_gateway.cfm?id=1718518&type=pdf&CFID=7653019&CFTOKEN=17876787 ACM digital library]].
+
An online version of this paper is available [http://arxiv.org/PS_cache/arxiv/pdf/1003/1003.2429v1.pdf here].
  
 
== Summary ==
 
== Summary ==
  
−
[[AddressesProblem::Influence propagation]] in social networks has interesting applications, especially for viral marketing.  Most past studies assume as input a graph with nodes for each person, and weighted edges between the nodes if there is influence between the two persons. However, less attention has been put on how to build this graph using social media data. This [[Category::paper]] introduces a model of influence built using social graph data on one hand, and a log of action (e.g., joining a community) on the other hand. The model is validated on the [[UsesDataset::Flick dataset]], which consists in a social graph with 1.3M nodes/40M edges and action log of 300K distinct actions.  They propose and evaluate both static and dynamic models for this problem, and show that the influence of users on others (e.g., influence another user to join a group) can be modeled with a high accuracy.
+
Machine learning has previously been used as a way of [[AddressesProblem::Determining Social Network Attributes]].  This [[Category::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 [[UsesDataset::SlashDot dataset]] to evaluate the quality of their approach.
  
 
== Key Contributions ==
 
== Key Contributions ==
  
−
The biggest contribution claimed by the authors in this paper is the empirical evidence of influence in social networks using a discrete time model.
+
Ways of predicting negative relations in social networks.
  
 
== Models ==
 
== Models ==
  
−
=== Static Model ===
+
=== Logistic Regression ===  
−
Everytime a user tries to activate (i.e. influence) his neighbor, he has a probability Pi of succeeding.  This can be modeled using a Bernouilli distribution.
 
−
 
 
−
=== Continuous Time ===
 
−
The previous model neglect the variation over time of the influence users have on each others.  For this reason, Goyal et al, present a continuous time model where the probability of a user influencing a neighbor depends on a time t variable (e.g., similar to an exponential decay model).
 
−
 
 
−
=== Discrete Time ===
 
 
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 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.
  

Revision as of 00:09, 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 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.

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.

Result learning influence probabilities.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=4469"