Method for node classification and scoring by combining parallel iterative scoring calculation

• US 20070179943A1
• Filed: 02/01/2006
• Published: 08/02/2007
• Est. Priority Date: 02/01/2006
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Maghoul, Farzin, Hegerty, Ian
• Granted Patent: US 7,584,183 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A plurality of documents is scored, where at least some of the documents are characterized by at least one link from at least one other of the documents. For each of at least particular ones of the plurality of documents, a score is assigned to that particular document, with respect to a topic, based at least in part on an incoherency characteristic associated with at least one document linking to that particular document.

Claims

1. A method of scoring a plurality of documents, where at least some of the documents are characterized by at least one link from at least one other of the documents, the method comprising:

for each of at least particular ones of the plurality of documents, assigning a score to that particular document, with respect to a topic, based at least in part on an incoherency characteristic associated with at least one document linking to that particular document.

2. The scoring method of claim 1, wherein:

the step of assigning a score to that particular document, with respect to the topic, based at least in part on an incoherency characteristic associated with at least one document linking to that particular document includes

treating the incoherency characteristic as a weighting factor with respect to assigning a score to that particular document, with respect to the topic.

3. The scoring method of claim 1, wherein:

the step of assigning a score to a particular document, with respect to the topic, based at least in part on an incoherency characteristic associated with at least one document linking to that particular document includes;

assigning a score to that particular document, with respect to the topic, based on the score, with respect to the topic, of each of the at least one document linking to that particular document, weighted by the incoherency characteristic associated with the at least one document linking to that particular document.

4. The scoring method of claim 1, further comprising:

determining the incoherency characteristic associated with each of the at least one document linking to that particular document includes, for each of the at least one document linking to that particular document, processing an indication of topics associated with that linking document.

5. The scoring method of claim 4, wherein:

processing an indication of topics associated with that linking document includes determining the incoherency characteristic as a function of scores, with respect to a plurality of topics, for that linking document.

6. The scoring method of claim 5, wherein:

the step of assigning a score to a particular document, with respect to the topic, based at least in part on an incoherency characteristic associated with at least one document linking to that particular document includes;

weighting the score assigned to that particular document, for the topic, by the incoherency characteristic associated with the at least one document linking to that particular document, so as to result in less weighting of the score assigned to that particular document, for the topic, the greater the number of topics associated with that linking document.

7. The scoring method of claim 6, wherein:

the number of topics associated with that linking document is determined based on a score, with respect to that linking document, for each of the topics associated with that linking document.

8. The scoring method of claim 1, wherein:

the score assigning step is performed iteratively among the plurality of documents.

9. The scoring method of claim 1, further comprising:

determining a value indicative of a probability of not linking to any of the at least particular ones of the plurality of documents; and

accounting for the determined value with respect to scores of documents other than the at least particular ones of the plurality of documents.

10. The method of claim 1, further comprising:

repeating the score assigning step for each of the at least particular one of the plurality of documents, for each of a plurality of topics.

11. The method of claim 10, further comprising:

targeting an advertisement to a viewer of a particular page based on the topic scores.

12. The method of claim 10, wherein:

the plurality of topics are countries associated with the documents; and

the method further comprises adjusting a search result based on the topic scores.

13. The method of claim 10, further comprising:

in response to a search query from a user, presenting a plurality of assisted search suggestions, wherein presenting the plurality of assisted search suggestions includes considering preferences of the user relative to determined topic scores for documents chosen by other users in response to particular assisted search suggestions.

14. The method of claim 10, further comprising:

determining for each document a factor that is nominally indicative of whether that document is spammy, including considering topic scores for each document, across a plurality of topics, relative to a link popularity measure for that document.

15. The method of claim 1, wherein:

the incoherency characteristic for the document linking to that particular document is adjusted based on a relationship between topics of the linking document to topics of that particular document.

16. The method of claim 15, wherein:

adjusting the incoherency characteristic includes indicating a linking document as less coherent, relative to that particular document, based on a generalization or specialization relationship between the topics of the linking document to topics of that particular document.

17. A computing device operable to perform the method of claim 1.

18. A method of operating a computing device to search a network of pages, comprising:

querying to a collection of information about the pages of the network of pages, wherein the collection of information about the pages includes;

an index of the pages; and

a collection of scores for the pages generated according to the method of claim 1;

receiving, in response to the query, an indication of pages according to the index of pages, ranked according to the collection of scores.

19. The method of claim 18, further comprising:

accessing at least one of the pages indicated by the received indication of pages.

20. A computer program product for scoring a plurality of documents, where at least some of the documents are characterized by at least one link from at least one other of the documents, the computer program product comprising at least one computer-readable medium having computer program instructions stored therein which are operable to cause at least one computing device to:

for each of at least particular ones of the plurality of documents, assign a score to that particular document, with respect to a topic, based at least in part on an incoherency characteristic associated with at least one document linking to that particular document.

21. The computer program product of claim 20, wherein:

the computer program instructions operable to cause the at least one computing device to assign a score to that particular document, with respect to the topic, based at least in part on an incoherency characteristic associated with at least one document linking to that particular document includes

computer program instructions operable to cause the at least one computing device to treat the incoherency characteristic as a weighting factor with respect to assigning a score to that particular document, with respect to the topic.

22. The computer program product of claim 20, wherein:

the computer program instructions operable to cause the at least one computing device to assign a score to a particular document, with respect to the topic, based at least in part on an incoherency characteristic associated with at least one document linking to that particular document includes;

computer program instructions operable to cause the at least one computing device to assign a score to that particular document, with respect to the topic, based on the score, with respect to the topic, of each of the at least one document linking to that particular document, weighted by the incoherency characteristic associated with the at least one document linking to that particular document.

23. The computer program product of claim 20, wherein:

the computer program instructions further include computer program instructions operable to cause the at least one computing device to determine the incoherency characteristic associated with each of the at least one document linking to that particular document includes, for each of the at least one document linking to that particular document, processing an indication of topics associated with that linking document.

24. The computer program product of claim 23, wherein:

the computer program instructions operable to cause the at least one computing device to process an indication of topics associated with that linking document includes computer program instructions operable to cause the at least one computing device to determine the incoherency characteristic as a function of scores, with respect to a plurality of topics, for that linking document.

25. The computer program product of claim 24, wherein:

the computer program instructions operable to cause the at least one computing device to assign a score to a particular document, with respect to the topic, based at least in part on an incoherency characteristic associated with at least one document linking to that particular document includes;

computer program instructions operable to cause the at least one computing device to weight the score assigned to that particular document, for the topic, by the incoherency characteristic associated with the at least one document linking to that particular document, so as to result in less weighting of the score assigned to that particular document, for the topic, the greater the number of topics associated with that linking document.

26. The computer program product of claim 25, wherein:

the number of topics associated with that linking document is determined based on a score, with respect to that linking document, for each of the topics associated with that linking document.

27. The computer program product of claim 20, wherein:

the computer program instructions are operable to cause the at least one computing device to perform the score assigning iteratively among the plurality of documents.

28. The computer program product of claim 20, wherein:

the computer program instructions further include computer program instructions operable to cause the at least one computing device to;

determine a value indicative of a probability of not linking to any of the at least particular ones of the plurality of documents; and

account for the determined value with respect to scores of documents other than the at least particular ones of the plurality of documents.