Dynamically ranking nodes and labels in a hyperlinked database

• US 20060136098A1
• Filed: 12/17/2004
• Published: 06/22/2006
• Est. Priority Date: 12/17/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kashyap, Srinivas Raaghav, Chitrapura, Krishna Prasad
• Granted Patent: US 7,991,755 B2
• Time in Patent Office: Days
• US Class Current: 700/262
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

The World Wide Web (WWW) can be modelled as a labelled directed graph G(V,E,L), in which V is the set of nodes, E is the set of edges, and L is a label function that maps edges to labels. This model, when applied to the WWW, indicates that V is a set of hypertext documents or objects, E is a set of hyperlinks connecting the documents in V, and the edge-label function represents the anchor-text corresponding to the hyperlinks. One can find a probabilistic ranking of the nodes for any given label, a ranking of the labels for any given node, and rankings of labels and pages using flow based models. Further, the flows can be computing using sparse matrix operations.

Claims

1. A method for computing probabilistic measures for a labelled directed graph, said method comprising:

accessing data representative of a labelled directed graph of nodes and labels connected by directed edges;

determining, from the directed graph, a matrix of values representative of the influence between pairs of the nodes in the directed graph; and

determining, from the matrix and a distribution of a particular label in the directed graph, one or more probabilistic measures associated with at least one of the nodes or labels of the directed graph.

2. The method as claimed in claim 1, further comprising calculating values of the matrix as a summation of matrices representative of the influence between pairs of the nodes through paths of different lengths.

3. The method as claimed in claim 1, further comprising computing flow vectors for the directed graph that represent flows for each label at every node.

4. The method as claimed in claim 3, further comprising computing a steady state vector based upon a transition matrix that defines flow from nodes, and a labeled node.

5. The method as claimed in claim 1, wherein said matrix is stored as a sparse matrix in which B_ij represents the total influence that node j exerts on node i.

6. The method as claimed in claim 1, further comprising ranking the labels based upon a probabilistic measure of a node given a label.

7. The method as claimed in claim 1, further comprising ranking the labels based upon a probabilistic measure of a label given a node.

8. The method as claimed in claim 1, further comprising ranking the labels based upon the a probabilistic measure of a label.

9. The method as claimed in claim 1, further comprising ranking the labels based upon a probabilistic measure of a node.

10. The method as claimed in claim 1, wherein the directed graph models a hyperlinked database.

11. The method as claimed in claim 8, wherein the directed graph models the World Wide Web (WWW).

12. The method as claimed in claim 9, wherein the nodes model hypertext pages of the World Wide Web (WWW).

13. The method as claimed in claim 9, wherein the directed edges model a set of hyperlinks connecting the hypertext pages of the World Wide Web (WWW).

14. The method as claimed in claim 9, wherein the labels model anchor-text for the hyperlinks of the hypertext pages of the World Wide Web (WWW).

15. A computer program product for computing probabilistic measures for a labelled directed graph comprising computer software recorded on a computer-readable medium for performing a method comprising:

accessing data representative of a labelled directed graph of nodes and labels connected by directed edges;

determining, from the directed graph, a matrix of values representative of the influence between pairs of the nodes in the directed graph; and

determining, from the matrix and a distribution of a particular label in the directed graph, one or more probabilistic measures associated with at least one of the nodes or labels of the directed graph.

17. The computer program product as claimed in claim 15, wherein said method further comprises calculating values of the matrix as a summation of matrices representative of the influence between pairs of the nodes through paths of different lengths.

18. The computer program product as claimed in claim 15, wherein said method further comprises computing flow vectors for the directed graph that represent flows for each label at every node.

19. The computer program product as claimed in claim 18, wherein said method further comprises computing a steady state vector based upon a transition matrix that defines flow from nodes, and a labeled node.

16. A computer system for computing probabilistic measures for a labelled directed graph comprising computer software recorded on a computer-readable medium for performing a method comprising:

accessing data representative of a labelled directed graph of nodes and labels connected by directed edges;

determining, from the directed graph, a matrix of values representative of the influence between pairs of the nodes in the directed graph; and

determining, from the matrix and a distribution of a particular label in the directed graph, one or more probabilistic measures associated with at least one of the nodes or labels of the directed graph.