Real-time abnormal change detection in graphs
First Claim
1. A method for detecting abnormal changes in real-time in dynamic graphs, the method comprising:
- reducing computation time for detection of the abnormal changes in real-time by extracting, by a graph sampler, an active sampled graph from an underlying base graph, the extracting comprising;
partitioning each of one or more connected components, and assigning a node sample limit for each of one or more partitions;
selecting ambassador nodes, the ambassador nodes being a mix of recently added nodes within the one or more partitions and nodes lying across cut edges, wherein a cut edge connects two partitions within a connected component, each ambassador node functions as a starting point for a Forest Fire model which is a cellular automaton on a grid of a plurality of cells, each cell comprises one of three states;
empty, occupied by a tree, or burning, and the Forest Fire model being run within the one or more partitions;
adding one or more nodes to the active sampled graph until the node sample limit of the partition associated with the active sample graph is reached; and
partitioning the active sampled graph across multiple nodes and storing the active sampled graph in a memory for low-latency retrieval;
merging, by a graph merger, the active sampled graph with graph updates within a predetermined recent time period to generate a merged graph;
computing, by a graph diameter computer, a diameter of the merged graph;
determining, by a graph diameter change determination device, whether a graph diameter change exists; and
generating, by an alarm generator, a user-perceptible alarm responsive to the graph diameter change.
2 Assignments
0 Petitions
Accused Products
Abstract
A method for detecting abnormal changes in real-time in dynamic graphs. The method includes extracting, by a graph sampler, an active sampled graph from an underlying base graph. The method further includes merging, by a graph merger, the active sampled graph with graph updates within a predetermined recent time period to generate a merged graph. The method also includes computing, by a graph diameter computer, a diameter of the merged graph. The method additionally includes determining, by a graph diameter change determination device, whether a graph diameter change exists. The method further includes generating, by an alarm generator, a user-perceptible alarm responsive to the graph diameter change.
-
Citations
20 Claims
-
1. A method for detecting abnormal changes in real-time in dynamic graphs, the method comprising:
-
reducing computation time for detection of the abnormal changes in real-time by extracting, by a graph sampler, an active sampled graph from an underlying base graph, the extracting comprising; partitioning each of one or more connected components, and assigning a node sample limit for each of one or more partitions; selecting ambassador nodes, the ambassador nodes being a mix of recently added nodes within the one or more partitions and nodes lying across cut edges, wherein a cut edge connects two partitions within a connected component, each ambassador node functions as a starting point for a Forest Fire model which is a cellular automaton on a grid of a plurality of cells, each cell comprises one of three states;
empty, occupied by a tree, or burning, and the Forest Fire model being run within the one or more partitions;adding one or more nodes to the active sampled graph until the node sample limit of the partition associated with the active sample graph is reached; and partitioning the active sampled graph across multiple nodes and storing the active sampled graph in a memory for low-latency retrieval; merging, by a graph merger, the active sampled graph with graph updates within a predetermined recent time period to generate a merged graph; computing, by a graph diameter computer, a diameter of the merged graph; determining, by a graph diameter change determination device, whether a graph diameter change exists; and generating, by an alarm generator, a user-perceptible alarm responsive to the graph diameter change. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A computer program product for detecting abnormal changes in real-time in dynamic graphs, the computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to perform a method comprising:
-
reducing computation time for detection of the abnormal changes in real-time by extracting, by a graph sampler, an active sampled graph from an underlying base graph, the extracting comprising; partitioning each of one or more connected components, and assigning a node sample limit for each of one or more partitions; selecting ambassador nodes, the ambassador nodes being a mix of recently added nodes within the one or more partitions and nodes lying across cut edges, wherein a cut edge connects two partitions within a connected component, each ambassador node functions as a starting point for a Forest Fire model which is a cellular automaton on a grid of a plurality of cells, each cell comprises one of three states;
empty, occupied by a tree, or burning, and the Forest Fire model being run within the one or more partitions;adding one or more nodes to the active sampled graph until the node sample limit of the partition associated with the active sample graph is reached; and partitioning the active sampled graph across multiple nodes and storing the active sampled graph in a memory for low-latency retrieval; merging, by a graph merger, the active sampled graph with graph updates within a predetermined recent time period to generate a merged graph; computing, by a graph diameter computer, a diameter of the merged graph; determining, by a graph diameter change determination device, whether a graph diameter change exists; and generating, by an alarm generator, a user-perceptible alarm responsive to the graph diameter change. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. A system for detecting abnormal changes in real-time in dynamic graphs, the system comprising:
-
a graph sampler for reducing computation time for detection of the abnormal changes in real-time by extracting an active sampled graph from an underlying base graph, the extracting comprising; partitioning, using a hardware processor, each of one or more connected components, and assigning a node sample limit for each of one or more partitions; selecting ambassador nodes, the ambassador nodes being a mix of recently added nodes within the one or more partitions and nodes lying across cut edges, wherein a cut edge connects two partitions within a connected component, each ambassador node functions as a starting point for a Forest Fire model which is a cellular automaton on a grid of a plurality of cells, each cell comprises one of three states;
empty, occupied by a tree, or burning, and the Forest Fire model being run within the one or more partitions;adding one or more nodes to the active sampled graph until the node sample limit of the partition associated with the active sample graph is reached; and partitioning the active sampled graph across multiple nodes and storing the active sampled graph in a memory for low-latency retrieval; a graph merger for merging the active sampled graph with graph updates within a predetermined recent time period to generate a merged graph; a graph diameter computer for computing a diameter of the merged graph; a graph diameter change determination device for determining whether a graph diameter change exists; and an alarm generator for generating a user-perceptible alarm responsive to the graph diameter change. - View Dependent Claims (18, 19, 20)
-
Specification