Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Chinese whispers (clustering method)
open-in-new
<h2 id="algorithm">Algorithm</h2> <p>The algorithm works in the following way in an undirected unweighted graph:<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <ol><li>All nodes are assigned to a distinct class, so that the number of initial classes equals the number of nodes.</li> <li>All of the network nodes are selected one by one in a random order. For each selected node, its cluster label is changed to the cluster with which it has the most connections. If there is a tie, one is picked randomly from the tied clusters.</li> <li>Step two repeats itself until a predetermined number of iterations or until the process converges. In the end the emerging classes represent the clusters of the network.</li></ol> <p>The predetermined threshold for the number of the iterations is needed because it is possible that process does not converge. On the other hand in a network with approximately 10000 nodes the clusters does not change significantly after 40-50 iterations even if there is no convergence.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p> <h2 id="strengths-and-weaknesses">Strengths and weaknesses</h2> <p>The main strength of Chinese whispers lies in its time linear property. Because the processing time increases linearly with the number of nodes, the algorithm is capable of identifying communities in a network very fast. For this reason Chinese whispers is a good tool to analyze community structures in graph with a very high number of nodes. The effectiveness of the method increases further if the network has the <a href="/facts/Small-world_experiment/5ksGm26o">small world property</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p><p>On the other hand because the algorithm is not deterministic in the case of small node number the resulting clusters often significantly differ from each other. The reason for this is that in the case of a small network it matters more from which node the iteration process starts while in large networks the relevance of starting points disappears.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> For this reason for small graphs other clustering methods are recommended. </p> <h2 id="applications">Applications</h2> <p>Chinese whispers is used in many subfield of network science. Most frequently it is mentioned in the context of <a href="/facts/Natural_language_processing/1hjMKsSN">natural language processing</a> problems.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a><a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> On the other hand the algorithm is applicable to any kind of community identification problem which is related to a network framework. Chinese whispers is available for personal use as an extension package for <a href="/facts/Gephi/4NqBTF6J">Gephi</a><a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> which is an <a href="/facts/Open-source_software/HzTaB8E9">open source</a> program designed for network analysis. </p> <h2 id="external-links">External links</h2> <ul><li><a href="https://github.com/nlpub/chinese-whispers-python">Implementation in Python</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Chris Biemann,"Chinese Whispers- an Efficient Graph Clustering Algorithm and its Applications to Natural Language Processing Problems", 2006 <a href="https://www.aclweb.org/anthology/W06-3812.pdf" target="_blank">https://www.aclweb.org/anthology/W06-3812.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Chris Biemann,"Chinese Whispers- an Efficient Graph Clustering Algorithm and its Applications to Natural Language Processing Problems", 2006 <a href="https://www.aclweb.org/anthology/W06-3812.pdf" target="_blank">https://www.aclweb.org/anthology/W06-3812.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Chris Biemann,"Chinese Whispers- an Efficient Graph Clustering Algorithm and its Applications to Natural Language Processing Problems", 2006 <a href="https://www.aclweb.org/anthology/W06-3812.pdf" target="_blank">https://www.aclweb.org/anthology/W06-3812.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Chris Biemann,"Chinese Whispers- an Efficient Graph Clustering Algorithm and its Applications to Natural Language Processing Problems", 2006 <a href="https://www.aclweb.org/anthology/W06-3812.pdf" target="_blank">https://www.aclweb.org/anthology/W06-3812.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Chris Biemann,"Chinese Whispers- an Efficient Graph Clustering Algorithm and its Applications to Natural Language Processing Problems", 2006 <a href="https://www.aclweb.org/anthology/W06-3812.pdf" target="_blank">https://www.aclweb.org/anthology/W06-3812.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Chris Biemann,"Chinese Whispers- an Efficient Graph Clustering Algorithm and its Applications to Natural Language Processing Problems", 2006 <a href="https://www.aclweb.org/anthology/W06-3812.pdf" target="_blank">https://www.aclweb.org/anthology/W06-3812.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Chris Biemann,"Chinese Whispers- an Efficient Graph Clustering Algorithm and its Applications to Natural Language Processing Problems", 2006 <a href="https://www.aclweb.org/anthology/W06-3812.pdf" target="_blank">https://www.aclweb.org/anthology/W06-3812.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Chris Biemann,"Chinese Whispers- an Efficient Graph Clustering Algorithm and its Applications to Natural Language Processing Problems", 2006 <a href="https://www.aclweb.org/anthology/W06-3812.pdf" target="_blank">https://www.aclweb.org/anthology/W06-3812.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Chris Biemann,"Chinese Whispers- an Efficient Graph Clustering Algorithm and its Applications to Natural Language Processing Problems", 2006 <a href="https://www.aclweb.org/anthology/W06-3812.pdf" target="_blank">https://www.aclweb.org/anthology/W06-3812.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Antonio Di Marco - Roberto Navigili,"Clustering and Diversifying Web Search Results with Graph Based Word Sense Induction", 2013 <a href="http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00148#.VW4sDc_tmko" target="_blank">http://www.mitpressjournals.org/doi/full/10.1162/COLI_a_00148#.VW4sDc_tmko</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Ioannis Korkontzelos - Suresh Manandhar,"Detecting Compositionality in Multi-Word Expressions", 2009 <a href="http://www.aclweb.org/anthology/P09-2017" target="_blank">http://www.aclweb.org/anthology/P09-2017</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>""Gephi Marketplace"". Archived from the original on 2015-09-23. Retrieved 2015-06-02. <a href="https://web.archive.org/web/20150923031454/https://marketplace.gephi.org/plugin/chinese-whispers-clustering/" target="_blank">https://web.archive.org/web/20150923031454/https://marketplace.gephi.org/plugin/chinese-whispers-clustering/</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> </ol>