Directed incremental clustering of causally related events
Described systems and techniques determine causal associations between events that occur within an information technology landscape. Individual situations that are likely to represent active occurrences requiring a response may be identified as causal event clusters, without requiring manual tuning to determine cluster boundaries. Consequently, it is possible to identify root causes, analyze effects, predict future events, and prevent undesired outcomes, even in complicated, dispersed, interconnected systems.
1. A computer program product, the computer program product being tangibly embodied on a non-transitory computer-readable storage medium and comprising instructions that, when executed by at least one computing device, are configured to cause the at least one computing device to:
determine a plurality of events within a network;
determine, from the plurality of events, a plurality of causal event pairs, each causal event pair connected by a directional edge having a causal score indicating a strength of causation;
generate a cluster tree of candidate event clusters, each candidate event cluster having at least one included causal event pair of the plurality of causal event pairs and having a cluster score defined by the at least one included causal event pair; and
select an event cluster from the candidate event clusters, based on the cluster scores, to thereby identify a situation within the network.
2. The computer program product of claim 1 , wherein the instructions are further configured to cause the at least one computing device to:
determine the plurality of events including dynamically updating the plurality of events as new events are determined based on metrics monitored within the network.
3. The computer program product of claim 1 , wherein the instructions are further configured to cause the at least one computing device to:
determine pairwise combinations of the plurality of events to obtain event pairs;
determine, for each event pair of the event pairs, the directional edge and causal score, to thereby obtain the causal event pairs.
4. The computer program product of claim 1 , wherein the instructions are further configured to cause the at least one computing device to:
determine, from the plurality of events, a multi-layer small world graph; and
determine, from the multi-layer small world graph, the causal event pairs.
5. The computer program product of claim 1 , wherein the instructions are further configured to cause the at least one computing device to:
determine the directional edge and the causality score of each causal event pair using a probabilistic function based on at least one of a topological graph and a knowledge graph characterizing the network.
6. The computer program product of claim 1 , wherein the instructions are further configured to cause the at least one computing device to:
generate, from the causal event pairs, an arborescence graph.
7. The computer program product of claim 6 , wherein the instructions are further configured to cause the at least one computing device to:
generate the arborescence graph as a minimum arborescence graph based on topological distances between events of each causal event pair, each topological distance being determined from the causal score of each corresponding causal event pair.
8. The computer program product of claim 6 , wherein the instructions are further configured to cause the at least one computing device to:
generate the cluster tree from the arborescence graph.
9. The computer program product of claim 6 , wherein the instructions are further configured to cause the at least one computing device to:
determine a set of causal scores present between causal event pairs of the arborescence graph;
generate the cluster tree including a plurality of cluster levels, each cluster level corresponding to a causal score of the set of causal scores and defining the cluster score of a corresponding candidate event cluster; and
define each candidate event cluster of the candidate event clusters at a corresponding cluster level of the plurality of cluster levels.
10. The computer program product of claim 1 , wherein the instructions are further configured to cause the at least one computing device to:
select a candidate event cluster from among the candidate event clusters;
calculate a rate of change for the candidate event cluster based on a comparison of a parent distance, defined between a cluster score of the candidate event cluster and a parent cluster score of a parent candidate event cluster of the candidate event cluster, with a child distance, defined between the cluster score of the candidate event cluster and a child cluster score of a child candidate event cluster of the candidate event cluster; and
select the candidate event cluster as the event cluster, based on the rate of change.
11. A computer-implemented method, the method comprising:
determining a plurality of events within a network;
determining, from the plurality of events, a plurality of causal event pairs, each causal event pair connected by a directional edge having a causal score indicating a strength of causation;
generating a cluster tree of candidate event clusters, each candidate event cluster having at least one included causal event pair of the plurality of causal event pairs and having a cluster score defined by the at least one included causal event pair; and
selecting an event cluster from the candidate event clusters, based on the cluster scores, to thereby identify a situation within the network.
12. The method of claim 11 , further comprising:
determining pairwise combinations of the plurality of events to obtain event pairs;
determining, for each event pair of the event pairs, the directional edge and causal score, to thereby obtain the causal event pairs.
13. The method of claim 11 , further comprising:
determining, from the plurality of events, a multi-layer small world graph; and
determining, from the multi-layer small world graph, the causal event pairs.
14. The method of claim 11 , further comprising:
generating, from the causal event pairs, an arborescence graph; and
generating the cluster tree from the arborescence graph.
15. The method of claim 14 , further comprising:
generating the arborescence graph as a minimum arborescence graph based on topological distances between events of each causal event pair, each topological distance being determined from the causal score of each corresponding causal event pair.
16. The method of claim 14 , further comprising:
determining a set of causal scores present between causal event pairs of the arborescence graph;
generating the cluster tree including a plurality of cluster levels, each cluster level corresponding to a causal score of the set of causal scores and defining the cluster score of a corresponding candidate event cluster; and
defining each candidate event cluster of the candidate event clusters at a corresponding cluster level of the plurality of cluster levels.
17. The method of claim 11 , further comprising:
selecting a candidate event cluster of the candidate event clusters;
calculating a rate of change for the candidate event cluster based on a comparison of a parent distance, defined between a cluster score of the candidate event cluster and a parent cluster score of a parent candidate event cluster of the candidate event cluster, with a child distance, defined between the cluster score of the candidate event cluster and a child cluster score of a child candidate event cluster of the candidate event cluster; and
selecting the candidate event cluster as the event cluster, based on the rate of change.
18. A system comprising:
at least one memory including instructions; and
at least one processor that is operably coupled to the at least one memory and that is arranged and configured to execute instructions that, when executed, cause the at least one processor to:
determine a plurality of events within a network;
determine, from the plurality of events, a plurality of causal event pairs, each causal event pair connected by a directional edge having a causal score indicating a strength of causation;
generate a cluster tree of candidate event clusters, each candidate event cluster having at least one included causal event pair of the plurality of causal event pairs and having a cluster score defined by the at least one included causal event pair; and
select an event cluster from the candidate event clusters, based on the cluster scores, to thereby identify a situation within the network.
19. The system of claim 18 , wherein the instructions are further configured to cause the at least one processor to:
generate, from the causal event pairs, an arborescence graph;
generate the cluster tree from the arborescence graph;
determine a set of causal scores present between causal event pairs of the arborescence graph;
generate the cluster tree including a plurality of cluster levels, each cluster level corresponding to a causal score of the set of causal scores and defining the cluster score of a corresponding candidate event cluster; and
define each candidate event cluster of the candidate event clusters at a corresponding cluster level of the plurality of cluster levels.
20. The system of claim 18 , wherein the instructions are further configured to cause the at least one processor to:
select a candidate event cluster from the candidate event clusters;
calculate a rate of change for the candidate event cluster based on a comparison of a parent distance, defined between a cluster score of the candidate event cluster and a parent cluster score of a parent candidate event cluster of the candidate event cluster, with a child distance, defined between the cluster score of the candidate event cluster and a child cluster score of a child candidate event cluster of the candidate event cluster; and
select the candidate event cluster as the event cluster, based on the rate of change.