複雑ネットワーク
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/08/06 18:03 UTC 版)
スケールフリーグラフの頑強性と脆弱性
スケールフリーグラフが持つ注目すべき特性として、ネットワーク障害など「ランダムな故障や攻撃」に対して頑強性が高いことがあげられる。スケールフリーなトポロジーを持つネットワークでは、全頂点のうちのランダムに5パーセントがダウンしたとしても、代替経路の存在によって頂点間の接続を維持でき、系全体の平均経路長(平均最短距離)はほとんど変化しないのである。同じ頂点数、同じ辺数でトポロジーが異なる他のネットワークではこのような特性は見られない。頑強性は次数分布のベキ指数と関係がありベキ指数が 2 < γ < 3 の場合は非常に頑健性が高くなることがモデルにより示されている。[13]しかしながら、頑健性は両刃の剣である。見方を変えれば頑健性が高いということは感染症やコンピュータウイルスがネットワーク全体に広がり易いということでもあるからだ。実際、ランダムネットワークにおいては存在するウイルスあるいは流行の拡散に関する閾値(threshold)がスケールフリーネットワークでは存在しないため拡散しやすく退治するのも困難で時間がより長くかかることが判明している。
一方で、スケールフリーなネットワークは、特定の重要なハブをピンポイントで狙った攻撃に対しては脆弱であるという弱点も併せ持っている。次数の集中した上位5パーセントの頂点がダウンしたとすると、系全体の平均経路長は約2倍にまで増大してしまう[14]。
同様の特性は自然界の食物連鎖のネットワークでも観察されている。食物連鎖のネットワークは生物種のランダムな絶滅に対しては頑強であるが、特定の重要な種が絶滅すると大きな影響を受けてしまう。こうした点を考慮することは生物多様性に関する議論においても重要であろう[15]。
注釈
- ^ Amaral, L.A.N. et al (2000) によれば、現実世界の全てのネットワークが完全なべき乗則の次数分布となるわけではない。辺が集中することで混雑などのコストが発生する場合は集中は頭打ちとなる。典型例は航空路線のネットワークである。
- ^ 「スモールワールド性」という用語の定義に関しては曖昧さがある。単にグラフの平均最短距離が小さい状態を指す場合もあれば、小さな平均最短距離と大きなクラスター係数とを共に満たす状態を指す場合もある。ランダムグラフは、前者の定義に従えばスモールワールドであり、後者に従えばスモールワールドではない。
- ^ Barabási Albert László [ˈbɒrabɑ̈ːʃi ˌɒrbɛrtˌlɑ̈ːsloː]。バラバーシが姓、アルベルトとラースローが名(男性名)。セーケイ人(ハンガリー人の一派)。ルーマニア領トランシルヴァニアのセーケイ地方のハルギタ県カルツファルヴァ村またはカルツ村(ルーマニア語名 クルツァ村)生まれ。国籍はルーマニアとハンガリーと米国の三重国籍。
- ^ Albert Réka [ˈɒrbɛrt ˌre̝ːkɒ]。アルベルトが姓、レーカが名(女性名)。セーケイ人(ハンガリー人の一派)。ルーマニア領トランシルヴァニアのセーケイ地方のマロシュ県サースレーゲン市(ルーマニア語名 レギン市)生まれ。国籍はルーマニアとハンガリーと米国の三重国籍。
出典
- ^ 右田・今野 2011, p. 14.
- ^ 右田・今野 2011, p. 26.
- ^ 今野・町田 2008, p. 46.
- ^ a b c d 今野・町田 2008, pp. 12–13.
- ^ 右田・今野 2011, p. 142.
- ^ a b 右田・今野 2011, p. 146.
- ^ Watts, D.J., and Strogatz, S.H. (1998)
- ^ F Liljeros et al. "The web of human sexual contacts". Nature, 411, pp.907-908(2001) オンライン・ペーパー
- ^ A. Schneeberger et al. "Scale-Free Networks and Sexually Transmitted Diseases" Sexually Transmitted Diseases, 31(6), pp.380-387(2004) オンライン・ペーパー
- ^ Albert, R., and Barabási, A.-L. (2002)
- ^ a b 右田・今野 2011, p. 162.
- ^ 例えば Dorogovtsev, S.N. et al. (2002) や Klemm, K., and Eguíluz, V.M. (2002)
- ^ Reuven Cohen , Shlomo Havlin (Jul 2010), RobustComplex Networks: Structure,ness and Function, Cambridge University Press, pp. 120, ISBN 978-0-521-84156-6
- ^ Albert, R. et al. (2000)
- ^ Solë, R.V., and Montoya, J.M. (2001)
- ^ Newman, M.E.J., and Girvan, M. (2004)
- ^ Costa, L.F. et al. (2005)
- 1 複雑ネットワークとは
- 2 複雑ネットワークの概要
- 3 複雑ネットワークのモデル
- 4 スケールフリーグラフの頑強性と脆弱性
- 5 複雑ネットワーク研究の現状と今後
- 複雑ネットワークのページへのリンク