RANKING DOCUMENTS BASED ON A SERIES OF DOCUMENT GRAPHS

• US 20080313168A1
• Filed: 06/18/2007
• Published: 12/18/2008
• Est. Priority Date: 06/18/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Tie-Yan, Yang, Lei, Li, Hang, Qi, Lei, Gao, Bin
• Granted Patent: US 8,244,737 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Ranking documents based on a series of web graphs collected over time is provided. A ranking system provides multiple transition probability distributions representing different snapshots or times. Each transition probability distribution represents a probability of transitioning from one document to another document within a collection of documents using a link of the document. The ranking system determines a stationary probability distribution for each snapshot based on the transition probability distributions for that snapshot and the stationary probability distribution of the previous snapshot. The stationary probability distributions represent a ranking of the documents over time.

Claims

1. A method in a computing device for ranking documents with links between the documents, the method comprising:

providing a first document graph and a second document graph;

determining a first ranking of the documents based on the first document graph; and

determining a second ranking of the documents based on the second document graph and the first ranking of the documents based on the first document graph.

2. The method of claim 1 wherein:

the providing includes providing a first and a second transition probability distribution indicating probability of transitioning from one document to another document using a link;

the determining of the first ranking includes determining a first stationary probability distribution based on the first transition probability distribution indicating a stationary probability of transitioning to each document; and

the determining of the second ranking includes determining a second stationary probability distribution based on the second transition probability distribution and the first stationary probability distribution wherein the second stationary probability distribution represents a ranking of the documents.

3. The method of claim 2 wherein the determining of the second stationary probability distribution uses the first stationary probability distribution as an indication of the probability of transitioning to each document without using a link.

4. The method of claim 2 wherein the determining of the first stationary probability distribution is additionally based on an initial probability distribution of transitioning to each document without using a link.

5. The method of claim 4 wherein the initial probability distribution is based, at least in part, on a user'"'"'s history of visiting documents.

6. The method of claim 4 wherein the initial probability distribution is based, at least in part, on a document being considered spam.

7. The method of claim 2 wherein the documents are web pages and the transition probability distribution is generated based on the links between the web pages.

8. A computer-readable medium containing instructions for controlling a computing device to rank web pages, by a method comprising:

providing web graphs collected at different times, a web graph representing web pages and links between web pages; and

for web graphs in time order, generating a ranking of the web pages based on the probability of transitioning to each web page based on the probability of transitioning from each web page to each other web page using the links as indicated by the web graph and the probability of next visiting each web page without using a link, wherein the probability of next visiting is based on the ranking of web pages based on a web graph of an earlier time.

9. The computer-readable medium of claim 8 wherein the generating of the ranking of web pages for a web graph uses a page rank algorithm in which the probability of transitioning is derived from an adjacency matrix derived from the web graph and the probability of next visiting each web page without using a link is a jumping vector.

10. The computer-readable medium of claim 9 wherein the jumping vector is derived from a ranking of web pages based on a web graph of the earlier time.

11. The computer-readable medium of claim 10 wherein the jumping vector is modified based, at least in part, on a user'"'"'s history of visiting documents.

12. The computer-readable medium of claim 10 wherein the jumping vector is modified based, at least in part, on a web page being considered spam.

13. The computer-readable medium of claim 8 wherein the ranking of web pages is based on a stationary probability distribution derived from the probability of transitioning and the probability of next visiting.

14. The computer-readable medium of claim 8 including receiving search results of a search request, the search results identifying web pages relating to the search request, and ranking the web pages of the search results based, at least in part, on the generated ranking of web pages.

15. The computer-readable medium of claim 14 wherein the ranking of web pages of the search results uses the generated ranking of web pages derived from the most recent web graph.

16. A computing device for ranking web pages with links between the web pages, comprising:

a transition probability distribution store having a first and a second transition probability distribution indicating probability of transitioning from one web page to another web page using a link of a currently visited web page;

an initial jumping vector indicating probability of next visiting each web page without using a link of a currently visited web page;

a component for determining a first stationary probability distribution based on the first transition probability distribution and the initial jumping vector and determines a second stationary probability distribution based on the second transition probability distribution and a jumping vector derived from the first stationary probability distribution; and

a component that ranks web pages of search results based, at least in part, on determining the second stationary probability distribution.

17. The computing device of claim 16 wherein the jumping vector is based, at least in part, on a user'"'"'s history of visiting documents.

18. The computing device of claim 16 wherein the jumping vector is based, at least in part, on a web page being considered spam.

19. The computing device of claim 16 including a component that displays indications of the web pages of the search results in an order that is based on the ranking of the web pages of the search results.

20. The computing device of claim 16 wherein the first and second transition probability distributions are generated from web graphs collected at different times.