SUPERVISED RANKING OF VERTICES OF A DIRECTED GRAPH
First Claim
1. A computing system for ranking of vertices of a directed graph, the system comprising:
- an indication of links between the vertices of the directed graph;
prior knowledge relating to ranking of the vertices of the directed graph; and
a component that generates a ranking of the vertices based on the links between the vertices consistent with the prior knowledge relating to ranking of the vertices.
2 Assignments
0 Petitions
Accused Products
Abstract
A method and system for ranking importance of vertices of a directed graph based on links between the vertices and some prior knowledge of importance of the vertices is provided. A ranking system inputs an indication of the vertices along with an indication of the links between the vertices as the directed graph. The ranking system generates a transition-probability matrix that represents the probability of transitioning from vertex to vertex. The ranking system then generates a ranking of the vertices based on the links between the vertices represented by the stationary distribution of the transition-probability matrix that is minimally perturbed to satisfy the prior knowledge, which may be a partial ranking of the vertices.
-
Citations
20 Claims
-
1. A computing system for ranking of vertices of a directed graph, the system comprising:
-
an indication of links between the vertices of the directed graph; prior knowledge relating to ranking of the vertices of the directed graph; and a component that generates a ranking of the vertices based on the links between the vertices consistent with the prior knowledge relating to ranking of the vertices. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A computer-readable medium embedded with computer-executable instructions for controlling a computer system to rank web pages, by a method comprising:
-
providing an adjacency matrix indicating links between the web pages; providing a partial ranking of the web pages; generating a transition-probability matrix based on the links of the web pages, the transition-probability matrix indicating probability of transitioning from one web page to another web page; and generating a stationary distribution for the transition-probability matrix that attempts to satisfy the partial ranking of the web pages and minimizes perturbation of the transition probability matrix, the stationary distribution representing the ranking of the web pages. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A method in a computer system for ranking documents, the method comprising:
-
providing an adjacency matrix indicating links between the documents; providing a partial ordering of the documents indicating relative ranking of some documents; generating a transition-probability matrix from the adjacency matrix that indicates probability of transitioning from one document to another document; and generating a stationary distribution for the transition-probability matrix that attempts to minimize perturbation to the transition-probability matrix needed to satisfy the partial ordering, the stationary distribution representing the ranking of the documents. - View Dependent Claims (20)
-
Specification