Clustering based on a directed graph

• US 10,642,867 B2
• Filed: 09/15/2017
• Issued: 05/05/2020
• Est. Priority Date: 09/15/2017
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Inc.
• Inventors: Palanciuc, Virgil-Artimon
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US15/706,115
• Publication Number:
  US 20190087480A1
• Time in Patent Office: 963 Days
• Field of Search: 707737
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0269 based on user profile or attribute

Abstract

Various embodiments describe clustering of nodes of a directed graph based on the oriented edges of the directed graph and on a set of rules. In an example, each node represents a device identifier associated with a computing device. The device identifier facilitates an online activity provided by a computing service. A computing system accesses the directed graph and generates clusters that contain subsets of the nodes by at least iteratively updating the directed graph based on the set of rules. The set of rules specifies (i) removal of leaf nodes from the directed graph, (ii) reconnection of nodes that form a chain in the directed graph, and (iii) reconnection of nodes that form a split in the directed graph. The computing system also associates a client profile with a subset of the nodes contained in a cluster from the clusters.

Claims

1. A computer-implemented method for large-scale graph clustering, the computer-implemented method performed on a computing system and comprising:

accessing, by a clustering module hosted on the computing system, a directed graph generated based on data associated with online activities of computing devices, the directed graph comprising nodes and oriented edges connecting the nodes, each node representing a device identifier associated with one of the computing devices;

generating, by the clustering module, clusters that contain subsets of the nodes by at least iteratively updating the directed graph based on a set of rules, the set of rules specifying (i) removal of leaf nodes from the directed graph, (ii) reconnection of nodes that form a chain in the directed graph, and (iii) reconnection of nodes that form a split in the directed graph;

associating, by a profile module hosted on the computing system, a client profile with a subset of the nodes contained in a cluster from the clusters; and

customizing, by a client service module hosted on the computing system, an online activity of a computing device associated with a device identifier, the online activity customized according to the client profile based on a determination that the device identifier corresponds to a node from the subset of nodes associated with the client profile.

2. The computer-implemented method of claim 1, wherein the set of rules specify that, in a chain of nodes where oriented edges connect a first node to a second node and the second node to a third node, the first node should be reconnected to the third node, the oriented edge between the first node and the second node should be removed, and the oriented edge between the second node and the third node should be preserved.

3. The computer-implemented method of claim 1, wherein the set of rules specify that, in a split of nodes where oriented edges connect a first node to a second node and to a third node, the second node should be reconnected to the third node, the oriented edge between the first node and the second node should be removed, and the oriented edge between the first node and the third node should be preserved.

4. The computer-implemented method of claim 1, wherein the set of rules further specify that oriented edges connecting nodes that form a star in the directed graph should be preserved, wherein the star is formed when oriented edges connect each of a first node and a second node to a third node.

5. The computer-implemented method of claim 1, wherein the data is represented first in an undirected graph or a bipartite graph, and wherein representing the data in the directed graph comprises generating the directed graph from the undirected graph or the bipartite graph based on the set of rules.

6. The computer-implemented method of claim 5, wherein the directed graph is generated from the bipartite graph based on the set of rules specifying (i) a selection of a partition of interest from the bipartite graph and (ii) a minimum number of oriented edges to be maintained for the nodes in the directed graph based on connections between the nodes and a second partition of the bipartite graph.

7. The computer-implemented method of claim 6, wherein the set of rules specifies that, in the directed graph, a first oriented edge connects a first node to the first node from the partition of interest and a second oriented edge connects the first node to a second node from the partition of interest based on connections of the first node and the second node with a common node in the second partition.

8. The computer-implemented method of claim 1, further comprising:

assigning a label to each node; and

storing key-value pairs that correspond to the nodes and oriented edges, wherein a key of a key-value pair represents a first label of a first node, wherein a value of the key-value pair represents a second label of a second node, wherein an oriented edge connects the first node to the second node in the directed graph.

9. The computer-implemented method of claim 8, wherein the labels are numerically assigned, and wherein the key and the value in each key-value pair are stored based on a numerical value of a label corresponding to the key being smaller than a numerical value of a label corresponding to the value.

10. The computer-implemented method of claim 8, wherein iteratively updating the directed graph based on the set of rules specifying the removal of the leaf nodes comprises:

generating a set of reversed key-value pairs by reversing an order of a key and a value in each of the key-value pairs;

generating a candidate set of key-value pairs by removing a reversed key-value pair from the set of reversed key-value pairs based on a determination that a key of the reversed key-value pair is common with at least another reversed key-value pair; and

identifying a leaf node by subtracting the key-value pairs from the candidate set of key-value pairs based on keys of the key-value pairs and of the candidate set.

11. The computer-implemented method of claim 10, wherein iteratively updating the directed graph further comprises:

identifying that a key appears in the key-value pairs at a frequency that exceeds a threshold;

removing a subset of the key-value pairs that contain the key to generate a remaining set of key-value pairs, wherein the set of reversed key-value pairs and the candidate set are generated based on the remaining set of key-value pairs; and

subtracting the subset of the key-value pairs from the key-value pairs.

12. The computer-implemented method of claim 1, wherein iteratively updating the directed graph based on the set of rules comprises reconnecting the nodes that form the chain and reconnecting the nodes that form the split in the directed graph after the removal of the leaf nodes from the directed graph.

13. The computer-implemented method of claim 1, wherein removal of a leaf node comprises forming a complete set that contains the leaf node and an incomplete set, and wherein nodes are reconnected by applying the set of rules to the incomplete set.

14. A computing system comprising:

means for accessing a directed graph generated based on data associated with online activities of computing devices, the directed graph comprising nodes and oriented edges connecting the nodes, each node representing a device identifier associated with one of the computing devices;

means for generating clusters that contain subsets of the nodes by at least iteratively updating the directed graph based on a set of rules, the set of rules specifying (i) removal of leaf nodes from the directed graph, (ii) reconnection of nodes that form a chain in the directed graph, and (iii) reconnection of nodes that form a split in the directed graph;

means for associating a client profile with a subset of the nodes contained in a cluster from the clusters; and

means for customizing an online activity of a computing device associated with a device identifier, the online activity customized according to the client profile based on a determination that the device identifier corresponds to a node from the subset of nodes associated with the client profile.

15. The computing system of claim 14, wherein iteratively updating the directed graph comprises iterating between reconnections of nodes that form chains and reconnections of nodes that form a split.

16. A non-transitory computer-readable storage medium comprising instructions that, upon execution on a computing system, configure the computing system to perform operations comprising:

accessing a directed graph generated based on data associated with online activities of computing devices, the directed graph comprising nodes and oriented edges connecting the nodes, each node representing a device identifier associated with one of the computing devices;

generating clusters that contain subsets of the nodes by at least iteratively updating the directed graph based on a set of rules, the set of rules specifying (i) removal of leaf nodes from the directed graph, (ii) reconnection of nodes that form a chain in the directed graph, and (iii) reconnection of nodes that form a split in the directed graph;

associating a client profile with a subset of the nodes contained in a cluster from the clusters; and

customizing an online activity of a computing device associated with a device identifier, the online activity customized according to the client profile based on a determination that the device identifier corresponds to a node from the subset of nodes associated with the client profile.

17. The non-transitory computer-readable storage medium of claim 16, wherein iteratively updating the directed graph comprises iterating between reconnections of nodes that form chains and reconnections of nodes that form a split.

18. The non-transitory computer-readable storage medium of claim 16, wherein removal of a leaf node comprises storing in a complete set a key-value pair having a label of the leaf node as a key of the key-value pair and having a label of a node connected to the leaf node as a value of the key-value pair, and wherein reconnecting a node to another node of a chain or a split comprises storing in an incomplete set a second key-value pair having a label of the node as a key of the second key-value pair and having a label of the other node as a value of the second key-value pair.

19. The non-transitory computer-readable storage medium of claim 16, wherein the operations further comprise propagating, upon completion of the iterative updating of the directed graph, a final label as a cluster identifier based on matching a value from a key-value pair with a key of another key-value pair, wherein the key corresponds to the final label.