Random walk with restart
From Cohen Courses
Jump to navigationJump to searchThis is a technical method discussed in Social Media Analysis 10-802 in Spring 2010.
What problem does it address
Given a weighted graph, its often asked "how closely related are two nodes in a graph?". Random walk with restart (RWR) provides a good relevance score between two nodes in a weighted graph.
Algorithm
- Input -
A : Adjecency matrix
q : Query node
c : probability of restarting the random walk from node q
- Output - u : steady state probability vector
- Let v = query vector where all 0 except qth node = 1
- A = Column_Norm(A) i.e. Normalize A such that each column sums to 1
- Intialize u = v
- while (u has not converged)
u = (1-c)*A*u + c*v
There are many possible convergence criteria. e.g delta(norm(u)) < 1e-9
Used in
This technique is widely used practice. e.g personalized pagerank, automatic image captioning etc.
