Real-time abnormal change detection in graphs

• US 10,019,190 B2
• Filed: 08/20/2015
• Issued: 07/10/2018
• Est. Priority Date: 10/15/2014
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Rao, Kunal, Coviello, Giuseppe, Chakradhar, Srimat, Bhattacherjee, Souvik, Cadambi, Srihari
• Primary Examiner(s): Hoang, Son T
• Application Number:
  US14/831,775
• Publication Number:
  US 20160110404A1
• Time in Patent Office: 1,055 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2372 Updates performed during offline database operations
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

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.

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.

2. The method of claim 1, wherein the determining whether the graph diameter change exists comprises comparing the diameter of the merged graph with one or more diameters of one or more past sampled graphs.

3. The method of claim 2, wherein the comparing step compares the diameter of the merged graph with the one or more diameters of the one or more past sampled graphs using a sliding window.

4. The method of claim 3, wherein a target time period of the sliding window is continuously shifting.

5. The method of claim 3, further comprising updating the merged graph using a batch input stream for at least a duration of the sliding window.

6. The method of claim 2, wherein the determining whether the graph diameter change exists comprises comparing the diameter of the merged graph with the one or more diameters of the one or more past sampled graphs with respect to a threshold amount of diameter change.

7. The method of claim 1, further comprising determining whether the merged graph has a sufficient number of reference points, and wherein the computing of the diameter of the merged graph is stalled until the merged graph has the sufficient number of reference points.

8. The method of claim 1, wherein the extracting the active sampled graph from the underlying base graph comprises selecting graph samples such that all sections of the underlying graph are processed and represented in the active sampled graph.

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.

10. The computer program product of claim 9, wherein the determining whether the graph diameter change exists comprises comparing the diameter of the merged graph with one or more diameters of one or more past sampled graphs.

11. The computer program product of claim 10, wherein the comparing step compares the diameter of the merged graph with the one or more diameters of the one or more past sampled graphs using a sliding window.

12. The computer program product of claim 11, wherein a target time period of the sliding window is continuously shifting.

13. The computer program product of claim 11, further comprising updating the merged graph using a batch input stream for at least a duration of the sliding window.

14. The computer program product of claim 10, wherein the determining whether the graph diameter change exists comprises comparing the diameter of the merged graph with the one or more diameters of the one or more past sampled graphs with respect to a threshold amount of diameter change.

15. The computer program product of claim 9, further comprising determining whether the merged graph has a sufficient number of reference points, and wherein the computing of the diameter of the merged graph is stalled until the merged graph has the sufficient number of reference points.

16. The computer program product of claim 9, wherein the extracting the active sampled graph from the underlying base graph comprises selecting graph samples such that all sections of the underlying graph are processed and represented in the active sampled graph.

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.

18. The system of claim 17, wherein the graph diameter change determination device compares the diameter of the merged graph with one or more diameters of one or more past sampled graphs.

19. The system of claim 18, wherein the diameter of the merged graph is compared with the one or more diameters of the one or more past sampled graphs using a sliding window.

20. The system of claim 19, wherein a target time period of the sliding window is continuously shifting.