We introduce Chinese Whispers, a randomized graph-clustering algorithm, which is time-linear in the number of edges. After a detailed definition of the algorithm and a discussion of its strengths and weaknesses, the performance of Chinese Whispers is measured on Natural Language Processing (NLP) problems as diverse as language separation, acquisition of syntactic word classes and word sense disambiguation. At this, the fact is employed that the small-world property holds for many graphs in NLP.
Specifically, they propose an incremental version of Chinese Whispers REF , a randomized graph-clustering algorithm.
Chinese Whispers - An Efficient Graph Clustering Algorithm And Its Application To Natural Language Processing Problems
TextGraphs Workshop On Graph Based Methods For Natural Language Processing
Computer Science