Method for assigning relative quality scores to a collection of linked documents

• US 20060143197A1
• Filed: 12/23/2005
• Published: 06/29/2006
• Est. Priority Date: 12/23/2004
• Status: Active Grant

• Current Assignee: Connexity, Inc.
• Original Assignee: Become Incorporated (Connexity, Inc.)
• Inventors: Kaul, Rohit, Yun, Yeogirl, Kadluczka, Marcin, Kim, Seong-Gon
• Granted Patent: US 7,797,344 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A method for assigning relative quality scores to a collection of linked documents is presented. The method includes constructing a spring network according to a connectivity graph of a linked database and determining the strength of inter-nodal springs based on the link structure of the network and the displacements on end-nodes. The method may further include computing the displacements of the nodes in a spring network through an iterative process and obtaining the quality scores for documents from the converged displacements of nodes. The method may also include obtaining the relative quality scores for groups of documents. The method may further include assigning topic-specific quality scores to documents in a linked database.

Claims

1. A computer-implemented method for assigning scores to a plurality of linked documents, at least some of the documents being hypermedia documents, comprising:

constructing a spring network according to a connectivity graph of a collection of documents and links among the documents;

identifying a plurality of nodes as reference nodes and others as regular nodes;

applying a predetermined amount of displacements on the reference nodes;

computing the displacements of regular nodes in the spring network; and

assigning scores to documents based on the displacements of the nodes that correspond to the documents.

2. The method of claim 1, wherein the constructing comprises:

adding one node for each document in the collection;

adding one additional spring to each node; and

connecting nodes with elastic springs according to a link structure of the documents in the collection.

3. The method of claim 2, wherein strength of the additional springs is uniform and proportional to a full strength of the inter-nodal springs.

4. The method of claim 2, wherein strength of the additional springs is different for each node based on a classification of a corresponding document.

5. The method of claim 1, wherein the amount of displacements applied to reference nodes is uniform.

6. The method of claim 1, wherein the amount of displacements applied to reference nodes is dependent on a class of the associated documents.

7. The method of claim 1, wherein the computing comprises:

initializing an input displacement vector; and

repeating the steps of;

a) adjusting strength of inter-nodal springs;

b) computing an output displacement vector;

c) comparing the output displacement vector with the input displacement vector for convergence, and terminating the procedure if converged; and

d) if not converged, combining the input and output displacement vectors to generate a new input displacement vector.

8. The method of claim 7, wherein strength of the inter-nodal springs is adjusted based on current values of displacements of two end-nodes and weighting factors of links between the two end-nodes.

9. The method of claim 8, wherein the weighting factors of links have predetermined constant values.

10. The method of claim 8, wherein the weighting factors of links have a uniform value corresponding to a reciprocal of a total number of links outbound from an originating document.

11. The method of claim 8, wherein weighting factors of links have variable values, which depend on a number of outbound links, an offset of the link, a size of the paragraph where the link is located, and whether the link points to a document in a same site or a different site.

12. The method of claim 7, wherein computing the output displacement vector comprises balancing a total force on each node.

13. The method of claim 7, wherein computing the output displacement vector comprises minimizing a total strain energy of the spring network.

26. The method of claim 1, wherein identifying a plurality of nodes as reference nodes comprises identifying nodes that corresponds to documents that are authoritative in a specific topic.

14. A computer-implemented method for assigning scores to a plurality of groups of linked documents, at least some of the documents being hypermedia documents, comprising:

constructing a spring network according to a connectivity graph of a collection of groups of documents and links among the documents;

identifying a plurality of nodes as reference nodes and others as regular nodes;

applying a predetermined amount of displacements on the reference nodes;

computing the displacements of regular nodes in the spring network; and

assigning scores to groups of documents based on the displacements of the nodes that correspond to the documents.

15. The method of claim 14, wherein the constructing comprises:

dividing documents in a collection into groups;

adding one node for each group in the collection;

adding one additional spring to each node;

connecting nodes with elastic springs according to a link structure of the groups of documents in the collection;

adding one additional node for each group that contains at least one reference documents; and

connecting each node to its associated additional node with an elastic spring with strength corresponding to a number of reference pages in the group.

16. The method of claim 15, wherein the strength of the additional springs is uniform and proportional to a full strength of inter-nodal springs.

17. The method of claim 15, wherein the strength of the additional springs is different for each group based on a classification of the group.

18. The method of claim 14, wherein the amount of displacements applied to reference nodes is uniform.

19. The method of claim 14, wherein the amount of displacements applied to reference nodes is dependent on a class of the associated groups;

20. The method of claim 14, wherein the computing comprises:

initializing an input displacement vector; and

repeating the steps of;

a) adjusting strength of inter-nodal springs;

b) computing an output displacement vector;

c) comparing the output displacement vector with the input displacement vector for convergence, and terminating the procedure if converged; and

d) if not converged, combining the input and output displacement vectors to generate a new input displacement vector.

21. The method of claim 20, wherein the strength of the inter-nodal springs is adjusted based on displacements of two end-nodes and weighting factors of the links between the two end-nodes.

22. The method of claim 21, wherein the weighting factors of inbound links have predetermined constant values.

23. The method of claim 21, wherein the weighting factors of inbound links have a uniform value corresponding to a reciprocal of a total number of links outbound from an originating group of documents.

24. The method of claim 20, wherein computing the output displacement vector comprising balancing a total force on each node.

25. The method of claim 20, wherein computing the output displacement vector comprises minimizing a total strain energy of the spring network.

27. A computer-implemented method for assigning scores to a plurality of linked documents, at least some of the documents being hypermedia documents, comprising:

constructing a spring network according to the connectivity graph of a collection of documents and links among the documents;

identifying a plurality of nodes as a first set of reference nodes and others as a first set of regular nodes;

applying a predetermined amount of displacements on the first set of reference nodes;

computing the displacements of the first set of regular nodes in the spring network; and

identifying a plurality of nodes as a second set of reference nodes that may differ from the first set and other nodes as a second set of regular nodes;

applying a predetermined amount of displacements on the second set of reference nodes;

computing the displacements of the second set of regular nodes in the spring network; and

assigning scores to documents based on the second set of displacements of the nodes that correspond to the documents.

28. The method of claim 27, wherein the computing the second set of displacements comprises:

initializing an input displacement vector;

setting a strength of inter-nodal springs based on a first set of displacements of two end-nodes and a weighting factors of the links between the two end-nodes; and

repeating the steps of;

a) computing an output displacement vector;

b) comparing the output displacement vector with the input displacement vector for convergence, and terminating the procedure if converged; and

c) if not converged, combining the input and output displacement vectors to generate a new input displacement vector.