Design and analysis of algorithms to invent similarity patterns in large graph databases

Abstract

Graphs are very appropriate for modelling complicated structural data, such as circuits, images, communication network, molecular structures, biological networks, protein interactions and so on. More specifically, labeled graphs have been a promising abstraction to capture the characteristics of data sets rising in these fields. Hence, efficient graph mining algorithms are necessary for increasing our understanding of the information represented by these large datasets of graphs. Identifying similarities of graphs is a challenging and essential process in various domains, such as pattern recognition, information retrieval and bioinformatics. There are various similarity measures in the domain of graph mining, out of which the most familiar measures are maximum common subgraph, frequent subgraph search and query graph search to visualize the common and frequent structures of the graph database. This dissertation focuses on two types of graph databases to find the similarity patterns. The first one is the graph database of communication network where the state of the communication network is captured as a time series of graphs which has periodic snapshots of logical communications within the network. The second one is the chemical graph database which consists of chemical compounds which are easily visualized as undirected labelled graphs where atoms are the nodes with labels representing the name of the atoms and bonds representing the edges. The devised algorithms for chemical graph database can handle at most two input chemical graphs at a time, whereas the algorithms of communication network can handle k input graphs simultaneously. newline newline newline