Detecting changes in time series of network graphs using minimum mean squared error and cumulative summation

Abstract

Through characterising a computer network as a time series of graphs, with IP addresses on the vertices and edges weighted by the number of packets transmitted, we apply graph distance metrics to arrive at a measure of the distance between the network at different times. Two computationally simple methods of detecting change points in a one dimensional time series of this distance data are proposed. These techniques are cumulative summation and minimum mean squared error. This offers a very space efficient method of detecting change points as only the time series of graph distances and the network graph for the last time slice need be kept. The two techniques are compared on a dataset containing 102~consecutive working days of TCP/IP traffic collected from five probes on the enterprise network of an organisation with many tens of thousands of employees. Network managers identified three highly anomalous days, one a change point associated with the introduction of a web based personnel management system. Computationally simpler graph distance metrics are shown to yield better results than their more complicated counterparts when coupled with either change point detection technique.