Date of Award

2012

Degree Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

First Advisor

Ziad Kobti

Second Advisor

Scott Goodwin

Keywords

AHSCAN, DHSCAN, edge weights, graph clustering, SCAN

Rights

CC-BY-NC-ND 4.0

Abstract

In this thesis we evaluate current neighbour-based graph clustering algorithms: SCAN, DHSCAN, and AHSCAN. These algorithms possess the ability to identify special nodes in graphs such as hubs and outliers. We propose and extension for each of these in order to support weighted edges. We further implemented two graph generating frameworks to create test cases. In addition we used a graph derived from the ENRON email log. We also implemented a Fast Modularity clustering algorithm, which is considered as one of the top graph clustering algorithms nowadays. One of three sets of experiments showed that results produced by extended algorithms were better than one of the reference algorithms, in other words more nodes were classified correctly. Other experiments revealed some limitations of the newly proposed methods where we noted that they do not perform as well on other types of graphs. Hence, the proposed algorithms perform best on social graphs with pronounced community structure.

Share

COinS