複雑ネットワーク

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

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

目次 1 概要 2 背景 3 現実世界のネットワークの性質 3.1 スケールフリー性 3.2 スモールワールド性 3.3 クラスター性 4 複雑ネットワークのモデル 4.1 スモールワールドモデル 4.2 バラバシ＝アルバートモデル 5 スケールフリーグラフの頑強性と脆弱性 6 複雑ネットワーク研究の現状と今後 7 分析用ツール 8 脚注 9 参考文献 9.1 論文 9.2 レビュー論文 9.3 学術書 9.4 一般向け書籍 10 関連項目

[編集] 概要

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

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

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

[編集] 背景

グラフ理論における「グラフ」はノードとエッジの集合である。グラフ G はノード（頂点ともいう）の集合 V = {v₁, v₂, ..., v_n} とエッジ（枝、弦、リンク、紐帯ともいう）の集合 E = {e₁, e₂, ..., e_m} によって記述される。ノード i に繋がっているエッジの本数をそのノードの次数 k_i という（右の図では、ノード1の次数は2、ノード2の次数は3である）。ノードとエッジのパターンを変えることによって様々な特性を持つグラフが生成される。

グラフ理論は18世紀にレオンハルト・オイラーが創始した学問であるが、20世紀に理論に重要な影響を与えたのはポール・エルデシュの業績であった。1959年にエルデシュとアルフレッド・レーニィが考案した「ランダムグラフ」（エルデシュ＝レーニィモデル、ERモデル）は、各種の興味深い性質を有し、グラフの解析的な取り扱いを大きく進歩させた。だが、その後はグラフ理論の分野では目立った進展はあまり起きていなかった。

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

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

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

[編集] 現実世界のネットワークの性質

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

[編集] スケールフリー性

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

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

数学的には、スケールフリー性はノードが次数 k を持つ確率 p(k) の確率分布が p(k) ∝ k^-γ のべき乗則になると表現される^[4]。このような次数分布では、分布の偏りを特徴付ける平均的な尺度（スケール）といったものが存在しない。グラフがこのような性質を持つことを「スケールフリー」と呼ぶ。また、このような確率分布のとき分散 V は無限大となる。

スケールフリー性を持つグラフを数学モデルで表現することができるだろうか。まず、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 - ベーコン数がわかるサイト

数学的には、スモールワールド性はグラフの「平均最短距離」（固有パス長もしくは直径ともいう） L がノード数 n の大きさに比べて小さい値となることで表現される。無方向・重み無しのグラフにおいて、任意のノード v_i からノード v_j へ行くまでに通過しなければならないエッジの最小の本数を「パス長」（距離ともいう）、パス長の中で最短のものを ij 間の「最短距離」 d_ij と呼ぶが、d_ij の平均値がそのグラフの平均最短距離である。グラフにおいて n が増大したときに L が高々 log(n) に比例する程度でゆるやかに増加するとき、そのグラフはスモールワールド性を満たすと定義される^[5]。

スモールワールド性を持つグラフを数学モデルで表現することができるだろうか。まず2次元格子を考えると、グラフの端から端まで行くためにはいくつものノードを経由せねばならない。すなわち L は√n に比例する。n が増大すると L もかなり増大してしまうので、スモールワールド性を満たさない。一方、ランダムグラフではノードがランダムに繋がっているので、格子の場合と違って近道がありそうである。実際、ランダムグラフでは L = log(n) / log(pn) ∝ 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程度と報告されている^[6]。

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

[編集] 複雑ネットワークのモデル

[編集] スモールワールドモデル

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

スモールワールドモデルでは次のようなアルゴリズムでグラフを生成する。

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

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

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

[編集] バラバシ＝アルバートモデル

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

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

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

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

[編集] スケールフリーグラフの頑強性と脆弱性

スケールフリーグラフが持つ注目すべき特性として、ネットワーク障害に対する頑強性が高いことがあげられる。スケールフリーなトポロジーを持つネットワークでは、全ノードのうちの5パーセントがダウンしたとしても、代替経路の存在によってノード間の接続を維持でき、系全体の平均経路長（平均最短距離）はほとんど変化しないのである。同じノード数、同じエッジ数でトポロジーが異なる他のネットワークではこのような特性は見られない。

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

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

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

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

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

[編集] 分析用ツール

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

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

[編集] 脚注

1. ^ Watts, D.J., and Strogatz, S.H. (1998)
2. ^ F Liljeros et al. "The web of human sexual contacts". Nature, 411, pp.907-908(2001) オンライン・ペーパー
3. ^ A. Schneeberger et al. "Scale-Free Networks and Sexually Transmitted Diseases" Sexually Transmitted Diseases, 31(6), pp.380-387(2004) オンライン・ペーパー
4. ^ Amaral, L.A.N. et al (2000) によれば、現実世界の全てのネットワークが完全なべき乗則の次数分布となるわけではない。エッジが集中することで混雑などのコストが発生する場合は集中は頭打ちとなる。典型例は航空路線のネットワークである。
5. ^ 「スモールワールド性」という用語の定義に関しては曖昧さがある。単にグラフの平均最短距離が小さい状態を指す場合もあれば、小さな平均最短距離と大きなクラスター係数とを共に満たす状態を指す場合もある。ランダムグラフは、前者の定義に従えばスモールワールドであり、後者に従えばスモールワールドではない。
6. ^ Albert, R., and Barabási, A.-L. (2002)
7. ^ 例えば Dorogovtsev, S.N. et al. (2002) や Klemm, K., and Eguíluz, V.M. (2002)
8. ^ Albert, R. et al. (2000)
9. ^ Solë, R.V., and Montoya, J.M. (2001)
10. ^ Newman, M.E.J., and Girvan, M. (2004)
11. ^ Costa, L.F. et al. (2005)

[編集] 参考文献

[編集] 論文

• 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)

[編集] レビュー論文

• 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 3540223541
• Dorogovtsev, S.N., and Mendes, J.F.F., Evolution of Networks: from biological networks to the Internet and WWW, Oxford University Press (2003), ISBN 0198515901
• Pastor-Satorras, R., and Diaz-Guilera, A., Statistical Mechanics of Complex Networks, Springer (2003), ISBN 3540403728
• 増田直紀、今野紀雄、『複雑ネットワークの科学』、産業図書、2005年2月、ISBN 4782851510

[編集] 一般向け書籍

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

[編集] 関連項目

• 社会的ネットワーク
• 六次の隔たり