1. A method for processing a random-walk based vertex-proximity query on a graph, wherein the method comprises: dividing a graph into multiple clusters that are estimated to contain a random walk for a duration of time; computing meta-information related to the random walk inside each of the multiple clusters from the graph; dynamically updating the multiple clusters and corresponding meta-information upon modification of the graph; and identifying a subset of one or more clusters from the multiple updated clusters that are relevant to a query vertex and aggregating corresponding meta-information to process the query by computing a stationary distribution of the random walk from the query vertex; wherein at least one of the steps is carried out by a computer device.