研究概要

近年，センサーの高性能化やスマートフォンの普及により，センサーネットワークやソーシャルネットワークなどのビッグデータが存在し，ビッグデータから有用な特徴を抽出するための効率的なアルゴリズムが求められています．例えば，ソーシャルネットワークからある一定以上の大きなコミュニティを見つけることを考えます．ここでのコミュニティとはどの２人もお互いが知り合いである集団とします．こうしたコミュニティをネットワークから抽出することで，よりターゲットを絞ったコマーシャルを流す情報推薦の分野で活用することができます．
今回定義したコミュニティはグラフ理論におけるクリークと呼び，コミュニティを求める問題をクリーク問題と言います．クリーク問題のようなグラフ上の多くの組合せ最適化問題は NP-困難で，計算量理論上，効率的に解くことは難しいとされています．もう少し詳しく言うと，多くの組合せ最適化問題は指数時間で解くアルゴリズムしか知られていません．指数時間アルゴリズムは問題サイズが少し大きくなるだけで，爆発的に計算時間が増えてしまい，現実的な時間で解くことができません． 本グループではこうした計算量理論上，困難な問題に対して，様々なアプローチにもとづいた効率的なアルゴリズムの開発や計算複雑性に関する研究を行っています．