This Title All WIREs
How to cite this WIREs title:
WIREs Comp Stat

Anomaly detection in dynamic networks: a survey

Full article on Wiley Online Library:   HTML PDF

Can't access this content? Tell your librarian.

Anomaly detection is an important problem with multiple applications, and thus has been studied for decades in various research domains. In the past decade there has been a growing interest in anomaly detection in data represented as networks, or graphs, largely because of their robust expressiveness and their natural ability to represent complex relationships. Originally, techniques focused on anomaly detection in static graphs, which do not change and are capable of representing only a single snapshot of data. As real‐world networks are constantly changing, there has been a shift in focus to dynamic graphs, which evolve over time. In this survey, we aim to provide a comprehensive overview of anomaly detection in dynamic networks, concentrating on the state‐of‐the‐art methods. We first describe four types of anomalies that arise in dynamic networks, providing an intuitive explanation, applications, and a concrete example for each. Having established an idea for what constitutes an anomaly, a general two‐stage approach to anomaly detection in dynamic networks that is common among the methods is presented. We then construct a two‐tiered taxonomy, first partitioning the methods based on the intuition behind their approach, and subsequently subdividing them based on the types of anomalies they detect. Within each of the tier one categories—community, compression, decomposition, distance, and probabilistic model based—we highlight the major similarities and differences, showing the wealth of techniques derived from similar conceptual approaches. WIREs Comput Stat 2015, 7:223–247. doi: 10.1002/wics.1347 This article is categorized under: Algorithms and Computational Methods > Algorithms Data: Types and Structure > Graph and Network Data Statistical Learning and Exploratory Methods of the Data Sciences > Pattern Recognition
Example of an anomalous vertex. A dynamic graph with two time steps showing a vertex, v6, that is found to be anomalous based on its change in community involvement. In time step 1, v6 is only part of community 2, whereas in time step 2 it is part of both communities 1 and 2. As no other vertex's community involvement changes, v6 is deemed anomalous.
[ Normal View | Magnified View ]
The proposed two‐tiered taxonomy that illustrates the layout of the survey. Methods are first categorized based on their overarching approach, then subdivided based on the types of anomalies they detect.
[ Normal View | Magnified View ]
An example of an event (a), a change (b), and the difference between them. In both, the graphs initially have only a few edges. At time step 3, the graphs become highly connected, almost forming a clique. The major difference is observed at the time step following the insertion of the edges. In Figure (a) the edges are then removed and the graph returns to a state similar to the one before the insertion, representing an isolated event. In Figure (b), however, the graph maintains its new state indicating the sustained shift, or change, in the graph.
[ Normal View | Magnified View ]
Two different types of anomalous subgraphs. (a) Shrunken community shows a shrunken community, where a community loses members from one time step to the next. (b) Split community shows a split community, where a single community breaks into several distinct smaller communities.
[ Normal View | Magnified View ]
An illustration of anomalous edges that occur because of an irregular pattern of their weight over time, with anomalous edges highlighted. At each time step, a vertex's weight typically shifts by ± 0.05 at most. However, edge (3, 4) has a spike in its weight at time step 2, unlike any other time in the series. Similarly, at time step 3, edge (1, 4) spikes in value. These spikes cause the edges to be considered anomalous.
[ Normal View | Magnified View ]

Browse by Topic

Statistical Learning and Exploratory Methods of the Data Sciences > Pattern Recognition
Data: Types and Structure > Graph and Network Data
Algorithms and Computational Methods > Algorithms

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts