Method for ranking hyperlinked pages using content and connectivity analysis

• US 7,117,206 B1
• Filed: 05/05/2003
• Issued: 10/03/2006
• Est. Priority Date: 01/15/1998
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Overture Services Incorporated (Apollo Global Management, Inc.)
• Inventors: Bharat, Krishna Asur, Henzinger, Monika R.
• Primary Examiner(s): Coby, Frantz
• Assistant Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US10/429,237
• Time in Patent Office: 1,247 Days
• Field of Search: 707/5, 707/3, 707/7, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A computerized method determines the ranking of documents including information content. The present method uses both content and connectivity analysis. An input set of documents is represented as a neighborhood graph in a memory. In the graph, each node represents one document, and each directed edge connecting a pair of nodes represents a linkage between the pair of documents. The input set of documents represented in the graph is ranked according to the contents of the documents. A subset of documents is selected from the input set of documents if the content ranking of the selected documents is greater than a first predetermined threshold. Nodes representing any documents, other than the selected documents, are deleted from the graph. The selected subset of documents is ranked according the linkage of the documents, and an output set of documents exceeding a second predetermined threshold is selected for presentation to users.

Claims

1. A computer implemented method for ranking linked data objects containing information content, the method comprising the steps of:

generating an input set of linked data objects based upon a topic, each of the linked data objects having at least one link to another linked data object;

ranking the linked data objects in the input set based at least in part upon their closeness to the topic;

generating a subset of linked data objects from the input set of linked data objects having a closeness ranking greater than a first predetermined threshold;

ranking the linked data objects in the subset based at least in part upon their links; and

generating an output set of linked data objects from the subset of linked data objects having a link ranking greater than a second predetermined threshold.

2. The method of claim 1, wherein the step of generating an input set of linked data objects comprises the step of generating a start set of linked data objects based at least in part upon a result of a search engine query.

3. The method of claim 2, wherein the step of generating an input set of linked data objects further comprises the steps of:

locating linked data objects having links directed to linked data objects in the start set of linked data objects; and

adding the located linked data objects to the linked data objects in the start set of linked data objects.

4. The method of claim 2, wherein the step of generating an input set of linked data objects further comprises the steps of:

locating linked data objects having links directed from linked data objects in the start set of linked data objects; and

adding the located linked data objects to the linked data objects in the start set of linked data objects.

5. The method of claim 2, wherein the first predetermined threshold is a median closeness ranking of the start set of linked data objects.

6. The method of claim 1, wherein the step of ranking the linked data objects in the input set comprises the step of generating a similarity score for each of the linked data objects in the input set based upon the similarity of the information content of each of the linked data objects to the information content of a collection of linked data objects.

7. The method of claim 6, wherein the similarity is measured according to a vector space model.

8. The method of claim 6, wherein the similarity is measured according to a probabilistic model.

9. The method of claim 1, wherein the first predetermined threshold is a median closeness ranking of the input set of linked data objects.

10. The method of claim 1, wherein the first predetermined threshold is a fixed.

11. The method of claim 1, wherein the first predetermined threshold is determined interactively.

12. The method of claim 1, wherein the first predetermined threshold is determined from the slope of a graph plotting closeness ranking scores versus closeness ranking levels.

13. The method of claim 1, wherein the first predetermined threshold is a fraction of a maximum closeness score of the input set of linked data objects.

14. The method of claim 1, wherein the step of ranking the linked data objects in the subset comprises the steps of:

generating a hub score for each linked data object in the subset; and

generating an authority score for each linked data object in the subset.

15. The method of claim 14, wherein the step of generating a hub score for a first linked data object comprises the step of multiplying the authority score of a second linked data object by a link weight that is calculated based upon the number of linked data objects having links directed from the first linked data object that are located on a server common to the second linked data object.

16. The method of claim 14, wherein the step of generating an authority score for a first linked data object comprises the step of multiplying the hub score of a second linked data object by a link weight that is calculated based upon the number of linked data objects having links directed to the first linked data object that are located on a server common to the second linked data object.

17. The method of claim 14, wherein the link ranking for each linked data object in the subset is determined based at least in part upon the hub score and the authority score for each linked data object in the subset.