CLUSTERING SIGNIFIERS IN A SEMANTICS GRAPH

• US 20140214834A1
• Filed: 01/31/2013
• Published: 07/31/2014
• Est. Priority Date: 01/31/2013
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Ozonat, Mehmet Kivanc, Bartolini, Claudio
• Granted Patent: US 9,355,166 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Clustering signifiers in a semantics graph can comprise coarsening a semantics graph associated with an enterprise communication network containing a plurality of nodes into a number of sub-graphs containing supernodes; partitioning each of the number of sub-graphs into a number of clusters; and iteratively refining the number of clusters to reduce an edge-cut of the semantics graph, based on the number of clusters.

Claims

1. A method for clustering signifiers in a semantics graph, comprising:

coarsening a semantics graph associated with an enterprise communication network containing a plurality of nodes into a number of sub-graphs containing supernodes;

partitioning each of the number of sub-graphs into a number of clusters; and

iteratively refining the number of clusters to reduce an edge-cut of the semantics graph, based on the number of clusters.

2. The method of claim 1, wherein a supernode comprises a number of nodes and incident edges associated with the number of nodes.

3. The method of claim 1, wherein the semantics graph comprises a weighted semantics graph.

4. The method of claim 3, wherein the weighted semantics graph comprises a positive numerical value representing a distance metric between a pair of related signifiers.

5. The method of claim 1, comprising calculating a vertex weight for the semantics graph.

6. The method of claim 5, wherein the partitioning of the number of sub-graphs is based on the vertex weight for the semantics graph.

7. A non-transitory computer-readable medium storing a set of instructions executable by a processing resource, wherein the set of instructions can be executed by the processing resource to:

transform a weighted semantics graph into a number of sub-graphs by iteratively matching a number of nodes within the weighted semantics graph;

divide each of the number of sub-graphs into at least two distinct clusters to create a partitioned graph including a number of clusters; and

reduce an edge-cut of the partitioned graph by using local refinement heuristics and based on the number of clusters.

8. The medium of claim 7, wherein the local refinement heuristics comprises the Kernighan-Lin algorithm.

9. The medium of claim 7, wherein the set of instructions can be executed by the processing resource to iteratively match the number of nodes within the weighted semantics graph until no two edges in each of the number of sub-graphs are incident to the same node.

10. The medium of claim 9, wherein the set of instructions can be executed by the processing resource to calculate a vertex weight for each of the sub-graphs by finding a sum of the weight of each vertex in the sub-graph.

11. The medium of claim 10, wherein each of the at least two distinct clusters comprises an equal sub-portion of the vertex weight of the sub-graph.

12. A system for clustering signifiers in a semantics graph, comprising:

a processing resource; and

a memory resource coupled to the processing resource containing instructions executable by the processing resource to;

create a coarsened graph by iteratively matching a number of nodes within a subset of nodes in a semantics graph, and collapsing each set of matched nodes to create a supernode;

create a partitioned graph from the coarsened graph by partitioning a number of sub-graphs in the coarsened graph based on a vertex weight, wherein the partitioned graph comprises a reduced edge-cut as compared to the semantics graph; and

reduce the edge-cut of the partitioned graph using local refinement heuristics.

13. The system of claim 12, wherein the instructions executable to reduce the edge-cut of the partitioned graph using local refinement heuristics comprise instructions to determine the edge-cut of the partitioned graph after switching a first node in a first cluster in the partitioned graph with a second node in a second cluster in the partitioned graph.

14. The system of claim 13, wherein the instructions executable to reduce the edge-cut of the partitioned graph using local refinement heuristics comprise instructions to maintain the switched first node and second node if the switch reduces the edge-cut of the partitioned graph.

15. The system of claim 13, wherein the instructions executable to reduce the edge-cut of the partitioned graph using local refinement heuristics comprise instructions to reverse the switched first node and second node if the switch does not reduce the edge-cut of the partitioned graph.