Extension of graph clustering algorithms based on SCAN method in order to target weighted graphs

Anton Chertov, University of Windsor


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.