Simplifying a graph of correlation rules while preserving semantic coverage

• US 8,825,581 B2
• Filed: 09/10/2012
• Issued: 09/02/2014
• Est. Priority Date: 09/10/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Duftler, Matthew J., Rozsnyai, Szabolcs
• Primary Examiner(s): Starks, Wilbert L
• Application Number:
  US13/608,813
• Publication Number:
  US 20140074764A1
• Time in Patent Office: 722 Days
• Field of Search: None
• US Class Current: 706/47
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management

Abstract

A method, system and computer program product for simplifying a plurality of correlation rules of a graph. The method includes the steps of: receiving correlation rules; creating an undirected graph; removing redundant edges from the undirected graph; splitting nodes in the undirected graph; replacing a probability that an edge that connects two nodes to a seed value; modifying the seed value by adding a first value to said seed value and adding a second value to the first value; determining a maximum modified seed value; adding the maximum modified seed value to a probability that the uncertain edge connects two nodes; removing any temporary certain edge; and running a minimum spanning tree algorithm on said modified undirected graph.

Claims

1. A computer implemented method of simplifying a plurality of correlation rules of a graph, comprising:

receiving said plurality of correlation rules;

creating an undirected graph using said plurality of correlation rules;

removing at least one edge from said undirected graph if (i) said at least one edge is an uncertain edge connecting a first node and second node and (ii) said first node and said second node are connected by a first certain edge;

adding a fifth node to said undirected graph if (i) a third node is connected to a fourth node by a second certain edge and (ii) said third node is connected to at least one other node by a plurality of uncertain edges;

replacing one of said plurality of uncertain edges which connects said third node to one of said at least one other node with a temporary uncertain edge which connects said fifth node to said one of said at least one other node;

creating a temporary certain edge which connects said fifth node to said fourth node;

for each certain edge or temporary certain edge, changing said certain edge or temporary certain edge to a modified certain edge by (i) replacing a probability that said certain edge or said temporary certain edge connects two nodes to a seed value, (ii) modifying said seed value by adding a first value to said seed value and (iii) adding a second value to said first value;

determining a maximum modified seed value wherein said maximum modified seed value was assigned to said modified certain edge;

changing each uncertain edge and temporary uncertain edge to a modified uncertain edge by adding said maximum modified seed value to a probability that said uncertain edge or said temporary uncertain edge connects two nodes;

removing said modified temporary certain edge; and

running a minimum spanning tree algorithm on said modified undirected graph;

wherein at least one of the steps is carried out using a computer device.

2. The method according to claim 1 wherein said undirected graph is created by stripping direction and event type attributes from said received correlation rules.

3. The method according to claim 1 further comprising the step of translating said modified undirected graph into at least one new correlation rule.

4. The method according to claim 1 wherein said minimum spanning tree algorithm is a Kruskals Minimum Spanning Tree algorithm.

5. The method according to claim 1 wherein said second value is determined by an exponential weighting algorithm.

6. The method according to claim 1 further comprising the step of:

removing an unused edge from said modified undirected graph, if said unused edge is not used by said minimum spanning tree algorithm.

7. A computer implemented system for simplifying a plurality of correlation rules of a graph, comprising:

a receiving module configured to receive said plurality of correlation rules;

a first creating module configured to create an undirected graph using said plurality of correlation rules;

a first removing module configured to remove at least one edge from said undirected graph if (i) said at least one edge is an uncertain edge connecting a first node and second node and (ii) said first node and said second node are connected by a first certain edge;

an adding module configured to add a fifth node to said undirected graph if (i) a third node is connected to a fourth node by a second certain edge and (ii) said third node is connected to at least one other node by a plurality of uncertain edges;

a replacing module configured to replace one of said plurality of uncertain edges which connects said third node to one of said at least one other node with a temporary uncertain edge which connects said fifth node to said one of said at least one other node;

a second creating module configured to create a temporary certain edge which connects said fifth node to said fourth node;

a first changing module configured to change, for each certain edge or temporary certain edge, said certain edge or temporary certain edge to a modified certain edge by (i) replacing a probability that said certain edge or said temporary certain edge connects two nodes to a seed value, (ii) modifying said seed value by adding a first value to said seed value and (iii) adding a second value to said first value;

a determining module configured to determine a maximum modified seed value wherein said maximum modified seed value was assigned to said modified certain edge;

a second changing module configured to change each uncertain edge and temporary uncertain edge to a modified uncertain edge by adding said maximum modified seed value to a probability that said uncertain edge or said temporary uncertain edge connects two nodes;

a second removing module configured to remove said modified temporary certain edge; and

a running module configured to run a minimum spanning tree algorithm on said modified undirected graph.

8. The system according to claim 7 further comprising a stripping module configured to strip direction and event type attributes from said received correlation rules.

9. The system according to claim 7 further comprising a translating module configured to translate said modified undirected graph into at least one new correlation rule.

10. The system according to claim 7 wherein said running module uses a Kruskals Minimum Spanning Tree algorithm.

11. The system according to claim 7 wherein said first changing module uses an exponential weighting algorithm to determine said second value.

12. The system according to claim 7, further comprising:

a third removing module configured to remove an unused edge from said modified undirected graph, if said unused edge is not used by said minimum spanning tree algorithm.

13. A non-transitory computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions which when implemented, cause a computer to carry out the steps of a method comprising:

receiving said plurality of correlation rules;

creating an undirected graph using said plurality of correlation rules;

removing at least one edge from said undirected graph if (i) said at least one edge is an uncertain edge connecting a first node and second node and (ii) said first node and said second node are connected by a first certain edge;

adding a fifth node to said undirected graph if (i) a third node is connected to a fourth node by a second certain edge and (ii) said third node is connected to at least one other node by a plurality of uncertain edges;

replacing one of said plurality of uncertain edges which connects said third node to one of said at least one other node with a temporary uncertain edge which connects said fifth node to said one of said at least one other node;

creating a temporary certain edge which connects said fifth node to said fourth node;

for each certain edge or temporary certain edge, changing said certain edge or temporary certain edge to a modified certain edge by (i) replacing a probability that said certain edge or said temporary certain edge connects two nodes to a seed value, (ii) modifying said seed value by adding a first value to said seed value and (iii) adding a second value to said first value;

determining a maximum modified seed value wherein said maximum modified seed value was assigned to said modified certain edge;

changing each uncertain edge and temporary uncertain edge to a modified uncertain edge by adding said maximum modified seed value to a probability that said uncertain edge or said temporary uncertain edge connects two nodes;

removing said modified temporary certain edge; and

running a minimum spanning tree algorithm on said modified undirected graph.

14. The computer readable storage medium according to claim 13 wherein said undirected graph is created by stripping direction and event type attributes from said received correlation rules.

15. The computer readable storage medium according to claim 13 further comprising the step of translating said modified undirected graph into at least one new correlation rule.

16. The computer readable storage medium according to claim 13 wherein said minimum spanning tree algorithm is a Kruskals Minimum Spanning Tree algorithm.

17. The computer readable storage medium according to claim 13 wherein said second value is determined by exponential weighting algorithm.

18. The computer readable storage medium according to claim 13 further comprising:

removing an unused edge from said modified undirected graph, if said unused edge is not used by said minimum spanning tree algorithm.