本研究課題の目的は，ネットワーク内の有用な構造を検出するための数理モテルの構築と効率的な計算手法の設計である．本年度は，昨年度に引き続き，大規模なネットワークを解析するために，制約付き劣モジュラ関数最大化に対するストリーミングアルゴリズムの設計に取り組んだ．我々が提案したアルゴリズムは，入力データを定数回しか見ずに効率的に近似解を計算するものであり，メモリ効率が高くデータが大規模な場合に有用である．まず，サイズ制約付きの問題に対して，従来手法よりも高速に，理論的に最適な近似解を求めるアルゴリズムを提案した．さらに，ナップサック制約付の問題について初めて非自明な近似比解析を与えた．本成果はフランス ENS の Chien-Chung Huang 氏との共同研究である．
さらに，ネットワークの中から同じ性質や構造を持つ部分（コミュニティ）を検出するための最適化モデルを提案した．ネットワーク内のコミュニティを検出する問題はグラフマイニングにおける基本的な問題である．本研究課題では，コミュニティがその内部では密なつながりを持つが外へのつながりが薄いという性質を持つことに着目し，コミュニティ検出のための新しい最適化モデルを提案した．提案モデルは，最密グラフ問題と呼ばれる組合せ最適化問題の拡張でありモジュラリティ密度最大化問題とも関連が深い．本研究ではまず，提案モデルが多項式時間で計算可能であることを示した．具体的には，線形計画問題に基づくものと最大流アルゴリズムを用いたものという2つのアルゴリズムを提案した．さらに，大規模ネットワークに適用できる，ほぼ線形時間の貪欲近似アルゴリズムを提案した．データセットを用いた計算機実験により提案アルゴリズムが効果的にコミュニティを検出できることを確認した．本成果は宮内 敦史氏（理研AIP）との共同研究であり，査読付国際会議CIKMに採択された．