ジョージ・ワシントン橋

現在、グラフ探索のアルゴリズムを用いて大規模グラフ・ネットワーク分析を行っているが、様々な元問題からグラフが作成されていることもあって、ゲノム解析のように元問題の隠れた構造や性質が浮かび上がってくることが多い。詳細な分析は公式の機会に発表するとして、簡単な例を紹介する。
ニューヨークにジョージ・ワシントン橋という大きな橋がある。



ニューヨーク近辺の２６万点のグラフにおいて各点の中心性を求めるとジョージ・ワシントン橋の所の値が非常に高くなっている（赤くなっている部分）。真ん中に大きな川があって、この川の橋が数本しか存在していないので当然ながら橋の部分の中心性は高くなる。



例えばサンディエゴから北東部のメーン州までの最短路（赤：最短距離、青：最短時間）を求めてみる。



最短時間の経路は以下のようにジョージ・ワシントン橋を通過する。この橋はローカルな重要性だけでなく、もっとグローバルにも重要性が高い可能性がある。現在、研究室のクラスタ計算機を用いて全米データでも厳密な中心性の計算を行っている。



日本の首都圏では３環状（首都高速中央環状(C2)、外環道、圏央道）の整備が行われているだが、ある程度完成するまでは、都心に用事が無い車でも都心を完全に迂回することができずに、首都高速都心環状(C1)に依存する状況は続いていくだろう。今後、グラフ解析が進んでいけば、このような自明な例だけでなく、隠れた重要点（交通のボトルネックとなる点）も発見されていくだろう。