大規模ネットワークに対する超高精度なコミュニティ検出法の構築

平成 28 年度においては，以下の二つの成果を得た．一つ目は，ネットワークからコミュニティを一つ取り出すようなコミュニティ検出（局所的コミュニティ検出）に関する成果である．局所的コミュニティ検出においては，「密度」と呼ばれる評価関数が標準的であり，「最密部分グラフ問題」が標準的な最適化問題として知られている．最密部分グラフ問題は，多項式時間可解であり，また線形時間で十分良い近似解が得られるため，大規模ネットワークの解析で頻繁に利用されている．しかしながら，出力グラフが大きすぎたり小さすぎたりするという「サイズの問題」が指摘されており，これを克服するため，出力グラフのサイズを陽に指定するような最適化問題に関する研究が行われてきた．本研究では，従来の密度の定義を拡張し，より一般的な最適化問題を考えることで，最密部分グラフ問題のサイズの問題に対する解決方策を与えた．拡張版の最密部分グラフ問題に対しては，精度保証付き近似解法や厳密解法を設計した．二つ目は，ネットワークをコミュニティに分割するようなコミュニティ検出（大域的コミュニティ検出）に関する成果である．本研究課題の主な研究対象である「モジュラリティ最大化問題」や，その他の様々なクラスタリング問題の共通の一般化として，「クリーク分割問題」と呼ばれる最適化問題が知られている．クリーク分割問題に対しては，これまでに数多くのアルゴリズムが提案されており，そのほとんどが整数線形計画問題としての定式化を利用している．しかしながら，この定式化（といくつかの修正版）は膨大な数の制約式をもっており，数百頂点のネットワークに対してすら適用することができなかった．本研究では，多くの実ネットワークに対して従来よりも大幅に少ない制約式をもつ，整数線形計画問題としての定式化を設計した．提案定式化は，数千頂点のネットワークに対しても適用することができる．

平成 28 年度においては，以下の二つの成果を得た．一つ目は，ネットワークからコミュニティを一つ取り出すようなコミュニティ検出（局所的コミュニティ検出）に関する成果である．局所的コミュニティ検出においては，「密度」と呼ばれる評価関数が標準的であり，「最密部分グラフ問題」が標準的な最適化問題として知られている．最密部分グラフ問題は，多項式時間可解であり，また線形時間で十分良い近似解が得られるため，大規模ネットワークの解析で頻繁に利用されている．しかしながら，出力グラフが大きすぎたり小さすぎたりするという「サイズの問題」が指摘されており，これを克服するため，出力グラフのサイズを陽に指定するような最適化問題に関する研究が行われてきた．本研究では，従来の密度の定義を拡張し，より一般的な最適化問題を考えることで，最密部分グラフ問題のサイズの問題に対する解決方策を与えた．拡張版の最密部分グラフ問題に対しては，精度保証付き近似解法や厳密解法を設計した．二つ目は，ネットワークをコミュニティに分割するようなコミュニティ検出（大域的コミュニティ検出）に関する成果である．本研究課題の主な研究対象である「モジュラリティ最大化問題」や，その他の様々なクラスタリング問題の共通の一般化として，「クリーク分割問題」と呼ばれる最適化問題が知られている．クリーク分割問題に対しては，これまでに数多くのアルゴリズムが提案されており，そのほとんどが整数線形計画問題としての定式化を利用している．しかしながら，この定式化（といくつかの修正版）は膨大な数の制約式をもっており，数百頂点のネットワークに対してすら適用することができなかった．本研究では，多くの実ネットワークに対して従来よりも大幅に少ない制約式をもつ，整数線形計画問題としての定式化を設計した．提案定式化は，数千頂点のネットワークに対しても適用することができる．