Patent ID: 7945565

Claim:
A method of ascribing scores to each of a plurality of documents and each of a plurality of search queries, said method comprising: generating, from the plurality of search queries and a first subset of the plurality of documents, a click graph representative of relationships between the plurality of search queries and the documents comprising the first subset of documents; generating, from a second subset of the documents, a hyperlink graph representative of relationships between the documents in the second subset; generating, by using computer, a hyperlink-click graph from union of hyperlink graph and click graph, wherein: each node of the hyperlink-click graph corresponds either to one of the plurality of documents or one of the plurality of search queries; each directed edge between documents corresponds to the relationships defined in the hyperlink graph; and each undirected edge between documents and search queries corresponds to the relationships defined in the click graph; conducting a random walk on the hyperlink-click graph which accounts for browsing behavior and searching behavior; wherein a transition-probability matrix P HC for the random walk is given by: P HC =αβN c +α(1−β)N H +(1−α)1, where α is a probability that the random walk follows a link in the hyperlink graph; β is a rate at which the random walk switches between searching behavior and browsing behavior; N c is a row-stochastic version of A C ′ = ( A C 0 0 A C T ) , where A c is an M×N matrix, whose: M rows correspond to the plurality of search queries; N columns correspond to the first subset of documents; and each entry has a value associated with the number of clicks between the entry's corresponding search query and the entry's corresponding document; N H is a row-stochastic version of A H , where A H is an (M+N)×(M+N) matrix where all rows corresponding to search queries are zeroes; and 1=1 c where 1 c is an (M+N)×(M+N) matrix in which each entry has a value of 1/(M+N); and for each of the plurality of documents and search queries, associating a transition probability resulting from the random walk with a score.