研究背景・目的
Web構造やFacebook・TwitterなどのSNSに代表される巨大なネットワークは、各々100億に近いユーザーが利用し、現代社会に欠かせない存在となり、さらに年々急速に膨張しています。ネットワークの膨張に伴う情報量の増大はハードウェアの進歩を上回る速さで進んでおり、いわゆる「ビッグデータ」の中でも特に巨大な、10の10乗以上のサイズのグラフに対しては、現行のアルゴリズムでは実用的な速度で情報を解析することが不可能であり、高速アルゴリズムの開発が急務となっています。
インターネット、GPSを発明したDARPA(米)が2011年の研究課題に「ソーシャルネットワークなどの巨大グラフ解析」を選ぶなど、巨大グラフの解析は現在世界的にも重要な問題であると認識されています。
このような背景のもと、理論計算機科学や離散数学などにおける最先端の数学的理論を駆使して、巨大グラフを解析する高速アルゴリズムの開発を目指します。
研究内容
具体的には、次の4つのテーマに取り組んでいます。
- 巨大な道路・交通ネットワークにおける2点間の最短経路の探索に関して、最新の理論的研究に基づいた前処理アルゴリズムを開発し、実用的なサイズのデータ構造を予め作成することで短時間に探索結果を得ることを目指します。
- リアルタイムで変化・膨張を続けることから、モデル化や解析が非常に困難なWeb構造やソーシャルネットワークについて、その近未来を予測する成長モデルの構築を図ります。
- 携帯電話や個人利用のPCなど、解析に高性能コンピュータ(HPC)を利用できない環境を考慮して、作業メモリに制限のある状況下でも高速計算の可能なアルゴリズムを作成します。
- アルゴリズムの高速化に寄与するとされる、ヒューリスティック手法の巨大ネットワーク解析における適用範囲について、理論的な検証を行います。
これらの研究を通じて、新たな数学的理論を構築するだけでなく、ネットワーク解析における理論的研究の有効性を実証し、巨大な情報量のために従来の手法では対処できなかった諸問題解決の糸口を得ることを目標としています。
産業応用の可能性
- 多くの企業が取り組んでいる「ビッグデータ」の活用・分析に貢献
- 交通網やWebの解析に貢献(新たな数学的理論を構築するだけでなく、ネットワーク解析における理論的研究の有効性を実証)
- バイオインフォマティクスや、災害時における有効な情報伝達方法の解析
研究者の発明
- 特願2011-171261:情報処理装置、日程決定方法及びコンピュータプログラム ほか
連絡先
河原林 健一[情報学プリンシプル研究系 教授]
http://bigdata.nii.ac.jp/wp/
k_keniti[at]nii.ac.jp ※[at]を@に変換してください
関連リンク
Recommend
さらにみる