Link-based spam detection

• US 7,533,092 B2
• Filed: 08/04/2005
• Issued: 05/12/2009
• Est. Priority Date: 10/28/2004
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Gyongyi, Zoltan Istvan, Berkhin, Pavel, Pedersen, Jan
• Primary Examiner(s): Fleurantin; Jean B
• Application Number:
  US11/198,471
• Publication Number:
  US 20060095416A1
• Time in Patent Office: 1,377 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 715/513, 715/234
• 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
• 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 computer implemented method of ranking search hits in a search result set. The computer-implemented method includes receiving a query from a user and generating a list of hits related to the query, where each of the hits has a relevance to the query, where the hits have one or more boosting linked documents pointing to the hits, and where the boosting linked documents affect the relevance of the hits to the query. The method associates a metric to each of at least a subset of the hits, the metric being representative of the number of boosting linked documents that point to each of at least a subset of the hits and which artificially inflate the relevance of the hits. The method then compares the metric, which is representative of the size of a spam farm pointing to the hit, with a threshold value, processes the list of hits to form a modified list based in part on the comparison, and transmits the modified list to the user.

Claims

1. A computer implemented method of ranking search hits in a search result set, the method comprising:

receiving a query from a user;

generating a list of hits related to the query,

wherein each of the hits has a relevance to the query,

wherein at least one hit is pointed to by a link in a boosting document, and

wherein the link in the boosting document artificially elevates the relevance of the at least one hit to the query;

determining a first measure for said at least one hit, wherein the first measure is a link- based popularity measure for said at least one hit;

determining a second measure for said at least one hit, wherein the second measure is a trustworthiness measure for said at least one hit indicative of the likelihood that said at least one hit is a reputable document;

generating a metric for said at least one hit, based at least in part on a discrepancy between the first measure and the second measure;

wherein the metric is representative of the number of boosting documents that contain links, to said at least one hit, which artificially elevate the relevance of said at least one hit to the query;

comparing a threshold value to a value that is based, at least in part, on the metric;

processing the list of hits to form a modified list based in part on the comparing, wherein said at least one hit is either excluded from said modified list, or is presented in said modified list with a lower relevance than was attributed to said at least one hit in said list of hits; and

transmitting the modified list to the user as a response to said query.

2. The method of claim 1, wherein said generating said metric is performed prior to said receiving the query.

3. The method of claim 1, wherein determining the second measure comprises

forming a seed set of reputable documents, the seed set of reputable documents comprising links to other documents;

assigning a trust value to each of the documents in the seed set;

propagating the trust value to each of a plurality of documents being pointed to by at least one of the documents in the seed set; and

assigning a prorated trust value to each of the plurality of documents being pointed to by at least one of the documents in the seed set.

4. The method of claim 3, wherein said forming the seed set comprises determining for each of a plurality of documents an outlink metric representative of the number of outlinks contained in each of the plurality of documents, respectively;

ranking the plurality of documents using the outlink metric;

identifying a set of highest ranked documents in the plurality of documents;

evaluating the quality of each of the set of highest ranked documents;

forming a modified set of highest ranked documents by removing from the set of highest ranked documents those documents deemed inappropriate; and

forming the seed set using the modified set of highest ranked documents.

5. The method of claim 1 wherein:

the steps of determining a first measure, determining a second measure, and generating a metric are performed for each hit in the list of hits;

the method further includes the steps of;

after generating the metric for each hit in the list of hits, sorting the list based on the metrics generated for the hits in the list of hits, to produce a sorted list;

identifying a top portion of the sorted list, wherein the hits in said top portion are associated with metrics that are higher than hits that are not in said top portion;

for each hit in the top portion of the sorted list, determining whether to classify the hit as spam based on the ratio of the metric to the first measure.

6. A computer implemented computer-readable storage medium storing instruction for ranking search hits in a search result set, instructions including instructions for performing the steps of:

receiving a query from a user;

generating a list of hits related to the query,

wherein each of the hits has a relevance to the query,

wherein at least one hit is pointed to by a link in a boosting document, and

wherein the link in the boosting document artificially elevates the relevance of the at least one hit to the query;

determining a first measure for said at least one hit, wherein the first measure is a link-based popularity measure for said at least one hit;

determining a second measure for said at least one hit, wherein the second measure is a trustworthiness measure for said at least one hit indicative of the likelihood that said at least one hit is a reputable document;

generating a metric for said at least one hit, based at least in part on a discrepancy between the first measure and the second measure;

wherein the metric is representative of the number of boosting documents that contain links, to said at least one hit, which artificially elevate the relevance of said at least one hit to the query;

comparing a threshold value to a value that is based, at least in part, on the metric;

processing the list of hits to form a modified list based in part on the comparing, wherein said at least one hit is either excluded from said modified list, or is presented in said modified list with a lower relevance than was attributed to said at least one hit in said list of hits; and

transmitting the modified list to the user as a response to said query.

7. The computer-readable storage medium of claim 6, wherein generating said metric is performed prior to said receiving the query.

8. The computer-readable storage medium of claim 6, wherein determining the second measure comprises

forming a seed set of reputable documents, the seed set of reputable documents comprising links to other documents;

assigning a trust value to each of the documents in the seed set;

propagating the trust value to each of a plurality of documents being pointed to by at least one of the documents in the seed set; and

assigning a prorated trust value to each of the plurality of documents being pointed to by at least one of the documents in the seed set.

9. The computer-readable storage medium of claim 8, wherein said forming the seed set comprises

determining for each of a plurality of documents an outlink metric representative of the number of outlinks contained in each of the plurality of documents, respectively;

ranking the plurality of documents using the outlink metric;

identifying a set of highest ranked documents in the plurality of documents;

evaluating the quality of each of the set of highest ranked documents;

forming a modified set of highest ranked documents by removing from the set of highest ranked documents those documents deemed inappropriate; and

forming the seed set using the modified set of highest ranked documents.

10. The computer-readable medium of claim 6 wherein:

the steps of determining a first measure, determining a second measure, and generating a metric are performed for each hit in the list of hits;

the instructions further include instructions for performing the steps of;

after generating the metric for each hit in the list of hits, sorting the list based on the metrics generated for the hits in the list of hits, to produce a sorted list;

identifying a top portion of the sorted list, wherein the hits in said top portion are associated with metrics that are higher than hits that are not in said top portion;

for each hit in the top portion of the sorted list, determining whether to classify the hit as spam based on the ratio of the metric to the first measure.