The problem of subgraph isomorphism is concerned with finding the
occurrences of a given pattern graph in a given target graph. This is an
important problem in the area of graph analysis, for it finds its use whenever
one is interested in searching for graph patterns, e.g., in chemistry or in
social network analysis. However, since the subgraph isomorphism problem
is NP-complete, research is focused on discovering algorithms that work
well in a majority of practical cases. As it turns out, though, many of
those algorithms are inefficient when given a pattern graph with a large
number of automorphisms (symmetries). In this thesis, we will show how to
speed up existing algorithms using a concept called exploratory equivalence,
an equivalence relation on the graph’s vertex set that is based on the set
of automorphisms. In particular, knowing exploratory equivalence of the
pattern graph enables us to define a set of constraints that can be used to
reduce the set of candidate mappings to be considered when searching for
the occurrences of the pattern graph in the target graph. We improved the
selected existing algorithms for the subgraph isomorphism problem in such a
way that they make use of exploratory equivalence. We tested and evaluated
our enhancements on multiple publicly available datasets. We published
improvements of the algorithms in the form of a publicly available module
within an existing library for solving the subgraph isomorphism problem.
|
