複雑ネットワーク

ウィキペディア周辺のWWWの構造

ヒトのタンパク質間相互作用の一部

BAモデルにより生成されたランダムネットワーク。各頂点の大きさが次数に対応している。Cytoscape上でRandomNetworksプラグインを使用し作成。

複雑ネットワーク（ふくざつネットワーク、complex networks）は、現実世界に存在する巨大で複雑なネットワークの性質について研究する学問である。

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

概要

現実世界に存在するネットワークは多様であり、巨大で複雑な構造を有しているが、一定の共通する性質を見出すことができる。それらの性質は「スケールフリー性」（次数分布のべき乗則）、「スモールワールド性」、「クラスター性」と呼ばれている。「スケールフリー性」（次数分布のべき乗則）とは、例えば、一部の人は非常にたくさんの知人を持っているが、大多数の人々の知人の数は少ないという性質である。「スモールワールド性」とは、例えば、「世間は狭い」と言われるように、一見赤の他人に見えても、実際は中間に少数の人を介するだけでつながっているという性質である。「クラスター性」とは、例えば、「自分と知人Aさんがいるときに、自分もAさんもどちらも知っている共通の知人Bさんのような人が1人もいない」という状況はまずありえないという性質である。

従来、こうした社会的ネットワークの性質は主に社会学の研究対象となってきたが、1998年に発表された「ワッツ・ストロガッツモデル」という数学モデルが注目を集めた。ワッツ・ストロガッツモデルは、現実世界のネットワークに近いような性質を持つネットワークモデルを、極めて単純なアルゴリズムで生成するものである。この研究に触発される形で、現実世界のネットワークが持つ性質への関心が高まり、インターネット、食物連鎖、さらには論文の被引用関係や言語の文法構造といったネットワークにおいても共通の性質が発見された。

現実世界の様々な現象を説明する新たなパラダイムとして、複雑ネットワークの研究は現在急速に進展しており、他の研究分野との相互影響も活発化しているテンプレート:Sfn。今後、複雑ネットワークの科学は、ネットワークの問題が関連する多数の分野において、普遍性と重要性を増していくものと予想される。

背景

グラフの例

グラフ理論は、18世紀にレオンハルト・オイラーが創始した学問で、この場合のグラフは頂点と辺の集合である。グラフ G は頂点（ノード、サイトともいう）の集合 V = {v₁, v₂, ..., v_n} と辺（枝、リンク、エッジ、ボンド、タイともいう）の集合 E = {e₁, e₂, ..., e_m} によって記述されるテンプレート:Sfn。頂点 i に繋がっている辺の本数をその頂点の次数 k_i というテンプレート:Sfn。右図の例では、頂点1の次数は2、頂点2の次数は3である。頂点と辺のパターンを変えることによって様々な特性を持つグラフが生成される。

1959年にポール・エルデシュとアルフレード・レーニは、グラフの一種であるテンプレート:仮リンクを作るテンプレート:仮リンクを考案した。エルデシュ＝レーニモデルは、各種の興味深い性質を有し、グラフの解析的な取り扱いを大きく進歩させた。だが、その後はグラフ理論の分野では目立った進展はあまり起きていなかった。

1960年代から70年代にかけて社会学で2つの動きがあった。第一は実験社会心理学者スタンレー・ミルグラムによる、いわゆるスモール・ワールド現象、日本語にすれば「世間は狭い」現象を実証しようという試みであるテンプレート:Sfn。ミルグラムは1967年に考案した実験において、アメリカ内陸部の住人に手紙を渡し、全く面識のない東海岸の受取人へ向けて、郵便ではなく知人（ファーストネームで呼び合うような親しい間柄）経由で転送するように依頼し、届くまでに何人の仲介者が必要かを調べたテンプレート:Sfn。結果は、平均して6人を仲介するだけで届くというものであったテンプレート:Sfn。この結果は現在では標語的に六次の隔たりと呼ばれるテンプレート:Sfn。

第二は、社会学者マーク・グラノヴェッターが発見した「弱い紐帯の重要性」と呼ばれる性質である。グラノヴェッターは1973年の論文において、人々が職を探す活動をする際に有効な紹介者となるのは、親友や家族などの身近な付き合いのある「強い紐帯」の間柄ではなく、ごくまれに接するような「弱い紐帯」の間柄であることを見出した。

以降、こうした社会的ネットワークの性質は主に社会学の研究対象となってきたが、1998年にブレイクスルーが訪れた。コーネル大学の博士課程の学生だったダンカン・ワッツと指導教官だったテンプレート:仮リンクは、多数のホタルの明滅やコオロギの鳴き声が同調する現象を究明する中で、スモール・ワールド現象を説明する「ワッツ・ストロガッツモデル」（WSモデル）という数学モデルを考案しテンプレート:Sfnテンプレート:Sfn、同様の性質が映画俳優の共演関係や、電力系統、線虫の神経細胞など、現実世界の様々なネットワークにも共通して存在することを発見した。研究成果は『ネイチャー』に発表されテンプレート:Sfn、これに触発された研究によって、インターネット、食物連鎖、さらには論文の被引用関係や言語の文法構造といったネットワークにおいても同様の性質が発見された。こうして、社会学、経済学、情報工学、生物学などの幅広い分野において「複雑ネットワーク」という新たなパラダイムが注目を集めることになった。

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

完全グラフ K₆

2次元格子

ランダムグラフ

ランダムグラフとスケールフリーグラフの次数分布の比較。ランダムグラフの次数分布は特定のピークを持つが、スケールフリーグラフの次数分布にはピークは存在しない

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

スケールフリー性

現実世界のネットワークが持つ第1の性質は「スケールフリー性」（次数分布のべき乗則）である。これは、一部の頂点が他のたくさんの頂点と辺で繋がっており、大きな次数を持っている一方で、その他の大部分はわずかな頂点としか繋がっておらず、次数は小さいという性質である。次数の大きな頂点は「ハブ」とも呼ばれる。

スケールフリー性は、社会学をはじめとするこれまでの研究により、現実世界のネットワークで幅広く観察されている。例えば、人々の持っている知人関係の数をみると、一部の人は非常にたくさんの知人を持っているが、大多数の人々の知人の数は限られている。WWWではごく少数の有名サイトが数百万単位のリンクを集めているが、大多数のサイトはわずかなリンク先からしかリンクされていない。生体内の相互作用でも、ごく一部のたんぱく質が多数のたんぱく質と反応する構造になっている。男女の性的関係でも、ごく一部の人は何百人という相手と関係するが、大多数の人々は限られた相手としか関係を持たない。

数学的には、スケールフリー性は頂点が次数 k を持つ確率 p(k) の確率分布の裾が $p(k)\propto k^{-\gamma }$ のべき乗則になると表現される。このような次数分布には、分布の形を特徴付ける大きさ（スケール）が存在しない。グラフがこのような次数分布にしたがうことを「スケールフリー」と呼ぶ。また、このような確率分布の指数$\gamma$が3以下の値を持つとき、分散は無限大に発散する。

スケールフリー性の出現を説明する適切な数理モデルの探求は、複雑ネットワークの理論において大きな問題である。例えば、n 個の頂点の間に全て辺を張った「完全グラフ」 K_n では全ての頂点の次数は n-1 であるからスケールフリー性を全く満たさない。「格子」状のグラフでも同様である。右の図のような2次元の三角格子を考えてみると、全ての頂点の次数は6であるから、やはりスケールフリー性を満たさない。 また、辺を生成確率 p で一様ランダムに張るランダムグラフは頂点数を n とすると頂点の次数が k となる確率は p(k) = _n-1C_k p^k(1-p)^n-1-k の二項分布となり、n→∞、p→0、np→λ の極限では p(k) = e^-λλ^k / k! のポアソン分布となる。ポアソン分布では全ての頂点の次数は平均値の周辺に分散 λ で分布しており、べき乗則の分布には程遠い。この問題に一定の解決策を示したのが後述のバラバーシ・アルベルトモデルである。

スモールワールド性

現実世界のネットワークが持つ第2の性質は「スモールワールド性」である。これは、任意の2つの頂点が、中間にわずかな数の頂点を介するだけで接続されるという性質である。上述のミルグラムの実験は現実世界のスモール・ワールド現象を最初に実証しようとした試みであるが、近年の研究ではネットワークのスモールワールド性が実際に測定されている。

例としてしばしば取り上げられるのは「エルデシュ数」である。先に登場した数学者ポール・エルデシュと論文を共著で執筆したことのある数学者のエルデシュ数を1、エルデシュ数 e の数学者と共著関係にある数学者のエルデシュ数を e+1 とする。世界中の数学者のエルデシュ数を調べてみると、大部分はエルデシュ数5から6程度で繋がっている。「ベーコン数」という遊びもある。アメリカの俳優ケヴィン・ベーコン（起点は誰でも良いのだが）と映画で共演したことのある俳優のベーコン数を1、ベーコン数 b の俳優と共演関係にある俳優のベーコン数を b+1 とする。世界中の俳優のベーコン数を調べてみると、大多数がベーコン数3から4の範囲に収まる。

• The Oracle of Bacon at Virginia - ベーコン数がわかるサイト

数学的には、スモールワールド性はグラフの「平均最短距離」（固有パス長もしくは直径ともいう） テンプレート:Mvar が頂点数 テンプレート:Mvar の大きさに比べて小さい値となることで表現される。無方向・重み無しのグラフにおいて、任意の頂点 テンプレート:Mvar から頂点 テンプレート:Mvar へ行くまでに通過しなければならない辺の最小の本数を「パス長」（距離ともいう）、パス長の中で最短のものを テンプレート:Mvar 間の「最短距離」 テンプレート:Mvar と呼ぶが、テンプレート:Mvar の平均値がそのグラフの平均最短距離である。グラフにおいて テンプレート:Mvar が増大したときに テンプレート:Mvar が高々 テンプレート:Math に比例する程度でゆるやかに増加するとき、そのグラフはスモールワールド性を満たすと定義される。

スモールワールド性を持つグラフを数学モデルで表現することができるだろうか。まず2次元格子を考えると、グラフの端から端まで行くためにはいくつもの頂点を経由せねばならない。すなわち テンプレート:Mvar はテンプレート:Math に比例する。テンプレート:Mvar が増大すると テンプレート:Mvar もかなり増大してしまうので、スモールワールド性を満たさない。一方、ランダムグラフでは頂点がランダムに繋がっているので、格子の場合と違って近道がありそうである。実際、枝の接続確率 テンプレート:Mvar のランダムグラフでは

$L=\frac{\log n}{\log (pn)}\propto \log n$

となる。この点では、ランダムグラフは現実世界のネットワークに近いといえる。

クラスター性

現実世界のネットワークが持つ第3の性質は「クラスター性」である。身の回りの知人関係のネットワークを見てみよう。「自分と知人Aさんがいるときに、自分もAさんもどちらも知っている共通の知人Bさんのような人が1人もいない」という状況は、出会い系サイトでも利用しない限りまずありえない。すなわち、現実世界のネットワークには、自分、Aさん、Bさんから構成される三角形のネットワークがたくさん含まれている。このような性質を、ワッツとストロガッツは「クラスター性」と名づけた。

数学的には、クラスター性はグラフの「クラスター係数」 C が十分大きな値を取ることで表現される。グラフにおいて任意の頂点 v_i と v_j、同じく v_i と v_k が共に辺で繋がっているような組み合わせの数を N₃、v_i、v_j、v_k が三角形で繋がっているような組み合わせの数を NΔ とする。このグラフのクラスター係数は C = 3NΔ / N₃と定義される。クラスター係数は現実世界の各種のネットワークにおいて計測されており、それらの値は0.1から0.7程度と報告されている。

クラスター性を持つグラフを数学モデルで表現することができるだろうか。まずランダムグラフでは、全ての辺はランダムに生成されるのであるから、都合よく三角形が形成される確率はきわめて低い。辺の生成確率 p の値にもよるが、p が小さければクラスター係数はほぼ0となるのでクラスター性を満たさない。一方、2次元の三角格子では、図でわかる通り三角形が多数含まれている。2次元の三角格子のクラスター係数は 6 / ₆C₂ = 0.4 となる。格子のクラスター係数は十分に大きく、この点では現実世界のネットワークに近いといえる。

複雑ネットワークのモデル

ワッツ・ストロガッツモデル

1次元格子

1次元格子からのワッツ・ストロガッツモデルの生成

バラバシ・アルバートモデル

ワッツ・ストロガッツモデルにより生成されたグラフ。100頂点

バラバシ・アルバートモデルの一例。1000頂点。igraphのba-modelにて生成、Cytoscape2.5にて可視化を行ったもの。頂点の色と大きさが次数に対応

このように、グラフ理論における既存の数学モデルは現実社会のネットワークを表現する上では一長一短といったところであったが、1998年にブレイクスルーが訪れた。ダンカン・ワッツとスティーヴン・ストロガッツが「ワッツ・ストロガッツモデル」（WSモデル）を発表したのである。

ワッツ・ストロガッツモデルでは次のアルゴリズムでグラフを生成する。

1. 全ての頂点を、近隣の a 個の頂点と格子（1次元格子）状に辺で繋ぐ。
2. それらの辺を確率 p でランダムに張り替える。

パラメータ p を0とおけば格子、1とおけばランダムグラフとなる。p を0.1前後とすると、格子とランダムグラフをあわせもったような性質のグラフが生成される。ワッツ・ストロガッツモデルでは、ショートカットが形成される効果によって平均最短距離はほぼ L ∝ log n となり、スモールワールド性を満たす。同時に格子の構造を残していることで、クラスター係数は格子に近い値となりクラスター性をも満たす。

もっともワッツ・ストロガッツモデルにも限界があり、次数分布は格子とポアソン分布の中間となるのでスケールフリー性は満たさない。しかし、現実世界のネットワークに近いような性質を持つグラフを極めて単純なアルゴリズムで生成できることが関心を呼んだ。この研究に触発される形で、現実世界のネットワークが持つ性質への関心が高まり、またこの研究をさらに発展させた研究が続々と発表されていった。

バラバーシ・アルベルト・モデル（バラバシ・アルバートモデル）

1999年、バラバーシ・アルベルト・ラースロー（アルバート＝ラズロ・バラバシ）とテンプレート:仮リンクはスケールフリー性を持つグラフの数学モデルを考案し、「バラバーシ・アルベルトモデル」（バラバシ・アルバートモデル；BAモデル）と呼ばれるテンプレート:Sfn。BAモデルでは次のようなアルゴリズムでグラフを生成するテンプレート:Sfn。やはり、極めて単純なアルゴリズムである。

1. m 個の頂点からなる完全グラフ K_mをスタートとする。
2. 新しい頂点を1個追加する。その頂点から、すでに存在している m 個の頂点に対して辺を張る。このとき、辺が張られる確率は、それぞれの頂点のその時点での次数 k に比例するものとする。
3. 2を、頂点が所定の数になるまで繰り返す。

BAモデルでは、既存の次数の大きな頂点に対して新しい辺が高い確率で加わってゆき、その頂点がハブへと成長してゆく（右の図では一番上にある頂点がハブに相当する）。このモデルでは頂点の次数分布は p(k) = 2m(m+1) / [k(k+1)(k+2)] ∝ k^-3 となり γ = -3 のスケールフリー性を満たす。モデルはランダムグラフと似たところもあるので、平均最短距離は L ∝ log n となりスモールワールド性をも満たす。

BAモデルの弱点は、クラスター係数が0に近い小さな値となり、クラスター性を満たさないことである。だがその後、これらの研究をさらに発展させる形で、単純なアルゴリズムでありながら「スケールフリー性」「スモールワールド性」「クラスター性」という現実世界のネットワークの3つの特徴全てを満たすようなモデルが発表されている。

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

スケールフリーグラフが持つ注目すべき特性として、ネットワーク障害など「ランダムな故障や攻撃」に対して頑強性が高いことがあげられる。スケールフリーなトポロジーを持つネットワークでは、全頂点のうちのランダムに5パーセントがダウンしたとしても、代替経路の存在によって頂点間の接続を維持でき、系全体の平均経路長（平均最短距離）はほとんど変化しないのである。同じ頂点数、同じ辺数でトポロジーが異なる他のネットワークではこのような特性は見られない。頑強性は次数分布のベキ指数と関係がありベキ指数が 2 < γ < 3 の場合は非常に頑健性が高くなることがモデルにより示されている。しかしながら、頑健性は両刃の剣である。見方を変えれば頑健性が高いということは感染症やコンピュータウイルスがネットワーク全体に広がり易いということでもあるからだ。実際、ランダムネットワークにおいては存在するウイルスあるいは流行の拡散に関する閾値(threshold)がスケールフリーネットワークでは存在しないため拡散しやすく退治するのも困難で時間がより長くかかることが判明している。

一方で、スケールフリーなネットワークは、特定の重要なハブをピンポイントで狙った攻撃に対しては脆弱であるという弱点も併せ持っている。次数の集中した上位5パーセントの頂点がダウンしたとすると、系全体の平均経路長は約2倍にまで増大してしまう。

同様の特性は自然界の食物連鎖のネットワークでも観察されている。食物連鎖のネットワークは生物種のランダムな絶滅に対しては頑強であるが、特定の重要な種が絶滅すると大きな影響を受けてしまう。こうした点を考慮することは生物多様性に関する議論においても重要であろう。

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

2008年現在、複雑ネットワークの研究は急速に進展しており、他の研究分野との相互影響も活発化している。そうした中で、「コミュニティ構造」などの現実世界のネットワークを分析するための新たな視点が提案され、「スケールフリー性」「スモールワールド性」「クラスター性」といった従来からの分析指標はもはや“古典的”な部類に属するものとなりつつある。

今後、複雑ネットワークの科学は、堅牢な通信ネットワークの構築、感染症の予防、口コミのマーケティングといった、ネットワークの問題が関連する多数の分野において、普遍性と重要性を増していくものと予想される。

分析用ツール

複雑ネットワークの解析では、可視化・統計解析などを行う際に計算機の力を借りることが不可欠である。現在では、様々な分析用ツールがフリーウェアとして利用できる。

• Pajek - Windows用ネットワーク解析ソフト。
• igraph - グラフ関連のアルゴリズムが実装されたパッケージ。Rでの実装もある。
• Cytoscape - マルチプラットフォーム対応のネットワーク可視化／解析ソフト。LGPLで配布されている。（日本語サイト）

参考文献

論文

• Albert, R. et al., "Error and attack tolerance of complex networks", Nature 406, pp. 378-382 (2000)
• Amaral, L.A.N. et al, "Classes of small-world networks", Proceedings of the National Academy of Sciences of the United States of America 97, No. 21, pp. 11149-11152 (2000)
• Barabási, A.-L., and Albert, R., "Emergence of scaling in random networks", Science 286, pp. 509-512 (1999)
• Dorogovtsev, S.N. et al., "Pseudofractal Scale-free Web", Physical Review E 65, 066122 (2002)
• Klemm, K., and Eguíluz, V.M., "Growing scale-free networks with small-world behavior", Physical Review E 65, 057102 (2002)
• Newman, M.E.J., and Girvan, M., "Finding and evaluating community structure in networks", Physical Review E 69, 026113 (2004)
• Solë, R.V., and Montoya, J.M., "Complexity and fragility in ecological networks", Proceedings of the Royal Society B: Biological Sciences 268, No. 1480, pp. 2039 - 2045 (2001)
• Watts, D.J., and Strogatz, S.H., "Collective dynamics of small-world networks", Nature 393, pp. 440-442 (1998)
• R. Nishida, M.Mori, and T. Iba, "Analyzing Co-Purchase Network of CDs in Japanease Online Store",Internal Workshop and Conference on Network Science 2008

レビュー論文

• Albert, R., and Barabási, A.-L., "Statistical mechanics of complex networks", Reviews of Modern Physics 74, pp. 47-97 (2002)
• Costa, L.F. et al., "Characterization of complex networks: A survey of measurements", arXiv.org
• Dorogovtsev, S.N., and Mendes, J.F.F., "Evolution of networks", Advances in Physics 51, No.4, pp. 1079-1187 (2002)
• Newman, M.E.J., "The structure and function of complex networks", SIAM Review 45, pp. 167-256 (2003)

学術書

• Ben-Naim, E., Frauenfelder, H., and Toroczkai, Z., Complex Networks, Springer-Verlag (2004), ISBN 3-540-22354-1
• Dorogovtsev, S.N., and Mendes, J.F.F., Evolution of Networks: from biological networks to the Internet and WWW, Oxford University Press (2003), ISBN 0-19-851590-1
• Pastor-Satorras, R., and Diaz-Guilera, A., Statistical Mechanics of Complex Networks, Springer (2003), ISBN 3-540-40372-8
• 増田直紀、今野紀雄、『複雑ネットワークの科学』、産業図書、2005年2月、ISBN 4-7828-5151-0
• テンプレート:Cite book ja-jp

一般向け書籍

• Barabási, A.-L., Linked：The New Science of Networks, Perseus Books Group (2002), ISBN 0-7382-0667-9
  • アルバート＝ラズロ・バラバシ、青木薫（訳）、『新ネットワーク思考―世界のしくみを読み解く』、NHK出版、2002年12月、ISBN 4-14-080743-1
• Buchanan, M., Nexus: Small Worlds and the Groundbreaking Science of Networks, W W Norton & Co Inc (2002), ISBN 0-393-04153-0
  • マーク・ブキャナン、阪本芳久（訳）、『複雑な世界、単純な法則―ネットワーク科学の最前線』、草思社、2005年2月、ISBN 4-7942-1385-9
• Strogatz, S.H., SYNC: The Emerging Science of Spontaneous Order, Hyperion Books (2003), ISBN 0-7868-6844-9
  • スティーヴン・ストロガッツ、蔵本由紀（訳）、長尾力（訳）、『SYNC』、早川書房、2005年3月、ISBN 4-15-208626-2
• Watts, D.J., Small Worlds: The Dynamics of Networks Between Order and Randomness, Princeton Univ Pr (1999), ISBN 0-691-00541-9
  • ダンカン・ワッツ、栗原聡（訳）、福田健介（訳）、佐藤進也（訳）、『スモールワールド―ネットワークの構造とダイナミクス』、東京電機大学出版局、2006年1月、ISBN 4-501-54070-2
• Watts, D.J., Six Degrees: The Science of a Connected Age, W W Norton & Co Inc (2003), ISBN 0-393-04142-5
  • ダンカン・ワッツ、辻竜平（訳）、友知政樹（訳）、『スモールワールド・ネットワーク―世界を知るための新科学的思考法』、阪急コミュニケーションズ、2004年10月、ISBN 4-484-04116-2
• 増田直紀、今野紀雄、『「複雑ネットワーク」とは何か―複雑な関係を読み解く新しいアプローチ』、講談社ブルーバックス、2006年2月、ISBN 4-06-257511-6
• テンプレート:Cite book ja-jp

関連項目

• 社会的ネットワーク
• 六次の隔たり
• パーコレーション理論