複雑ネットワークとグラフ理論
「たった六人を介するだけで、世界中の人とつながれるのです。」キャッチーで身近なテーマが多く、一般的な読み物としても人気の高いネットワークの分野。バラバシ著の新ネットワーク思考は、ネットワークの理論が発展してきた背景を時系列で追うことができるし、ワッツのスモールワールドは、理論的な部分にも言及していて、入門用として大学院生のゼミなどに活用することもできるだろう。
ネットワークというと、インターネットの通信技術などを想定するひとが多いと思うが、ここでは、ノードとエッジ(点と線)に一般化したもの。
複雑なインターネットから、人間の交友関係や感染症の拡散、空港間のリンク、電力線などなど、適用範囲がめちゃめちゃ広い。生物(特に脳)は神経細胞のネットワークを持っているし、化学反応は分子間の相互作用であるから、生物、化学への応用も考えられている。
では、理論的な部分はどのようになっているかと調べてみると、すぐに「グラフ理論」という言葉を検索結果に見ることができるだろう。
グラフ理論は、元々18世紀ごろにオイラーによって考えだされたものだが、特に注目を集めるようになったのは、20世紀も後半になってから。これは、交通手段が発達したことや通信手段(とりわけインターネット)の発展が関連していると思う。
グラフ理論
ここでのグラフとは、x-y座標に表される二次曲線とかではなくて、前述の点と線で構成されたものである。特に、コンピュータのアルゴリズム面での発展が進んでいて、情報系の研究室で扱われることも多いと思う。ルータなどのノードとケーブルなど、通信に関連する部分はイメージしやすいが、データベースの検索最適化などもグラフ理論に含まれる。様々な構造のグラフを考えることで、最小の検索ルートを見つけ出すアルゴリズムの開発は特に盛んなのではないか。
道を歩いているときに、目的地への経路を考えたらそれはグラフ理論だし、いつか流行ったakinatorというアプリにもグラフ理論に基づいたアルゴリズムが使用されているだろう。
ネットワーク
初期のネットワークモデルでは、エルディシュのランダムネットワークが有名だ。これは、ノードを他のノードへランダムにつなぐというルールでグラフを構成していく。これによって、ひとつのノード当たりのリンク数が決まる。このデータを統計的な手法を用いて解析していくとリンク数は正規分布、ポアソン分布に従う。実は、世界には正規分布に従わない現象のほうが多いと言われているし、実際にそうだと思う。著者自身も、現実への応用はあまり考えていなかったらしい。だが、グラフ理論が構造化されたグラフを扱うのに対して、確率を用いてグラフの構造化にスポットライトを当てたことに大きな意義がある。
次に、スモールネットワークで有名なダンカンワッツのクラスターネットワーク。
これは、きっちりと作られた構造(例えば格子状モデル)に少しだけランダムなエッジを加えるというもの。正規グラフとの比較で特徴的なのは、"直径"である。正規グラフにおいては、遠くのノードへ到達するのにかなりのステップが必要な場合がある。さらにノードの数が増えるにつれて、その距離は大きくなっていく。
対して、ワッツのモデルでは小数のランダムなエッジが、直径を劇的に減らす役割を果たす。かっちりと作られた構造に、ほんの少しのエッジを加えることで世界は小さくなるのである。
では、ワッツの提唱したモデルは現実のネットワークをうまく説明できるのか。この疑問に対して、バラバシの研究グループはインターネットの世界を巡回し、大量のwebページのデータを取得するロボットを作成した。
予想に反し、ロボットは大量のリンクをもつ小数のノード、"ハブ"の存在を発見した。エルディシュのモデルもワッツのモデルもこのようなハブは存在し得ない。なぜならば、彼らのモデルはすべてのノードを平等に扱うからである。このことは、インターネット上のwebサイトに限らず、空港(ハブ空港という言葉はよく聞くだろう)や科学論文、感染症をもったホストなどなど、圧倒的な数のリンク(ノードとの接続)をもつような現象に見ることができる。
典型的なリンクの数を持たない。べき乗則に従っていたのである。
このような現象を説明しようと試みたのが、次のスケールフリーネットワークである。
バラバシらの研究グループは、ハブをもつようなネットワークの構造モデルとして、これまでのネットワークモデルがもっていた二つの仮定を考え直した。ひとつは、多数のノードが同時に存在するということ、これを修正するために、ノードを一つずつ追加していくような"成長"モデルを導入した。古いノードほど多くのノードをもつが、新しいノードはゼロからリンクを集めなければならない。これにより、たくさんのリンクをもつノードと小数のリンクしか持たないノードをはっきりと見て取ることができるようになった。しかし、度数分布をとると、そのようなノードの数は指数関数的な減少を示したのである。現実を表現するには、もっとたくさんのリンクを集める必要がある。そこで、ノードを対等に扱うという仮定に修正を加え、"優先度"を考えた。多くのリンクをもつノードほど、優先的にリンクを集めることができるのである。
