Discovering Regions of Correlated Change in Dynamic Graphs
Jeffrey Kai, Chi Ho Roger Chan · 2009
Many types of applications involve large datasets that describe the relationships between a set of entities. This has led to a growing need to design data mining algorithms to find interesting and significant patterns in these very large datasets. In these types of data mining problems, graphs provide a natural representation for such relational data. Hence, there has been a growth in research into graph mining – the field of finding interesting patterns in graphs. Most existing graph mining work considers graphs as non-changing and static, but many graph datasets do changewith time. There has been recent work on algorithms that take the dynamics of graphs into consideration, such as finding subgraphs that are frequent across multiple periods of time in a dynamic graph. However, none of the current work discovers groups of vertices and edges of a dynamic graph that change in a similar manner and are topologically close. These groups of vertices and edges are called regions of correlated spatio-temporal change. They can be used in a variety of contexts, including fault localisation in multi-layered computer networks, identification of activated parts of the brain during different activities and discovering trends in spatio-temporal datasets. In this thesis, we introduce the new concept of regions of correlated spatio-temporal change and the associated problem of finding these regions in dynamic graphs. Given that graph datasets can be very large, algorithms to find these regions must be scalable and the regions discovered by the algorithms must be accurate. In this thesis, we introduce three different algorithms to discover the regions in a dynamic graph and we propose a new method to evaluate the accuracy of discovered regions. The first algorithm we propose to find regions of correlated change is a greedy approach. It considers the region discovery problem as a multi-objective clustering prob-