Date of Award
2012
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
AHSCAN, DHSCAN, edge weights, graph clustering, SCAN
Supervisor
Ziad Kobti
Supervisor
Scott Goodwin
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
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.
Recommended Citation
Chertov, Anton, "Extension of graph clustering algorithms based on SCAN method in order to target weighted graphs" (2012). Electronic Theses and Dissertations. 5408.
https://scholar.uwindsor.ca/etd/5408