Granted Patent B2

US 9,529,887 · App. 14/102,283 · Granted Dec 27, 2016

Abstract

Claims (82)

1. A computer-executable method, comprising:

identifying for a first graph clustering, by a computer, a first set of vertices in a graph, wherein a respective vertex in the first set of vertices is an exemplar of a respective vertex cluster and a vertex identifier of the vertex identifies the corresponding vertex cluster;

identifying a second set of vertices in the graph, wherein a respective vertex in the second set of vertices is not an exemplar of a vertex cluster and the vertex is not associated with a vertex identifier;

assigning a vertex identifier of a first vertex in the first set of vertices to a second vertex in the second set of vertices based on an edge between the first vertex and the second vertex, wherein the first vertex and the second vertex represent element in a data set, and wherein the edge represent a type and strength of relationship between the first vertex and the second vertex;

wherein the vertex identifiers of the first vertex and the second vertex do not change before convergence;

disregarding input from a respective vertex without a vertex identifier for calculation of mode used for assigning a respective vertex identifier a respective vertex in the graph;

allocating the first vertex and the second vertex to a first vertex cluster associated with the vertex identifier, wherein the vertex cluster represents information of interest in the data set; and

detecting convergence of the first graph clustering based on allocation of vertex identifier to a respective vertex in the second set of vertices.

2. The method of claim 1 , wherein in response to an undesired cluster formation, the method further comprises using the first graph clustering as an input to a second graph clustering, wherein the second graph clustering comprises:

assigning a second vertex identifier to the second vertex based on the mode of the vertex identifiers that have been assigned to neighbor vertices of the second vertex;

allocating the second vertex to a second vertex cluster associated with the second vertex identifier, wherein the second vertex cluster represents information of interest in the data set; and

detecting convergence of the second graph clustering based on modularity associated with updated vertex clusters of the graph, wherein the updated vertex clusters of the graph include the second vertex cluster.

3. The method of claim 1 , further comprising allocating a subset of vertices in the graph to a thread running in the computer for forming vertex clusters, wherein forming the vertex clusters for the subset of vertices is computed within the thread.

4. The method of claim 1 , further comprising:

representing a plurality of vertex clusters as vertices in a community graph;

computing marginal modularity for respective candidate vertex cluster pair in a community graph; and

merging two or more vertex clusters based on the marginal modularity.

5. The method of claim 4 , wherein computing the marginal modularity is based on one or more of:

weight of edges between the candidate clusters;

weight of all edges in the community graph; and

weight of a respective candidate cluster.

6. The method of claim 5 , further comprising adjusting affect of the weight of all edges in the community graph on the marginal modularity, wherein the affect includes formation of large clusters or formation of small clusters.

7. The method of claim 4 , further comprising removing consolidating edges and merged clusters.

8. The method of claim 4 , further comprising renaming vertices and edge references to the vertices in the community graph.

9. The method of claim 1 , further comprising applying an oscillation damping effect.

10. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:

identifying for a first graph clustering a first set of vertices in a graph, wherein a respective vertex in the first set of vertices is an exemplar of a respective vertex cluster and a vertex identifier of the vertex identifies the corresponding vertex cluster;

identifying a second set of vertices in the graph, wherein a respective vertex in the second set of vertices is not an exemplar of a vertex cluster and the vertex is not associated with a vertex identifier;

assigning a vertex identifier of a first vertex in the first set of vertices to a second vertex in the second set of vertices based on an edge between the first vertex and the second vertex, wherein the first vertex and the second vertex represent element in a data set, and wherein the edge represent a type and strength of relationship between the first vertex and the second vertex;

wherein the vertex identifiers of the first vertex and the second vertex do not change before convergence;

disregarding input from a respective vertex without a vertex identifier for calculation of mode used for assigning a respective vertex identifier a respective vertex in a graph;

allocating the first vertex and the second vertex to a first vertex cluster associated with the vertex identifier, wherein the vertex cluster represents information of interest in the data set; and

detecting convergence of the first graph clustering based on allocation of vertex identifier to a respective vertex in the second set of vertices.

11. The non-transitory computer-readable storage medium of claim 10 , wherein in response to an undesired cluster formation, the method further comprises using the first graph clustering as an input to a second graph clustering, wherein the second graph clustering comprises:

assigning a second vertex identifier to the second vertex based on the mode of the vertex identifiers that have been assigned to neighbor vertices of the second vertex;

allocating the second vertex to a second vertex cluster associated with the second vertex identifier, wherein the second vertex cluster represents information of interest in the data set; and

detecting convergence of the second graph clustering based on modularity associated with updated vertex clusters of the graph, wherein the updated vertex clusters of the graph include the second vertex cluster.

12. The non-transitory computer-readable storage medium of claim 10 , wherein the method further comprises allocating a subset of vertices in the graph to a thread running in the computer for forming vertex clusters, wherein forming the vertex clusters for the subset of vertices is computed within the thread.

13. The non-transitory computer-readable storage medium of claim 10 , wherein the method further comprises:

representing a plurality of vertex clusters as vertices in a community graph;

computing marginal modularity for respective candidate vertex cluster pair in a community graph; and

merging two or more vertex clusters based on the marginal modularity.

14. The non-transitory computer-readable storage medium of claim 13 , wherein computing the marginal modularity is based on one or more of:

weight of edges between the candidate clusters;

weight of all edges in the community graph; and

weight of a respective candidate cluster.

15. The non-transitory computer-readable storage medium of claim 14 , wherein the method further comprises adjusting affect of the weight of all edges in the community graph on the marginal modularity, wherein the affect includes formation of large clusters or formation of small clusters.

16. The non-transitory computer-readable storage medium of claim 13 , wherein the method further comprises removing consolidating edges and merged clusters.

17. A computing system, comprising:

a processor;

a memory;

a clustering mechanism configured to:

identify for a first graph clustering a first set of vertices in a graph, wherein a respective vertex in the first set of vertices is an exemplar of a respective vertex cluster and a vertex identifier of the vertex identifies the corresponding vertex cluster;

identify a second set of vertices in the graph, wherein a respective vertex in the second set of vertices is not an exemplar of a vertex cluster and the vertex is not associated with a vertex identifier;

assign a vertex identifier of a first vertex in the first set of vertices to a second vertex in the second set of vertices based on an edge between the first vertex and the second vertex, wherein the first vertex and the second vertex represent element in a data set, and wherein the edge represent a type and strength of relationship between the first vertex and the second vertex; and

wherein the vertex identifiers of the first vertex and the second vertex do not change before convergence; and

a convergence mechanism configured to:

disregard input from a respective vertex without a vertex identifier for calculation of mode used for assigning a respective vertex identifier a respective vertex in a graph;

wherein the clustering mechanism is further configured to allocate the first vertex and the second vertex to a first vertex cluster associated with the vertex identifier, wherein the vertex cluster represents information of interest in the data set;

and

wherein the convergence mechanism is further configured to detect convergence of the first graph clustering based on allocation of vertex identifier to a respective vertex in the second set of vertices.

18. The computing system of claim 17 , wherein in response to an undesired cluster formation, the clustering mechanism is further configured to use the first graph clustering as an input to a second graph clustering;

wherein for the second graph clustering the clustering mechanism is further configured to:

assign a second vertex identifier to the second vertex based on the mode of the vertex identifiers that have been assigned to neighbor vertices of the second vertex; and

allocate the second vertex to a second vertex cluster associated with the second vertex identifier, wherein the second vertex cluster represents information of interest in the data set;

and

wherein for the second graph clustering the convergence mechanism is further configured to detect convergence of the second graph clustering based on modularity associated with updated vertex clusters of the graph, wherein the updated vertex clusters of the graph include the second vertex cluster.

19. The computing system of claim 17 , further comprising a thread management mechanism configured to allocate a subset of vertices in the graph to a thread running in the computer for forming vertex clusters, wherein forming the vertex clusters for the subset of vertices is computed within the thread.

20. The computing system of claim 17 , wherein the clustering mechanism is further configured to:

represent a plurality of vertex clusters as vertices in a community graph;

compute marginal modularity for respective candidate vertex cluster pair in a community graph; and

merge two or more vertex clusters based on the marginal modularity.

21. The computing system of claim 20 , the clustering mechanism is configured to compute the marginal modularity based on one or more of:

weight of edges between the candidate clusters;

weight of all edges in the community graph; and

weight of a respective candidate cluster.

22. The computing system of claim 21 , wherein the clustering mechanism is further configured to adjust affect of the weight of all edges in the community graph on the marginal modularity, wherein the affect includes formation of large clusters or formation of small clusters.

23. The method of claim 9 , wherein the oscillation damping effect include one or more of: randomization in label propagation, periodic bias, and oscillation detection.

24. The non-transitory computer-readable storage medium of claim 10 , wherein the method further comprises applying an oscillation damping effect, wherein the oscillation damping effect include one or more of:

randomization in label propagation, periodic bias, and oscillation detection.

25. The computing system of claim 17 , wherein the convergence mechanism is further configured to apply an oscillation damping effect, wherein the oscillation damping effect include one or more of:

randomization in label propagation, periodic bias, and oscillation detection.

Assignments (10)