複雑ネットワーク

複雑ネットワーク（ふくざつネットワーク、complex networks）は、現実世界に存在する巨大で複雑なネットワークの性質について研究する学問である。
複雑ネットワークは、1998年に「ワッツ・ストロガッツモデル」という数学モデルが発表されたことを契機に、現実世界の様々な現象を説明する新たなパラダイムとして注目を集めている。多数の因子が相互に影響しあうことでシステム全体の性質が決まるという点において複雑系の一分野でもある。

概要

現実世界に存在するネットワークは多様であり、巨大で複雑な構造を有しているが、一定の共通する性質を見出すことができる。それらの性質は「スケールフリー性」（次数分布のべき乗則）、「スモールワールド性」、「クラスター性」と呼ばれている。「スケールフリー性」（次数分布のべき乗則）とは、例えば、一部の人は非常にたくさんの知人を持っているが、大多数の人々の知人の数は少ないという性質である。「スモールワールド性」とは、例えば、「世間は狭い」と言われるように、一見赤の他人に見えても、実際は中間に少数の人を介するだけでつながっているという性質である。「クラスター性」とは、例えば、「自分と知人Aさんがいるときに、自分もAさんもどちらも知っている共通の知人Bさんのような人が1人もいない」という状況はまずありえないという性質である。
従来、こうした社会的ネットワークの性質は主に社会学の研究対象となってきたが、1998年に発表された「ワッツ・ストロガッツモデル」という数学モデルが注目を集めた。ワッツ・ストロガッツモデルは、現実世界のネットワークに近いような性質を持つネットワークモデルを、極めて単純なアルゴリズムで生成するものである。この研究に触発される形で、現実世界のネットワークが持つ性質への関心が高まり、インターネット、食物連鎖、さらには論文の被引用関係や言語の文法構造といったネットワークにおいても共通の性質が発見された。
現実世界の様々な現象を説明する新たなパラダイムとして、複雑ネットワークの研究は現在急速に進展しており、他の研究分野との相互影響も活発化している。今後、複雑ネットワークの科学は、ネットワークの問題が関連する多数の分野において、普遍性と重要性を増していくものと予想される。

背景

グラフ理論は、18世紀にレオンハルト・オイラーが創始した学問で、この場合のグラフは頂点と辺の集合である。グラフ G は頂点（ノード、サイトともいう）の集合 V = {v₁, v₂, ..., vₙ} と辺（枝、リンク、ボンドともいう）の集合 E = {e₁, e₂, ..., eₘ} によって記述される。頂点 i に繋がっている辺の本数をその頂点の次数 kᵢ という。右図の例では、頂点1の次数は2、頂点2の次数は3である。頂点と辺のパターンを変えることによって様々な特性を持つグラフが生成される。
1959年にポール・エルデシュとアルフレッド・レーニィは、グラフの一種であるランダムグラフを作るエルデシュ＝レーニィモデルを考案した。エルデシュ＝レーニィモデルは、各種の興味深い性質を有し、グラフの解析的な取り扱いを大きく進歩させた。だが、その後はグラフ理論の分野では目立った進展はあまり起きていなかった。
1960年代から70年代にかけて社会学で2つの動きがあった。第1は実験社会心理学者スタンレー・ミルグラムによる、いわゆるスモール・ワールド現象、日本語にすれば「世間は狭い」現象を実証しようという試みである。ミルグラムは1967年に考案した実験において、アメリカ内陸部の住人に手紙を渡し、全く面識のない東海岸の受取人へ向けて、郵便ではなく知人（ファーストネームで呼び合うような親しい間柄）経由で転送するように依頼し、届くまでに何人の仲介者が必要かを調べた。結果は、平均して6人を仲介するだけで届くというものであった。この結果は現在では標語的に六次の隔たりと呼ばれる。
第2は、社会学者マーク・グラノヴェッターが発見した「弱い紐帯の重要性」と呼ばれる性質である。グラノヴェッターは1973年の論文において、人々が職を探す活動をする際に有効な紹介者となるのは、親友や家族などの身近な付き合いのある「強い紐帯」の間柄ではなく、ごくまれに接するような「弱い紐帯」の間柄であることを見出した。
以降、こうした社会的ネットワークの性質は主に社会学の研究対象となってきたが、1998年にブレイクスルーが訪れた。コーネル大学の博士課程の学生だったダンカン・ワッツと指導教官だったスティーヴン・ストロガッツは、多数のホタルの明滅やコオロギの鳴き声が同調する現象を究明する中で、「ワッツ・ストロガッツモデル」（WSモデル）という数学モデルを考案し、同様の性質が映画俳優の共演関係や、電力系統、線虫の神経細胞など、現実世界の様々なネットワークにも共通して存在することを発見した。研究成果は『ネイチャー』に発表され、これに触発された研究によって、インターネット、食物連鎖、さらには論文の被引用関係や言語の文法構造といったネットワークにおいても同様の性質が発見された。こうして、社会学、経済学、情報工学、生物学などの幅広い分野において「複雑ネットワーク」という新たなパラダイムが注目を集めることになった。

現実世界のネットワークの性質

現実世界に存在するネットワークは多様であり、巨大で複雑な構造を有しているが、一定の共通する性質を見出すことができる。それらの性質は「スケールフリー性」（次数分布のべき乗則）、「スモールワールド性」、「クラスター性」と呼ばれている。

スケールフリー性

現実世界のネットワークが持つ第1の性質は「スケールフリー性」（次数分布のべき乗則）である。これは、一部の頂点が他のたくさんの頂点と辺で繋がっており、大きな次数を持っている一方で、その他の大部分はわずかな頂点としか繋がっておらず、次数は小さいという性質である。次数の大きな頂点は「ハブ」とも呼ばれる。
スケールフリー性は、社会学をはじめとするこれまでの研究により、現実世界のネットワークで幅広く観察されている。例えば、人々の持っている知人関係の数をみると、一部の人は非常にたくさんの知人を持っているが、大多数の人々の知人の数は限られている。WWWではごく少数の有名サイトが数百万単位のリンクを集めているが、大多数のサイトはわずかなリンク先からしかリンクされていない。生体内の相互作用でも、ごく一部のたんぱく質が多数のたんぱく質と反応する構造になっている。男女の性的関係でも、ごく一部の人は何百人という相手と関係するが、大多数の人々は限られた相手としか関係を持たない。
数学的には、スケールフリー性は頂点が次数 k を持つ確率 p(k) の確率分布が p(k) ∝ k-γ のべき乗則になると表現される。このような次数分布では、分布の偏りを特徴付ける平均的な尺度（スケール）といったものが存在しない。グラフがこのような性質を持つことを「スケールフリー」と呼ぶ。また、このような確率分布のとき分散 V は無限大となる。
スケールフリー性を持つグラフを数学モデルで表現することができるかは大きな問題である。例えば、n 個の頂点の間に全て辺を張った「完全グラフ」 Kₙ では全ての頂点の次数は n-1 であるからスケールフリー性を全く満たさない。「格子」状のグラフでも同様である。右の図のような2次元の三角格子を考えてみると、全ての頂点の次数は6であるから、やはりスケールフリー性を満たさない。 また、辺を生成確率 p でランダムにはるランダムグラフは頂点数を n とすると頂点の次数が k となる確率は p(k) = ₙ₋₁Cₖ pᵏ(1-p)ⁿ⁻¹⁻ᵏ の二項分布となり、n→∞、p→0、np→λ の極限では p(k) = e-λλᵏ / k! のポアソン分布となる。ポアソン分布では全ての頂点の次数は平均値の周辺に分散 λ で分布しており、べき乗則の分布には程遠い。

クラスター性

現実世界のネットワークが持つ第3の性質は「クラスター性」である。身の回りの知人関係のネットワークを見てみよう。「自分と知人Aさんがいるときに、自分もAさんもどちらも知っている共通の知人Bさんのような人が1人もいない」という状況は、出会い系サイトでも利用しない限りまずありえない。すなわち、現実世界のネットワークには、自分、Aさん、Bさんから構成される三角形のネットワークがたくさん含まれている。このような性質を、ワッツとストロガッツは「クラスター性」と名づけた。
数学的には、クラスター性はグラフの「クラスター係数」 C が十分大きな値を取ることで表現される。グラフにおいて任意の頂点 vᵢ と vⱼ、同じく vᵢ と vₖ が共に辺で繋がっているような組み合わせの数を N₃、vᵢ、vⱼ、vₖ が三角形で繋がっているような組み合わせの数を NΔ とする。このグラフのクラスター係数は C = 3NΔ / N₃と定義される。クラスター係数は現実世界の各種のネットワークにおいて計測されており、それらの値は0.1から0.7程度と報告されている。
クラスター性を持つグラフを数学モデルで表現することができるだろうか。まずランダムグラフでは、全ての辺はランダムに生成されるのであるから、都合よく三角形が形成される確率はきわめて低い。辺の生成確率 p の値にもよるが、p が小さければクラスター係数はほぼ0となるのでクラスター性を満たさない。一方、2次元の三角格子では、図でわかる通り三角形が多数含まれている。2次元の三角格子のクラスター係数は 6 / ₆C₂ = 0.4 となる。格子のクラスター係数は十分に大きく、この点では現実世界のネットワークに近いといえる。

スケールフリーグラフの頑強性と脆弱性

スケールフリーグラフが持つ注目すべき特性として、ネットワーク障害など「ランダムな故障や攻撃」に対して頑強性が高いことがあげられる。スケールフリーなトポロジーを持つネットワークでは、全頂点のうちのランダムに5パーセントがダウンしたとしても、代替経路の存在によって頂点間の接続を維持でき、系全体の平均経路長（平均最短距離）はほとんど変化しないのである。同じ頂点数、同じ辺数でトポロジーが異なる他のネットワークではこのような特性は見られない。頑強性は次数分布のベキ指数と関係がありベキ指数が 2 < γ < 3 の場合は非常に頑健性が高くなることがモデルにより示されている。しかしながら、頑健性は両刃の剣である。見方を変えれば頑健性が高いということは感染症やコンピュータウイルスがネットワーク全体に広がり易いということでもあるからだ。実際、ランダムネットワークにおいては存在するウイルスあるいは流行の拡散に関する閾値(threshold)がスケールフリーネットワークでは存在しないため拡散しやすく退治するのも困難で時間がより長くかかることが判明している。
一方で、スケールフリーなネットワークは、特定の重要なハブをピンポイントで狙った攻撃に対しては脆弱であるという弱点も併せ持っている。次数の集中した上位5パーセントの頂点がダウンしたとすると、系全体の平均経路長は約2倍にまで増大してしまう。
同様の特性は自然界の食物連鎖のネットワークでも観察されている。食物連鎖のネットワークは生物種のランダムな絶滅に対しては頑強であるが、特定の重要な種が絶滅すると大きな影響を受けてしまう。こうした点を考慮することは生物多様性に関する議論においても重要であろう。

複雑ネットワーク研究の現状と今後

2008年現在、複雑ネットワークの研究は急速に進展しており、他の研究分野との相互影響も活発化している。そうした中で、「コミュニティ構造」などの現実世界のネットワークを分析するための新たな視点が提案され、「スケールフリー性」「スモールワールド性」「クラスター性」といった従来からの分析指標はもはや“古典的”な部類に属するものとなりつつある。
今後、複雑ネットワークの科学は、堅牢な通信ネットワークの構築、感染症の予防、口コミのマーケティングといった、ネットワークの問題が関連する多数の分野において、普遍性と重要性を増していくものと予想される。