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.
- Assign a unique cluster label to each node. If you have 5 nodes, they can be labeled (0, 1, 2, 3, 4).
- 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.
- Repeat step two for N steps, or until the clustering converges.