不確実性を考慮した頑健なコミュニティ検出法の開発

点击翻译按钮获取中文摘要

令和4年度においては，本研究課題の進展に寄与する以下の成果を得た．具体的には，ネットワーク上のコミュニティ検出に対する有力な最適化モデルであるモジュラリティ密度最大化問題に対して，列生成法の高速化と計算困難性の解析を行った．列生成法とは，組合せ最適化問題に対する有力な解法設計の枠組みであり，多くのインスタンスで厳密解が得られるようなアルゴリズムを設計できる．モジュラリティ密度最大化問題に対しても列生成法に基づくアルゴリズムが知られているが，非常に小規模なインスタンスにのみ適用可能なものであった．本研究では，列生成法に基づくアルゴリズムの設計で中心的な役割を果たす補助問題と呼ばれる最適化問題を密グラフ抽出問題として捉え直し，密グラフ抽出問題に対する有力な解法設計戦略である貪欲ピーリングを用いた．また，補助問題に対する再定式化を行った．その結果，既存手法の性能を大きく上回るアルゴリズムの設計に成功した．一方，計算困難性に関しては，モジュラリティ密度最大化問題の変種と上記の補助問題のNP困難性を示した．研究期間全体を通じては，研究実施計画に沿った形で，多くの研究成果を得ることができた．本研究の目的は，ネットワーク上のコミュニティ検出に対して，不確実性を考慮した最適化モデルの導入とそれに対するアルゴリズムの設計を行うことで，既存研究では実現し得なかった頑健なコミュニティ検出法を開発することであった．本研究で提案した最適化モデルとしては，枝重みが不確実な場合の最密部分グラフ問題，最密k-連結部分グラフ問題，二層ネットワークや多層ネットワーク上の最密部分グラフ問題が挙げられる．これらの最適化モデルや既存の最適化モデルに対して，理論保証をもつアルゴリズムの設計や計算困難生の解析を行った．また，密グラフ抽出の新たな応用先として，クラウドソーシングの中心的な研究課題である意見集約を指摘した．