Reverse Top-k Search using Random Walk with Restart
With the increasing popularity of social networks, large volumes of graph data are becoming available. Large graphs are also derived by structure extraction from relational, text, or scientific data (e.g., relational tuple networks, citation graphs, ontology networks, protein-protein interaction graphs). Node-to-node proximity is the key building block for many graph-based applications that search or analyze the data. Among various proximity measures, Random Walk with Restart (RWR) is widely adopted because of its ability to consider the global structure of the whole network.