マルコフ確率場モデルに基づくコミュニティー抽出アルゴリズム

摘要

本研究ではマルコフ確率場モデリングの視点に基づくモジュラリティー最適化によるコミュニティー構造の検出アルゴリズムを提案する．複雑ネットワークにおけるコミュニティーとは，同じコミュニティー内の頂点は密に繋がっているが，異なるコミュニティー間の結合が疎であるような部分ネットワークのことである．与えられたネットワークの構造からこのようなコミュニティー構造を抽出する方法としてモジュラリティーの最適化法が知られており，マルコフ確率場の視点ではこのモジュラリティーの最適化はネットワーク構造が与えられたもとでの事後確率を最大にする確率分布を推定するMAP推定とみなすことができる．本研究ではMAP推定を近似的に行うMax-Productアルゴリズムの手法をモジュラリティー最適化に対して定式化し，モジュラリティー最適化を行う効果的な推論アルゴリズムを提案する．さらに数値実験によりコミュニティーの検出精度について従来法との比較を行う．