Clustering via the modified Petford-Welsh algorithm

Authors

DOI:

https://doi.org/10.26493/1855-3974.2079.7b1

Keywords:

Graph algorithm, community detection, the Petford-Welsh algorithm, simulated annealing, complex networks

Abstract

Detecting meaningful communities has become crucial to advance our knowledge in diverse research areas that deal with datasets which can be naturally represented as networks. By regarding vertex clustering as the opposite problem of vertex colouring, we were able to leverage the Petford-Welsh colouring algorithm to develop a fast, efficient, and highly-scalable decentralised clustering algorithm. Its greatest potential lies in outperforming conventional methods when the community structure is fairly clear-cut.

Published

2020-06-08

Issue

Section

Articles