DCBM（次数補正ブロックモデル）におけるコミュニティ検出のための行列因子分解フレームワーク

要旨: コミュニティ検出はデータ分析における基本的な課題であり、ブロックモデルは、高い解釈可能性を提供しながら、多様なコミュニティ構造を識別するためのアプローチを提供します。次数補正ブロックモデル（DCBM）は、ノード次数の異質性を考慮する確立されたモデルです。しかし、推論手法は計算コストが高く、初期化に対して非常に敏感です。一方で、スペクトル法やモジュラリティに基づく手法のようなより安価な代替手法は、通常は同類的（assortative）な特定の構造の検出に限られます。本研究では、DCBMの推論を制約付きの非負行列因子分解（constrained nonnegative matrix factorization）問題として再定式化できることを示します。この洞察を活用して、コミュニティ検出のための新しい手法と、推論アルゴリズムに対するコミュニティの初期推定値を与える理論的に裏付けのある初期化戦略を提案します。提案手法は、特定のネットワーク構造に依存せず、DCBMで表現可能な任意の構造をもつグラフに適用できます。合成データおよび実データのベンチマークネットワークでの実験により、本手法は、DCBMの推論で見られるものと同等のコミュニティを検出できる一方で高速であることが示されました。例えば、100,000ノードおよび1,000,000エッジのグラフを約4分で処理します。さらに、提案する初期化戦略は、検証したすべての推論アルゴリズムにおいて、解の質を大幅に向上させ、必要な反復回数を削減します。全体として、本研究は、コミュニティ検出のためのスケーラブルで頑健な枠組みを提供し、DCBMに対する行列因子分解の観点の利点を示します。