Dynamically ranking nodes and labels in a hyperlinked database
AssigneeInternational Business Machines Corporation
InventorsKrishna Chitrapura, Srinivas Kashyap
Life of this patent
Estimating the term…
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.
Claims19
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.
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.
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.
Dependencies are inferred from the claim text.