Methods and systems of identifying a device using strong component conflict detection

• US 9,807,198 B2
• Filed: 08/20/2015
• Issued: 10/31/2017
• Est. Priority Date: 08/20/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gat, Yoram
• Primary Examiner(s): Won, Michael Y
• Application Number:
  US14/831,092
• Publication Number:
  US 20170054827A1
• Time in Patent Office: 803 Days
• Field of Search: 709203, 709220, 709223, 709230
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70

Abstract

A system implements a method of identifying an electronic device that requests access to a web service. A processor may receive, from an electronic device via a communication network, a first group of requests to access one or more web service functions on behalf of a registered user of the web service. The processor will receive, in connection each of the requests in the first group, one or more data points about the electronic device from which the request originated, will analyze the data points and grouping the requests into a plurality of strong components so that each strong component comprises requests that originate from either a single electronic device or from a plurality of electronic devices having one or more similar properties, and will generate a graph representative of one or more associations between or among the strong components within the grouping.

Claims

1. A method of identifying an electronic device that requests access to a web service, comprising:

by one or more processors of a provider of a web service;

receiving, from one or more electronic devices of a registered user of the web service via a communication network, a first group of requests to access one or more web service functions,

receiving, in connection each of the requests in the first group, one or more data points about an electronic device from which the request originated,

analyzing the data points and grouping the requests into a plurality of strong components so that each strong component comprises requests that originate from either a single electronic device or from a plurality of electronic devices having one or more similar properties,

organizing the strong components into one or more groupings based on a shared characteristic,

for each grouping, generating a graph representative of one or more associations between or among the strong components within the grouping by;

identifying each strong component within the grouping as a node of the graph,

for each pair of strong components within the grouping;

determining whether a conflict exists, and

in response to determining that a conflict exists, adding an edge to the graph that connects the pair of strong components,

identifying, based on the edges, one or more sets of strong components, wherein each set comprises one or more strong components whose data points likely originated from a same electronic device,

for each set, assigning the nodes associated with the identified strong components within the set a same designation,

storing characteristics of one or more of the sets in a profile for the registered user, and

storing the graph in a data store.

2. The method of claim 1, further comprising:

receiving, from the registered user via a requesting electronic device, an additional request to access one of the more of the web service functions;

analyzing the additional request to determine whether the requesting electronic device is one of the electronic devices in the registered user'"'"'s profile; and

upon determining that the requesting electronic device is one of the electronic devices in the user'"'"'s profile, providing the web service functions of the additional request to the requesting electronic device.

3. The method of claim 1, wherein organizing the strong components into one or more groupings based on a shared characteristic comprises organizing the strong components into one or more groupings based on one or more of the following:

an operating system; and

a device model.

4. The method of claim 1, wherein determining whether a conflict exists comprises comparing one or more data points of a first strong component in the pair to one or more data points of a second component in the pair to determine whether they conflict.

5. The method of claim 1, wherein identifying, based on the edges, one or more sets of strong components comprises using a graph labeling technique to:

identify a plurality of nodes of the graph that are not connected to one another by an edge; and

identify the strong components that correspond to the plurality of nodes as a set.

6. The method of claim 5, wherein using a graph labeling technique comprises using a graph coloring technique.

7. The method of claim 6, further comprising assigning the nodes in the set a same color.

8. A web service provider system, comprising:

a processor; and

a computer-readable storage medium comprising one or more programming instructions configured to cause the processor to;

receive, from an electronic device via a communication network, a first group of requests to access one or more web service functions on behalf of a registered user of the web service,

receive, in connection each of the requests in the first group, one or more data points about the electronic device from which the request originated,

analyze the data points and grouping the requests into a plurality of strong components so that each strong component comprises requests that originate from either a single electronic device or from a plurality of electronic devices having one or more similar properties,

organize the strong components into one or more groupings based on a shared characteristic,

for each grouping, generate a graph representative of one or more associations between or among the strong components within the grouping by;

identifying each strong component within the grouping as a node of the graph,

for each pair of strong components within the grouping;

determining whether a conflict exists, and

in response to determining that a conflict exists, adding an edge to the graph that connects the pair of strong components,

identifying, based on the edges, one or more sets of strong components, wherein each set comprises one or more strong components whose data points likely originated from a same electronic device,

for each set, assigning the nodes associated with the identified strong components within the set a same designation,

storing characteristics of one or more of the sets in a profile for the registered user, and

storing the graph in a data store.

9. The web service provider system of claim 8, further comprising additional programming instructions configured to cause the processor to:

receive, from the registered user via a requesting electronic device, an additional request to access one of the more of the web service functions;

analyze the additional request to determine whether the requesting electronic device is one of the devices in the registered user'"'"'s profile; and

upon determining that the requesting electronic device is one of the electronic devices in the user'"'"'s profile, provide the web service functions of the additional request to the requesting electronic device.

10. The web service provider system of claim 8, wherein the programming instructions that are configured to cause the processor to organize the strong components into one or more groupings based on a shared characteristic comprise one or more programming instructions that are configured to cause the processor to organize the strong components into one or more groupings based on one or more of the following:

an operating system; and

a device model.

11. The system of claim 8, wherein the programming instructions that are configured to cause the processor to determine whether a conflict exists comprise one or more programming instructions that are configured to cause the processor to compare one or more data points of a first strong component in the pair to one or more data points of a second component in the pair to determine whether they conflict.

12. The system of claim 8, wherein the programming instructions that are configured to cause the processor to identify, based on the edges, one or more sets of strong components comprise one or more programming instructions that are configured to cause the processor to use a graph labeling technique to:

identify a plurality of nodes of the graph that are not connected to one another by an edge; and

identify the strong components that correspond to the plurality of nodes as a set.

13. The system of claim 12, wherein the programming instructions that are configured to cause the processor to use a graph labeling technique comprise one or more programming instructions that are configured to cause the processor to use a graph coloring technique.

14. The system of claim 13, further comprising additional programming instructions configured to cause the processor to assign the nodes in the set a same color.