System, method and computer program product for comprehensive collusion detection and network traffic quality prediction

• US 8,561,184 B1
• Filed: 06/10/2010
• Issued: 10/15/2013
• Est. Priority Date: 02/04/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Adometry, Inc. (Alphabet Inc.)
• Inventors: Marsa, Robert Lee, Doddi, Srinivas Rao
• Primary Examiner(s): Kim, Jung
• Assistant Examiner(s): Tran, Tri
• Application Number:
  US12/797,904
• Time in Patent Office: 1,223 Days
• Field of Search: 726/22
• US Class Current: 726/22
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 63/168 above the transport layer
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34

Abstract

Embodiments disclosed herein seamlessly integrate several components into a comprehensive collusion detection and traffic quality prediction system, including a strong modeling module for processing historical click data and transforming potential collusions hidden therein into solvable graph partitioning (network) and/or vector space clustering (pattern) models, a scalable and robust toolkit comprising a plurality of graph partitioning and clustering heuristics for analyzing and generating high density subgraphs and high dimensional clusters or groups, and a post processing module for extracting entities from the subgraphs and clusters and placing them on global block lists. Entities thus listed can be blocked from client networks in real time. As such, high traffic quality can be predicted. A job scheduler may schedule individual jobs from the modeling module based on the number of available resources in a distributed computing environment to minimize completion time while balancing load.

Claims

1. A system, comprising:

a modeling module embodied on a non-transitory computer readable medium for processing historical click data received from a client and generating one or more models, wherein each of the one or more models formulates potential collusion among entities in the historical click data as a graph partitioning problem, a vector space clustering problem, or a combination thereof;

a toolkit comprising a plurality of heuristics for solving problems formulated by the modeling module, the problems including graph partitioning problems, vector space clustering problems, or a combination thereof, wherein the plurality of heuristics comprises;

a first set of heuristics for solving graph partitioning problems formulated by the modeling module to generate subgraphs of connected nodes representing entities involved in suspicious activities;

a second set of heuristics for solving vector space clustering problems formulated by the modeling module to generate high dimensional vector space clusters or groups of entities having similar patterns over a period of time; and

a third set of heuristics for transforming graphs into vector spaces and performing clustering associated therewith; and

a post processor comprising a set of rules for filtering results from the toolkit, extracting entities of interest, and placing the entities of interest on global block lists, wherein filtering the results comprises eliminating subgraphs that do not meet a density requirement and removing known entities to eliminate or reduce false positives.

2. The system of claim 1, further comprising:

a job scheduler for assigning jobs, each corresponding to one of the one or more models.

3. The system of claim 2, wherein the plurality of heuristics is performed by a plurality of processors in a distributed computing environment having a plurality of main memories.

4. The system of claim 1, wherein the global block lists comprise Internet Protocol (IP) addresses to be blocked from entering a plurality of client networks.

5. The system of claim 1, further comprising:

a real time click scoring engine for scoring incoming real time click data utilizing the global block lists.

6. The system of claim 1, wherein the historical click data comprises a plurality of clicks generated over a period of time and information associated with the plurality of clicks, and wherein the information comprises visitor Internet Protocol (IP) address information, date and time information, publisher information, referrer information, user-agent information, searched keywords, and cookie.

7. A method, comprising:

at a server computer in a distributed computing environment, receiving historical click data from a client computer connected to the distributed computing environment over a network;

the server computer processing the historical click data and generating one or more models, wherein each of the one or more models formulates potential collusion among entities in the historical click data as a graph partitioning problem, a vector space clustering problem, or a combination thereof, and wherein a modeling module performs the formulating;

the server computer applying a plurality of heuristics to solve problems formulated by the modeling module, the problems including graph partitioning problems, vector space clustering problems, or a combination thereof, wherein the plurality of heuristics comprises;

a first set of heuristics for solving graph partitioning problems formulated by the modeling module to generate subgraphs of connected nodes representing entities involved in suspicious activities;

a second set of heuristics for solving vector space clustering problems formulated by the modeling module to generate high dimensional vector space clusters or groups of entities having similar patterns over a period of time; and

a third set of heuristics for transforming graphs into vector spaces and performing clustering associated therewith; and

the server computer post processing results from the applying step, wherein the post processing comprises;

eliminating subgraphs that do not meet a density requirement;

removing known entities to eliminate or reduce false positives;

extracting entities of interest from high density subgraphs and high dimensional vector space clusters or groups; and

placing the entities of interest on global block lists.

8. The method according to claim 7, further comprising:

updating the global block lists dynamically or per a time interval.

9. The method according to claim 8, wherein the global block lists are updated daily.

10. The method according to claim 7, further comprising:

utilizing the global block lists to score click data in real time.

11. The method according to claim 7, further comprising:

blocking the entities of interest on the global block lists from entering a plurality of client networks.

12. The method according to claim 11, wherein the global block lists comprise Internet Protocol (IP) addresses of the entities of interest.

13. The method according to claim 7, further comprising:

distributing a plurality of jobs, wherein each of the jobs corresponds to one of the one or more models.

14. A computer program product comprising at least one non-transitory computer readable medium storing computer instructions translatable by at least one processor to implement:

a modeling module for processing historical click data received from a client and generating one or more models, wherein each of the one or more models formulates potential collusion among entities in the historical click data as a graph partitioning problem, a vector space clustering problem, or a combination thereof;

a toolkit comprising a plurality of heuristics for solving problems formulated by the modeling module, the problems including graph partitioning problems, vector space clustering problems, or a combination thereof, wherein the plurality of heuristics comprises;

a first set of heuristics for solving graph partitioning problems formulated by the modeling module to generate subgraphs of connected nodes representing entities involved in suspicious activities;

a second set of heuristics for solving vector space clustering problems formulated by the modeling module to generate high dimensional vector space clusters or groups of entities having similar patterns over a period of time; and

a third set of heuristics for transforming graphs into vector spaces and performing clustering associated therewith; and

a post processor comprising a set of rules for filtering results from the toolkit, extracting entities of interest, and placing the entities of interest on global block lists, wherein filtering the results comprises eliminating subgraphs that do not meet a density requirement and removing known entities to eliminate or reduce false positives.

15. The computer program product of claim 14, wherein the computer instructions are further translatable by the at least one processor to implement a job scheduler for assigning jobs, each corresponding to one of the one or more models.

16. The computer program product of claim 14, wherein the computer instructions are further translatable by the at least one processor to perform:

updating the global block lists dynamically or per a time interval.

17. The computer program product of claim 14, wherein the global block lists are updated daily.

18. The computer program product of claim 14, wherein the computer instructions are further translatable by the at least one processor to perform:

utilizing the global block lists to score click data in real time.

19. The computer program product of claim 14, wherein the computer instructions are further translatable by the at least one processor to perform:

blocking the entities of interest on the global block lists from entering a plurality of client networks.

20. The computer program product of claim 14, wherein the global block lists comprise Internet Protocol (IP) addresses of the entities of interest.