Scoring documents in a linked database
View Patent ↗A method assigns importance ranks to nodes in a linked database, such as any database of documents containing citations, the world wide web or any other hypermedia database. The rank assigned to a document is calculated from the ranks of documents citing it. In addition, the rank of a document is calculated from a constant representing the probability that a browser through the database will randomly jump to the document.
1. A computer implemented method for calculating an importance rank for N linked nodes of a linked database, the method comprising:
(a) selecting an initial N-dimensional vector p 0 , wherein each component of p 0 represents a probability that a user will start at a given node, wherein each node of the N linked nodes is a computer-readable document containing information;
(b) computing an approximation p n to a steady-state probability p ∞ , wherein each component of p ∞ represents a probability that the user will randomly end up at a particular node after following a number of forward links, in accordance with the equation p n =A n p 0 , where A is an N×N transition probability matrix having elements A[i][j] representing a probability of moving from node i to node j; and
(c) determining a rank r[k] for a node k from a k th component of p n , wherein r[k] represents an importance of the information contained in node k.
2. The method of claim 1 wherein the matrix A is chosen so that an importance rank of a node is calculated, in part, from a weighted sum of importance ranks of backlink nodes of the node.
3. The method of claim 2 wherein the importance rank of each of the backlink nodes is weighted in dependence upon the total number of links in the backlink node.
4. The method of claim 1 wherein the matrix A is chosen so that an importance rank of a node is calculated, in part, from a constant α representing the probability that a surfer will randomly jump to the node.
5. The method of claim 1 wherein the matrix A is chosen so that an importance rank of a node is calculated, in part, from a measure of distances between the node and backlink nodes of the node.
6. The method of claim 1 wherein the initial N-dimensional vector p 0 is selected to represent a uniform probability distribution.
7. The method of claim 1 wherein the initial N-dimensional vector p 0 is selected to represent a non-uniform probability distribution, wherein a predetermined set of nodes is given a large initial probability relative to other nodes.
8. A computer implemented method for calculating an importance rank for each of N linked web page documents, the method comprising:
(a) selecting an initial N-dimensional vector p 0 , wherein each component of p 0 represents an initial estimate of a probability that a user will start at a given web page document;
(b) computing an approximation p 0 to a steady-state probability p ∞ , wherein each component of p ∞ represents an estimate of a probability that the user will randomly end up at a particular web page document, in accordance with the equation p n =A n p 0 , where A is an N×N transition probability matrix having elements A[i][j] representing a probability of moving from web page document i to web page document j; and
(c) determining a rank r[k] for a web page document k from a k th component of p n , wherein r[k] represents an importance of the information contained in a particular web page document k.
9. The method of claim 8 wherein the matrix A is chosen so that an importance rank of a given web page document is calculated, in part, from a weighted sum of importance ranks of web page documents backlinked to the given web page document.
10. The method of claim 9 wherein the importance rank of each of the backlinked web page documents is weighted in dependence upon the total number of links in the backlinked web page document.
11. The method of claim 8 wherein the matrix A is chosen so that an importance rank of a web page document is calculated, in part, from a constant α representing the probability that a surfer will randomly jump to the web page document.
12. The method of claim 8 wherein the matrix A is chosen so that an importance rank of a web page document is calculated, in part, from a measure of distances between the web page document and backlink nodes of the web page document.
13. The method of claim 8 wherein the initial N-dimensional vector p 0 is selected to represent a uniform probability distribution.
14. The method of claim 8 wherein the initial N-dimensional vector p 0 is selected to represent a non-uniform probability distribution, wherein a predetermined set of web page documents is given a large initial probability relative to other web page documents.