Methods for ranking nodes in large directed graphs
First Claim
1. A computer implemented method for computing ranks in a linked database, the method comprising:
- obtaining a local rank vector associated with a selected subset of nodes in the linked database, wherein each component of the local rank vector represents a local rank of a node in the selected subset of nodes;
obtaining a block rank vector associated with the linked database, wherein each component of the block rank vector represents a block rank of a subset of nodes in the linked database, wherein the subset is one of a plurality of subsets of nodes defined by a partition of the nodes in the linked database;
selecting a component of the block rank vector corresponding to the selected subset of nodes;
selecting a component of the local rank vector corresponding to a selected node in the selected subset of nodes;
combining the selected component of the block rank vector and the selected component of the local rank vector to obtain a global rank for the selected node; and
storing the global rank of the selected node on a computer readable medium.
1 Assignment
0 Petitions
Accused Products
Abstract
Techniques for assigning ranks to nodes in a large linked database, such as world wide web or any other hypermedia database, partition the nodes so that the link matrix has a predominantly block-diagonal form. Within each block, a local rank is computed for nodes in the block, possibly by different computer in a distributed computing environment. A block rank is then estimated for each block as a whole, and may optionally include block-level weights to implement customized ranking. The local ranks and block ranks are then combined to form a global rank, which may be used to rank the nodes. Alternatively, a global rank vector for the database may be used as an initial vector in an iterative link-based ranking scheme to obtain more accurate global ranks for the nodes. The global rank vector may be divided to provide local rank vectors for use in subsequent applications of the method.
-
Citations
30 Claims
-
1. A computer implemented method for computing ranks in a linked database, the method comprising:
-
obtaining a local rank vector associated with a selected subset of nodes in the linked database, wherein each component of the local rank vector represents a local rank of a node in the selected subset of nodes; obtaining a block rank vector associated with the linked database, wherein each component of the block rank vector represents a block rank of a subset of nodes in the linked database, wherein the subset is one of a plurality of subsets of nodes defined by a partition of the nodes in the linked database; selecting a component of the block rank vector corresponding to the selected subset of nodes; selecting a component of the local rank vector corresponding to a selected node in the selected subset of nodes; combining the selected component of the block rank vector and the selected component of the local rank vector to obtain a global rank for the selected node; and storing the global rank of the selected node on a computer readable medium. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A computer implemented method for computing a rank value for a node in a linked database, the method comprising:
-
partitioning nodes of the linked database into K subsets according to a classification of the nodes, wherein K comprises the number of subsets produced by the partitioning; computing K local rank vectors for the K subsets of the nodes; computing a block rank vector from a K×
K reduced link matrix;computing a global rank vector from the local rank vectors and the block rank vector; selecting a component of the global rank vector corresponding to the node to obtain the rank value for the node; and storing the rank value of the selected node on a computer readable medium. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
27. A computer implemented method for computing a rank value for a block of nodes in a linked database, the method comprising:
-
partitioning nodes of the linked database into subsets according to a classification of the nodes; forming a reduced link matrix whose elements represent links between the subsets of the partition; calculating a block rank vector from the reduced link matrix; selecting a component of the block rank vector corresponding to the block of nodes to obtain the rank value for the block of nodes; and storing the rank value for the block of nodes on a computer readable medium. - View Dependent Claims (28, 29, 30)
-
Specification