Green's function formulations for pagerank algorithm using helmholtz wave equation representations of internet interactions

• US 8,250,069 B2
• Filed: 10/14/2008
• Issued: 08/21/2012
• Est. Priority Date: 10/14/2008
• Status: Expired due to Fees

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Jandhyala, Vikram
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Mamillapalli, Pavan
• Application Number:
  US12/250,990
• Publication Number:
  US 20100094904A1
• Time in Patent Office: 1,407 Days
• Field of Search: 707/726, 707/748
• US Class Current: 707/726
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A novel approach to determining PageRank for web pages views the problem as being comparable to solving for an electromagnetic field problem. This view of ranking web pages enables appropriate entries for a matrix G of the web (or a subset), so that fast-solver techniques can be employed to iterate G, solving for ranks, or a dominant eigenstructure, achieving an O(N log N) performance in time and memory requirements. The specific solver technique that is used can be, for example, a fast multi-pole method (FMM), or a multilevel low-rank compression method. Once the problem is correctly formulated, it is not necessary to create the matrix G. Local information can be queried on demand by the solver. This approach can also be used to determine different scores of web pages, such as TrustRank, which is indicative of their trustworthiness.

Claims

1. A method for determining a score for each of a plurality of web pages, wherein the score of a web page relates to a predefined characteristic of the web page, comprising the steps of

(a) creating a directed graph that defines regions for at least a portion of a network, based on properties associated with the regions, wherein the web pages included in each region have the same score;

(b) determining the scores of the web pages in the regions of the directed graph using the Helmholtz equation; and

(c) physically carrying out at least one function selected from the group of functions consisting of;

(i) storing the scores of the web pages in a non-volatile storage;

(ii) displaying the scores of the web pages;

(iii) displaying a sequence of web pages in an order that is based upon the scores of the web pages included in the sequence;

(iv) displaying web pages in groups that are based upon the scores of the web pages in each group; and

(v) presenting to potential customers a rank ordering of web pages related to online services or products in response to a search by the potential customer.

2. The method of claim 1, wherein the step of determining the scores of the web pages comprises the step of accelerating the determination of the scores using the Helmholtz equation.

3. The method of claim 2, wherein the step of accelerating the determination of the scores using the Helmholtz equation comprises the steps of:

(a) setting up a mesh for the regions;

(b) setting up a compressed matrix for the mesh;

(c) iteratively solving the compressed matrix to obtain a value at each node of the directed graph, where nodes of the directed graph correspond to web pages; and

(d) normalizing the values that were obtained for the nodes to determine the scores of the web pages.

4. The method of claim 1, wherein the scores comprise one of PageRanks and TrustRanks for the web pages.

5. The method of claim 1, further comprising the step of determining scores that are specific to one item selected from the group consisting of a user, a domain, and a context, in regard to which the scores are being determined.

6. The method of claim 2, wherein the step of accelerating the determination of the scores using the Helmholtz equation comprises the step of employing a block decomposition of an associated Green'"'"'s function method of moments approach for determining the scores of the web pages.

7. The method of claim 1, further comprising the step of selecting a mesh for the directed graph and a basis function when solving for the scores of the web pages, wherein the mesh and the basis function determine a level of coarseness for the directed graph, and thereby a resolution in determining the scores of the web pages.

8. The method of claim 1, further comprising the step of adding a time varying term to the Helmholtz equation before determining the scores of the web pages.

9. A nontransitory memory medium on which machine readable and executable instructions are stored for use in determining a score for each of a plurality of web pages, wherein the score of a web page relates to a predefined characteristic of the web page, by performing the following:

(a) creating a directed graph that defines regions for at least a portion of a network, based on properties associated with the regions, wherein the web pages included in each region have the same score;

(b) determining the scores of the web pages in the regions of the directed graph using a Helmholtz equation; and

(c) physically carrying out at least one function selected from the group of functions consisting of;

(i) storing the scores of the web pages in a non-volatile storage;

(ii) displaying the scores of the web pages;

(iii) displaying a sequence of web pages in an order that is based upon the scores of the web pages included in the sequence;

(iv) displaying web pages in groups that are based upon the scores of the web pages in each group; and

(v) presenting to potential customers a rank ordering of web pages related to online services or products in response to a search by the potential customer.

10. The memory medium of claim 9, wherein the machine readable and executable instructions further cause an accelerated determination of the scores using the Helmholtz equation.

11. The memory medium of claim 10, wherein the machine readable and executable instructions cause the accelerated determination of the scores using the Helmholtz equation comprised by:

(a) setting up a mesh for the regions;

(b) setting up a compressed matrix for the mesh;

(c) iteratively solving the compressed matrix to obtain a value at each node of the directed graph, where nodes of the directed graph correspond to web pages; and

(d) normalizing the values that were obtained for the nodes to determine the scores of the web pages.

12. The memory medium of claim 9, wherein the scores comprise one of PageRanks and TrustRanks for the web pages.

13. A system for determining a score for each of a plurality of web pages, wherein the score of a web page relates to a predefined characteristic of the web page, comprising:

(a) a memory in which machine executable instructions are stored;

(b) a display device for displaying text and images; and

(c) a processor coupled to the memory and the display device, for executing the machine executable instructions, to carry out a plurality of functions, including;

(i) creating a directed graph that defines regions for at least a portion of a network, based on properties associated with the regions, wherein the web pages included in each region have the same score;

(ii) determining the scores of the web pages in the regions of the directed graph using a Helmholtz equation; and

(iii) physically carrying out at least one function selected from the group of functions consisting of;

(1) storing the scores of the web pages in the memory for subsequent use;

(2) displaying the scores of the web pages;

(3) displaying a sequence of web pages in an order that is based upon the scores of the web pages included in the sequence;

(4) displaying web pages in groups that are based upon the scores of the web pages in each group; and

(5) presenting to potential customers a rank ordering of web pages related to online services or products in response to a search by the potential customer.

14. The system of claim 13, wherein the machine executable instructions cause the processor to determine the scores by applying one or more acceleration techniques.

15. The system of claim 14, wherein the machine executable instructions accelerate the determination of the scores by implementing the following functions:

(a) setting up a mesh for the regions;

(b) setting up a compressed matrix for the mesh;

(c) iteratively solving for a value at each node of the compressed matrix of the directed graph, where nodes of the directed graph correspond to web pages; and

(d) normalizing the values that were obtained for the nodes to determine the scores of the web pages.

16. The system of claim 13, wherein the scores of the web pages comprise one of PageRanks and TrustRanks for the web pages.

17. The system of claim 13, wherein the machine executable instructions further cause the processor to determine scores that are specific to one selected from the group consisting of a user, a domain, and a context.

18. The system of claim 14, wherein the machine executable instructions cause the processor to accelerate the determination of the scores of the web pages by employing a block decomposition of an associated Green'"'"'s function method of moments approach.

19. The system of claim 13, wherein the machine executable instructions cause the processor to select a mesh for the directed graph and a basis function when solving for the scores of the web pages, wherein the mesh and the basis function determine a level of coarseness for the directed graph, and thereby a resolution in determining the scores of the web pages.

20. The system of claim 13, wherein the machine executable instructions cause the processor to add a time varying term to the Helmholtz equation before determining the scores of the web pages.