Locally computable spam detection features and robust pagerank

• US 8,010,482 B2
• Filed: 03/03/2008
• Issued: 08/30/2011
• Est. Priority Date: 03/03/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hopcroft, John E, Teng, Shang-Hua, Prakash, Amit, Andersen, Reid Marlow, Jain, Kamal, Mirrokni, Seyed Vahab, Borgs, Christian Herwarth, Chayes, Jennifer Tour
• Primary Examiner(s): Fernandez Rivas; Omar F
• Application Number:
  US12/041,474
• Publication Number:
  US 20090222435A1
• Time in Patent Office: 1,275 Days
• Field of Search: None
• US Class Current: 706/62
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

The claimed subject matter provides a system and/or a method that facilitates reducing spam in search results. An interface can obtain web graph information that represents a web of pages. A spam detection component can determines one or more features based at least in part on the web graph information. The one or more features can provide indications that a particular page of the web graph is spam. In addition, a robust rank component is provided that limits amount of contribution a single page can provide to the target page.

Claims

1. A computer-implemented system that facilitates reducing spam in search results, comprising:

one or more processors; and

memory, communicatively coupled to the one or more processors, for storing;

an interface that obtains web graph information associated with a web graph;

a spam detection component that determines one or more features based at least in part on the web graph information, the one or more features indicating pages of the web graph that are spam; and

a robust rank component that ranks at least one page of the web graph, the robust rank component including a contribution limiting component that restricts a contribution of a page in a supporting set of the at least one page, the contribution limiting component decreasing the contribution of the page in the supporting set to a value no greater than a predetermined threshold.

2. The system of claim 1, wherein the spam detection component includes a contribution vector component that ascertains a contribution vector of a target page in the web graph, the contribution vector including pages in the web graph that contribute to a rank of the target page.

3. The system of claim 2, wherein the contribution vector further indicates an amount of contribution for each included page.

4. The system of claim 2, wherein the spam detection component further includes a supporting set component that evaluates a supporting set of the target page based at least in part on the contribution vector.

5. The system of claim 4, wherein the supporting set of the target page includes pages of the contribution vector that provide an amount of contribution greater than the threshold.

6. The system of claim 4, wherein the spam detection component further includes an unsupervised feature component that generates one or more unsupervised learning features based at least in part on the supporting set and contribution vector of the target page.

7. The system of claim 6, wherein the unsupervised learning features facilitate labeling the target page as one of a spam page or a non spam page.

8. The system of claim 6, wherein the unsupervised learning features include at least one of a size of the supporting set of the target vector, a percentage of total contribution to the target page provided by pages in the supporting set of the target page, and an I.sub.2 norm of the contribution provided by pages in the supporting set of the target page or a conductance of the supporting set of the target page.

9. The system of claim 4, wherein the interface further collects preexisting label information related to the obtained web graph information, the preexisting label information indicating pages in the web graph previously labeled as one of spam or non spam.

10. The system of claim 9, wherein the spam detection component further includes a supervised features component that generates one or more supervised learning features based at least in part on the supporting set of the target page and the preexisting label information.

11. The system of claim 10, wherein the supervised features component determines a set of pages included in the supporting set of the target page that are labeled as spam.

12. The system of claim 11, wherein the supervised learning features include at least one of a ratio between the size of the set of spam pages in the supporting set of the target page and the supporting set of the target page or a ratio of the contribution derived from pages labeled spam to the total contribution provided by pages in the supporting set of the target page.

13. The system of claim 1, further comprising an approximation component that produces an approximate contribution vector of a target page based at least in part on a local region of the web graph.

14. The system of claim 13, wherein the approximation component generates the approximate contribution vector based at least in part on an approximate error parameter, an overall rank of the target page and a teleportation parameter.

15. The system of claim of claim 14, wherein the spam detection component employs the approximate contribution vector generated by the approximation component to determine the one or more features.

16. A method that facilitates reducing a rank of spam pages in a web graph, comprising:

evaluating, by a computing device, a contribution vector of a target page in the web graph, the contribution vector including individual contributions of other pages in the web graph to the target page;

ascertaining, by the computing device, a supporting set of the target page, the supporting set including pages in the contribution vector that provide a contribution above a pre-determined threshold;

determining, by the computing device, if contributions from pages in the supporting set exceed a predetermined maximum value; and

restricting, by the computing device, the determined contributions to no more than the predetermined maximum value.

17. The method of claim 16, further comprising summing a minimum of the contributions of pages in the web graph and the threshold value to ascertain an overall rank of the target page.

18. The method of claim 16, wherein the evaluating the contribution vector includes evaluating an approximate contribution vector in accordance with an approximation error parameter, the approximate contribution vector being based upon local approximations of a region of the web graph.

19. A system that facilitates reducing spam created via engineered link structures, comprising:

one or more processors; and

computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising;

obtaining an approximation of a contribution vector for a target page;

evaluating an approximate supporting set based upon the approximation of the contribution vector;

determining one or more unsupervised learning features according to the approximate supporting set;

ascertaining one or more supervised learning features based at least in part on the approximate supporting set and a set of preexisting labels; and

labeling the target page as one of spam or non spam based at least in part on the unsupervised learning features or the supervised learning features.