Method And System For Generating A Hyperlink-Click Graph

• US 20100125572A1
• Filed: 11/20/2008
• Published: 05/20/2010
• Est. Priority Date: 11/20/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Gionis, Aristides, Poblete, Barbara
• Granted Patent: US 7,945,565 B2
• Time in Patent Office: Days
• US Class Current: 707/722
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]

Abstract

A method of ascribing scores to web documents and search queries generates a hyperlink-click graph by taking the union of the hyperlink and click graphs, takes a random walk on the hyperlink-click graph, and associates the transition probabilities resulting from the random walk with scores for each of the documents and search queries.

Claims

1. A method of ascribing scores to each of a plurality of documents and each of a plurality of search queries, said method comprising using a processor to perform the steps of:

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 a hyperlink-click graph from the union of the hyperlink and click graphs, wherein;

each node 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; and

for each of the plurality of documents and search queries, associating a transition probability resulting from the random walk with a score.

2. The method of claim 1 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 the probability that the random walk will follow a link in the hyperlink graph;

β

is the rate at which the random walk switches between searching behavior and browsing behavior;

N_C is the row-stochastic version of

3. The method of claim 1 further comprising ranking the plurality of documents according to at least their scores.

4. The method of claim 3 wherein the ranked documents are used by a search engine to order search results.

5. The method of claim 1 further comprising, in response to a search engine receiving a search query:

determining a subset of the plurality of search queries, where the subset comprises search queries that are similar to the search query received by the search engine;

ranking the search queries comprising the subset according to at least their scores, and;

recommending at least one of the subset of search queries.

6. The method of claim 5 wherein said determining is informed by at least the hyperlink-click graph.

7. The method of claim 1 further comprising using information gleaned from the random walk to inform a spam-detection algorithm.

8. The method of claim 1 wherein said generating a hyperlink graph and said generating a click graph occur in parallel.

9. The method of claim 1 wherein said generating a hyperlink graph, said generating a click graph, and said generating a hyperlink-click graph occur in parallel.

10. A method of ascribing scores to each of a plurality of documents and each of a plurality of search queries, said method comprising using a processor to perform the steps of:

generating a hyperlink-click graph wherein;

each node corresponds either to one of the plurality of documents or to one of the plurality of search queries;

each directed edge corresponds to a relationship between two of the plurality of documents; and

each undirected edge corresponds to a relationship between one of the plurality of search queries and one of the plurality of documents, which document is associated with a search result related to the search query;

conducting a random walk on the hyperlink-click graph which accounts for browsing behavior and searching behavior;

for each of the plurality of documents and search queries, associating a transition probability resulting from the random walk with a score.

11. A system, comprising:

a click graph generator to generate, from a plurality of search queries and a first subset of a plurality of documents, a click graph representative of relationships between the plurality of search queries and the documents comprising the first subset of documents;

a hyperlink graph generator to generate, from a second subset of the documents, a hyperlink graph representative of relationships between the documents in the second subset;

a hyperlink-click graph generator to generate a hyperlink-click graph from the union of the hyperlink and click graphs, wherein;

each node 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; and

a random walker to;

conduct a random walk on the hyperlink-click graph which accounts for browsing behavior and searching behavior; and

associate, for each of the plurality of documents and search queries, a transition probability resulting from the random walk with a score.

12. A computer-readable medium encoded with a set of instructions which, when performed by a computer, perform 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 a hyperlink-click graph from the union of the hyperlink and click graphs, wherein;

each node 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; and

for each of the plurality of documents and search queries, associating a transition probability resulting from the random walk with a score.

13. The computer-readable medium of claim 12 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 the probability that the random walk will follow a link in the hyperlink graph;

β

is the rate at which the random walk switches between searching behavior and browsing behavior;

N_C is the row-stochastic version of

14. The computer-readable medium of claim 12 further comprising ranking the plurality of documents according to at least their scores.

15. The computer-readable medium of claim 14 wherein the ranked documents are used by a search engine to order search results.

16. The computer-readable medium of claim 12 further comprising, in response to a search engine receiving a search query:

determining a subset of the plurality of search queries, where the subset comprises search queries that are similar to the search query received by the search engine;

ranking the search queries comprising the subset according to at least their scores, and;

recommending at least one of the subset of search queries.

17. The computer-readable medium of claim 16 wherein said determining is informed by the hyperlink-click graph.

18. The computer-readable medium of claim 12 further comprising using information gleaned from the random walk to inform a spam-detection algorithm.

19. The computer-readable medium of claim 12 wherein said generating a hyperlink graph and said generating a click graph occur in parallel.

20. The computer-readable medium of claim 12 wherein said generating a hyperlink graph, said generating a click graph, and said generating a hyperlink-click graph occur in parallel.

21. A computer-readable medium encoded with a set of instructions which, when performed by a computer, perform a method of ascribing scores to each of a plurality of documents and each of a plurality of search queries, said method comprising:

generating a hyperlink-click graph wherein;

each node corresponds either to one of the plurality of documents or to one of the plurality of search queries;

each directed edge corresponds to a relationship between two of the plurality of documents; and

each undirected edge corresponds to a relationship between one of the plurality of search queries and one of the plurality of documents, which document is associated with a search result related to the search query;

conducting a random walk on the hyperlink-click graph which accounts for browsing behavior and searching behavior;

for each of the plurality of documents and search queries, associating a transition probability resulting from the random walk with a score.

22. A method of generating a hyperlink-click graph, wherein the hyperlink-click graph comprises a plurality of nodes, a plurality of directed edges, and a plurality of undirected edges, said method comprising using a processor to perform the step of:

taking the union of a hyperlink graph and a click graph, such that;

each resultant node corresponds either to one of a plurality of documents or to one of a plurality of search queries;

each resultant directed edge corresponds to a relationship between two of the plurality of documents; and

each resultant undirected edge corresponds to a relationship between one of a plurality of search queries and one of a plurality of documents, which document is associated with a search result related to the search query.