Random Walk with Restart in Large Graphs

PhD Qualifying Examination


Title: "Random Walk with Restart in Large Graphs"

by

Miss Dandan LIN


Abstract:

The Random Walk with Restart (RWR) algorithm has attracted considerable 
concerns in recent years due to its powerful ability of measuring the node 
proximity in the graph which has been widely recognized as one of the 
fundamental problems in computer science. An efficient proximity 
measurement is required for a huge number of applications, such as the 
link prediction and the image segmentation. Unfortunately, given a graph 
with n nodes, using the RWR algorithm to compute the exact node proximity 
takes O(n^3) time because the solution is based on the computation of a 
matrix inversion, which is extremely expensive when n is large. Extensive 
studies have been conducted for improving the online querying efficiency.

This survey broadly reviews the state-of-the-art works, all of which are 
based on one of the three basic methods: (1) the iterative method, (2) the 
matrix-inversion method and (3) the Monte Carlo method. In addition, in 
order to improve the online querying efficiency, most of the reported 
methods construct indexes which pre-store intermediate results computed in 
the preprocessing phase. In this survey, we give detailed comparisons 
among existing methods in terms of time complexity, index size, error 
bound, strengths and weaknesses.


Date:			Tuesday, 25 April 2017

Time:                  	1:30pm - 3:30pm

Venue:                  Room 5564
                        Lifts 27/28

Committee Members:	Dr. Raymond Wong (Supervisor)
 			Prof. Dik-Lun Lee (Chairperson)
 			Prof. Dit-Yan Yeung
 			Dr. Wei Wang


**** ALL are Welcome ****