Detecting distributed anomalies rapidly and accurately is critical for efficient backbone network management. In this letter, we propose a novel anomaly detection method that uses router connection relationships to detect distributed anomalies in the backbone Internet. The proposed method unveils the underlying relationships among abnormal traffic behavior through closed frequent graph mining, which makes the detection effective and scalable.

In this letter, a new definition of two-stage spatiotemporal approach, called ICA-WFS (Independent-Component-Analysis-Weighted-Frequent-Substructure) is proposed. To facilitate capturing abnormal behavior across multiple networks and dimensionality reduction at a single Point of Presence (PoP), ICA is applied. With application of WFS, an complete graph is examined, unusual substructures of which are reported. Experiments are conducted and, together with application of backbone network (Internet2) Netflow data, show some positive results.