Statistical methods utilizing structural properties of time-evolving networks for event detection

Abstract

With the advancement of technology, real-world networks have become vulnerable to many attacks such as cyber-crimes, terrorist attacks, and financial frauds. Accuracy and scalability are the two principal but contrary characteristics for algorithms detecting such attacks (or events) in these time-varying networks. However, existing approaches confirm to either of these two prerequisites. Hence, we propose two algorithms designated as GraphAnomaly and GraphAnomaly-CS, both satisfying these two requirements together. Given a stream of time-evolving real-world network edges, the proposed algorithms first extract the local structure of network graphs by identifying the relationship between egonets and their properties, and then use this information in Chi-square statistics to discover (1) anomalous time-points at which many network nodes deviate from their normal behavior and (2) those nodes and features that majorly contribute to the change. The proposed algorithms are (a) accurate: upto 7 to 12% more accurate than state-of-the-art methods; (b) speedy: process millions of edges within a few minutes; (c) scalable: scale linearly with the number of edges and nodes in the network graph; (d) theoretically sound: providing theoretical guarantees on the false positive probability of algorithms; We show theoretically and experimentally that the proposed algorithms successfully detect anomalies in time-evolving edge streams. We have selected six baselines, five evaluation metrics, and six real-world network datasets from three different network classes for empirical analysis. The experimental results show that both algorithms are efficient at detecting anomalies in networks that reduce false positives and false negatives in the results, especially in successive time-points. Furthermore, algorithms discover the maximum number of critical events from real-world networks, demonstrating their effectiveness over baselines