複雑なネットワーク

ネットワーク理論の文脈では、複雑ネットワークとは、非自明なトポロジー的特徴を持つグラフ（ネットワーク）のことです。これらの特徴は、格子やランダムグラフなどの単純なネットワークには見られませんが、実際のシステムを表すネットワークにはよく見られます。複雑ネットワークの研究は、コンピュータネットワーク、生物学的ネットワーク、技術ネットワーク、脳ネットワーク^{[ 3 ] [ 4 ]}、ソーシャルネットワークなどの現実世界のネットワークの経験的発見に大きく触発された、若く活発な科学研究分野です^{[ 1 ] [ 2 ]} （2000年以降） 。

ほとんどの社会的、生物学的、および技術的ネットワークは、要素間の接続パターンが純粋に規則的でも純粋にランダムでもない、実質的な非自明なトポロジー的特徴を示します。このような特徴には、次数分布の裾が重いこと、高いクラスタリング係数、頂点間の同類性または異類性、コミュニティ構造、および階層構造が含まれます。有向ネットワークの場合、これらの特徴には、相互性、三者関係の有意性プロファイル、およびその他の特徴も含まれます。対照的に、格子やランダムグラフなど、過去に研究されてきたネットワークの数学的モデルの多くは、これらの特徴を示しません。最も複雑な構造は、中程度の数の相互作用を持つネットワークによって実現できます。^{[ 5 ]}これは、最大の情報量（エントロピー）が中程度の確率で得られるという事実に対応します。

複雑ネットワークのよく知られ、研究されている2つのクラスは、スケールフリーネットワーク^{[ 6 ]}とスモールワールドネットワーク^{[ 7 ] [ 8 ]}であり、その発見と定義は、この分野における典型的なケーススタディである。どちらも、前者はべき乗則次数分布、後者は短い経路長と高いクラスタリングという、特定の構造的特徴によって特徴付けられる。しかし、複雑ネットワークの研究の重要性と人気が高まり続けるにつれて、ネットワーク構造の他の多くの側面も注目を集めるようになった。

この分野は急速に発展を続けており、数学、物理学、電力システム^{[ 9 ]} 、生物学、気候学、コンピュータ科学、社会学、疫学など、多くの分野の研究者を集めています^{[ 10 ]} 。ネットワーク科学と工学のアイデアとツールは、代謝および遺伝子制御ネットワークの分析、生態系の安定性と堅牢性の研究^{[ 11 ]、}臨床科学^{[ 12 ]、}複雑な無線ネットワークの生成と可視化などのスケーラブルな通信ネットワークのモデリングと設計^{[ 13 ]}、その他幅広い実用的な問題に適用されています。ネットワーク科学は、さまざまな分野の多くの会議のテーマであり、一般向けと専門家向けの両方の書籍の主題となっています。

ネットワークは、次数分布、つまりランダムに一様に選択されたノードが特定の数のリンク（次数）を持つ確率がべき乗則と呼ばれる数学関数に従う場合、スケールフリー^{[ 6 ] [ 14 ]}と呼ばれます。べき乗則は、これらのネットワークの次数分布には特徴的なスケールがないことを意味します。対照的に、単一の明確に定義されたスケールを持つネットワークは、すべてのノードが（ほぼ）同じ次数を持つという点で、格子にいくらか似ています。単一のスケールを持つネットワークの例には、エルデシュ・レニー（ER）ランダムグラフ、ランダム正則グラフ、正則格子、ハイパーキューブなどがあります。スケール不変の次数分布を生成する成長ネットワークのモデルには、バラバシ・アルバートモデルとフィットネスモデルがあります。次数分布がスケールフリーなネットワークでは、一部の頂点の次数が平均次数よりも桁違いに大きい場合があります。これらの頂点はしばしば「ハブ」と呼ばれますが、定義上、ノードがハブとみなされる基準となる閾値は存在しないため、この表現は誤解を招く可能性があります。もしそのような閾値が存在するならば、ネットワークはスケールフリーではなくなります。

スケールフリーネットワークへの関心は、1990年代後半に、ワールドワイドウェブ、自律システム（AS）ネットワーク、インターネットルーターネットワーク、タンパク質相互作用ネットワーク、電子メールネットワークなど、現実世界のネットワークでべき乗則次数分布が発見されたという報告から始まった。これらの報告された「べき乗則」のほとんどは、厳密な統計的テストで検証すると失敗するが、これらのネットワークの多くが実際に示す（有限サイズ効果が発生する前）裾の重い次数分布というより一般的な概念は、エッジが独立してランダムに存在する場合（つまり、ポアソン分布に従う場合）に予想されるものとは大きく異なる。べき乗則次数分布を持つネットワークを構築する方法は数多くある。ユール過程はべき乗則の標準的な生成過程であり、1925年から知られています。しかし、頻繁に再発明されているため、ハーバート・A・サイモンによるジブラ原理、マシュー効果、累積的優位性、そしてべき乗則次数分布に対するバラバシとアルバートによる優先的アタッチメントなど、多くの別名で知られています。最近では、スケールフリーネットワークを構築する別の方法として、双曲幾何グラフが提案されています。

べき乗則次数分布（およびその他の特定の構造）を持つネットワークの中には、頂点のランダム削除に対して非常に耐性のあるものがあり、つまり、頂点の大部分が巨大なコンポーネントで接続されたままになります。このようなネットワークは、ネットワークを迅速に分断することを目的とした標的型攻撃に対しても非常に敏感です。次数分布を除いてグラフが均一にランダムである場合、これらの重要な頂点は次数が最も高いものであり、ソーシャルネットワークやコミュニケーションネットワークにおける病気（自然発生的および人為的）の蔓延、および流行の蔓延（どちらもパーコレーションまたは分岐プロセスによってモデル化される）に関与していると考えられています。ランダムグラフ（ER）では、ノード間の平均距離は log N ^{[ 7 ]}のオーダーですが、スケールフリーグラフでは、距離は log log N になります。

ネットワークは、スモールワールド現象（一般に「六次の隔たり」として知られる）になぞらえて、スモールワールドネットワーク^{[ 7 ]}と呼ばれます。スモールワールド仮説は、ハンガリーの作家フリジェシュ・カリンティが1929年に初めて提唱し、スタンレー・ミルグラムが1967年に実験的に検証したもので、任意の2人の人物はわずか6次の隔たりでつながっている、つまり、対応する社会的つながりのグラフの直径は6より大きくないという考え方です。1998年、ダンカン・J・ワッツとスティーブン・ストロガッツは、単一のパラメータによってランダムグラフと格子の間を滑らかに補間する最初のスモールワールドネットワークモデルを発表しました。^{[ 7 ]}彼らのモデルは、少数の長距離リンクを追加するだけで、直径がネットワークのサイズに比例する通常のグラフが、任意の2つの頂点間のエッジの平均数が非常に小さい（数学的には、ネットワークのサイズの対数として増加するはずである）一方でクラスタリング係数が大きいままの「スモールワールド」に変換できることを示した。ランダムグラフやスケールフリーネットワークなど、さまざまな抽象グラフがスモールワールド特性を示すことが知られている。さらに、ワールドワイドウェブや代謝ネットワークなどの現実世界のネットワークもこの特性を示す。

ネットワークに関する科学文献では、「スモールワールド」という用語には曖昧さが伴います。ネットワークの直径の大きさを指すだけでなく、直径が小さいこととクラスタリング係数が高いことの共起を指す場合もあります。クラスタリング係数は、ネットワーク内の三角形の密度を表す指標です。例えば、疎なランダムグラフのクラスタリング係数は極めて小さいですが、現実世界のネットワークでは、係数がかなり大きくなることがよくあります。科学者たちは、この違いは現実世界のネットワークではエッジが相関していることを示唆していると指摘しています。望ましい次数分布とスモールワールド特性を維持しながら、高い相関を示すネットワークモデルを生成するためのアプローチが開発されています。これらのアプローチは、これらのシステムの研究のために解析的に解けるおもちゃのモデルを生成するために使用できます。^{[ 15 ]}

多くの実際のネットワークは空間に埋め込まれています。例としては、交通やその他のインフラネットワーク、脳ネットワークなどがあります。^{[ 3 ] [ 4 ]}空間ネットワークのモデルはいくつか開発されています。^{[ 16 ]}

• BS Manoj、Abhishek Chakraborty、Rahul Singh、『複雑ネットワーク：ネットワークと信号処理の観点から』、Pearson、ニューヨーク、米国、2018年2月。ISBN 978-0-13-478699-5
• S.N. ドロゴフツェフ、J.F.F. メンデス著『ネットワークの進化：生物学的ネットワークからインターネットとWWWへ』オックスフォード大学出版局、2003年、ISBN 0-19-851590-1
• ダンカン・J・ワッツ著『六次の隔たり：つながりの時代の科学』、WWノートン社、2003年、ISBN 0-393-04142-5
• ダンカン・J・ワッツ著『スモールワールド：秩序とランダム性の間のネットワークのダイナミクス』プリンストン大学出版局、2003年、ISBN 0-691-11704-7
• Albert-László Barabasi、Linked: How Everything is Connected to Everything Else、2004、ISBN 0-452-28439-2
• アラン・バラ、マルク・バルテルミー、アレッサンドロ・ヴェスピニャーニ、『複雑ネットワーク上の動的プロセス』、ケンブリッジ大学出版局、2008年、ISBN 978-0-521-87950-7
• シュテファン・ボルンホルト（編集）およびハインツ・ゲオルク・シュスター（編集）、『グラフとネットワークのハンドブック：ゲノムからインターネットまで』、2003年、ISBN 3-527-40336-1
• グイド・カルダレッリ著『スケールフリーネットワーク』、オックスフォード大学出版局、2007年、ISBN 978-0-19-921151-7
• Guido Caldarelli、Michele Catanzaro、ネットワーク: 非常に短い紹介、オックスフォード大学出版局、2012 年、ISBN 978-0-19-958807-7
• E. エストラーダ著、『複雑ネットワークの構造：理論と応用』、オックスフォード大学出版局、2011年、ISBN 978-0-199-59175-6
• マーク・ニューマン著『ネットワーク入門』オックスフォード大学出版局、2010年、ISBN 978-0-19-920665-0
• Mark Newman、Albert-László Barabási、Duncan J. Watts、『The Structure and Dynamics of Networks』、プリンストン大学出版局、プリンストン、2006 年、ISBN 978-0-691-11357-9
• R. Pastor-Satorras および A. Vespignani、『インターネットの進化と構造：統計物理学的アプローチ』、ケンブリッジ大学出版局、2004 年、ISBN 0-521-82698-5
• T. ルイス、ネットワークサイエンス、ワイリー、2009年、
• Niloy Ganguly (編集)、Andreas Deutsch (編集)、Animesh Mukherjee (編集)、『Dynamics On and Of Complex Networks Applications to Biology, Computer Science, and the Social Sciences』、2009年、ISBN 978-0-8176-4750-6
• ヴィト・ラトーラ、ヴィンチェンツォ・ニコシア、ジョヴァンニ・ルッソ、『複雑ネットワーク：原理、方法、応用』、ケンブリッジ大学出版局、2017年、ISBN 978-1-107-10318-4

• DJ Watts および SH Strogatz (1998) . 「スモールワールドネットワークの集団ダイナミクス」. Nature . 393 (6684): 440–442 . Bibcode : 1998Natur.393..440W . doi : 10.1038/30918 . PMID 9623998. S2CID 4429113 .  
• SH Strogatz (2001). "複雑ネットワークの探索" . Nature . 410 (6825): 268– 276. Bibcode : 2001Natur.410..268S . doi : 10.1038/35065725 . PMID 11258382 . 
• SN Dorogovtsev および JFF Mendes ( 2002). "ネットワークの進化". Adv. Phys . 51 (4): 1079–1187 . arXiv : cond-mat/0106144 . Bibcode : 2002AdPhy..51.1079D . doi : 10.1080/00018730110112519 . S2CID 429546 . 
• MEJ Newman、「複雑ネットワークの構造と機能」、SIAM Review 45、167–256 (2003)
• SN Dorogovtsev、AV Goltsev、JFF Mendes、「複雑ネットワークにおける臨界現象」、Rev. Mod. Phys. 80、1275、（2008）
• G. Caldarelli、R. Marchetti、L. Pietronero、「インターネットのフラクタル特性」、Europhysics Letters 52、386 (2000)。https ://arxiv.org/abs/cond-mat/0009178。DOI : 10.1209/epl/i2000-00450-8
• AE Motter (2004). "複雑ネットワークにおけるカスケード制御と防御". Phys. Rev. Lett . 93 (9) 098701. arXiv : cond-mat/0401074 . Bibcode : 2004PhRvL..93i8701M . doi : 10.1103/PhysRevLett.93.098701 . PMID 15447153 . S2CID 4856492 .  
• J. レーネルト著、『複雑ネットワークにおける同期パターンの制御』、シュプリンガー社、2016年
• Dolev, Shlomi; Elovici, Yuval; Puzis, Rami (2010)、「ルーティングの媒介中心性」、J. ACM、57 (4): 25:1–25:27、doi : 10.1145/1734213.1734219、S2CID 15662473