IH-004
Community Detection Using Random-walk Similarity and Application to Image Clustering

○奥田　誠（NICT）・佐藤真一（NICT/NII）・岩澤昭一郎・吉田俊介・木俵　豊（NICT）・佐藤洋一（東大）

本講演では，国際会議ICIP 2017 で発表したコミュニティ検出手法について概説する．コミュニティ検出とは，ネットワークからエッジ密度が高い部分グラフを検出することで，グラフクラスタリングとも呼ばれる．従来のコミュニティ検出手法の多くは，ネットワークモジュラリティを評価指標として，最適なコミュニティ構造を探索するというアプローチをとってきた．しかし，このような手法には，「解像度限界」と呼ばれる比較的小さなコミュニティを検出できないという欠点があることが知られている．そこで，筆者らは，そのようなアプローチをとらず，ランダムウォーク技術を用いた斬新な手法を開発した．提案手法の基本的なアイデアは，「ネットワークの全頂点からランダムウォークを実行し，通過頂点が類似するランダムウォークの出発頂点を同じコミュニティに属すると判断する」というものである．例え出発頂点が小さなコミュニティに属していても，ランダムウォーカが短期間にコミュニティ外に出る確率は小さいというランダムウォークの性質により，提案手法は小さなコミュニティを検出することができる．インタネットから収集した大量の観光画像を被写体毎にクラスタリングするという課題において本手法を評価した結果，提案手法は従来手法に比べ，小さなクラスタと大きなクラスタを同時に検出する能力に優れ，全体的なクラスタリング精度も高いことが示された．