What is Chinese Whispers clustering?

Chinese Whispers is a randomized graph-clustering algorithm. It can be implemented iteratively, and increasing the number of edges has a linear time cost. The algorithm is simple to implement with primitive data structures.

Algorithm Steps

  1. Assign a unique cluster label to each node. If you have 5 nodes, they can be labeled (0, 1, 2, 3, 4).
  2. Iterate the nodes in a random order. For each node, change its cluster label to the cluster with which we have the most connections. If there is a tie, pick one randomly from the tied clusters.
  3. Repeat step two for N steps, or until the clustering converges.

References and relevant links