複雑ネットワークのソースを表示

[[ファイル:WorldWideWebAroundWikipedia.png|thumb|right|350px|ウィキペディア周辺のWWWの構造]]
[[ファイル:Human_interactome.jpg|thumb|right|350px|ヒトの[[タンパク質間相互作用]]の一部]]
[[ファイル:Ba_model_1000nodes.png|thumb|right|350px|BAモデルにより生成されたランダムネットワーク。各頂点の大きさが次数に対応している。[http://www.cytoscape.org/ Cytoscape]上でRandomNetworksプラグインを使用し作成。]]

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

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

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

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

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

== 背景 ==
[[ファイル:6n-graf.svg|thumb|right|250px|グラフの例]]
[[グラフ理論]]は、18世紀に[[レオンハルト・オイラー]]が創始した学問で、この場合のグラフは頂点と辺の集合である。グラフ ''G'' は'''[[頂点]]'''（ノード、サイトともいう）の集合 ''V'' = {''v''<sub>1</sub>, ''v''<sub>2</sub>, ..., ''v''<sub>n</sub>} と'''[[辺]]'''（枝、リンク、エッジ、ボンド、タイともいう）の集合 ''E'' = {''e''<sub>1</sub>, ''e''<sub>2</sub>, ..., ''e''<sub>m</sub>} によって記述される{{Sfn|右田・今野|2011|p=26}}。頂点 ''i'' に繋がっている辺の本数をその頂点の'''[[次数 (グラフ理論)|次数]]''' ''k''<sub>i</sub> という{{Sfn|今野・町田|2008|p=46}}。右図の例では、頂点1の次数は2、頂点2の次数は3である。頂点と辺のパターンを変えることによって様々な特性を持つグラフが生成される。

[[1959年]]に[[ポール・エルデシュ]]と[[レーニ・アルフレード|アルフレード・レーニ]]は、グラフの一種である{{仮リンク|ランダムグラフ|en|Random graph}}を作る{{仮リンク|エルデシュ＝レーニモデル|en|Erdős–Rényi model}}を考案した。エルデシュ＝レーニモデルは、各種の興味深い性質を有し、グラフの解析的な取り扱いを大きく進歩させた。だが、その後はグラフ理論の分野では目立った進展はあまり起きていなかった。

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

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

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

== 現実世界のネットワークの性質 ==
[[ファイル:Complex network K6 complete graph.png|thumb|right|220px|完全グラフ K<sub>6</sub>]]
[[ファイル:Complex network trigonal lattice.png|thumb|right|220px|2次元格子]]
[[ファイル:Complex network n25 ER model.png|thumb|right|220px|ランダムグラフ]]
[[ファイル:Complex network degree distribution of random and scale-free.png|thumb|right|220px|ランダムグラフとスケールフリーグラフの次数分布の比較。ランダムグラフの次数分布は特定のピークを持つが、スケールフリーグラフの次数分布にはピークは存在しない]]

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

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

スケールフリー性は、社会学をはじめとするこれまでの研究により、現実世界のネットワークで幅広く観察されている。例えば、人々の持っている知人関係の数をみると、一部の人は非常にたくさんの知人を持っているが、大多数の人々の知人の数は限られている。[[World Wide Web|WWW]]ではごく少数の有名サイトが数百万単位のリンクを集めているが、大多数のサイトはわずかなリンク先からしかリンクされていない。生体内の相互作用でも、ごく一部のたんぱく質が多数のたんぱく質と反応する構造になっている。男女の性的関係でも、ごく一部の人は何百人という相手と関係するが、大多数の人々は限られた相手としか関係を持たない<ref>F Liljeros et al. "The web of human sexual contacts". ''Nature'', 411, pp.907-908(2001) [https://arxiv.org/pdf/cond-mat/0106507 オンライン・ペーパー]</ref><ref>A. Schneeberger et al. "Scale-Free Networks and Sexually Transmitted Diseases" ''Sexually Transmitted Diseases'', 31(6), pp.380-387(2004) [http://www.stdjournal.com/pt/re/std/fulltext.00007435-200406000-00012.htm;jsessionid=LkpQBnkJPhz2P48TGK1vQjs2DL6JLJdLHWTczhFhqrL35dMLxzpy!-1696092046!181195628!8091!-1 オンライン・ペーパー]</ref>。

数学的には、スケールフリー性は頂点が次数 ''k'' を持つ確率 ''p''(''k'') の[[確率分布]]の裾が <math>p(k) \propto k^{-\gamma}</math> のべき乗則になると表現される<ref group="注釈">Amaral, L.A.N. et al (2000) によれば、現実世界の全てのネットワークが完全なべき乗則の次数分布となるわけではない。辺が集中することで混雑などのコストが発生する場合は集中は頭打ちとなる。典型例は航空路線のネットワークである。</ref>。このような次数分布には、分布の形を特徴付ける大きさ（スケール）が存在しない。グラフがこのような次数分布にしたがうことを「スケールフリー」と呼ぶ。また、このような確率分布の指数<math>\gamma</math>が3以下の値を持つとき、[[分散 (確率論)|分散]]は無限大に発散する。

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

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

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

* [http://www.cs.virginia.edu/oracle/ The Oracle of Bacon at Virginia] - ベーコン数がわかるサイト

数学的には、スモールワールド性はグラフの「平均最短距離」（固有パス長もしくは直径ともいう） {{mvar|L}} が頂点数 {{mvar|n}} の大きさに比べて小さい値となることで表現される。無方向・重み無しのグラフにおいて、任意の頂点 {{mvar|v{{sub|i}}}} から頂点 {{mvar|v{{sub|j}}}} へ行くまでに通過しなければならない辺の最小の本数を「パス長」（距離ともいう）、パス長の中で最短のものを {{mvar|ij}} 間の「最短距離」 {{mvar|d{{sub|ij}}}} と呼ぶが、{{mvar|d{{sub|ij}}}} の平均値がそのグラフの平均最短距離である。グラフにおいて {{mvar|n}} が増大したときに {{mvar|L}} が高々 {{math|log(''n'')}} に比例する程度でゆるやかに増加するとき、そのグラフはスモールワールド性を満たすと定義される<ref group="注釈">「スモールワールド性」という用語の定義に関しては曖昧さがある。単にグラフの平均最短距離が小さい状態を指す場合もあれば、小さな平均最短距離と大きなクラスター係数とを共に満たす状態を指す場合もある。ランダムグラフは、前者の定義に従えばスモールワールドであり、後者に従えばスモールワールドではない。</ref>。

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

<math>
L = \frac{\log n}{\log (pn)} \propto \log n
</math>

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

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

数学的には、クラスター性はグラフの「クラスター係数」 ''C'' が十分大きな値を取ることで表現される。グラフにおいて任意の頂点 ''v''<sub>''i''</sub> と ''v''<sub>''j''</sub>、同じく ''v''<sub>''i''</sub> と ''v''<sub>''k''</sub> が共に辺で繋がっているような[[組合せ (数学)|組み合わせ]]の数を ''N''<sub>3</sub>、''v''<sub>''i''</sub>、''v''<sub>''j''</sub>、''v''<sub>''k''</sub> が三角形で繋がっているような組み合わせの数を ''N''Δ とする。このグラフのクラスター係数は ''C'' = 3''N''Δ / ''N''<sub>3</sub>と定義される。クラスター係数は現実世界の各種のネットワークにおいて計測されており、それらの値は0.1から0.7程度と報告されている<ref>Albert, R., and Barabási, A.-L. (2002)</ref>。

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

== 複雑ネットワークのモデル ==
=== ワッツ・ストロガッツモデル ===
[[ファイル:Complex network n25 1-d lattice.png|thumb|right|220px|1次元格子]]
[[ファイル:Complex network n25 WS model.png|thumb|right|220px|1次元格子からのワッツ・ストロガッツモデルの生成]]
[[ファイル:Complex network n25 BA model.png|thumb|right|220px|バラバシ・アルバートモデル]]
[[ファイル:Watts-Strogatz_small-world_model_100nodes.png|thumb|right|220px|ワッツ・ストロガッツモデルにより生成されたグラフ。100頂点]]
[[ファイル:Barabasi_Albert_1000nodes.png|thumb|right|220px|バラバシ・アルバートモデルの一例。1000頂点。[http://cneurocvs.rmki.kfki.hu/igraph/ igraph]のba-modelにて生成、[http://www.cytoscape.org Cytoscape2.5]にて可視化を行ったもの。頂点の色と大きさが次数に対応]]

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

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

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

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

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

=== バラバーシ・アルベルト・モデル（バラバシ・アルバートモデル） ===
1999年、[[バラバーシ・アルベルト・ラースロー]]（アルバート＝ラズロ・バラバシ）<ref group="注釈">{{lang|hu|Barabási Albert László}} {{IPA|ˈbɒrabɑ̈ːʃi ˌɒrbɛrtˌlɑ̈ːsloː}}。バラバーシが姓、アルベルトとラースローが名（男性名）。[[セーケイ人]]（[[ハンガリー人]]の一派）。ルーマニア領トランシルヴァニアの[[:hu:Székelyföld|セーケイ地方]]の[[ハルギタ県]][[:hu:Karcfalva|カルツファルヴァ村またはカルツ村]]（ルーマニア語名 [[:ro:Cârța|クルツァ村]]）生まれ。国籍は[[ルーマニア]]と[[ハンガリー]]と[[米国]]の三重国籍。</ref>と{{仮リンク|アルベルト・レーカ|en|Réka Albert}}<ref group="注釈">{{lang|hu|Albert Réka}} {{IPA|ˈɒrbɛrt ˌre̝ːkɒ}}。アルベルトが姓、レーカが名（女性名）。[[セーケイ人]]（[[ハンガリー人]]の一派）。ルーマニア領トランシルヴァニアの[[:hu:Székelyföld|セーケイ地方]]の[[ムレシュ県|マロシュ県]][[:hu: Szászrégen |サースレーゲン市]]（ルーマニア語名 [[:ro:Reghin|レギン市]]）生まれ。国籍は[[ルーマニア]]と[[ハンガリー]]と[[米国]]の三重国籍。</ref>はスケールフリー性を持つグラフの数学モデルを考案し、「バラバーシ・アルベルトモデル」（バラバシ・アルバートモデル；BAモデル）と呼ばれる{{Sfn|右田・今野|2011|p=162}}。BAモデルでは次のようなアルゴリズムでグラフを生成する{{Sfn|右田・今野|2011|p=162}}。やはり、極めて単純なアルゴリズムである。

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

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

BAモデルの弱点は、クラスター係数が0に近い小さな値となり、クラスター性を満たさないことである。だがその後、これらの研究をさらに発展させる形で、単純なアルゴリズムでありながら「スケールフリー性」「スモールワールド性」「クラスター性」という現実世界のネットワークの3つの特徴全てを満たすようなモデルが発表されている<ref>例えば Dorogovtsev, S.N. et al. (2002) や Klemm, K., and Eguíluz, V.M. (2002)</ref>。

== スケールフリーグラフの頑強性と脆弱性 ==
スケールフリーグラフが持つ注目すべき特性として、ネットワーク障害など「ランダムな故障や攻撃」に対して頑強性が高いことがあげられる。スケールフリーな[[ネットワーク構成|トポロジー]]を持つネットワークでは、全頂点のうちのランダムに5パーセントがダウンしたとしても、代替経路の存在によって頂点間の接続を維持でき、系全体の平均経路長（平均最短距離）はほとんど変化しないのである。同じ頂点数、同じ辺数でトポロジーが異なる他のネットワークではこのような特性は見られない。頑強性は次数分布のベキ指数と関係がありベキ指数が 2 < γ < 3 の場合は非常に頑健性が高くなることがモデルにより示されている。<ref>{{Cite | author = Reuven Cohen , Shlomo Havlin
  | title =  RobustComplex Networks: Structure,ness and Function
  | publisher = Cambridge University Press
  | series =
  | volume =
  | edition =
  | date = Jul 2010
  | pages = 120
  | url = http://www.cambridgejapan.org/academicproduct.html?isbn=9780521841566
  | doi =
  | isbn = 978-0-521-84156-6
  }}</ref>しかしながら、頑健性は両刃の剣である。見方を変えれば頑健性が高いということは感染症やコンピュータウイルスがネットワーク全体に広がり易いということでもあるからだ。実際、ランダムネットワークにおいては存在するウイルスあるいは流行の拡散に関する閾値(threshold)がスケールフリーネットワークでは存在しないため拡散しやすく退治するのも困難で時間がより長くかかることが判明している。

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

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

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

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

== 分析用ツール ==
複雑ネットワークの解析では、可視化・統計解析などを行う際に計算機の力を借りることが不可欠である。現在では、様々な分析用ツールが[[フリーウェア]]として利用できる。
* [http://vlado.fmf.uni-lj.si/pub/networks/pajek/ Pajek] - Windows用ネットワーク解析ソフト。
* [http://cneurocvs.rmki.kfki.hu/igraph/ igraph] - グラフ関連のアルゴリズムが実装されたパッケージ。Rでの実装もある。
* [http://www.cytoscape.org/ Cytoscape] - マルチプラットフォーム対応のネットワーク可視化／解析ソフト。LGPLで配布されている。（[https://cytoscape.wordpress.com/ 日本語サイト]）

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
<references />

== 参考文献 ==
=== 論文 ===
* Albert, R. et al., "[https://arxiv.org/abs/cond-mat/0008064 Error and attack tolerance of complex networks]", ''Nature'' '''406''', pp. 378-382 (2000)
* Amaral, L.A.N. et al, "[http://www.pnas.org/cgi/content/full/97/21/11149 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., "[https://arxiv.org/abs/cond-mat/9910332 Emergence of scaling in random networks]", ''Science'' '''286''', pp. 509-512 (1999)
* Dorogovtsev, S.N. et al., "[https://arxiv.org/abs/cond-mat/0112143 Pseudofractal Scale-free Web]", ''Physical Review E'' '''65''', 066122 (2002)
* Klemm, K., and Eguíluz, V.M., "[http://prola.aps.org/abstract/PRE/v65/i5/e057102 Growing scale-free networks with small-world behavior]", ''Physical Review E'' '''65''', 057102 (2002)
* Newman, M.E.J., and Girvan, M., "[http://link.aps.org/abstract/PRE/v69/e026113 Finding and evaluating community structure in networks]", ''Physical Review E'' '''69''', 026113 (2004)
* Solë, R.V., and Montoya, J.M., "[https://arxiv.org/abs/cond-mat/0011196 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., "[http://www.nature.com/nature/journal/v393/n6684/abs/393440a0_fs.html Collective dynamics of small-world networks]", ''Nature'' '''393''', pp. 440-442 (1998)
* R. Nishida, M.Mori, and T. Iba, "[https://web.sfc.keio.ac.jp/~iba/papers/2008NetSci08-cd.pdf 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., "[http://prola.aps.org/abstract/RMP/v74/i1/p47_1 Statistical mechanics of complex networks]", ''Reviews of Modern Physics'' '''74''', pp. 47-97 (2002)
* Costa, L.F. et al., "[https://arxiv.org/abs/cond-mat/0505185 Characterization of complex networks: A survey of measurements]", [https://arxiv.org/ arXiv.org]
* Dorogovtsev, S.N., and Mendes, J.F.F., "[https://arxiv.org/abs/cond-mat/0106144 Evolution of networks]", ''Advances in Physics'' '''51''', No.4, pp. 1079-1187 (2002)
* Newman, M.E.J., "[https://arxiv.org/abs/cond-mat/0303516 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 |author=今野紀雄・町田拓也 |title=よくわかる複雑ネットワーク |series=図解入門
|publisher=秀和システム |edition=第1版 |year=2008 |isbn=978-4-7980-2138-6 |ref={{Sfnref|今野・町田|2008}} }}

=== 一般向け書籍 ===
* 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 |author = 右田正夫・今野紀雄 |year= 2011 |title = マンガでわかる複雑ネットワーク―巨大ネットワークがもつ法則を科学する |series=サイエンス・アイ新書 |publisher = ソフトバンククリエイティブ |edition=初版 |isbn = 978-4-7973-5641-0 |ref={{Sfnref|右田・今野|2011}} }}

== 関連項目 ==
* [[社会的ネットワーク]]
* [[六次の隔たり]]
* [[パーコレーション理論]]

{{DEFAULTSORT:ふくさつねつとわあく}}
[[Category:グラフ理論]]
[[Category:複雑系]]
[[Category:社会的ネットワーク]]
[[Category:ネットワーク]]