It’s also prone to finding micro-clusters which in many cases could be construed as noise.įor my purposes it works incredibly well and I assume scales well. induce a subgraph with only edge weights greater than a threshold, then cluster that) an approach prone to graph fragmentation, which may or may not be desirable. You can get around this to extent by relaxing your edge weight threshold (i.e. For example, if your data is heavily interlinked (a high degree to cardinality ratio) with no natural subgraphs, CW may just find a single cluster where you can demand K-means go find some. This is, of course, also a draw-back in some circumstances. It just finds the clusters that are there. If you can fit you data into a graphical form, this is a very viable alternative to K-means style clustering, made even more attractive (for certain tasks) by the fact that it’s parameter free and thus you don’t need to pre-define the number of clusters (the bane of many a data scientist). CW took seconds to run whereas Gephi taxed my CPU to the max for many minutes (actually I think it was 10’s of minutes). The node colours show the clusters identified by CW.Īs you can see, the two algorithms broadly agree. The image below shows a Gephi visualisation using the ForceAtlas2 algorithm. Given its simplicity it’s a remarkably effective algorithm. # set the class of target node to the winning local class # find the class with the highest edge weight sum # do an inventory of the given nodes neighbours and edge weightsĬlasses] += GĬlasses] = G # I randomize the nodes to give me an arbitrary start point # After a certain number (individual to the data set) no further clustering occurs # You could use a random number or a counter or anything really # Here I use the ID of the node since I know it's unique # CW needs an arbitrary, unique class for each node before initialisation It uses NetworkX (for convenience – you could easily implement without this) and is incredibly fast.

I couldn’t find a simple implementation in Python so I created one myself using the formulas on the original paper. There isn’t exactly a lot of choice! I stumbled across Chinese Whispers an elegant and simple solution. MCL is a bit heavy for my needs and I was after something that was available in pure Python (because of environment access and compatibility issues) pretty much immediately.

I needed a simple and efficient unsupervised graph clustering algorithm.

Chinese whispers examples