Clustering via the modified Petford-Welsh algorithm
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.
Keywords
Graph algorithm, community detection, the Petford-Welsh algorithm, simulated annealing, complex networks
DOI: https://doi.org/10.26493/1855-3974.2079.7b1
ISSN: 1855-3974
Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications