複雑ネットワーク

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
ウィキペディア周辺のWWWの構造
BAモデルにより生成されたランダムネットワーク。各ノードの大きさが次数に対応している。Cytoscape上でRandomNetworksプラグインを使用し作成。

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

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

概要[編集]

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

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

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

背景[編集]

グラフの例

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

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

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

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

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

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

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

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

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

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

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

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

スケールフリー性を持つグラフを数学モデルで表現することができるかは大きな問題である。例えば、n 個のノードの間に全てエッジを張った「完全グラフ」 Kn では全てのノードの次数は n-1 であるからスケールフリー性を全く満たさない。「格子」状のグラフでも同様である。右の図のような2次元の三角格子を考えてみると、全てのノードの次数は6であるから、やはりスケールフリー性を満たさない。 また、エッジを生成確率 p でランダムにはるランダムグラフはノード数を n とするとノードの次数が k となる確率は p(k) = n-1Ck pk(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の範囲に収まる。

数学的には、スモールワールド性はグラフの「平均最短距離」(固有パス長もしくは直径ともいう) L がノード数 n の大きさに比べて小さい値となることで表現される。無方向・重み無しのグラフにおいて、任意のノード vi からノード vj へ行くまでに通過しなければならないエッジの最小の本数を「パス長」(距離ともいう)、パス長の中で最短のものを ij 間の「最短距離」 dij と呼ぶが、dij の平均値がそのグラフの平均最短距離である。グラフにおいて 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 が十分大きな値を取ることで表現される。グラフにおいて任意のノード vivj、同じく vivk が共にエッジで繋がっているような組み合わせの数を N3vivjvk が三角形で繋がっているような組み合わせの数を NΔ とする。このグラフのクラスター係数は C = 3NΔ / N3と定義される。クラスター係数は現実世界の各種のネットワークにおいて計測されており、それらの値は0.1から0.7程度と報告されている[6]

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

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

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

1次元格子
1次元格子からのスモールワールドモデルの生成
バラバシ=アルバートモデル
Watts-Strogatzのスモール・ワールドモデルにより生成されたグラフ。100ノード
バラバシ=アルバートモデルの一例。1000ノード。igraphのba-modelにて生成、Cytoscape2.5にて可視化を行ったもの。ノードの色と大きさが次数に対応

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

分析用ツール[編集]

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

  • 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. ^ Reuven Cohen , Shlomo Havlin (Jul 2010), RobustComplex Networks: Structure,ness and Function, Cambridge University Press, pp. 120, ISBN 978-0-521-84156-6, http://www.cambridgejapan.org/academicproduct.html?isbn=9780521841566 
  9. ^ Albert, R. et al. (2000)
  10. ^ Solë, R.V., and Montoya, J.M. (2001)
  11. ^ Newman, M.E.J., and Girvan, M. (2004)
  12. ^ Costa, L.F. et al. (2005)

参考文献[編集]

論文[編集]

レビュー論文[編集]

学術書[編集]

  • 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
  • 今野紀雄、町田拓也、『図解入門よくわかる 複雑ネットワーク』、秀和システム、2008年11月、ISBN 4798021386

一般向け書籍[編集]

  • 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
  • 右田正夫、今野紀雄、『マンガでわかる複雑ネットワーク 巨大ネットワークがもつ法則を科学する』、 サイエンス・アイ新書(ソフトバンククリエイティブ)、2011年2月、ISBN 4-797-35641-3

関連項目[編集]