Method and system for generating a hyperlink-click graph

• US 7,945,565 B2
• Filed: 11/20/2008
• Issued: 05/17/2011
• 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: Poblete, Barbara, Gionis, Aristides
• Primary Examiner(s): Truong; Cam Y T
• Application Number:
  US12/275,155
• Publication Number:
  US 20100125572A1
• Time in Patent Office: 908 Days
• Field of Search: None
• 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:

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

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

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

4. 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.

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

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

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

8. 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.

9. A method of ascribing scores to each of a plurality of documents and each of a plurality of search queries, said method comprising:

generating, by using a computer, a hyperlink-click graph wherein;

each node of the hyperlink-click graph 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, each document is associated with a search result related to search query;

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-click graph, representative of a relationship between documents of the plurality of documents;

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

N_c is a row-stochastic version of

10. A system, comprising:

a processor;

one or more non-transitory computer-readable media;

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 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; 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;

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

11. A non-transitory computer-readable medium encoded with a set of instructions which, when performed by a computer, cause the computer to perform steps of ascribing scores to each of a plurality of documents and each of a plurality of search queries, said steps 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 union of hyperlink graph and click graph, wherein;

each node of 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

12. The non-transitory computer-readable medium of claim 11, wherein the set of instructions further comprises instructions which, when performed by the computer, cause the computer to perform the step of ranking the plurality of documents according to at least their scores.

13. The non-transitory computer-readable medium of claim 12 wherein the ranked documents are used by a search engine to order search results.

14. The non-transitory computer-readable medium of claim 11, wherein the set of instructions further, comprises instructions which, when performed by the computer in response to a search engine receiving a search query, cause the computer to perform the steps of:

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.

15. The non-transitory computer-readable medium of claim 14 wherein said step of determining is informed by the hyperlink-click graph.

16. The non-transitory computer-readable medium of claim 11, wherein the set of instructions further comprises instructions which, when performed by the computer, cause the computer to perform the step of using information gleaned from the random walk to inform a spam-detection algorithm.

17. The non-transitory computer-readable medium of claim 11 wherein said steps of generating a hyperlink graph and generating a click graph occur in parallel.

18. The non-transitory computer-readable medium of claim 11 wherein said steps of generating a hyperlink graph, generating a click graph, and generating a hyperlink-click graph occur in parallel.

19. A non-transitory computer-readable medium encoded with a set of instructions which, when performed by a computer, cause the computer to perform steps of ascribing scores to each of a plurality of documents and each of a plurality of search queries, said steps comprising:

generating a hyperlink-click graph wherein;

each node of hyperlink-click graph 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 a search query;

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-click graph, representative of a relationship between documents of the plurality of documents;

β

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

N_c is a row-stochastic version of

20. A method of generating and using 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 the steps of:

taking a 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, each document is associated with a search result related to a search query;

conducting, by using a computer, a random walk on the union of the hyperlink graph and the 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 the probability that the random walk follows a link, in the union of the hyperlink graph and the click graph, representative of a relationship between documents of the plurality of documents;

β

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

N_c is the row-stochastic version of

21. A non-transitory computer-readable medium encoded with a set of instructions for generating and using 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, wherein the set of instructions when executed by a computer cause the computer to perform steps comprising:

taking a 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, each document is associated with a search result related to a search query;

conducting a random walk on the union of the hyperlink graph and the 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 union of the hyperlink graph and the click graph, representative of a relationship between documents of the plurality of documents;

β

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

N_c is a row-stochastic version of