Database Reference
In-Depth Information
that has occurred is normal or abnormal. This shortfall of useful informa-
tion for validation of network fault and performance anomalies is common
[43]. Visualisation tools have been used to assist with validating some of
the major changes by observing the network before and after a significant
change event. More work needs to be done in producing a reliable, validated
data set.
A number of additional experiments using median graphs have been
reported in [44]. In these experiments it was demonstrated that using the
median graph, computed over a running window of the considered time
series, rather than individual graphs has a smoothing effect, which reduces
the influence of outliers.
8. Conclusion
Graphs are one of the most popular data structures in computer science
and related fields. This chapter has examined a special class of graphs that
are characterised by the existence of unique node labels. This property
greatly reduces the computational complexity of many graph operations
and allows a user to deal with large sets of graphs, each consisting of many
nodes and edges. Furthermore, a number of graph distance measures have
been analysed. They are based on eigenvalues from spectral graph theory
and graph edit distance. A novel concept that can be used to measure the
similarity of graphs is median graph. The median of a set, or a sequence,
,
of graphs is a graph that minimises the average edit distance to all members
in
S
S
. Thus the median can be regarded as the best single representative of
a given set or sequence of graphs.
Abnormal events in a sequence of graphs representing elements of a
time dependent process can be detected by computing the distance of
consecutive pairs of graphs in the sequence. If the distance is larger than a
threshold than it can be concluded that an abnormal event has occurred.
Alternatively, to make the abnormal change detection procedure more
robust against noise and outliers, one can compute the median of the
time series of graphs over a window of a given span, and compare it to
an individual graph, or the median of a sequence of graphs, following that
window.
None of the formal concepts introduced in this paper is geared towards
a particular application. However, to demonstrate their usefulness in prac-
tice, an application in computer network monitoring was studied in this
chapter. Communication transactions, collected by a network management
