Ranking documents based on a series of document graphs

• US 8,244,737 B2
• Filed: 06/18/2007
• Issued: 08/14/2012
• 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, Li, Hang, Gao, Bin, Yang, Lei, Qi, Lei
• Primary Examiner(s): GORTAYO, DANGELINO N
• Application Number:
  US11/764,554
• Publication Number:
  US 20080313168A1
• Time in Patent Office: 1,884 Days
• Field of Search: 707/1, 707/3, 707/5, 707/7, 707/100, 707/104.1, 707/665, 707/723, 707/725, 707/726, 707/748, 707/751, 707/802, 707/749, 707/754
• US Class Current: 707/748
• 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 that is programmed for ranking documents with links between the documents, the method comprising:

providing a first document graph representing links between the documents at a first time and a second document graph representing links between the documents at a second time that is later than the first time;

determining by the computing device a first ranking of the documents based on the first document graph by;

initializing a first jumping vector indicating probabilities of visiting the documents without using a link, the initializing including setting the probability of visiting a suspected spam document without using a link to zero; and

generating a first transition probability matrix indicating probabilities of visiting the documents using links; and

applying a page ranking algorithm to the first document graph to generate a first ranking of the documents based on the first transition probability matrix and the first jumping vector wherein the ranking of the suspected spam document is lowered as a result of setting the probability of visiting the suspect spam document without using a link to zero; and

determining by the computing device 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 by;

initializing a second jumping vector indicating probabilities of visiting the documents without using a link, the second jumping vector being initialized based on the first ranking of documents such that a higher first ranking increases the probability of visiting a document without a link; and

generating a second transition probability matrix indicating probabilities of visiting the documents using links; and

applying a page ranking algorithm to the second document graph to generate a second ranking of the documents based on the second transition probability matrix and the second jumping vector.

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 the second 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 first transition probability distribution is based, at least in part, on a user'"'"'s history of visiting documents.

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

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

providing a first web graph representing links between the web pages at a first time and a second web graph representing links between the web pages at a second time that is later than the first time;

determining a first ranking of the web pages based on the first web graph by;

initializing a first jumping vector to indicate probabilities of visiting the web pages without using a link, the initializing including setting the probability of visiting a suspected spam web page without using a link based on confidence that the suspected spam web page is actually spam so that the set probability decreases as the confidence increases; and

generating a first transition probability matrix indicating probabilities of visiting the web pages using links; and

applying a page ranking algorithm to the first web graph to generate a first ranking of the web pages based on the first transition probability matrix and the first jumping vector wherein the ranking of a suspected spam web page is lowered as a result of setting the probability of visiting the suspect spam web page without using a link based on confidence that the suspected web page is actually spam; and

determining by the computing device a second ranking of the web pages based on the second web graph and the first ranking of the web pages based on the first web graph by;

initializing a second jumping vector indicating probabilities of visiting the web pages without using a link, the second jumping vector being initialized based on the first ranking of web pages such that a higher first ranking increases the probability of visiting a web page without a link; and

generating a second transition probability matrix indicating probabilities of visiting the web pages using links; and

applying a page ranking algorithm to the second web graph to generate a second ranking of the web pages based on the second transition probability matrix and the second jumping vector.

7. The computer-readable storage medium of claim 6 wherein:

the providing includes providing a first and a second transition probability distribution indicating probability of transitioning from one web page to another web page 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 web page; 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 the second ranking of the web pages.

8. The computer-readable storage medium of claim 7 wherein the first transition probability distribution is based, at least in part, on a user'"'"'s history of visiting web pages.

9. A computing device for ranking web pages, the computing device comprising:

a memory storing computer-executable instructions of;

a component that provides access to a first web graph representing links between the web pages at a first time and a second web graph representing links between the web pages at a second time that is later than the first time;

a component that determines a first ranking of the web pages based on the first web graph by;

initializing a first jumping vector to probabilities of visiting the web pages without using a link, the initializing including setting the probability of visiting a suspected spam web page without using a link based on confidence that the suspected spam web page is actually spam so that the set probability decreases as the confidence increases; and

generating a first transition probability matrix indicating probabilities of visiting the web pages using links; and

applying a page ranking algorithm to the first web graph to generate a first ranking of the web pages based on the first transition probability matrix and the first jumping vector wherein the ranking of a suspected spam web page is lowered as a result of setting the probability of visiting the suspect spam web page without using a link based on confidence that the suspected web page is actually spam; and

a component that determines a second ranking of the web pages based on the second web graph and the first ranking of the web pages based on the first web graph by;

initializing a second jumping vector indicating probabilities of visiting the web pages without using a link, the second jumping vector being initialized based on the first ranking of web pages such that a higher first ranking increases the probability of visiting a web page without a link; and

generating a second transition probability matrix indicating probabilities of visiting the web pages using links; and

applying a page ranking algorithm to the second web graph to generate a second ranking of the web pages based on the second transition probability matrix and the second jumping vector; and

a processor that executes the computer-executable instructions stored in the memory.

10. The computing device of claim 9 including:

a component that provides access to a first and a second transition probability distribution indicating probability of transitioning from one web page to another web page using a link; and

wherein

the component that determines the first ranking determines a first stationary probability distribution based on the first transition probability distribution indicating a stationary probability of transitioning to each web page; and

the component that determines the second ranking determines 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 the second ranking of the web pages.

11. The computing device of claim 10 wherein the first transition probability distribution is based, at least in part, on a user'"'"'s history of visiting documents.