19-06-2013, 12:30 PM
Link Prediction
Link Prediction.pdf (Size: 1.01 MB / Downloads: 127)
Problem Definition
Given a snapshot of a social network at time t (or network
evolution between t1 and t2), we seek to accurately predict the
edges that will be added to the network during the interval
from time t (or t2) to a given future time t'.
Applications
Accelerating a mutually beneficial professional- or
academic connection that would have taken longer
to form serendipitously (Farrell et al, 2005).
Link Completion
Goldenberg et al, 2003
Links can be incomplete.
Links can link more than two entities.
Given a node (or nodes) that is (are) known to have
a link, the task is to determine to which other node
the link is attached.
Anomalous Link Discovery
Rattigan et al, 2005.
Link Prediction: Number of Dyads to be evaluated
increases quadratically.
Networks are sparse extremely few positive
cases.
Focus on discovering surprising links in the existing
ones.
Very few common neighbors, or too distant apart.
Role of RMN
Define a single probabilistic model over the entire link
graph
Train model to maximize the probability of the (object
and) link labels given the known attributes
Use probabilistic inference to predict and classify links
using any observed attributes and other links.
Learning in RMN
To get clique potentials, we need to estimate the
feature weights (w)
Any particular setting for w fully specifies a
probability distribution P on training w data
Use gradient descent over w to find the weight
setting that maximizes the likelihood (ML) of
the link existence given other attributes