System and method for rapid computation of PageRank
First Claim
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;
and where xi 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 aij is defined to be the reciprocal of the number of links pointing out from page j (denoted dj) if page j points to page i, and zero otherwise.
2 Assignments
0 Petitions
Accused Products
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:
where xi 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 aij is defined to be the reciprocal of the number of links pointing out from page j (denoted dj) if page j points to page i, and zero otherwise.
-
Citations
15 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;
and where xi 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 aij is defined to be the reciprocal of the number of links pointing out from page j (denoted dj) if page j points to page i, and zero otherwise. - View Dependent Claims (2, 3, 4)
-
-
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;
and partitioning the matrix in order to solve for the rank via a sequence of smaller systems of equations. - View Dependent Claims (6, 7, 8, 9, 10, 11)
-
-
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χ
. - View Dependent Claims (13, 14)
-
-
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;
and where xi 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 aij is defined to be the reciprocal of the number of links pointing out from page j (denoted dj) if page j points to page i, and zero otherwise.
-
Specification