Patent ID: 7949661

Claim:
A method comprising: accessing, by one or more computing devices, a graph comprising a seed set of vertices representing a seed set of web pages, and a non-seed set of vertices representing a non-seed set of web pages; assigning, by the one or more computing devices, a non-zero probability to each vertex in the seed set of vertices, and a zero probability to each vertex in the non-seed set of vertices; determining, by the one or more computing devices, T sequences of probability distribution, denoted as p 1 , . . . , p T , where T≧1, by iteratively performing a one-step random walk to move probabilities from p t−1 to p t , where 2≦t≦T; determining, by the one or more computing devices, a level set of vertices with a least conductance for each of the T sequences of probability distribution, p t , where 1≦t≦T, comprising: sorting the seed set of vertices and the non-seed set of vertices together in descending order according to their respective probabilities from p t to obtain a sorted set of vertices; selecting, from the sorted set of vertices, J top-ranked vertices, where J≧1; constructing J level sets of vertices, denoted as v 1 , . . . , v J , using the J top-ranked vertices; computing a conductance for each of the J level sets of vertices, v j , where 1≦j≦J; and selecting, from the J level sets of vertices, one level set of vertices having the least conductance as the level set of vertices with the least conductance for p t ; and selecting, by the one or more computing devices, from T level sets of vertices determined for the T sequences of probability distribution respectively, one level set of vertices having the least conductance as a set of vertices representing a community of web pages identified from the seed set of web pages.