Affinity determination using graphs
View Patent ↗In some examples, a computer receives event data relating to events of a system, and builds a graph comprising nodes representing respective values of attributes of the events, and edges between the nodes, each respective edge of the edges representing co-occurrence of values of attributes represented by nodes connected by the respective edge. The computer computes edge weights of corresponding edges of the edges, and identifies paths in the graph, where each path of the paths comprises two or more nodes and a corresponding edge or edges. The computer determines an affinity among the values of the attributes based on a shortest path determining process that uses the edge weights for distances of the identified paths, and resolves an anomaly in the system based on the determined affinity.
1. A non-transitory machine-readable storage medium comprising instructions that upon execution cause a computer to:
receive event data relating to events of a system;
build a multi-planar graph comprising nodes representing respective values of attributes of the events, and edges between the nodes, each respective edge of the edges representing co-occurrence of values of attributes represented by nodes connected by the respective edge, and each plane of a plurality of planes of the multi-planar graph comprising values of a respective attribute of the attributes;
compute edge weights of corresponding edges of the edges;
identify paths in the graph, wherein each path of the paths comprises two or more nodes and a corresponding edge or edges;
determine an affinity among the values of the attributes based on a shortest path determining process that uses the edge weights for distances of the identified paths; and
resolve an anomaly in the system based on the determined affinity.
2. The non-transitory machine-readable storage medium of claim 1 , wherein the edge weights of corresponding edges of the edges are based on counts associated with the nodes and counts associated with the edges.
3. The non-transitory machine-readable storage medium of claim 2 , wherein the edge weights are further based on coefficients that indicate importance of respective attributes.
4. The non-transitory machine-readable storage medium of claim 2 , wherein the counts associated with the nodes are based on occurrences of respective values of attributes in the events.
5. The non-transitory machine-readable storage medium of claim 2 , wherein the counts associated with the edges are based on occurrences of respective pairs of values of attributes in the events.
6. The non-transitory machine-readable storage medium of claim 1 , wherein each respective path of the paths is non-reentrant on any plane of the plurality of planes.
7. The non-transitory machine-readable storage medium of claim 6 , wherein a path being non-reentrant on any plane of the plurality of planes restricts an attribute from appearing more than once in the respective path.
8. The non-transitory machine-readable storage medium of claim 1 , wherein the instructions upon execution cause the computer to:
for a respective path of the identified paths, compute a path weight that is based on an aggregate of the edge weights of edges that are part of the respective path, wherein the path weight is used to derive a distance of the shortest path determining process.
9. The non-transitory machine-readable storage medium of claim 8 , wherein the aggregate of the edge weights of edges that are part of the respective path comprises a sum of the edge weights of edges that are part of the respective path.
10. The non-transitory machine-readable storage medium of claim 8 , wherein the path weight represents an affinity between values of attributes connected by the respective path.
11. A computer comprising:
a processor; and
a non-transitory storage medium storing instructions executable on the processor to:
receive event data relating to events of a system;
build a multi-planar graph comprising nodes representing respective values of attributes of the events, and edges between the nodes, each respective edge of the edges representing co-occurrence of values of attributes represented by nodes connected by the respective edge, and each plane of a plurality of planes of the multi-planar graph comprising values of a respective attribute of the attributes;
compute edge weights of corresponding edges of the edges based on counts associated with the nodes and counts associated with the edges;
identify paths in the multi-planar graph, wherein each path of the paths comprises two or more nodes and a corresponding edge or edges;
apply a shortest path determining process that uses the edge weights for distances of the identified paths; and
resolve an anomaly in the system based on affinity among the values of the attributes determined using the shortest path determining process.
12. The computer of claim 11 , wherein each respective path of the paths is non-reentrant on any plane of the plurality of planes.
13. The computer of claim 12 , wherein a path being non-reentrant on any plane of the plurality of planes restricts an attribute from appearing more than once in the respective path.
14. The computer of claim 11 , wherein the instructions are executable on the processor to:
for a respective path of the identified paths, compute a path weight that is based on an aggregate of the edge weights of edges that are part of the respective path, wherein the path weight is used to derive a distance of the shortest path determining process.
15. The computer of claim 14 , wherein the path weight represents an affinity between values of attributes connected by the respective path.
16. The computer of claim 11 , wherein the counts associated with the nodes are based on occurrences of respective values of attributes in the events, and the counts associated with the edges are based on occurrences of respective pairs of values of attributes in the events.
17. The computer of claim 11 , wherein the shortest path determining process uses a shortest path algorithm.
18. A method performed by a computer, comprising:
receiving event data relating to events of a system;
building a multi-planar graph comprising nodes representing respective values of attributes of the events, and edges between the nodes, each respective edge of the edges representing co-occurrence of values of attributes represented by nodes connected by the respective edge, and each plane of a plurality of planes of the multi-planar graph comprising values of a respective attribute of the attributes;
computing edge weights of corresponding edges of the edges based on counts associated with the nodes and counts associated with the edges, the counts associated with the nodes based on occurrences of respective values of attributes in the events, and the counts associated with the edges are based on occurrences of respective pairs of values of attributes in the events;
identifying paths in the graph, wherein each path of the paths comprises two or more nodes and a corresponding edge or edges;
determining an affinity between the values of the attributes based on a shortest path determining process that uses the edge weights for distances of the identified paths; and
resolving an anomaly in the system based on the determined affinity.
19. The method of claim 18 , wherein each respective path of the paths is non-reentrant on any plane of the plurality of planes.
20. The method of claim 18 , further comprising:
for a respective path of the identified paths, compute a path weight that is based on an aggregate of the edge weights of edges that are part of the respective path, wherein the path weight is used to derive a distance of the shortest path determining process.