河原林巨大グラフプロジェクト

プロジェクトホームページ

研究総括 河原林 健一

研究総括 河原林 健一
(国立情報学研究所 教授)
研究期間 2012年10月~2018年3月

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

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

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

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

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

 

研究グループ

・グラフマイニング&WEB&AIグループ

・複雑ネットワーク・地図グラフグループ

・グラフ・ネットワークにおける理論と最適化グループ

・ネットワーク・アルゴリズムグループ

 

プロジェクトヘッドクオーター

〒101-8430 東京都千代田区一ツ橋2-1-2
国立情報学研究所 ビッグデータ数理国際研究センター

研究推進主任:安藤 清
研究推進員:鶴岡 舞子、津島 智子

TEL:03-4212-2664