JSTトッププレス一覧科学技術振興機構報 第915号 > 資料2
資料2

研究領域の概要および研究総括の略歴

戦略的創造研究推進事業(ERATO型研究)
平成24年度発足

河原林巨大(カワラバヤシキョダイ)グラフプロジェクト

写真

【研究総括】河原林 健一(カワラバヤシ ケンイチ) 氏
(国立情報学研究所 教授)

研究領域「巨大グラフ」の概要

インターネットのWeb構造や、Facebook、Twitterなどのソーシャルネットワークに代表される巨大なネットワークは、各々10(10億人)に近いユーザーが利用し、現代社会に欠かせない存在となっています。これらのネットワークは年々急速に膨張し、近い将来には1010を超えるサイズになると予想されています。

ネットワークの膨張に伴う情報量の増大はハードウェアの進歩を上回る速さで進んでおり、いわゆる「ビッグデータ」の中でも特に巨大な、1010以上のサイズのネットワークに対しては、現行のアルゴリズムでは実用的な速度で情報を解析することが不可能であり、高速アルゴリズムの開発が急務となっています。

このような背景のもと、本研究領域では、巨大なネットワークを膨大な点と辺の接続構造、すなわち1010以上の頂点を持つ「巨大グラフ」として表現し、理論計算機科学や離散数学などにおける最先端の数学的理論を駆使してそれを解析する、高速アルゴリズムの開発を目指します。

具体的には、次の4つのテーマに取り組みます。①巨大な道路・交通ネットワークにおける2点間の最短経路の探索に関して、最新の理論的研究に基づいた前処理アルゴリズムを開発し、実用的なサイズのデータ構造を予め作成することで短時間に探索結果を得ることを目指します。②リアルタイムで変化・膨張を続けることから、モデル化や解析が非常に困難なWeb構造やソーシャルネットワークについて、その近未来を予測する成長モデルの構築を図ります。③携帯電話や個人利用のPCなど、解析に高性能コンピュータ(HPC)を利用できない環境を考慮して、作業メモリに制限のある状況下でも高速計算の可能なアルゴリズムを作成します。④アルゴリズムの高速化に寄与するとされる、ヒューリスティック手法(正解である保証はないが、経験則などを用いて、ある程度のレベルで正解に近い解が得られる方法)の巨大ネットワーク解析における適用範囲について、理論的な検証を行います。これらの研究を通じて、新たな数学的理論を構築するだけでなく、ネットワーク解析における理論的研究の有効性を実証し、交通網やWebの解析に加えて、バイオインフォマティクスや、災害時における有効な情報伝達方法の解析手段となるなど、巨大な情報量のために従来の手法では対処できなかった諸問題解決の糸口を得ることを目標とします。

本研究領域は、センシングデータなど、大量の情報を解析して個人に必要かつ最適な作用・効果を提供する環境の実現にも寄与するものであり、戦略目標「人間と調和する情報環境を実現する基盤技術の創出」に資するものと期待されます。

概要図

研究総括 河原林 健一 氏の略歴など

1.氏名(現職) 河原林 健一(カワラバヤシ ケンイチ)
(国立情報学研究所 教授) 37歳
2.略歴
平成13年 3月 慶応義塾大学 大学院理工学研究科 後期博士課程修了(博士(理学))
平成13年 4月 バンダービルト大学 客員研究員
平成14年 8月 プリンストン大学 博士研究員
平成15年 8月 東北大学 大学院情報学研究科 助手
平成18年 4月 国立情報学研究所 情報学プリンシプル研究系 助教授
(平成19年4月より准教授)
平成21年11月 国立情報学研究所 情報学プリンシプル研究系 教授
3.研究分野 離散数学、グラフアルゴリズム、グラフ理論、理論計算機科学
4.学会活動など
平成20年~ Journal of Graph Theory 編集委員
平成21年~ Discrete Mathematics and Theoretical Computer Science 編集委員
平成22年~ Siam Journal of Discrete Mathematics 編集委員
平成22年 Siam Discrete Math Conference 2010 プログラム委員
平成23年 Annual ACM-Siam Symposium on Discrete Algorithms(SODA)2011 プログラム委員
平成24年 Annual ACM-SIAM Symposium on Discrete Algorithms(SODA)2012 組織委員
5.業績など  河原林 健一 氏は、グラフ理論を始めとする最先端の離散数学の理論を駆使して、それを理論計算機科学にも応用することで、両分野における多くの未解決問題を解決してきた。離散数学分野においては、難解なグラフマイナー理論をアルゴリズム科学へと深化させ、「アルゴリズム的グラフマイナー理論」という独創的分野の研究を推進しつつある。またグラフ彩色問題や4色定理の周辺問題、曲面上のグラフに関する同型判定など、数多くの成果を収めた。さらに理論計算機分野においても、数学的理論を応用してグラフの複数パス問題を解決するなど、多数のアルゴリズムの開発に成功している。これら一連の成果は、離散数学と理論計算機科学にまたがる新展開を開いた卓越した業績として、世界的にも高く評価されている。
6.受賞など
平成13年 日本数学会 建部賢弘奨励賞
平成15年 井上科学振興財団 井上科学研究奨励賞
平成15年 Kirkman Medal
(Institute of Combinatorics and its Applications)
平成18年 文部科学大臣表彰 若手科学者賞
平成20年 日本IBM科学賞(コンピューターサイエンス部門)
平成21年 井上科学振興財団 井上リサーチアウォード
平成23年 船井情報科学振興財団 船井学術賞船井哲良特別賞