Addressing Scalability and Performance for Community Detection and Clustering in Complex Graphs

Abstract

Graphs are increasingly being used to provide structured representations of data as they are able to well encapsulate complex relationships within the data. This has led to the development of an abundance of graph centric analysis methods. These methods are used across many academic and industrial domains and aim to extract structural and spacial information from the topology of a graph.

Current approaches for identifying community memberships and clusters within complex networks often rely on a global view of a graph, normally requiring the entire graph to be held in memory. With the ever-growing size of graph datasets, processing this global view in memory is becoming increasingly difficult. In addition there are currently gaps in the existing literature related to community classification, identification and measurements of similarity without maintaining an expensive global view of the graph.

This work aims to address some of these issues through a number of approaches. These include an investigation into finding optimal ways of comparing the similarity between graphs as well as identification of optimal way of identifying sub-graphs, with common features, within a larger graph or, more simply, Community Detection. Development of ideal strategies for reducing computational and memory requirements of graph processing is also a major contribution of this work.