Chinese Whispers clustering

Clustering algorithm
Reading time: less than 1 minute

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

Citation

If you find this work useful, please cite it as:
@article{yaltirakli,
  title   = "Chinese Whispers clustering",
  author  = "Yaltirakli, Gokberk",
  journal = "gkbrk.com",
  year    = "2024",
  url     = "https://www.gkbrk.com/chinese-whispers-clustering"
}
Not using BibTeX? Click here for more citation styles.
IEEE Citation
Gokberk Yaltirakli, "Chinese Whispers clustering", October, 2024. [Online]. Available: https://www.gkbrk.com/chinese-whispers-clustering. [Accessed Oct. 10, 2024].
APA Style
Yaltirakli, G. (2024, October 10). Chinese Whispers clustering. https://www.gkbrk.com/chinese-whispers-clustering
Bluebook Style
Gokberk Yaltirakli, Chinese Whispers clustering, GKBRK.COM (Oct. 10, 2024), https://www.gkbrk.com/chinese-whispers-clustering

Comments

© 2024 Gokberk Yaltirakli