« 読了: Kalinka & Tomancak (2011) linkcommパッケージ | メイン | 読了: 久野 (2009) ベティ・クロッカーさんの変遷 »
2013年6月12日 (水)
Bieman, C. (2006) Chinese Whispers - an Efficient Graph Clustering Algorithm and its Application to Natural Language Processing Problems. Proceedings of the HLT-NAACL-06 Workshop on Textgraphs.
ネットワーク・グラフの可視化・分析ソフトにgephiというのがあって、使いこなしているとは言い難いけど、しばらく前から愛用している。あのポヨンポヨンと動く感じがたまらない。ときどき落ちたり固まったりするところも愛嬌があってよい。例えていえば、ちょっとおっちょこちょいな巨乳の眼鏡っ子という感じだ。(なにを云っているのだ私は)
そのgephiに、ネットワーククラスタリングのためのChinese Whispersという機能が搭載されている。クラスタリングに関連する資料を読んでいて突然に気になったんだけど、あのChinese Whispersってなんだ？ 中国人のささやき？ 耳元で謝謝とか呟くのか？ チャイナドレスのお姉さんが？ ずいぶん色っぽいではないか。
...というわけで引用文献をめくってみた。正直、論文の本題にはあまり関心がない。すいません。
基本的には、非階層的なハード・パーティショニングのアルゴリズムである。最初は全ノードが各自のクラスに属する。で、全ノードをランダムな順序で抽出し、「近隣ノードにおける上位クラス」に所属させる。全部回ったらまた繰り返す。という、超簡単なアルゴリズムだが、巨大なネットワークでもすごく速くクラスタリングできるのだそうだ。もっとも、常に収束するとは限らないけど。
肝心の、命名の由来だが... 英語では「伝言ゲーム」のことをChinese Whispersというのだそうです。英和辞典にも載っていた。がっくり。
論文：データ解析(-2014) - 読了: Bieman (2006) チャイニーズ・ウィスパー・アルゴリズム