Backward and forward non-normalized link weight analysis method, system, and computer program product

• US 7,281,005 B2
• Filed: 10/20/2003
• Issued: 10/09/2007
• Est. Priority Date: 10/20/2003
• Status: Expired due to Fees

• Current Assignee: Telenor Asa (Government of Norway)
• Original Assignee: Telenor Asa (Government of Norway)
• Inventors: Canright, Geoffrey, Engo-Monsen, Kenth
• Primary Examiner(s): Kindred; Alford
• Assistant Examiner(s): NGUYEN, MERILYN P
• Application Number:
  US10/687,602
• Publication Number:
  US 20050086260A1
• Time in Patent Office: 1,450 Days
• Field of Search: 707 1- 5, 707/104.1, 707/7, 715/500, 715/501.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method, system, and computer program product for hypertext link analysis that includes independently employing non-normalized backward and forward operators to obtain two independent weights for each document in a hypertext-linked graph, for subsequent ranking and analysis.

Claims

1. A computer-implemented method of ranking a relevance of a node in a linked set of nodes, comprising:

determining an authority weight for said node using a non-compound, non-normalized Forward operator and without using a Backward operator;

determining a hub weight for said node using a non-compound, non-normalized Backward operator and without using a Forward operator such that said steps of determining are mathematically decoupled;

ranking said relevance based upon said authority weight and said hub weight;

searching, navigating or retrieving one or more information objects in one or more electronic archives based upon said ranking; and

storing, displaying or transmitting a result based on said searching, navigating or retrieving.

2. The method of claim 1, wherein said determining an authority weight for said node comprises:

choosing a forward start vector of initial authority weights of each node in the linked set of nodes;

determining an updated vector of node weights using the non-compound, non-normalized Forward operator;

normalizing the determined updated vector of node weights; and

testing for convergence, wherein said steps of determining an updated vector of node weights and normalizing the determined updated vector of node weights are repeated until the node weight converges to a determined authority weight.

3. The method of claim 1, wherein said determining a hub weight for said node comprises:

choosing a backward start vector of initial hub weights of each node in the linked set of nodes;

determining an updated vector of node weights using the non-compound, non-normalized Backward operator;

normalizing the determined updated vector of node weights; and

testing for convergence, wherein said steps of determining an updated vector of node weights and normalizing the determined updated vector of node weights are repeated until the node weight converges to a determined hub weight.

4. The method of claim 1, said step of ranking said relevance comprising:

determining a principal eigenvector of a matrix.

5. The method of claim 1, said step of ranking said relevance comprising:

selecting a search term; and

displaying a ranking result.

6. The method of claim 1, said step of ranking said relevance comprising:

ranking the textual content of the node.

20. A computer readable storage medium storing a computer program including instructions configured to cause a processor-based device to execute the steps of one of claims 1-6 and 14-19.

7. A system for ranking a relevance of a node in a linked set of nodes comprising:

a calculator configured to calculate an authority weight for said node and a hub weight for said node, using, respectively, a non-compound, non-normalized Forward operator without using a Backward operator and a non-compound, non-normalized Backward operator without using a Forward operator such that said calculations are mathematically decoupled, said calculator further configured to rank said relevance based upon said authority weight and said hub weight; and

a computer-based search engine configured to search, navigate or retrieve one or more information objects in one or more electronic archives based upon said ranked relevance, and to store, display or transmit a corresponding result.

8. The system of claim 7, wherein said calculator comprises:

a calculator configured to

accept as an input a forward start vector of initial authority weights of each node in the linked set of nodes;

determine an updated vector of node weights using the non-compound, non-normalized Forward operator;

normalize the determined updated vector of node weights;

test for convergence; and

to repeatedly determine an updated vector of node weights and normalize the determined updated vector of node weights until the node weight converges to a determined authority weight.

9. The system of claim 7, wherein said calculator comprises:

a calculator configured to

accept as an input a forward start vector of initial hub weights of each node in the linked set of nodes;

determine an updated vector of node weights using the non-compound, non-normalized Forward operator;

normalize the determined updated vector of node weights;

test for convergence; and

to repeatedly determine an updated vector of node weights and normalize the determined updated vector of node weights until the node weight converges to a determined hub weight.

10. The system of claim 7, said calculator comprising:

a calculator configured to calculate a principal eigenvector of a matrix.

11. The system of claim 7, further comprising:

a search term selection device connected to said calculator; and

a display connected to said calculator.

12. The system of claim 7, further comprising:

a textual content ranking mechanism connected to said calculator.

13. The system of claim 7, further comprising:

a relay module connected to said calculator and configured to relay a corresponding calculated authority weight and hub weight to a display.

14. A computer-implemented method of ranking a relevance of a node in a linked set of nodes, the improvement comprising:

determining one of

an authority weight for said node using a non-compound, non-normalized Forward operator and without using a Backward operator,

a hub weight for said node using a non-compound, non-normalized Backward operator and without using a Forward operator;

ranking said relevance based upon said one of an authority weight and a hub weight;

searching, navigating or retrieving one or more information objects in one or more electronic archives based upon said ranking; and

storing, displaying or transmitting a result based on said searching, navigating or retrieving.

15. The method of claim 14, wherein said determining an authority weight for said node comprises:

choosing a forward start vector of initial authority weights of each node in the linked set of nodes;

determining an updated vector of node weights using the non-compound, non-normalized Forward operator;

normalizing the determined updated vector of node weights; and

testing for convergence, wherein said steps of determining an updated vector of node weights and normalizing the determined updated vector of node weights are repeated until the node weight converges to determined authority weight.

16. The method of claim 14, wherein said determining a hub weight for said node comprises:

choosing a backward start vector of initial hub weights of each node in the linked set of nodes;

determining an updated vector of node weights using the non-compound, non-normalized Backward operator;

normalizing the determined updated vector of node weights; and

testing for convergence, wherein said steps of determining an updated vector of node weights and normalizing the determined updated vector of node weights are repeated until the node weight converges to determined hub weight.

17. The method of claim 14, said step of ranking said relevance comprising:

determining a principal eigenvector of a matrix.

18. The method of claim 14, said step of ranking said relevance comprising:

selecting a search term.

19. The method of claim 14, said step of ranking said relevance comprising:

ranking the textual content of the node.

21. A system for ranking a relevance of a node in a linked set of nodes, comprising:

means for determining an authority weight for said node using a non-compound, non-normalized Forward operator without using a Backward operator;

means for determining a hub weight for said node using a non-compound, non-normalized Backward operator without using a Forward operator such that said means for determining an authority weight and said means for determining a hub weight are mathematically decoupled;

means for ranking said relevance based upon said authority weight and said hub weight;

means for searching, navigating or retrieving one or more information objects in one or more electronic archives based upon said ranking; and

means for storing, displaying or transmitting a result output from said means for searching, navigating or retrieving.

22. The system of claim 21, wherein said means for determining an authority weight for said node comprises:

means for choosing a forward start vector of initial authority weights of each node in the linked set of nodes;

means for determining an updated vector of node weights using the non-compound, non-normalized Forward operator;

means for normalizing the determined updated vector of node weights; and

means for testing for convergence, wherein said means for determining an updated vector of node weights and means for normalizing the determined updated vector of node weights are configured to repeat their respective operations until the node weight converges to determined authority weight.

23. The system of claim 21, wherein said means for determining a hub weight for said node comprises:

means for choosing a backward start vector of initial hub weights of each node in the linked set of nodes;

means for determining an updated vector of node weights using the non-compound, non-normalized Backward operator;

means for normalizing the determined updated vector of node weights; and

means for testing for convergence, wherein said means for determining an updated vector of node weights and means for normalizing the determined updated vector of node weights are configured to repeat their respective operations until the node weight converges to determined hub weight.

24. The system of claim 21, said means for ranking comprising:

means for determining a principal eigenvector of a matrix.

25. The system of claim 21, said means for ranking comprising:

means for selecting a search term; and

means for displaying a ranking result.

26. The system of claim 21, said means for ranking comprising:

means for ranking the textual content of the node.

27. A system for ranking a relevance of a node in a linked set of nodes, the improvement comprising:

means for determining one of

an authority weight for said node using a non-compound, non-normalized Forward operator without using a Forward operator, and

a hub weight for said node using a non-compound, non-normalized Backward operator without using a Backward operator;

means for ranking said relevance based upon said one of an authority weight and a hub weight;

means for searching, navigating or retrieving one or more information objects in one or more electronic archives based upon said ranking; and

means for storing, displaying or transmitting a result output from said means for searching, navigating or retrieving.

28. The system of claim 27, wherein said means for determining an authority weight for said node comprises:

means for choosing a forward start vector of initial authority weights of each node in the linked set of nodes;

means for determining an updated vector of node weights using the non-compound, non-normalized Forward operator;

means for normalizing the determined updated vector of node weights; and

means for testing for convergence, wherein said means for determining an updated vector of node weights and means for normalizing the determined updated vector of node weights are configured to repeat their respective operations until the node weight converges to determined authority weight.

29. The system of claim 27, wherein said means for determining a hub weight for said node comprises:

means for choosing a backward start vector of initial hub weights of each node in the linked set of nodes;

means for determining an updated vector of node weights using the non-compound, non-normalized Backward operator;

means for normalizing the determined updated vector of node weights; and

means for testing for convergence, wherein said means for determining an updated vector of node weights and means for normalizing the determined updated vector of node weights are configured to repeat their respective operations until the node weight converges to determined hub weight.

30. The system of claim 27, said means for ranking comprising:

means for determining a principal eigenvector of a matrix.

31. The system of claim 27, said means for ranking comprising:

means for selecting a search term.

32. The system of claim 27, said means for ranking comprising:

means for ranking the textual content of the node.