System and method for rapid computation of PageRank

• US 20030204502A1
• Filed: 04/25/2002
• Published: 10/30/2003
• Est. Priority Date: 04/25/2002
• Status: Active Grant

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Tomlin, John Anthony, Arasu, Arvind, Tomkins, Andrew S.
• Granted Patent: US 7,089,252 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 17/12 Simultaneous equations , e.g. systems of linear equations
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method of ranking a plurality of linked documents. The method comprises obtaining a plurality of documents, and determining a rank of each document. The rank of each document is generally a function of a rank of all other documents in the plurality of documents which point to the document and is determined by solving, by equation-solving methods (including Gauss-Seidel iteration and partitioning) of a set of equations wherein: $x_i=\left(1-\alpha \right)+\alpha \sum _j^{}a_{\mathrm{ij}}x_j,$

where x_i is the rank of the page indexed by i, α is a number strictly between 0 and 1.0, the summation is over all indices j such that page j points to page i, and a_ij is defined to be the reciprocal of the number of links pointing out from page j (denoted d_j) if page j points to page i, and zero otherwise.

Claims

1. A method of ranking a plurality of linked documents, the method comprising the steps of:

obtaining a plurality of documents;

determining a rank of each document, the rank of each document being a function of a rank of all other documents in the plurality of documents which point to the document, wherein the rank of each document is determined by the solution of a set of equations wherein;

$x_i=\left(1-\mathrm{\alpha <br><br>}\right)+\mathrm{\alpha <br><br>}<br><br>\underset{\text{\hspace{1em}<br><br>}<br><br>j}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>a_{\mathrm{ij}}<br><br>x_j$

and where x_i is the rank of the page indexed by i, α

is a number strictly between 0 and 1.0, the summation is over all indices j such that page j points to page i, and a_ij is defined to be the reciprocal of the number of links pointing out from page j (denoted d_j) if page j points to page i, and zero otherwise.

2. The method of claim 1 wherein the solution of the set of equations is represented in matrix form as:

χ

=(1−

α

)e+α

Aχ

wherein A is the matrix [a_ij], e is a vector of 1'"'"'s and ξ

is the vector of x_i values.

3. The method of claim 1 wherein the rank of each document is determined by Gauss-Seidel iteration wherein a rank vector at each iteration is defined by

4. The method of claim 1 wherein the rank of each document is determined by Successive Over-Relaxation using a relaxation parameter ω

, wherein a rank vector at each iteration is defined by

5. A method for determining a ranking of each page in a network of linked pages, some pages being linked to other pages and at least some pages being linking pages or a combination thereof, the method comprising the steps of:

obtaining a plurality of pages from a web based structure comprising a plurality of input segments I with input nodes P, a plurality of output segments O with output nodes Q, a plurality of strongly connected segments S connected to both the input segments and output segments, and nodes T interconnecting the input and output segments;

forming a matrix structure defined by;

$A=\left(\begin{array}{cccccc}P& \text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}& A_{\mathrm{P1}}& \text{\hspace{1em}<br><br>}\\ \text{\hspace{1em}<br><br>}& O& A_{\mathrm{OS}}& A_{\mathrm{OT}}& \text{\hspace{1em}<br><br>}& A_{\mathrm{OQ}}\\ \text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}& S& \text{\hspace{1em}<br><br>}& A_{\mathrm{SI}}& \text{\hspace{1em}<br><br>}\\ \text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}& T& A_{\mathrm{TI}}& \text{\hspace{1em}<br><br>}\\ \text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}& I& \text{\hspace{1em}<br><br>}\\ \text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}& Q\end{array}\right)$

and partitioning the matrix in order to solve for the rank via a sequence of smaller systems of equations.

6. The method of claim 5 wherein the rank vector χ

is defined by χ

^T=(χ

_P^T,χ

_O^T,χ

_S^T,χ

_T^T,χ

_I^T,χ

_Q^T).

7. The method of claim 5 wherein the rank vector χ

is determined by determining the sequence of equations comprising;

(I−

α

Q)χ

_Q=(1−

α

)e and (I−

α

I)χ

_I=(1−

α

)e;

(I−

α

S)χ

_S=(1−

α

)e+α

A_SIχ

_I and (I−

α

T)χ

_T=(1−

α

)e+α

A_TIχ

_I; and

(I−

α

O)χ

_O=(1−

α

)e+A<sub>OSχ

S</sub>+α

A_oQχ

_Q.

8. The method of claim 7 wherein the equations (I−

α

Q)χ

_Q=(1−

α

)e and (1−

α

I)χ

_I=(1−

α

)e are solved in order.

9. The method of claim 7 wherein the equations (I−

α

Q)χ

_Q=(1−

α

)e and (I−

α

I)χ

_I=(1−

α

)e are solved in parallel.

10. The method of claim 7 wherein the equations (I−

α

S)χ

_S=(1−

α

)e+α

A_SIχ

_I and (I−

α

T)χ

_T=(1−

α

)e+α

A_TIχ

_I are solved in order or in parallel.

11. The method of claim 7 wherein the equation (I−

α

O)%χ

_O=(1−

α

)e+α

A<sub>OSχ

S</sub>+α

A_OTχ

_T+α

A_oQχ

_Q is resolved after a rank vector χ

_I is computed.

12. A computer program product comprising:

a computer useable medium having computer readable code means embodied therein for causing a computer to calculate a static ranking of web pages with a matrix equation, the computer readable code means in the computer program product comprising;

a computer useable medium having computer readable code means embodied therein for causing a computer to solve for a rank by an iterative solution of equations defined by χ

=(1−

α

)e+α

Aχ

.

13. The computer program product of claim 12 further comprising computer readable program code means for causing a computer to resolve the solution with a Gauss-Seidel iteration wherein a rank vector at each iteration is defined by the equation

14. The computer program product of claim 12 further comprising computer readable program code means for causing a computer to resolve the solution by Successive Over-Relaxation using a relaxation parameter ω

, wherein a rank vector at each iteration is defined by

15. An article of manufacture comprising:

a computer useable medium having computer readable program code means embodied therein for causing a computer to determine a ranking of a document in a plurality of linked document, the computer readable code means in the article of manufacture comprising;

computer readable program code means for causing a computer to obtain a plurality of documents for a network;

computer readable program code means for causing a computer to determine a rank of each document in the plurality of document, wherein the rank of each document being a function of a rank of all other documents in the plurality of documents which point to the document, wherein the rank of each document is determined by the solution of a set of equations wherein;

$x_i=\left(1-\mathrm{\alpha <br><br>}\right)+\mathrm{\alpha <br><br>}<br><br>\underset{j}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>a_{\mathrm{ij}}<br><br>x_j$

and where x_i is the rank of the page indexed by i, α

is a number strictly between 0 and 1.0, the summation is over all indices j such that page j points to page i, and a_ij is defined to be the reciprocal of the number of links pointing out from page j (denoted d_j) if page j points to page i, and zero otherwise.