Method for detecting link spam in hyperlinked databases

• US 8,250,114 B2
• Filed: 05/31/2011
• Issued: 08/21/2012
• Est. Priority Date: 08/18/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kamvar, Sepandar D., Haveliwala, Taher H., Jeh, Glen M.
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US13/149,806
• Publication Number:
  US 20110270890A1
• Time in Patent Office: 448 Days
• Field of Search: 707600-831, 709/215, 709/218
• US Class Current: 707/802
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A computer-implemented method identifies nodes that are beneficiaries of node importance inflating links in a directed graph of linked nodes. The directed graph of linked nodes corresponds to a linked database, and the nodes correspond to documents within the linked database. The method is performed by a computer system including one or more processors and memory storing one or more programs, the one or more processors executing the one or more programs to perform the method. The method includes computing, for each of at least a subset of the nodes in the directed graph, a respective quantity corresponding to a mathematical derivative of a node importance function, and performing a remedial action on a respective node in the directed graph in accordance with the respective computed quantity computed for the respective node.

Claims

1. A computer-implemented method for analyzing a directed graph of linked nodes, wherein the directed graph of linked nodes corresponds to a linked database, and wherein the nodes correspond to documents within the linked database, the method comprising:

at a computer system including one or more processors and memory storing one or more programs, the one or more processors executing the one or more programs to perform the operations of;

identifying nodes that are beneficiaries of node importance inflating links in the directed graph of linked nodes by computing, for each of at least a subset of the nodes in the directed graph, a respective quantity corresponding to a mathematical derivative of a node importance function; and

performing a remedial action on a respective node in the directed graph in accordance with the respective computed quantity computed for the respective node.

2. The method of claim 1, wherein performing the remedial action includes removing the respective node from the directed graph.

3. The method of claim 1, including normalizing the respective quantity in accordance with a respective rank for the node.

4. The method of claim 1, wherein the computing computes the mathematical derivative of the node importance function with respect to a coupling factor.

5. The method of claim 4, wherein the computing includes:

computing at least two intermediate quantities of the derivative of the node importance function for each of the set of nodes, each of the intermediate quantities computed using a different respective value of the coupling factor; and

averaging the intermediate quantities to produce the computed respective quantity.

6. The method of claim 4, wherein the coupling factor represents how tightly coupled the linked nodes are in the directed graph.

7. The method of claim 4, further including:

generating an adjusted importance for at least one node of the portion.

8. The method of claim 7, wherein the generating adjusts, for the at least one node, the importance by an amount proportional to the respective computed quantity.

9. The method of claim 1, wherein the computing includes:

calculating a matrix A(c) representing the directed graph, the matrix A(c) being an N×

N matrix that is a function of a link coupling coefficient c, where N is a number of nodes in the directed graph;

calculating a principal eigenvector of A(c), denoted x(c);

calculating a derivative with respect to c of x(c), denoted x′

(c); and

for at least one node, calculating from x′

(c) and a rank for the node, an inflation likelihood value S.

10. The method of claim 9, further comprising comparing the inflation likelihood value S with a predetermined spam threshold value.

11. A non-transitory computer readable storage medium storing one or more programs for analyzing a directed graph of linked nodes, wherein the directed graph of linked nodes corresponds to a linked database, and wherein the nodes correspond to documents within the linked database, the one or more programs for execution by one or more processors of a computer system, the one or more programs comprising instructions for:

identifying nodes that are beneficiaries of node importance inflating links in the directed graph of linked nodes by computing, for each of at least a subset of the nodes in the directed graph, a respective quantity corresponding to a mathematical derivative of a node importance function; and

performing a remedial action on a respective node in the directed graph in accordance with the respective computed quantity computed for the respective node.

12. The non-transitory computer readable storage medium of claim 11, wherein the instructions for performing the remedial action include instructions for removing the respective node from the directed graph.

13. The non-transitory computer readable storage medium of claim 11, the one or more programs further including instructions for normalizing the respective quantity in accordance with a respective rank for the node.

14. The non-transitory computer readable storage medium of claim 11, wherein the instructions for computing include instructions for computing the derivative of the node importance function with respect to a coupling factor.

15. The non-transitory computer readable storage medium of claim 14, wherein the instructions for computing include instructions for:

computing at least two intermediate quantities of the derivative of the node importance function for each of the set of nodes, each of the intermediate quantities computed using a different respective value of the coupling factor; and

averaging the intermediate quantities to produce the computed respective quantity.

16. The non-transitory computer readable storage medium of claim 14, wherein the coupling factor represents how tightly coupled the linked nodes are in the directed graph.

17. The non-transitory computer readable storage medium of claim 11, the one or more programs further including instructions for generating an adjusted importance for at least one node of the portion.

18. A system for analyzing a directed graph of linked nodes, the system comprising:

memory;

one or more processors;

one or more programs stored in the memory and configured for execution by the one or more processors, the one or more programs including instructions which, when executed by the one or more processors, cause the system to;

identify nodes that are beneficiaries of node importance inflating links in the directed graph of linked nodes by computing, for each of at least a subset of the nodes in the directed graph, a respective quantity corresponding to a mathematical derivative of a node importance function; and

perform a remedial action on a respective node in the directed graph in accordance with the respective computed quantity computed for the respective node.

19. The system of claim 18, wherein performing the remedial action includes removing the respective node from the directed graph.

20. The system of claim 18, the one or more programs further including instructions which cause the system to normalize the respective quantity in accordance with a respective rank for the node.

21. The system of claim 18, wherein computing includes instructions for computing the derivative of the node importance function with respect to a coupling factor.

22. The system of claim 21, wherein the instructions for computing includes instructions which cause the system to:

compute at least two intermediate quantities of the derivative of the node importance function for each of the set of nodes, each of the intermediate quantities computed using a different respective value of the coupling factor; and

average the intermediate quantities to produce the computed respective quantity.

23. The system of claim 21, wherein the coupling factor represents how tightly coupled the linked nodes are in the directed graph.

24. The system of claim 18, the one or more programs further including instructions which cause the system to generate an adjusted importance for at least one node of the portion.