要約
我々は、複雑ネットワークにおけるクラスタ検出のための新規フレームワーク「Ego-Splitting」を提案する。この手法は、各ノードの近傍領域から構成される局所構造（エゴネット、すなわちエゴネットとして知られる部分グラフ）を活用し、重複するクラスタを分離する。Ego-Splittingは、理論的に保証された性能を備えつつ、高いスケーラビリティと柔軟性を有するフレームワークであり、複雑な重複クラスタリング問題を、より単純かつ扱いやすい非重複（分割）問題に変換する。これにより、数十億エッジを有するグラフにおけるコミュニティ検出を実現でき、従来のエゴネット解析に基づく手法を上回る性能を発揮する。より正確に説明すると、本フレームワークは2段階のプロセスで構成される。第1段階は局所的なエゴネット分析フェーズであり、第2段階はグローバルなグラフ分割フェーズである。局所段階では、まずノードのエゴネットを分割アルゴリズムを用いて分割する。その後、得られたクラスタを基に、各ノードをその所属するコミュニティにおける「キャラクターノード（persona nodes）」に分割する。これらのキャラクターノードは、ノードが異なるコミュニティにおいて果たす役割の具体化を表す。次に、グローバル段階において、新たに構築されたグラフを分割することで、元のグラフに対する重複クラスタリング結果を獲得する。