Supervised ranking of vertices of a directed graph

• US 7,617,194 B2
• Filed: 12/29/2006
• Issued: 11/10/2009
• Est. Priority Date: 12/29/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Liu, Tie-Yan, Qin, Tao
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): MUELLER, KURT A
• Application Number:
  US11/618,380
• Publication Number:
  US 20080162453A1
• Time in Patent Office: 1,047 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

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.

Claims

1. A computing device for ranking of vertices of a directed graph, the computing device comprising:

a processor;

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 the component being implemented as computer-executable instructions stored in memory of the computing device for execution by the processor

wherein the ranking is based on solving the following objective functions and constraints;

$\mathrm{\pi <br><br>}<br><br>\left(E\right)=\arg <br><br><br><br>\underset{\mathrm{\pi <br><br>}}{\min }<br><br>{<br><br>E<br><br>}_F^2+c<br><br><br><br>{\mathrm{\pi <br><br>}}^T<br><br>\left(I+E-P\right)<br><br>{\left(I+E-P\right)}^T<br><br>\mathrm{\pi <br><br>}$
s.t. e^Tπ

=1

π

≧

0

Aπ

>

Bπ

and

$E<br><br>\left(\mathrm{\pi <br><br>}\right)=\arg <br><br><br><br>\underset{E}{\min }<br><br>{<br><br>E<br><br>}_F^2+c<br><br><br><br>{\mathrm{\pi <br><br>}}^T<br><br>\left(I+E-P\right)<br><br>{\left(I+E-P\right)}^T<br><br>\mathrm{\pi <br><br>}$
s.t. (P−

E)e=e

(P−

E)≧

0.

2. The computing device of claim 1 wherein the vertices represent documents and including a component that displays an indication of the new ranking of the documents.

3. The computing device of claim 1 wherein the vertices represent documents and including a component that determines an ordering of documents relating to a query based on the generated new ranking.

4. The computing device of claim 1 wherein the vertices represent documents and the prior ranking is a partial ranking of the documents.

5. The computing device of claim 1 wherein the indication of the links is an adjacency matrix.

6. The computing device of claim 1 wherein the component generates the new ranking based on minimizing perturbation of a transition-probability matrix derived from the links between the vertices.

7. The computing device of claim 6 wherein the component that generates the new ranking applies an interactive optimization to iteratively generate a new ranking based on a fixed perturbation and generate a perturbation based on a fixed ranking until the new ranking and perturbation converge on a solution.

8. The computing device of claim 7 wherein only elements of the transition-probability matrix that correspond to links are perturbed.

9. A computer-readable storage 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

wherein the generating of the stationary distribution applies an interior-point optimization technique.

10. The computer-readable storage medium of claim 9 wherein the information collected from a user includes a relative ranking of some web pages.

11. The computer-readable storage medium of claim 9 wherein the generating of the stationary distribution is performed based on a non-convex problem space being converted to a convex problem space.

12. The computer-readable storage medium of claim 9 including displaying an indication of the new ranking of the web pages.

13. The computer-readable storage medium of claim 9 including determining an ordering of the web pages as results of a query based on the generated new ranking.

14. The computer-readable storage medium of claim 9 wherein the information collected from a user is click-through data indicating access to the web pages by the user.

15. A computer-readable storage 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

wherein the generating of the stationary distribution applies an interactive optimization to iteratively generate a stationary distribution based on a fixed perturbation to the transition-probability matrix and generate a perturbation to the transition-probability matrix based on a fixed stationary distribution until the stationary distribution and perturbation converge on a solution and

wherein the stationary distribution is based on solving the following objective functions and constraints;

$\mathrm{\pi <br><br>}<br><br>\left(E\right)=\arg <br><br><br><br>\underset{\mathrm{\pi <br><br>}}{\min }<br><br>{<br><br>E<br><br>}_F^2+c<br><br><br><br>{\mathrm{\pi <br><br>}}^T<br><br>\left(I+E-P\right)<br><br>{\left(I+E-P\right)}^T<br><br>\mathrm{\pi <br><br>}$
s.t. e^Tπ

=1

π

≧

0

Aπ

>

Bπ

and

$E<br><br>\left(\mathrm{\pi <br><br>}\right)=\arg <br><br><br><br>\underset{E}{\min }<br><br>{<br><br>E<br><br>}_F^2+c<br><br><br><br>{\mathrm{\pi <br><br>}}^T<br><br>\left(I+E-P\right)<br><br>{\left(I+E-P\right)}^T<br><br>\mathrm{\pi <br><br>}$
s.t. (P−

E)e=e

(P−

E)≧

0.

16. The computer-readable storage medium of claim 15 wherein only elements of the transition-probability matrix that correspond to links are perturbed.

17. 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 by the computer system a transition-probability matrix from the adjacency matrix that indicates probability of transitioning from one document to another document; and

generating by the computer system 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 a new ranking of the documents that is based on both the partial ordering of the document and probability of transitioning from one document to another document

wherein the generating of the stationary distribution applies an interior-point optimization technique.

18. The method of claim 17 wherein the generating of the stationary distribution applies an interactive optimization to iteratively generate a stationary distribution based on a fixed perturbation and generate a perturbation based on a fixed stationary distribution until the stationary distribution and perturbation converge on a solution.