Discovering representative composite CI patterns in an it system

1. A method for discovering representative composite configuration item (CI) patterns in an Information Technology (IT) system that includes a plurality of configuration items (CIs), the method comprising:

for a graph representing the IT system, pruning attributes of a plurality of CI nodes, wherein each CI node of the graph represents a respective one of the CIs of the IT system;

data mining the plurality of CI nodes of the graph representing the IT system to extract composite CI patterns;

determining a plurality of similarity measures for the composite CI patterns, each similarity measure measuring a similarity between a unique pair of composite CI patterns, wherein each similarity measure is calculated by multiplying a Jaccard coefficient times a diffusion kernel similarity value;

clustering a first plurality of the composite CI patterns into a cluster based on the plurality of similarity measures for the composite CI patterns, wherein each composite CI pattern included in the cluster is unique and comprises multiple CI nodes;

extracting a single representative composite CI pattern from the cluster to represent the first plurality of composite CI patterns in the cluster; and

using an output device, outputting the single representative composite CI pattern for each of the cluster.

2. The method of claim 1 , wherein pruning the attributes of the plurality of CI nodes is based on an entropy distribution of the attributes of the plurality of CI nodes.

3. The method of claim 2 , wherein pruning the attributes of the plurality of CI nodes in the graph comprises:

determining the entropy distribution of the attributes of the plurality of CI nodes;

pruning the attributes having an entropy above a highest threshold in the entropy distribution; and

pruning attributes having an entropy below a lowest threshold in the entropy distribution.

4. The method of claim 1 , wherein the data mining of the plurality of CI nodes of the graph comprises considering a candidate composite configuration pattern extracted from the graph, and iteratively adding randomly selected graph parts which are found adjacent to that candidate composite CI pattern in the graph, determining whether the candidate composite CI pattern with the added randomly selected graph parts still qualifies as a frequent composite CI pattern, and when the candidate composite CI pattern in the graph does not qualify as a frequent composite CI pattern, disregarding a latter added randomly selected graph part and determining the candidate composite CI pattern with the added randomly selected graph parts but without the latter added randomly selected graph part, to be a composite CI pattern of the graph.

5. The method of claim 1 , wherein the data mining of the plurality of CI nodes of the graph representing the IT system to extract composite CI patterns includes computing a flow-based support.

6. The method of claim 1 , comprising pruning isomorphic composite CI patterns from the composite CI patterns.

7. The method of claim 1 , comprising applying polynomial time filters on the composite CI patterns.

8. The method of claim 1 , wherein:

the Jaccard coefficient is based on labels sets of the unique pair of composite CI patterns, and

the diffusion kernel similarity value is based on structure and label sets of the unique pair of composite CI patterns.

9. The method of claim 1 , wherein the clustering of the first plurality of composite CI patterns into the cluster comprises considering structural edges and attribute edges in the graph.

10. The method of claim 1 , comprising:

generating, based on the graph, an augmented weighted graph that includes both structural nodes and attribute nodes; and

determining the diffusion kernel similarity value based on the augmented weighted graph.

11. A system for discovering representative composite configuration item (CI) patterns for an Information Technology (IT) system that includes a plurality of configuration items (CIs), the system comprising:

a processor to:

for a graph representing the IT system, prune attributes of a plurality of CI nodes, wherein each CI node of the graph represents a respective one of the CIs of the IT system;

data mine the plurality of CI nodes of the graph representing the IT system to extract composite CI patterns;

determine a plurality of similarity measures for the composite CI patterns, each similarity measure measuring a similarity between a unique pair of composite CI patterns, wherein each similarity measure is a product of multiplying a Jaccard coefficient times a diffusion kernel similarity value;

cluster a first plurality of the composite CI patterns into a cluster based on the plurality of similarity measures for the composite CI patterns, wherein each composite CI pattern included in the cluster comprises multiple CI nodes;

extract a single representative composite CI pattern from the cluster to represent the first plurality of composite CI patterns in the cluster;

a communication interface to interface between the processor and the IT system; and

an output device to output the single representative composite CI pattern for the cluster.

12. The system of claim 11 , wherein:

the Jaccard coefficient is based on labels sets of the unique pair of composite CI patterns, and

the diffusion kernel similarity value is based on structure and label sets of the unique pair of composite CI patterns.

13. The system of claim 11 , wherein the processor is to prune the attributes of the plurality of CI nodes based on an entropy distribution of the attributes of the plurality of CI nodes.

14. The system of claim 13 , wherein the processor is to:

determine the entropy distribution of the attributes of the plurality of CI nodes;

prune the attributes having an entropy above a highest threshold in the entropy distribution; and

prune the attributes having an entropy below a lowest threshold in the entropy distribution.

15. A non-transitory computer readable medium having stored thereon instructions for discovering representative composite configuration item (CI) patterns for an Information Technology (IT) system that includes a plurality of configuration items (CIs), which when executed by a processor cause the processor to:

for a graph representing the IT system, prune attributes of a plurality of CI nodes, wherein each CI node of the graph represents a respective one of the CIs of the IT system;

data mine the plurality of CI nodes of the graph representing the IT system to extract composite CI patterns;

determine a plurality of similarity measures for the composite CI patterns, each similarity measure measuring a similarity between a unique pair of composite CI patterns, wherein each similarity measure is calculated by multiplying a Jaccard coefficient times a diffusion kernel similarity value;

cluster a first plurality of the composite CI patterns into a cluster based on the plurality of similarity measures for the composite CI patterns, wherein each composite CI pattern included in the cluster comprises multiple CI nodes;

extract a single representative composite CI pattern from the cluster to represent the first plurality of composite CI patterns in the cluster;

using an output device, output the single representative composite CI pattern for the cluster.

16. The non-transitory computer readable medium of claim 15 , wherein:

the Jaccard coefficient is based on labels sets of the unique pair of composite CI patterns, and

the diffusion kernel similarity value is based on structure and label sets of the unique pair of composite CI patterns.

17. The non-transitory computer readable medium of claim 15 , wherein the instructions cause the processor to:

generate, based on the graph, an augmented weighted graph that includes both structural nodes and attribute nodes; and

determine the diffusion kernel similarity value based on the augmented weighted graph.