Real-time Abnormal Change Detection in Graphs

• US 20160110404A1
• Filed: 08/20/2015
• Published: 04/21/2016
• Est. Priority Date: 10/15/2014
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Rao, Kunal, Coviello, Giuseppe, Chakradhar, Srimat, Bhattacherjee, Souvik, Cadambi, Srihari
• Granted Patent: US 10,019,190 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 is provided 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:

extracting, by a graph sampler, an active sampled graph from an underlying base graph;

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 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 said 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 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 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 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.

18. The system of claim 1, wherein said 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.

9. A computer program product for detecting abnormal changes in real-time in dynamic graphs, the computer program product comprising a 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:

extracting, by a graph sampler, an active sampled graph from an underlying base graph;

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 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 said 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 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 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 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 extracting an active sampled graph from an underlying base graph;

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.