Simplifying a graph of correlation rules while preserving semantic coverage
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
18 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification