Database Reference
In-Depth Information
and knowledge extraction process that is able to infer hitherto hidden rela-
tionships between normal and abnormal events in time series.
The procedures introduced in this chapter do not make any particular
assumptions about the underlying problem domain. In other words, the
given sequence of graphs may represent any time series of objects or sys-
tems. However, to demonstrate the feasibility of the proposed approach, a
special problem in the area of computer network monitoring is considered
[19]. In this application each graph in a sequence represents a computer
network at a certain point of time, for example, at a certain time each day.
Changes of the network are captured using a graph distance measure. Hence
a sequence of graph similarity values is derived from a given time series of
graphs. Each similarity value is an indicator of the degree of change that
occurred to the network between two consecutive points of time. In this
sequence of similarity values abnormal change can be detected by means of
thresholding and similar techniques. That is, it is assumed that an abnor-
mal change has occurred if the similarity between two consecutive graphs
is below a given threshold.
There are other applications where complex systems, which change their
behaviour or properties over time, are modelled through graphs. Examples
of such systems include electrical power grids [20], regulatory networks con-
trolling the mammalian cell cycle [21], and co-authorship and citation net-
works in science [22]. The formal tools introduced in this chapter can also
be used in these applications to detect abnormal change in the system's
behaviour.
The remainder of this chapter is organized as follows. In Section 2 our
basic terminology is introduced. Graph similarity measures based on graph
spectra are presented in Section 3. Another approach to measuring graph
similarity, using graph edit distance, is discussed in Section 4. The median
of a set, or sequence, of graphs is introduced in Section 5, and its use for
the classification of events in a sequence of graphs is discussed in Section 6.
Then in Section 7 the application of the similarity measures introduced in
the previous sections to the detection of abnormal change in communication
networks is discussed. Finally, some conclusions are drawn in Section 8.
2. Preliminaries
A
graph
G
=(
V, E
) consists of a finite set of vertices
V
and finite set of edges
E
which are pairs of vertices; a pair of vertices denotes the endpoints of an
edge. Two vertices
u, v ∈ V
are said to be
adjacent
if they are endpoints of
