CLASSIFICATION AND DETECTION OF ABNORMAL EVENTS IN TIME SERIES OF GRAPHS - Data Mining in Time Series Databases - page 127

CHAPTER 6
CLASSIFICATION AND DETECTION OF ABNORMAL
EVENTS IN TIME SERIES OF GRAPHS
H. Bunke
Institute of Computer Science and Applied Mathematics
University of Bern, CH-3012 Bern, Switzerland
E-mail: [e-mail]
M. Kraetzl
ISR Division, Defense Science and Technology Organization
Edinburgh SA 5111, Australia
E-mail: [e-mail]
Graphs are widely used in science and engineering. In this chapter, the
problem of detecting abnormal events in times series of graphs is inves-
tigated. A number of graph similarity measures are introduced. These
measures are useful to quantitatively characterize the degree of change
between two graphs in a time series. Based on any of the introduced
graph similarity measures, an abnormal change is detected if the simi-
larity between two consecutive graphs in a time series falls below a given
threshold. The approach proposed in this chapter is not geared towards
any particular application. However, to demonstrate its feasibility, its
application to abnormal event detection in the context of computer net-
works monitoring is studied.
Keywords : Graph; time series of graphs; graph similarity; abnormal
event detection; computer network monitoring.
1. Introduction
Graphs are a powerful and flexible data structure useful for the represen-
tation of objects and concepts in many disciplines of science and engineer-
ing. In a graph representation, the nodes typically model objects, object
parts, or object properties, while the edges describe relations between the
nodes, for example, temporal, spatial, or conceptual dependencies between
the objects that are modelled through the nodes. Examples of applications
127