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

Brandon Pincombe


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.

Full Text:

PDF BibTeX References


Remember, for most actions you have to record/upload into this online system
and then inform the editor/author via clicking on an email icon or Completion button.
ANZIAM Journal, ISSN 1446-8735, copyright Australian Mathematical Society.