  Dynamic networks, also called network streams, are an important data
representation that applies to many real-world domains. Many sets of network
data such as e-mail networks, social networks, or internet traffic networks are
best represented by a dynamic network due to the temporal component of the
data. One important application in the domain of dynamic network analysis is
anomaly detection. Here the task is to identify points in time where the
network exhibits behavior radically different from a typical time, either due
to some event (like the failure of machines in a computer network) or a shift
in the network properties. This problem is made more difficult by the fluid
nature of what is considered "normal" network behavior. The volume of traffic
on a network, for example, can change over the course of a month or even vary
based on the time of the day without being considered unusual. Anomaly
detection tests using traditional network statistics have difficulty in these
scenarios due to their Density Dependence: as the volume of edges changes the
value of the statistics changes as well making it difficult to determine if the
change in signal is due to the traffic volume or due to some fundamental shift
in the behavior of the network. To more accurately detect anomalies in dynamic
networks, we introduce the concept of Density-Consistent network statistics. On
synthetically generated graphs anomaly detectors using these statistics show a
a 20-400% improvement in the recall when distinguishing graphs drawn from
different distributions. When applied to several real datasets
Density-Consistent statistics recover multiple network events which standard
statistics failed to find.
