研究総括　河原林　健一

(国立情報学研究所　教授)

研究期間　2012年10月～2018年3月

インターネットのWeb構造や、Facebook、Twitterなどのソーシャルネットワークに代表される巨大なネットワークは、各々10⁹（10億人）に近いユーザーが利用し、現代社会に欠かせない存在となっています。これらのネットワークは年々急速に膨張し、近い将来には10¹⁰を超えるサイズになると予想されています。
　ネットワークの膨張に伴う情報量の増大はハードウェアの進歩を上回る速さで進んでおり、いわゆる「ビッグデータ」の中でも特に巨大な、10¹⁰以上のサイズのネットワークに対しては、現行のアルゴリズムでは実用的な速度で情報を解析することが不可能であり、高速アルゴリズムの開発が急務となっています。
　このような背景のもと、本プロジェクトでは、巨大なネットワークを膨大な点と辺の接続構造、すなわち10¹⁰以上の頂点を持つ「巨大グラフ」として表現し、理論計算機科学や離散数学などにおける最先端の数学的理論を駆使してそれを解析する、高速アルゴリズムの開発を目指します。
　具体的には、次の4つのテーマに取り組みます。(1)巨大な道路・交通ネットワークにおける2点間の最短経路の探索に関して、最新の理論的研究に基づいた前処理アルゴリズムを開発し、実用的なサイズのデータ構造を予め作成することで短時間に探索結果を得ることを目指します。(2)リアルタイムで変化・膨張を続けることから、モデル化や解析が非常に困難なＷｅｂ構造やソーシャルネットワークについて、その近未来を予測する成長モデルの構築を図ります。(3)携帯電話や個人利用のPCなど、解析に高性能コンピュータ（HPC）を利用できない環境を考慮して、作業メモリに制限のある状況下でも高速計算の可能なアルゴリズムを作成します。(4)アルゴリズムの高速化に寄与するとされる、ヒューリスティック手法（正解である保証はないが、経験則などを用いて、ある程度のレベルで正解に近い解が得られる方法）の巨大ネットワーク解析における適用範囲について、理論的な検証を行います。これらの研究を通じて、新たな数学的理論を構築するだけでなく、ネットワーク解析における理論的研究の有効性を実証し、交通網やWebの解析に加えて、バイオインフォマティクスや、災害時における有効な情報伝達方法の解析手段となるなど、巨大な情報量のために従来の手法では対処できなかった諸問題解決の糸口を得ることを目標とします。
　本プロジェクトは、センシングデータなど、大量の情報を解析して個人に必要かつ最適な作用・効果を提供する環境の実現にも寄与するものであり、戦略目標「人間と調和する情報環境を実現する基盤技術の創出」に資するものと期待されます。

　図を表示できない方は「図の説明」をご覧ください。

 

研究グループ

• グラフマイニング＆WEB＆AIグループ

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

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

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