Clustering signifiers in a semantics graph

• US 9,355,166 B2
• Filed: 01/31/2013
• Issued: 05/31/2016
• Est. Priority Date: 01/31/2013
• Status: Expired due to Fees

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Ozonat, Mehmet Kivanc, Bartolini, Claudio
• Primary Examiner(s): Bullock, Joshua
• Application Number:
  US13/756,221
• Publication Number:
  US 20140214834A1
• Time in Patent Office: 1,216 Days
• Field of Search: 707/737
• US Class Current: 1/1
• 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 comprising:

generating a semantics graph that represents content extracted from an enterprise network in the form of signifiers, wherein nodes of the semantics graph represent the signifiers;

coarsening the semantics graph of the signifiers into a number of sub-graphs, the number of sub-graphs including a particular sub-graph that comprises a first node and a second node of the semantics graph;

after coarsening the semantics graph into the number of sub-graphs, splitting the particular sub-graph into multiple clusters comprising a first cluster that includes the first node and a second cluster that includes the second node; and

after splitting the particular sub-graph into the multiple clusters, reducing an edge-cut of the multiple clusters by switching the first node from the first cluster to the second cluster and switching the second node from the second cluster to the first cluster.

2. The method of claim 1, wherein coarsening the semantics graph comprises condensing multiple individual nodes of the semantics graph into a supernode, the supernode including the multiple individual nodes and incident edges of the multiple individual nodes.

3. The method of claim 2, wherein prior to splitting the particular sub-graph, the particular sub-graph includes the supernode.

4. The method of claim 3, wherein splitting the particular sub-graph into the multiple clusters comprises:

splitting the supernode so that some of the multiple individual nodes of the supernode are included in the first cluster and others of the multiple individual nodes of the supernode are included in the second cluster.

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

and

wherein splitting the particular sub-graph comprises splitting the particular sub-graph into the multiple clusters based on weights of the nodes included in the particular sub-graph.

6. The method of claim 5, wherein splitting the particular sub-graph into multiple clusters based on the weights of the nodes comprises splitting the particular sub-graph so that the first cluster and the second cluster have equal node weights.

7. The method of claim 1, wherein reducing comprises iteratively reducing the edge-cut using local refinement heuristics.

8. A non-transitory computer-readable medium storing instructions executable by a processing resource to:

generate a weighted semantics graph that represents content extracted from an enterprise network in the form of signifiers, wherein nodes of the weighted semantics graph represent the signifiers;

coarsen the weighted semantics graph into a number of sub-graphs, including a particular sub-graph comprising a supernode comprising multiple individual nodes of the semantics graph;

after coarsening of the semantics graph, split the particular sub-graph into a first cluster and a second cluster of equal weight; and

after splitting the particular sub-graph into the first and second clusters, reduce an edge-cut of the first and second clusters by switching an individual node in the first cluster with another individual node in the second cluster.

9. The non-transitory computer-readable medium of claim 8, wherein the instructions are executable by the processing resource to split the particular sub-graph into the first and second clusters by assigning the supernode to the first cluster.

10. The non-transitory computer-readable medium of claim 8, wherein the instructions are executable by the processing resource to split the particular sub-graph into the first and second clusters by assigning some of the multiple individual nodes of the supernode to the first cluster and assigning others of the multiple individual nodes of the supernode to the second cluster.

11. The non-transitory computer-readable medium of claim 8, wherein the instructions are executable by the processing resource to coarsen the weighted semantics graph into the number of sub-graphs in multiple iterations.

12. The non-transitory computer-readable medium of claim 11, wherein the instructions are executable by the processing resource to coarsen the weighted semantics graphs by:

in a first iteration of the multiple iterations;

condense a first individual node and a second individual nodes of the semantics graph into a first supernode; and

in a second iteration of the multiple iterations;

condense the first supernode and a third individual node of the semantics graph to form the supernode comprising the multiple individual nodes of the weighted semantics graph.

13. The non-transitory computer-readable medium of claim 11, wherein a number individual nodes in the semantics graph is reduced with each of the multiple iterations as individual nodes are condensed into supernodes.

14. A system comprising:

a processing resource; and

a memory resource coupled to the processing resource, the memory resource comprising instructions executable by the processing resource to;

generate a semantics graph that represents content extracted from an enterprise network in the form of signifiers, wherein nodes of the semantics graph represent the signifiers;

create a coarsened graph from a semantics graph, the coarsened graph comprising multiple sub-graphs, the multiple sub-graphs comprising a particular sub-graph including a first node and a second node of the semantics graph;

create a partitioned graph from the coarsened graph by splitting each of the multiple sub-graphs into multiple clusters, including splitting the particular sub-graph itself into multiple clusters comprising a first cluster including the first node and a second cluster including the second node; and

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

15. The system of claim 14, wherein the instructions are executable by the processing resource to reduce the edge-cut of the partitioned graph using local refinement heuristics by determining the edge-cut of the partitioned graph after switching the first node in the first cluster with the second node in the second cluster.

16. The system of claim 15, wherein the instructions executable by the processing resource to reduce the edge-cut of the partitioned graph using local refinement heuristics further by maintaining the switched first node and second node when the switch reduces the edge-cut of the partitioned graph.

17. The system of claim 15, wherein the instructions executable by the processing resource to reduce the edge-cut of the partitioned graph using local refinement heuristics further by reversing the switched of the first node and the second node when the switch does not reduce the edge-cut of the partitioned graph.

18. The system of claim 14, wherein the semantics graph comprises a weighted semantics graph;

and

wherein the instructions are executable by the processing resource to create the partitioned graph from the coarsened graph by splitting the particular sub-graph itself into multiple clusters of equal weight.

19. The system of claim 14, wherein the instructions are executable by the processing resource to create the coarsened graph to include a supernode comprising multiple individual nodes of the semantics graph.

20. The system of claim 19, wherein the instructions are executable by the processing resource further to generate the supernode by condensing the multiple individual nodes into the supernode over multiple coarsening iterations.