Patent Document ID: 8903824
Application ID: 13315415

Base Claim:
1. A method for processing a random-walk based vertex-proximity query on a graph, wherein the method comprises: dividing a graph of vertices into multiple clusters that are each estimated to contain a random walk for a duration of time, wherein said dividing comprises dividing the graph of vertices into multiple clusters based on a conductance value computed for each of the multiple clusters, and wherein the conductance value for each of the multiple clusters is defined as ϕ ⁡ ( S ) =  ∂ ( S )  min ⁢ { VOL ⁡ ( S ) , VOL ⁡ ( S _ ) } ∈ [ 0 , 1 ] , wherein ⁢ ⁢ VOL ⁡ ( S ) = ∑ v ∈ S ⁢ ⁢ d v wherein d v denotes the degree of vertex v and ∂(s) denotes the set of edges with exactly one end-point in cluster S; computing meta-information for each of the multiple clusters, wherein the meta-information is 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; identifying a subset of one or more clusters from the multiple updated clusters that are relevant to a query vertex; and processing a nearest-neighbor query on the subset of one or more identified clusters by: pre-computing an intra-cluster random walk for each of the multiple clusters prior to the nearest-neighbor query; identifying the pre-computed intra-cluster random walk for each cluster in the subset of one or more identified clusters subsequent to the nearest-neighbor query; and computing a stationary distribution of an inter-cluster random walk across the subset of one or more identified clusters starting from the query vertex subsequent to the nearest-neighbor query, wherein said computing the stationary distribution of the inter-cluster random walk comprises combining the computed intra-cluster random walk for each cluster in the subset of one or more identified clusters; wherein at least one of the steps is carried out by a computer device.

---

Claim 5:
5. The method of claim 1 , wherein the graph is weighted.