Producing a ranking for pages using distances in a web-link graph

• US 9,953,049 B1
• Filed: 10/19/2015
• Issued: 04/24/2018
• Est. Priority Date: 10/12/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Hajaj, Nissan
• Primary Examiner(s): Ly, Cheyne D
• Application Number:
  US14/886,990
• Time in Patent Office: 918 Days
• Field of Search: 707709, 707726, 707748
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations

Abstract

One embodiment of the present invention provides a system that produces a ranking for web pages. During operation, the system receives a set of pages to be ranked, wherein the set of pages are interconnected with links. The system also receives a set of seed pages which include outgoing links to the set of pages. The system then assigns lengths to the links based on properties of the links and properties of the pages attached to the links. The system next computes shortest distances from the set of seed pages to each page in the set of pages based on the lengths of the links between the pages. Next, the system determines a ranking score for each page in the set of pages based on the computed shortest distances. The system then produces a ranking for the set of pages based on the ranking scores for the set of pages.

Claims

1. A method, comprising:

obtaining data identifying a set of pages to be ranked, wherein each page in the set of pages is connected to at least one other page in the set of pages by a page link;

obtaining data identifying a set of n seed pages that each include at least one outgoing link to a page in the set of pages, wherein n is greater than one;

accessing respective lengths assigned to one or more of the page links and one or more of the outgoing links; and

for each page in the set of pages;

identifying a kth-closest seed page to the page according to the respective lengths, wherein k is greater than one and less than n,

determining a shortest distance from the kth-closest seed page to the page; and

determining a ranking score for the page based on the determined shortest distance, wherein the ranking score is a measure of a relative quality of the page relative to other pages in the set of pages.

2. The method of claim 1, wherein the respective lengths assigned to a link are determined based on a function of the number of outgoing links from the source page of the link.

3. The method of claim 2, wherein the function is a monotonic non-decreasing function of the number of outgoing links from the source page, so that the length of the link increases as the number of outgoing links from the source page increases.

4. The method of claim 2, wherein determining the length of a link from a source page q to a target page p includes adding a term (α

+log(|q|_out)) to the length of the link, wherein a is a non-negative value, and wherein |q|_out is the number of outgoing links from the source page q.

5. The method of claim 4, wherein α

=−

log(d), wherein d is a damping factor.

6. The method of claim 2, wherein the function for the length of the link is also a function of a weight of the link.

7. The method of claim 1, wherein determining a shortest distance from a seed page to a given page includes summing lengths of individual links along a shortest path from the seed page to the given page.

8. The method of claim 1,

wherein a seed page s_i in the set of seed pages is associated with a predetermined weight w_i, wherein 0<

i≤

1; and

wherein the seed page s_i is associated with an initial distance d_i, wherein d_i=−

log(w_i).

9. The method of claim 8, wherein the determined shortest distance from the seed page s_i to a given page includes the initial distance d_i.

10. The method of claim 1, wherein the ranking score for the given page can be proportional to e⁻

D(p), wherein D(p) is the kth shortest distance.

11. The method of claim 1, further comprising including each link in a shortest path from the kth-closest seed page to the first web page in a reduced link-graph, wherein the shortest path is a path having the shortest distance from the kth-closest seed page to the first web page.

21. The method of claim 1, further comprising:

using the ranking score in ranking one or more of the pages in response to a received search query.

12. A non-transitory computer-readable storage medium storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

obtaining data identifying a set of pages to be ranked, wherein each page in the set of pages is connected to at least one other page in the set of pages by a page link;

obtaining data identifying a set of n seed pages that each include at least one outgoing link to a page in the set of pages, wherein n is greater than one;

accessing respective lengths assigned to one or more of the page links and one or more of the outgoing links; and

for each page in the set of pages;

identifying a kth-closest seed page to the page according to the respective lengths, wherein k is greater than one and less than n,

determining a shortest distance from the kth-closest seed page to the page; and

determining a ranking score for the page based on the determined shortest distance, wherein the ranking score is a measure of a relative quality of the page relative to other pages in the set of pages.

13. The computer-readable storage medium of claim 12, wherein the respective lengths assigned to a link are determined based on a function of the number of outgoing links from the source page of the link.

14. The computer-readable storage medium of claim 13, wherein the function is a monotonic non-decreasing function of the number of outgoing links from the source page, so that the length of the link increases as the number of outgoing links from the source page increases.

15. The computer-readable storage medium of claim 13, wherein determining the length of a link from a source page q to a target page p includes adding a term (α

+log(|q|_out)) to the length of the link, wherein a is a non-negative constant value, and wherein |q|_out is the number of outgoing links from the source page q.

16. The computer-readable storage medium of claim 15, wherein α

=−

log(d), wherein d is a damping factor.

17. The computer-readable storage medium of claim 12, wherein determining a shortest distance from a seed page to a given page involves summing lengths of individual links along a shortest path from the seed page to the given page.

18. The computer-readable storage medium of claim 12,

wherein a seed page s_i in the set of seed pages is associated with a predetermined weight w_i, wherein 0<

w_i≤

1; and

wherein the seed page s_i is associated with an initial distance d_i, wherein d_i=−

log(w_i).

19. The computer-readable medium of claim 12, the operations further comprising:

using the ranking score in ranking one or more of the pages in response to a received search query.

20. A system comprising:

one or more data processing apparatus; and

one or more computer-readable storage devices having stored thereon instructions that, when executed by the one or more data processing apparatus, cause the one or more data processing apparatus to perform operations comprising;

obtaining data identifying a set of pages to be ranked, wherein each page in the set of pages is connected to at least one other page in the set of pages by a page link;

obtaining data identifying a set of n seed pages that each include at least one outgoing link to a page in the set of pages, wherein n is greater than one;

accessing respective lengths assigned to one or more of the page links and one or more of the outgoing links; and

for each page in the set of pages;

identifying a kth-closest seed page to the page according to the respective lengths, wherein k is greater than one and less than n,

determining a shortest distance from the kth-closest seed page to the page; and

determining a ranking score for the page based on the determined shortest distance, wherein the ranking score is a measure of a relative quality of the page relative to other pages in the set of pages.

22. The system of claim 20, the operations further comprising:

using the ranking score in ranking one or more of the pages in response to a received search query.