複雑ネットワーク・地図グラフグループ - ERATO河原林巨大グラフプロジェクト（NIIサイト）

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

実世界で現れる巨大グラフの代表例は、ソーシャルネットワークやウェブグラフに代表される「複雑ネットワーク」と、交通網を表現した「地図グラフ」である。本グループでは、これら二つのグラフに関して、コンピュータサイエンスと物理の両面から研究を行う。

コンピュータサイエンスでは、これらのグラフに対して様々なアルゴリズムが提案されているが、実験的に良い性能を出すことが示されているだけで、何故良い性能を出すのかが理論的に十分に理解されているとは言えない。一方物理では、これらのグラフの性質が物理的な発想をもとに明らかにされてきているが、それらの性質を利用した実用的なアルゴリズムは殆ど作られていない。

本来、実験と理論は両輪をなすもののはずである。実際自然科学は、実験で得られた知見を理論にまとめ、その理論から予想されることを実験によって確かめるというサイクルによって発展してきた。それと同じサイクルを複雑ネットワークと地図グラフの研究においても実現するのが本グループの目標である。コンピュータサイエンスと物理の両面から研究するという相乗効果により、巨大グラフに対する真に実用的なアルゴリズムの開発が大いに進展すると期待される。

メンバー