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

• US 20050086260A1
• Filed: 10/20/2003
• Published: 04/21/2005
• Est. Priority Date: 10/20/2003
• Status: Active Grant

• Current Assignee: Telenor Asa (Government of Norway)
• Original Assignee: Telenor Asa (Government of Norway)
• Inventors: Canright, Geoffrey, Engo-Monsen, Kenth
• Granted Patent: US 7,281,005 B2
• Time in Patent Office: Days
• 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 method of ranking the relevance of a node in a linked set of nodes, comprising:

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

determining a hub-like weight for said node using a non-compound, non-normalized Backward operator,

said steps of determining being mathematically decoupled.

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

choosing a forward start vector;

determining a node weight using the non-compound, non-normalized Forward operator;

normalizing the node weight; and

testing for convergence, wherein said steps of determining a node weight and normalizing the node weight are repeated until the node weight converges to a constant value.

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

choosing a backward start vector;

determining a node weight using the non-compound, non-normalized Backward operator;

normalizing the node weight; and

testing for convergence, wherein said steps of determining a node weight and normalizing the node weight are repeated until the node weight converges to a constant value.

4. The method of claim 1, further comprising:

determining a principal eigenvector of a matrix.

5. The method of claim 1, further comprising:

selecting a search term; and

displaying a ranking result.

6. The method of claim 1, further comprising:

ranking the textual content of the node.

25. A computer program product configured to host instructions corresponding to any one of the steps of claims 1-6 and 13-18.

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

a calculator configured to calculate an authority-like weight for said node and a hub-like weight for said node, using, respectively, a non-compound, non-normalized Forward operator and a non-compound, non-normalized Backward operator, said calculations being mathematically decoupled.

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

a calculator configured to iteratively calculate a node forward weight, normalize the node forward weight, and test for convergence until the node forward weight converges to a constant value.

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

a calculator configured to iteratively calculate a node backward weight, normalize the node backward weight, and test for convergence until the node backward weight converges to a constant value.

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; and

a display.

12. The system of claim 7, further comprising:

a textual content ranking mechanism.

13. A method of ranking the relevance of a node in a linked set of nodes, the improvement comprising:

determining one of

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

a hub-like weight for said node using a non-compound, non-normalized Backward operator.

14. The method of claim 13, wherein said determining an authority-like weight of a node comprises:

choosing a forward start vector;

determining a node weight using the non-compound, non-normalized Forward operator;

normalizing the node weight; and

testing for convergence, wherein said steps of determining a node weight and normalizing the node weight are repeated until the node weight converges to a constant value.

15. The method of claim 13, wherein said determining a hub-like weight of a node comprises:

choosing a backward start vector;

determining a node weight using the non-compound, non-normalized Backward operator;

normalizing the node weight; and

testing for convergence, wherein said steps of determining a node weight and normalizing the node weight are repeated until the node weight converges to a constant value.

16. The method of claim 13, further comprising:

determining a principal eigenvector of a matrix.

17. The method of claim 13, further comprising:

selecting a search term.

18. The method of claim 13, further comprising:

ranking the textual content of the node.

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

a calculator configured to calculate one of an authority-like weight for said node and a hub-like weight for said node, using, respectively, a non-compound, non-normalized Forward operator and a non-compound, non-normalized Backward operator, said calculations being mathematically decoupled; and

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

20. The system of claim 19, wherein said calculator comprises:

a calculator configured to iteratively calculate a node forward weight, normalize the node forward weight, and test for convergence until the node forward weight converges to a constant value.

21. The system of claim 19, wherein said calculator comprises:

a calculator configured to iteratively calculate a node backward weight, normalize the node backward weight, and test for convergence until the node backward weight converges to a constant value.

22. The system of claim 19, said calculator comprising:

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

23. The system of claim 19, further comprising:

a search term selection device; and

a display.

24. The system of claim 19, further comprising:

a textual content ranking mechanism.

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

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

means for determining a hub-like weight for said node using a non-compound, non-normalized Backward operator,

said means for determining an authority-like weight and said means for determining a hub-like weight being mathematically decoupled.

27. The system of claim 26, wherein said means for determining an authority-like weight of a node comprises:

means for choosing a forward start vector;

means for determining a node weight using the non-compound, non-normalized Forward operator;

means for normalizing the node weight; and

means for testing for convergence, wherein said means for determining a node weight and means for normalizing the node weight are configured to repeat their respective operations until the node weight converges to a constant value.

28. The system of claim 26, wherein said means for determining a hub-like weight of a node comprises:

means for choosing a backward start vector;

means for determining a node weight using the non-compound, non-normalized Backward operator;

means for normalizing the node weight; and

means for testing for convergence, wherein said means for determining a node weight and means for normalizing the node weight are configured to repeat their respective operations until the node weight converges to a constant value.

29. The system of claim 26, further comprising:

means for determining a principal eigenvector of a matrix.

30. The system of claim 26, further comprising:

means for selecting a search term; and

means for displaying a ranking result.

31. The system of claim 26, further comprising:

means for ranking the textual content of the node.

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

means for determining one of

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

a hub-like weight for said node using a non-compound, non-normalized Backward operator.

33. The system of claim 32, wherein said means for determining an authority-like weight of a node comprises:

means for choosing a forward start vector;

means for determining a node weight using the non-compound, non-normalized Forward operator;

means for normalizing the node weight; and

means for testing for convergence, wherein said means for determining a node weight and means for normalizing the node weight are configured to repeat their respective operations until the node weight converges to a constant value.

34. The system of claim 32, wherein said means for determining a hub-like weight of a node comprises:

means for choosing a backward start vector;

means for determining a node weight using the non-compound, non-normalized Backward operator;

means for normalizing the node weight; and

means for testing for convergence, wherein said means for determining a node weight and means for normalizing the node weight are configured to repeat their respective operations until the node weight converges to a constant value.

35. The system of claim 32, further comprising:

means for determining a principal eigenvector of a matrix.

36. The system of claim 32, further comprising:

means for selecting a search term.

37. The system of claim 32, further comprising:

means for ranking the textual content of the node.