ネットワーク科学

ネットワーク科学は、通信ネットワーク、コンピュータネットワーク、生物学的ネットワーク、認知および意味ネットワーク、ソーシャルネットワークなどの複雑なネットワークを研究する学問分野であり、ノード（または頂点）で表される個別の要素またはアクターと、リンク（またはエッジ）としての要素またはアクター間の接続を考慮します。この分野は、数学のグラフ理論、物理学の統計力学、コンピュータサイエンスのデータマイニングと情報視覚化、統計学の推論モデリング、社会学の社会構造などの理論と方法を活用しています。米国国立研究会議は、ネットワーク科学を「これらの現象の予測モデルにつながる物理的、生物学的、社会的現象のネットワーク表現の研究」と定義しています。^[1]

ネットワークの研究は、複雑な関係データを分析する手段として、さまざまな分野で行われてきました。この分野で最も古い論文は、 1736 年にレオンハルト オイラーが書いた有名な「ケーニヒスベルクの七つの橋」です。オイラーの頂点と辺の数学的記述は、ネットワーク構造における一対一の関係の特性を研究する数学の一分野であるグラフ理論の基礎となりました。グラフ理論の分野は発展を続け、化学に応用されました (Sylvester、1878)。

ハンガリーの数学者で教授のデーネス・ケーニヒは、1936年にグラフ理論に関する最初の本『有限グラフと無限グラフの理論』を執筆した。^[2]

1930年代に、ゲシュタルト心理学者のジェイコブ・モレノが米国にやって来た。彼はソシオグラムを開発し、1933年4月に医学者会議で発表した。モレノは、「ソシオメトリーの出現以前は、集団の人間関係の構造が『正確に』どのようなものか誰も知らなかった」と主張した。^[3]ソシオグラムは、小学生の集団の社会構造を表現したものだった。男子は男子の友達で、女子は女子の友達だったが、一人の男子だけが、一人の女の子を好きだと言った。その気持ちは相手に返ってこなかった。この社会構造のネットワーク表現は非常に興味深いものであったため、ニューヨークタイムズに掲載された。^{[4]ソシオグラムは多くの用途が見出され、}ソーシャルネットワーク分析の分野にまで成長した。

ネットワーク科学における確率理論は、ポール・エルデシュとアルフレッド・レーニによるランダムグラフに関する 8 つの有名な論文とともにグラフ理論から派生して発展しました。ソーシャルネットワークの場合、指数ランダムグラフモデルまたは p* は、ソーシャルネットワークで発生する同点の確率空間を表すために使用される表記フレームワークです。ネットワーク確率構造に対する別のアプローチは、ネットワーク確率行列です。これは、ネットワークのサンプルにおけるエッジの履歴的存在または不在に基づいて、ネットワークで発生するエッジの確率をモデル化します。

2000年頃、ネットワークへの関心が爆発的に高まりました。これは、さまざまなネットワークトポロジーを記述する新しい数学的枠組みを提供する新しい発見が続き、「ネットワーク科学」という用語が生まれたためです。Albert -László BarabásiとReka Albertは、WWWから細胞まで、多くの実際のネットワークのスケールフリーネットワーク^[5]の性質を発見しました 。スケールフリーの特性は、実際のネットワークハブが多くの小さな次数の頂点と共存するという事実を捉えており、著者らはこのスケールフリー状態の起源を説明する動的モデルを提案しました。^[5] Duncan WattsとSteven Strogatzは、ネットワークに関する経験的データと数学的表現を調和させ、スモールワールドネットワークを記述しました。^[6]

決定論的ネットワークの定義は、確率的ネットワークの定義と比較して定義されます。重み付けされていない決定論的ネットワークでは、エッジが存在するか存在しないかのどちらかであり、通常、エッジが存在しないことを示すには 0 を使用し、エッジが存在することを示すには 1 を使用します。重み付けされた決定論的ネットワークでは、エッジ値は各エッジの重み (強度レベルなど) を表します。

確率ネットワークでは、各エッジの背後にある値は、各エッジの存在確率を表します。たとえば、1つのエッジの値が0.9の場合、このエッジの存在確率は0.9であると言います。^[7]

多くの場合、ネットワークには、ネットワークの特性と特徴を分析するために計算できる特定の属性があります。これらのネットワーク特性の動作は、多くの場合、ネットワーク モデルを定義し、特定のモデルが互いにどのように対照的であるかを分析するために使用できます。ネットワーク サイエンスで使用されるその他の用語の定義の多くは、グラフ理論の用語集に記載されています。

ネットワークのサイズは、ノードの数、またはあまり一般的ではないがエッジの数を指します。エッジの数の範囲は、(複数のエッジのない接続されたグラフの場合) (ツリー)から(完全グラフ) までです。単純なグラフ (各頂点のペアの間に最大で 1 つの (無向) エッジが存在し、頂点が自分自身に接続されていないネットワーク) の場合は、 です。有向グラフ (自己接続ノードがない) の場合は、 です。自己接続が許可されている有向グラフの場合は、 です。頂点のペアの間に複数のエッジが存在する可能性があるグラフの状況では、 です。 ${\displaystyle N}$${\displaystyle E}$${\displaystyle N-1}$${\displaystyle E_{\max }}$${\displaystyle E_{\max }={\tbinom {N}{2}}=N(N-1)/2}$${\displaystyle E_{\max }=N(N-1)}$${\displaystyle E_{\max }=N^{2}}$${\displaystyle E_{\max }=\infty }$

ネットワークの密度は、ノードを持つネットワーク内の可能なエッジの数に対するエッジの数の 0 と 1 の間の正規化された比率として定義されます。ネットワーク密度は、ネットワーク内に存在する「オプションの」エッジのパーセンテージの尺度であり、次のように計算できます 。 ここで、 と は、それぞれノードを持つ接続されたネットワーク内の最小および最大のエッジ数です。単純なグラフの場合、は二項係数と によって与えられ、密度 になります 。もう 1 つの可能な式は、 です。一方、つながりは一方向です (Wasserman & Faust 1994)。^[8]これにより、一方向の関係を測定できるため、ネットワーク密度のより良い概要が得られます。 ${\displaystyle D}$${\displaystyle E}$${\displaystyle N}$${\displaystyle D={\frac {E-E_{\mathrm {min} }}{E_{\mathrm {max} }-E_{\mathrm {min} }}}}$${\displaystyle E_{\mathrm {min} }}$${\displaystyle E_{\mathrm {max} }}$${\displaystyle N}$${\displaystyle E_{\mathrm {max} }}$ ${\displaystyle {\tbinom {N}{2}}}$${\displaystyle E_{\mathrm {min} }=N-1}$${\displaystyle D={\frac {E-(N-1)}{E_{\mathrm {max} }-(N-1)}}={\frac {2(E-N+1)}{N(N-3)+2}}}$${\displaystyle D={\frac {T-2N+2}{N(N-3)+2}},}$${\displaystyle T}$

エッジ間の交差がないネットワークの密度は、交差するエッジのないグラフによって与えられるノードを持つネットワーク内の可能なエッジの数に対するエッジの数の比として定義され、次の式で表される。${\displaystyle D}$${\displaystyle E}$${\displaystyle N}$${\displaystyle (E_{\max }=3N-6)}$${\displaystyle D={\frac {E-N+1}{2N-5}}.}$

ノードの次数とは 、そのノードに接続されている辺の数です。ネットワークの密度と密接に関連しているのは平均次数です(または、有向グラフの場合は、前者の係数 で、無向グラフの各辺から生じる 2 の係数が 2 つの異なる頂点の次数に寄与します)。ERランダム グラフ モデル( ) では、 の期待値 (任意の頂点の の期待値に等しい) を計算できます。ランダムな頂点には、ネットワーク内で使用可能な他の頂点があり、確率 で各頂点に接続します。したがって、 です。 ${\displaystyle k}$${\displaystyle \langle k\rangle ={\tfrac {2E}{N}}}$${\displaystyle \langle k\rangle ={\tfrac {E}{N}}}$${\displaystyle G(N,p)}$${\displaystyle \langle k\rangle }$${\displaystyle k}$${\displaystyle N-1}$${\displaystyle p}$${\displaystyle \mathbb {E} [\langle k\rangle ]=\mathbb {E} [k]=p(N-1)}$

平均最短経路長は、すべてのノードペア間の最短経路を見つけ、その経路の長さ（経路に含まれる中間エッジの数、つまりグラフ内の2 つの頂点間の距離）のすべての経路の平均をとることによって計算されます。これにより、ネットワークの 1 つのメンバーから別のメンバーに到達するのにかかる平均ステップ数がわかります。ランダム ネットワーク モデルの頂点数の関数としての期待平均最短経路長（つまり、平均最短経路長のアンサンブル平均）の動作によって、そのモデルがスモール ワールド効果を示すかどうかが決まります。つまり、 としてスケールする場合、モデルはスモール ワールド ネットを生成します。対数よりも速い成長の場合、モデルはスモール ワールドを生成しません。 の特殊なケースは、超スモール ワールド効果として知られています。 ${\displaystyle d_{u,v}}$${\displaystyle u,v}$${\displaystyle N}$${\displaystyle O(\ln N)}$${\displaystyle O(\ln \ln N)}$

ネットワーク グラフを測定する別の方法として、ネットワークの直径を、ネットワーク内で計算された最短経路の中で最も長い経路として定義できます。これは、ネットワーク内で最も遠い 2 つのノード間の最短距離です。言い換えると、すべてのノードから他のすべてのノードまでの最短経路長が計算されると、直径は計算された経路長の中で最も長くなります。直径は、ネットワークの線形サイズを表します。ノード ABCD が接続されている場合、A から D に進むと、直径は 3 (3 ホップ、3 リンク) になります。^{[引用が必要]}

クラスタリング係数は、「友達全員がお互いを知っている」という特性の尺度です。これは、友達の友達は友達である、と説明されることもあります。より正確には、ノードのクラスタリング係数は、ノードの近隣を相互に接続する既存のリンクと、そのようなリンクの最大可能数の比率です。ネットワーク全体のクラスタリング係数は、すべてのノードのクラスタリング係数の平均です。ネットワークのクラスタリング係数が高いことは、スモールワールドのもう 1 つの兆候です。

'番目のノード のクラスタリング係数は${\displaystyle i}$

${\displaystyle C_{i}={2e_{i} \over k_{i}{(k_{i}-1)}}\,,}$

ここで、 は' 番目のノードの隣接ノードの数であり、 はこれらの隣接ノード間の接続数です。隣接ノード間の接続の最大可能数は、 ${\displaystyle k_{i}}$${\displaystyle i}$${\displaystyle e_{i}}$

${\displaystyle {\binom {k}{2}}={{k(k-1)} \over 2}\,.}$

確率論的な観点から見ると、期待されるローカル クラスタリング係数は、同じノードの任意の 2 つの隣接ノード間にリンクが存在する可能性です。

ネットワークの接続方法は、ネットワークの分析と解釈に大きな役割を果たします。ネットワークは次の 4 つのカテゴリに分類されます。

• クリーク/完全グラフ: すべてのノードが他のすべてのノードに接続されている、完全に接続されたネットワーク。これらのネットワークは、すべてのノードが他のすべてのノードからのインリンクとアウトリンクを持つという点で対称的です。
• 巨大コンポーネント: ネットワーク内のほとんどのノードを含む単一の接続されたコンポーネント。
• 弱く接続されたコンポーネント: エッジの方向性を無視して、任意のノードから他の任意のノードへのパスが存在するノードのコレクション。
• 強く接続されたコンポーネント:任意のノードから他の任意のノードへの有向パスが存在するノードのコレクション。

中心性指標は、ネットワーク モデルで最も重要なノードを識別するためのランキングを作成します。異なる中心性指標は、「重要性」という単語の異なるコンテキストをエンコードします。たとえば、媒介中心性では、ノードが他の多くのノードの間にブリッジを形成する場合、そのノードは非常に重要であるとみなされます。対照的に、固有値中心性では、他の多くの非常に重要なノードがそのノードにリンクしている場合、そのノードは非常に重要であるとみなされます。文献では、このような尺度が何百も提案されています。

中心性指標は、最も重要なノードを識別する場合にのみ正確です。この指標は、ネットワーク ノードの残りの部分では、ほとんど意味を持ちません。^{[9] [10]}また、その指標は、重要性の想定コンテキスト内でのみ正確であり、他のコンテキストでは「間違っている」傾向があります。^[11]たとえば、唯一のリンクが各コミュニティの最年少メンバー間のエッジである 2 つの別々のコミュニティを想像してください。一方のコミュニティからもう一方のコミュニティへの転送はすべてこのリンクを経由する必要があるため、2 人の年少メンバーは高い媒介中心性を持ちます。しかし、年少であるため、(おそらく) コミュニティ内の「重要な」ノードとのつながりがほとんどなく、固有値中心性は非常に低くなります。

中心性指標の限界により、より一般的な指標が開発されました。2つの例としては、ランダムウォークの多様性を使用して、特定の開始ノードからネットワークの残りの部分へのアクセス可能性を測定するアクセス可能性^[12] と、ノードによって生成される感染力の期待値から導かれる期待力^[9]があります。 これらの指標は両方とも、ネットワークの構造のみから意味のある形で計算できます。

ネットワーク内のノードは、コミュニティを表すグループに分割できます。コンテキストに応じて、コミュニティは別々であったり、重複したりすることがあります。通常、このようなコミュニティ内のノードは、同じコミュニティ内の他のノードとは強く接続されていますが、コミュニティ外のノードとは弱く接続されています。特定のネットワークのコミュニティ構造を説明するグラウンド トゥルースがない場合、教師ありまたは教師なしのクラスタリング方法を使用して、考えられるコミュニティ構造を推測するアルゴリズムがいくつか開発されています。

ネットワーク モデルは、経験的な複雑なネットワーク内の相互作用を理解するための基礎として機能します。さまざまなランダム グラフ生成モデルによって、現実世界の複雑なネットワークと比較するために使用できるネットワーク構造が生成されます。

ポール・エルデシュとアルフレッド・レーニにちなんで名付けられたエルデシュ・レーニモデルは、等確率でノード間にエッジが設定されるランダムグラフを生成するために使用されます。確率的手法で、さまざまな特性を満たすグラフの存在を証明したり、ほとんどすべてのグラフに当てはまる特性が何を意味するかを厳密に定義したりするために使用できます。

Erdős–Rényi モデルを生成するには、ノードの総数nと、ランダムなノードのペアがエッジを持つ 確率pの 2 つのパラメータを指定する必要があります。${\displaystyle G(n,p)}$

モデルは特定のノードに偏ることなく生成されるため、次数分布は二項分布となる。ランダムに選択された頂点に対して、 ${\displaystyle v}$

${\displaystyle P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k}.}$

このモデルでは、クラスタリング係数は0 a.sです。 の動作は 3 つの領域に分けられます。 ${\displaystyle G(n,p)}$

亜臨界 : すべてのコンポーネントは単純かつ非常に小さく、最大のコンポーネントのサイズは です。 ${\displaystyle np<1}$${\displaystyle |C_{1}|=O(\log n)}$

致命的 ：; ${\displaystyle np=1}$${\displaystyle |C_{1}|=O(n^{\frac {2}{3}})}$

超臨界 :は方程式の正の解です。 ${\displaystyle np>1}$${\displaystyle |C_{1}|\approx yn}$${\displaystyle y=y(np)}$${\displaystyle e^{-pny}=1-y}$

最も大きな連結コンポーネントは複雑度が高い。その他のコンポーネントはすべて単純で小さい。 ${\displaystyle |C_{2}|=O(\log n)}$

構成モデルは、次数列^{[13] [14]}または次数分布^[15] (これは、後で次数列を生成するために使用される) を入力として受け取り、次数列以外のすべての点でランダムに接続されたグラフを生成します。つまり、次数列の特定の選択に対して、グラフはこの次数列に準拠するすべてのグラフの集合から一様にランダムに選択されます。ランダムに選択された頂点の次数は、整数値を持つ 独立した同一分布のランダム変数です。 のとき、構成グラフには、無限サイズを持つ巨大な接続コンポーネント が含まれます。^[14]残りのコンポーネントは有限サイズであり、サイズ分布の概念で定量化できます。ランダムにサンプリングされたノードがサイズのコンポーネントに接続される確率は、次数分布の畳み込みべき乗で与えられます。 ^[16]ここで、 は次数分布、 を表します。巨大なコンポーネントは、すべてのエッジの臨界部分をランダムに削除することで破壊できます。このプロセスは、ランダムネットワーク 上のパーコレーションと呼ばれます。次数分布の2次モーメントが有限のとき、この臨界辺率は^[17]で与えられ、巨大成分の平均頂点間距離はネットワークの総サイズに比例して比例します。[ ^15]${\displaystyle k}$${\textstyle \mathbb {E} [k^{2}]-2\mathbb {E} [k]>0}$${\displaystyle w(n)}$${\displaystyle n}$$${\displaystyle w(n)={\begin{cases}{\frac {\mathbb {E} [k]}{n-1}}u_{1}^{*n}(n-2),&n>1,\\u(0)&n=1,\end{cases}}}$$${\displaystyle u(k)}$${\displaystyle u_{1}(k)={\frac {(k+1)u(k+1)}{\mathbb {E} [k]}}}$${\displaystyle p_{c}}$${\textstyle \mathbb {E} [k^{2}]<\infty }$ ${\displaystyle p_{c}=1-{\frac {\mathbb {E} [k]}{\mathbb {E} [k^{2}]-\mathbb {E} [k]}}}$ ${\displaystyle l}$${\displaystyle l=O(\log N)}$

有向配置モデルでは、ノードの次数は入次数と出次数 の2つの数値で与えられ、その結果、次数分布は2変量となる。入辺と出辺の期待数は一致するため、 となる。有向配置モデルに巨大成分が含まれるのは、次の場合である^[18] 。後者の不等式では、 と は等しく、したがって相互に交換可能であることに注意する。ランダムに選択された頂点がサイズの成分に属する確率は、入成分 については 次式で与えられる。^[19]${\displaystyle k_{\text{in}}}$${\displaystyle k_{\text{out}}}$${\textstyle \mathbb {E} [k_{\text{in}}]=\mathbb {E} [k_{\text{out}}]}$$${\displaystyle 2\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{in}}k_{\text{out}}]-\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{out}}^{2}]-\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{in}}^{2}]+\mathbb {E} [k_{\text{in}}^{2}]\mathbb {E} [k_{\text{out}}^{2}]-\mathbb {E} [k_{\text{in}}k_{\text{out}}]^{2}>0.}$$${\textstyle \mathbb {E} [k_{\text{in}}]}$${\textstyle \mathbb {E} [k_{\text{out}}]}$${\displaystyle n}$$${\displaystyle h_{\text{in}}(n)={\frac {\mathbb {E} [k_{in}]}{n-1}}{\tilde {u}}_{\text{in}}^{*n}(n-2),\;n>1,\;{\tilde {u}}_{\text{in}}={\frac {k_{\text{in}}+1}{\mathbb {E} [k_{\text{in}}]}}\sum \limits _{k_{\text{out}}\geq 0}u(k_{\text{in}}+1,k_{\text{out}}),}$$

${\displaystyle h_{\text{out}}(n)={\frac {\mathbb {E} [k_{\text{out}}]}{n-1}}{\tilde {u}}_{\text{out}}^{*n}(n-2),\;n>1,\;{\tilde {u}}_{\text{out}}={\frac {k_{\text{out}}+1}{\mathbb {E} [k_{\text{out}}]}}\sum \limits _{k_{\text{in}}\geq 0}u(k_{\text{in}},k_{\text{out}}+1),}$

アウトコンポーネント用。

Wattsと Strogatz モデルは、スモールワールド特性を持つグラフを生成するランダム グラフ生成モデルです。

初期格子構造は、ワッツ・ストロガッツ モデルを生成するために使用されます。ネットワーク内の各ノードは、最初に最も近い隣接ノードにリンクされます。別のパラメータは、再配線確率として指定されます。各エッジには、ランダム エッジとしてグラフに再配線される確率があります。モデル内の再配線されるリンクの予想数は です。 ${\displaystyle \langle k\rangle }$${\displaystyle p}$${\displaystyle pE=pN\langle k\rangle /2}$

Watts-Strogatz モデルは非ランダムな格子構造から始まるため、平均パス長が長いだけでなく、クラスタリング係数も非常に高くなります。各再配線により、高度に接続されたクラスター間のショートカットが作成される可能性があります。再配線の確率が増加すると、クラスタリング係数は平均パス長よりもゆっくりと減少します。実際には、これにより、クラスタリング係数がわずかに減少するだけで、ネットワークの平均パス長が大幅に減少します。p の値が高いほど、再配線されるエッジが多くなり、Watts-Strogatz モデルはランダム ネットワークになります。

Barabási -Albert モデルは、優先的な接続または「金持ちはさらに金持ちになる」効果を示すために使用されるランダム ネットワーク モデルです。このモデルでは、エッジは次数の高いノードに接続される可能性が最も高くなります。ネットワークは、m ₀ノードの初期ネットワークから始まります。m _{0 ≥ 2 であり、初期ネットワークの各ノードの次数は少なくとも 1 である必要があります。そうでない場合}、 常にネットワークの残りの部分から切断されたままになります。

BAモデルでは、新しいノードがネットワークに1つずつ追加されます。各新しいノードは、既存のノードがすでに持っているリンクの数に比例した確率で既存のノードに接続されます。正式には、新しいノードがノードiに接続される確率p _i^は[20]です。${\displaystyle m}$

${\displaystyle p_{i}={\frac {k_{i}}{\sum _{j}k_{j}}},}$

ここで、k _{i は}ノードiの次数です。リンクが密集したノード (「ハブ」) は、さらに多くのリンクをすぐに蓄積する傾向がありますが、リンクが少ないノードは、新しいリンクの宛先として選択される可能性は低くなります。新しいノードは、すでにリンクが密集しているノードに接続することを「優先」します。

BA モデルから得られる次数分布はスケールフリーであり、特に次数が大きい場合は次の形式のべき乗法則になります。

${\displaystyle P(k)\sim k^{-3}\,}$

ハブは高い媒介中心性を示し、ノード間に短いパスが存在することを可能にします。その結果、BA モデルの平均パス長は非常に短くなる傾向があります。このモデルのクラスタリング係数も 0 になる傾向があります。

バラバシ・アルバートモデル^[21]は、スケールフリー特性の普遍性を説明することを目的として無向ネットワーク向けに開発され、さまざまなネットワークやアプリケーションに幅広く適用されています。このモデルの有向バージョンはプライスモデル^{[22] [23]}であり、引用ネットワークのみを対象に開発されました。

非線形優先接続（NLPA）では、ネットワーク内の既存のノードは、ノード次数の定数正の累乗に比例して新しいエッジを獲得します。[ ^24]正式には、ノードが新しいエッジを獲得する 確率は次のように表されます。${\displaystyle \alpha }$${\displaystyle i}$

${\displaystyle p_{i}={\frac {k_{i}^{\alpha }}{\sum _{j}k_{j}^{\alpha }}}.}$

の場合、NLPA は BA モデルに簡約され、「線形」と呼ばれます。 の場合、NLPA は「サブ線形」と呼ばれ、ネットワークの次数分布は引き伸ばされた指数分布に近づきます。 の場合、NLPA は「スーパー線形」と呼ばれ、少数のノードがネットワーク内のほぼすべての他のノードに接続します。と の両方について、ネットワークのスケールフリー特性は、無限システムサイズの限界で破綻します。ただし、が よりわずかに大きいだけの場合、NLPA は一時的にスケールフリーであるように見える次数分布をもたらす可能性があります。 ^[25]${\displaystyle \alpha =1}$${\displaystyle 0<\alpha <1}$${\displaystyle \alpha >1}$${\displaystyle \alpha <1}$${\displaystyle \alpha >1}$${\displaystyle \alpha }$${\displaystyle 1}$

仲介駆動型接続（MDA）モデルでは、エッジを持つ新しいノードが既存の接続ノードをランダムに選択し、そのノードではなく、同様にランダムに選択された隣接ノードと接続します。選択された既存のノードの ノードが${\displaystyle m}$${\displaystyle m}$${\displaystyle \Pi (i)}$${\displaystyle i}$

${\displaystyle \Pi (i)={\frac {k_{i}}{N}}{\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}.}$

係数は、ノードの近傍の次数の調和平均 (IHM) の逆数です。広範な数値調査により、おおよそ に対して、大極限での平均 IHM 値は定数となり、つまり となることが示唆されています。これは、ノードが持つリンク (次数) が高いほど、仲介者を介してより多くの方法でリンクに到達できるため、より多くのリンクを獲得するチャンスが高くなることを意味します。これは、本質的に、金持ちはさらに金持ちになるという直感的なメカニズム (またはバラバシ-アルバート モデルの優先的接続規則) を体現しています。したがって、MDA ネットワークは PA 規則に従っているように見えますが、それは偽装されています。^[26]${\displaystyle {\frac {\sum _{j=1}^{k_{i}}{\frac {1}{k_{j}}}}{k_{i}}}}$${\displaystyle k_{i}}$${\displaystyle i}$${\displaystyle m>14}$${\displaystyle N}$${\displaystyle \Pi (i)\propto k_{i}}$

しかし、これは勝者がすべてを手に入れるメカニズムを説明しています。全体のノードのほとんどが次数 1 を持ち、1 つのノードが次数で超富裕層であることがわかります。価値が増加すると、超富裕層と貧困層の間の格差が減少し、金持ちがさらに超富裕層になるメカニズムから、金持ちがさらに富裕層になるメカニズムへの移行が見られます。 ${\displaystyle m=1}$${\displaystyle 99\%}$${\displaystyle m}$${\displaystyle m>14}$

頂点の性質が重要な要素となる別のモデルが、カルダレッリらによって導入されている。^[27]ここでは、2つの頂点の間にリンクが作成され、その確率は関連する頂点の適応度のリンク関数によって与えられる。頂点iの次数は^{[28]で与えられる。}${\displaystyle i,j}$${\displaystyle f(\eta _{i},\eta _{j})}$

${\displaystyle k(\eta _{i})=N\int _{0}^{\infty }f(\eta _{i},\eta _{j})\rho (\eta _{j})\,d\eta _{j}}$

が の可逆かつ増加関数である場合、確率分布は次のように与えられる。 ${\displaystyle k(\eta _{i})}$${\displaystyle \eta _{i}}$${\displaystyle P(k)}$

${\displaystyle P(k)=\rho (\eta (k))\cdot \eta '(k)}$

その結果、適応度がべき乗法則として分布する場合、ノード次数も同様にべき乗法則として分布します。 ${\displaystyle \eta }$

あまり直感的ではないが、次のようなリンク関数と組み合わせると、 急速に減衰する確率分布となる。 ${\displaystyle \rho (\eta )=e^{-\eta }}$

${\displaystyle f(\eta _{i},\eta _{j})=\Theta (\eta _{i}+\eta _{j}-Z)}$

定数とHeavyside関数 を使用すると、スケールフリーネットワークも得られます。${\displaystyle Z}$${\displaystyle \Theta }$

このようなモデルは、GDPを様々なノードの適合度として、そして次のようなリンク関数を 使用することで、国家間の貿易を記述するためにうまく適用されてきた^{[29] [30]}${\displaystyle i,j}$

${\displaystyle {\frac {\delta \eta _{i}\eta _{j}}{1+\delta \eta _{i}\eta _{j}}}.}$

指数ランダムグラフモデル（ERGM）は、ソーシャルネットワークやその他のネットワークからのデータを分析するための統計モデルファミリーです^{。 [31]}指数ファミリーは、ネットワークだけでなく多くの種類のデータをカバーする幅広いモデルファミリーです。ERGMはこのファミリーのモデルであり、ネットワークを記述します。

ランダム グラフを 表すために、ノードのセットと、ノードのペアによってインデックス付けされたタイ変数のコレクション(ノードがエッジで接続されている場合、 、そうでない場合) という表記法を採用します。 ${\displaystyle Y\in {\mathcal {Y}}}$${\displaystyle n}$${\displaystyle \{Y_{ij}:i=1,\dots ,n;j=1,\dots ,n\}}$${\displaystyle ij}$${\displaystyle Y_{ij}=1}$${\displaystyle (i,j)}$${\displaystyle Y_{ij}=0}$

ERGM の基本的な仮定は、観測されたグラフの構造は、観測されたネットワークと、場合によってはノードの属性の関数である十分な統計量の与えられたベクトルによって説明できるということです。ERGM 内のグラフの確率は次のように定義されます。 ${\displaystyle y}$ ${\displaystyle s(y)}$${\displaystyle y\in {\mathcal {Y}}}$

${\displaystyle P(Y=y|\theta )={\frac {\exp(\theta ^{T}s(y))}{c(\theta )}}}$

ここで、はに関連付けられたモデルパラメータのベクトルであり、は正規化定数です。 ${\displaystyle \theta }$${\displaystyle s(y)}$${\displaystyle c(\theta )=\sum _{y'\in {\mathcal {Y}}}\exp(\theta ^{T}s(y'))}$

ソーシャルネットワーク分析は、社会的実体間の関係の構造を調査します。 ^[32]これらの実体は多くの場合個人ですが、グループ、組織、国家、ウェブサイト、学術出版物である場合もあります。

1970年代以来、ネットワークの実証的研究は社会科学において中心的な役割を果たしており、ネットワークの研究に使用される数学的および統計的ツールの多くは、社会学で最初に開発されたものである。^[33] 他の多くの応用の中でも、ソーシャルネットワーク分析は、イノベーション、ニュース、噂の拡散を理解するために使用されてきた。同様に、病気と健康関連行動の両方の蔓延を調査するために使用されてきている。また、市場の研究にも適用されており、交換関係における信頼の役割と価格設定における社会的メカニズムの役割を調べるために使用されている。同様に、政治運動や社会組織へのリクルートメントの研究にも使用されている。また、科学的意見の相違や学術的名声を概念化するためにも使用されている。最近では、ネットワーク分析（およびそれに近いトラフィック分析）は、階層型とリーダーレス型の両方の反乱ネットワークを発見するために、軍事情報で重要な用途を得ている。^{[34] [35]}犯罪学では、犯罪組織の有力者、犯罪者の動き、共犯者を特定し、犯罪活動を予測し、政策を立案するために使用されています。^[36]

動的ネットワーク分析は、複雑な社会技術システムの影響における異なるクラスのエンティティ間の関係の変化する構造を調査し、新しいグループ、トピック、リーダーの出現などの社会的安定性と変化を反映します。^{[37] [38] [39]動的ネットワーク分析は、複数のタイプのノード（エンティティ）と}複数のタイプのリンク で構成されるメタネットワークに焦点を当てています。これらのエンティティは非常に多様です。例としては、人、組織、トピック、リソース、タスク、イベント、場所、信念などがあります。

動的ネットワーク技術は、時間の経過に伴うネットワークの傾向や変化を評価したり、新たなリーダーを特定したり、人々とアイデアの共進化を調べたりするのに特に役立ちます。

近年、公開されている高スループットの生物学的データの爆発的な増加により、分子ネットワークの分析が大きな関心を集めています。この内容の分析の種類はソーシャルネットワーク分析と密接に関連していますが、多くの場合、ネットワーク内のローカルパターンに焦点を当てています。たとえば、ネットワークモチーフは、ネットワーク内で過剰に表現されている小さなサブグラフです。アクティビティモチーフは、ネットワーク構造を考えると過剰に表現されている、ネットワーク内のノードとエッジの属性における同様の過剰表現パターンです。生物学的ネットワークの分析は、インタラクトームにおける疾患の影響を調べるネットワーク医学の発展につながっています。^[40]

セマンティックネットワーク分析は、ネットワーク分析のサブフィールドであり、ネットワーク内の単語と概念の関係に焦点を当てています。単語はノードとして表され、テキスト内での単語の近接性または共起はエッジとして表されます。したがって、セマンティックネットワークは知識のグラフィカルな表現であり、神経言語学や自然言語処理アプリケーションでよく使用されます。セマンティックネットワーク分析は、大規模なテキストを分析して主要なテーマやトピック（ソーシャルメディアの投稿など）を特定したり、偏見（ニュース報道など）を明らかにしたり、研究分野全体をマッピングしたりする方法として使用されます。^[41]

リンク分析はネットワーク分析のサブセットであり、オブジェクト間の関連性を調査します。例としては、警察の捜査の一環として、容疑者や被害者の住所、特定の期間にダイヤルした電話番号や参加した金融取引、これらの対象者間の家族関係を調べることが挙げられます。ここでのリンク分析は、個別の情報からは明らかではない、非常に多くの異なるタイプのオブジェクト間の重要な関係と関連性を提供します。コンピューター支援または完全に自動のコンピューターベースのリンク分析は、銀行や保険会社による詐欺検出、通信事業者による通信ネットワーク分析、医療部門による疫学および薬理学、法執行機関の捜査、検索エンジンによる関連性評価（逆にスパマーによるスパムデクシング、企業オーナーによる検索エンジン最適化）、その他多くのオブジェクト間の関係を分析する必要があるあらゆる場所でますます採用されています。

SIRモデルは、感染集団内での世界的パンデミックの拡大を予測する最もよく知られたアルゴリズムの 1 つです。

${\displaystyle S=\beta \left({\frac {1}{N}}\right)}$

上記の式は、感染集団内の各感受性単位の感染の「力」を表しており、βは当該疾患の伝染率に相当します。

感染集団における感受性者の変化を追跡するには:

${\displaystyle \Delta S=\beta \times S{1 \over N}\,\Delta t}$

${\displaystyle \Delta I=\mu I\,\Delta t}$

時間の経過とともに、感染者数は、平均感染期間にわたって 1 に減算された特定の回復率、感染者数、、および時間の変化によって変動します。 ${\displaystyle \mu }$${\displaystyle {1 \over \tau }}$${\displaystyle I}$${\displaystyle \Delta t}$

SIR モデルに関して、人口がパンデミックに襲われるかどうかは、「感染者 1 人によって感染する平均人数」の値に依存します。 ${\displaystyle R_{0}}$

${\displaystyle R_{0}=\beta \tau ={\beta \over \mu }}$

いくつかのWeb 検索 ランキングアルゴリズムは、リンク ベースの中心性メトリックを使用します。これには、(出現順に) MarchioriのHyper Search、GoogleのPageRank、Kleinberg のHITS アルゴリズム、CheiRankおよびTrustRankアルゴリズムが含まれます。リンク分析は、Web ページのコレクションの構造を理解し、そこから情報を抽出するために、情報科学およびコミュニケーション科学でも行われます。たとえば、政治家の Web サイトまたはブログ間の相互リンクを分析する場合があります。

PageRank は、「ノード」または Web サイトをランダムに選択し、一定の確率で他のノードに「ランダムにジャンプ」することで機能します。他のノードにランダムにジャンプすることで、一部の Web ページが周辺に存在し、容易に評価されない場合でも、PageRank がネットワークを完全に横断できるようになります。

各ノード には、にリンクしているページの合計数に のアウトリンクまたは「アウト次数」を掛けたものと、 の「重要度」または PageRank を掛けたもので定義される PageRank があります。 ${\displaystyle x_{i}}$${\displaystyle j}$${\displaystyle i}$${\displaystyle j}$${\displaystyle j}$

${\displaystyle x_{i}=\sum _{j\rightarrow i}{1 \over N_{j}}x_{j}^{(k)}}$

上で説明したように、PageRank はインターネット上のすべての Web サイトに PageRank を割り当てるためにランダム ジャンプを使用します。これらのランダム ジャンプにより、幅優先検索や深さ優先検索などの通常の検索方法では見つからない可能性のある Web サイトが見つかります。

PageRank を決定するための前述の公式の改良には、これらのランダム ジャンプ コンポーネントの追加が含まれます。ランダム ジャンプがなければ、一部のページの PageRank が 0 になり、これは好ましくありません。

1 つ目は、ランダム ジャンプが発生する確率です。対照的なのは、「減衰係数」、つまり です。 ${\displaystyle \alpha }$${\displaystyle 1-\alpha }$

${\displaystyle R{(p)}={\alpha \over N}+(1-\alpha )\sum _{j\rightarrow i}{1 \over N_{j}}x_{j}^{(k)}}$

別の見方をすると:

${\displaystyle R(A)=\sum {R_{B} \over B_{\text{(outlinks)}}}+\cdots +{R_{n} \over n_{\text{(outlinks)}}}}$

グラフ内のノードとエッジの相対的な重要性に関する情報は、社会学などの分野で広く使用されている中心性尺度を通じて取得できます。中心性尺度は、ネットワーク分析で「メッセージや情報がネットワーク内のすべてのノードまたはほとんどのノードに広がるようにするには、ネットワーク内のどのノードをターゲットにする必要がありますか？」、または逆に「病気の蔓延を抑えるには、どのノードをターゲットにする必要がありますか？」などの質問に答える必要がある場合に不可欠です。正式に確立された中心性の尺度は、次数中心性、近接中心性、媒介中心性、固有ベクトル中心性、およびカッツ中心性です。ネットワーク分析の目的によって、一般的に使用される中心性尺度の種類が決まります。^[32]

• ネットワーク内のノードの次数中心性は、ノードに接続するリンク (頂点) の数です。
• 近接中心性は、ネットワーク内のノードと他のすべてのノード間の最短距離 (測地線パス) の合計を測定することで、ノードがネットワーク内の他のノードにどれだけ「近い」かを決定します。
• 媒介中心性は、ネットワーク内の他のノードに流れるトラフィックの量を測定することで、ノードの相対的な重要性を決定します。これは、すべてのノード ペアを接続し、対象のノードを含むパスの割合を測定することで行われます。グループ媒介中心性は、ノードのグループを流れるトラフィックの量を測定します。
• 固有ベクトル中心性は次数中心性のより洗練されたバージョンであり、ノードの中心性はノードに関係するリンクの数だけでなく、それらのリンクの品質にも依存します。この品質係数は、ネットワークの隣接行列の固有ベクトルによって決まります。
• ノードのKatz 中心性は、そのノードとネットワーク内のすべての (到達可能な) ノード間の測地線パスを合計することによって測定されます。これらのパスは重み付けされており、ノードとそのすぐ近くのノードを接続するパスは、すぐ近くのノードから遠く離れたノードに接続するパスよりも重みが高くなります。

複雑ネットワーク内のコンテンツは、保存的拡散と非保存的拡散という2つの主要な方法で拡散します。^[42] 保存的拡散では、複雑ネットワークに入るコンテンツの総量は、通過するときに一定のままです。保存的拡散のモデルは、一定量の水が入ったピッチャーが、チューブで接続された一連の漏斗に注がれていることで最もよく表すことができます。ここで、ピッチャーは元のソースを表し、水は拡散されるコンテンツです。漏斗と接続チューブは、それぞれノードとノード間の接続を表します。水が1つの漏斗から別の漏斗に渡されると、以前に水にさらされていた漏斗から水は瞬時に消えます。非保存的拡散では、コンテンツの量は、複雑なネットワークに入り、通過するときに変化します。非保存的拡散のモデルは、チューブで接続された一連の漏斗を流れる、連続的に流れる蛇口で最もよく表すことができます。ここで、元のソースからの水の量は無限です。また、水にさらされた漏斗は、次の漏斗に水が流れていくときも、引き続き水にさらされます。非保存モデルは、ほとんどの感染症の伝染を説明するのに最も適しています。

1927 年、WO Kermack と AG McKendrick は、感受性、感染、回復の3 つのコンパートメントのみを持つ固定集団を考慮したモデルを作成しました。このモデルで使用されるコンパートメントは、次の 3 つのクラスで構成されています。 ${\displaystyle S(t)}$${\displaystyle I(t)}$${\displaystyle R(t)}$

• ${\displaystyle S(t)}$t時点でまだ病気に感染していない人、または病気にかかりやすい人の数を表すために使用される。
• ${\displaystyle I(t)}$病気に感染し、感受性のある人に病気を広める可能性のある人の数を示します。
• ${\displaystyle R(t)}$感染し、その後回復した人のための区画です。このカテゴリーの人は、再び感染したり、他の人に感染させたりすることはありません。

このモデルの流れは次のように考えられます。

${\displaystyle {\mathcal {S}}\rightarrow {\mathcal {I}}\rightarrow {\mathcal {R}}}$

固定された人口、を使用して、KermackとMcKendrickは次の式を導出しました。 ${\displaystyle N=S(t)+I(t)+R(t)}$

${\displaystyle {\begin{aligned}{\frac {dS}{dt}}&=-\beta SI\\[8pt]{\frac {dI}{dt}}&=\beta SI-\gamma I\\[8pt]{\frac {dR}{dt}}&=\gamma I\end{aligned}}}$

これらの方程式を定式化する際に、いくつかの仮定が立てられました。まず、集団内の個人は、他のすべての個人と等しく、 の割合で病気にかかる確率を持つと見なされなければなりません。これは、病気の接触率または感染率と見なされます。したがって、感染者は単位時間あたりに他の人と接触して病気を伝染させることができ、感染者と感受性者の接触率は です。この場合、単位時間あたりの感染者 1 人あたりの新規感染数は となり、新規感染率 (または感受性カテゴリを離れる者) は次のようになります(Brauer & Castillo-Chavez、2001)。2 番目と 3 番目の方程式では、感受性クラスを離れる集団が感染者クラスに入る数と等しいと見なします。ただし、感染者は単位時間あたりにこのクラスを離れ、単位時間あたりの割合で回復/除去クラスに入ります ( は平均回復率、または 平均感染期間を表します)。同時に発生するこれらのプロセスは、集団行動の法則と呼ばれ、集団内の 2 つのグループ間の接触率は、関係する各グループのサイズに比例するという広く受け入れられている考え方です (Daley & Gani、2005)。最後に、感染と回復の速度は出生と死亡の時間スケールよりもはるかに速いと想定されているため、これらの要因はこのモデルでは無視されます。 ${\displaystyle \beta }$${\displaystyle \beta N}$${\displaystyle S/N}$${\displaystyle \beta N(S/N)}$${\displaystyle \beta N(S/N)I=\beta SI}$${\displaystyle \gamma }$${\displaystyle \gamma }$${\displaystyle 1/\gamma }$

このモデルの詳細については、 Epidemic モデルのページをご覧ください。

マスター方程式は、無向成長ネットワークの動作を表現できます。このネットワークでは、各時間ステップで、新しいノードがネットワークに追加され、古いノードにリンクされます (ランダムに選択され、優先順位はありません)。 初期ネットワークは、時刻 で 2 つのノードとそれらの間の 2 つのリンクによって形成されます。この構成は、以降の計算を簡略化するためにのみ必要なため、 の時点では、ネットワークにはノードとリンクがあります。 ${\displaystyle t=2}$${\displaystyle t=n}$${\displaystyle n}$${\displaystyle n}$

このネットワークのマスター方程式は次のとおりです。

${\displaystyle p(k,s,t+1)={\frac {1}{t}}p(k-1,s,t)+\left(1-{\frac {1}{t}}\right)p(k,s,t),}$

ここで、 は時刻 に次数 のノードが存在する確率であり、 はこのノードがネットワークに追加されたときの時間ステップです。時刻 に古いノードがリンクを持つ方法は 2 つしかないことに注意してください。 ${\displaystyle p(k,s,t)}$${\displaystyle s}$${\displaystyle k}$${\displaystyle t+1}$${\displaystyle s}$${\displaystyle s}$${\displaystyle k}$${\displaystyle t+1}$

• ノードは時間で次数を持ち、確率で新しいノードによってリンクされます${\displaystyle s}$${\displaystyle k-1}$${\displaystyle t}$${\displaystyle 1/t}$
• 時点ですでに次数があり、新しいノードによってリンクされません。${\displaystyle k}$${\displaystyle t}$

このモデルを簡略化すると、次数分布は^[43]${\displaystyle P(k)=2^{-k}.}$

この成長するネットワークに基づいて、単純なルールに従って伝染病モデルが開発されます。新しいノードが追加されるたびに、リンクする古いノードを選択した後、この新しいノードが感染するかどうかが決定されます。この伝染病モデルのマスター方程式は次のとおりです。

${\displaystyle p_{r}(k,s,t)=r_{t}{\frac {1}{t}}p_{r}(k-1,s,t)+\left(1-{\frac {1}{t}}\right)p_{r}(k,s,t),}$

ここで、感染する（ ）かしないか（ ）の決定を表す。このマスター方程式を解くと、次の解が得られる：^[44]${\displaystyle r_{t}}$${\displaystyle r_{t}=1}$${\displaystyle r_{t}=0}$${\displaystyle {\tilde {P}}_{r}(k)=\left({\frac {r}{2}}\right)^{k}.}$

多層ネットワークとは、複数の種類の関係を持つネットワークです。^[45]現実世界のシステムを多次元ネットワークとしてモデル化する試みは、ソーシャルネットワーク分析、^[46]経済学、歴史学、都市および国際交通、生態学、心理学、医学、生物学、商業、気候学、物理学、計算神経科学、運用管理、金融など、さまざまな分野で使用されてきました。

何かを行うための最適な方法を見つけることを伴うネットワークの問題は、組み合わせ最適化という名前で研究されています。例としては、ネットワークフロー、最短経路問題、輸送問題、積み替え問題、場所問題、マッチング問題、割り当て問題、梱包問題、ルーティング問題、クリティカルパス分析、PERT (プログラム評価およびレビュー手法) などがあります。

相互依存ネットワークとは、あるネットワークのノードの機能が別のネットワークのノードの機能に依存しているネットワークのことである。自然界では、ネットワークが孤立して現れることはめったになく、むしろ、通常、ネットワークはより大きなシステムの要素であり、その複雑なシステムの要素と相互作用する。このような複雑な依存関係は、互いに重要な影響を及ぼす可能性がある。よく研究されている例として、インフラ ネットワークの相互依存性がある。 ^[47]電力網のノードを形成する発電所は、道路やパイプのネットワークを介して供給される燃料を必要とし、通信ネットワークのノードを介して制御される。輸送ネットワークは機能するために電力ネットワークに依存していないが、通信ネットワークは依存している。このようなインフラ ネットワークでは、電力ネットワークまたは通信ネットワークのいずれかの重要な数のノードが機能しなくなると、システム全体に連鎖的な障害が発生し、システム全体の機能に壊滅的な結果をもたらす可能性がある。^[48] 2 つのネットワークを個別に扱うと、この重要なフィードバック効果は見られず、ネットワークの堅牢性の予測は大幅に過大評価されることになる。

• ネットワークサイエンス入門、F. Menczer 、S . Fortunato、CA Davis。（ケンブリッジ大学出版局、2020年）。ISBN 9781108471138。チュートリアル、データセット、その他のリソースを含むGitHubサイト 
• 「つながり: 6 度の力」、https://web.archive.org/web/20111006191031/http://ivl.slis.indiana.edu/km/movies/2008-talas-connected.mov
• Cohen, R.; Erez, K. (2000). 「ランダムな故障に対するインターネットの回復力」. Phys. Rev. Lett . 85 (21): 4626–4628. arXiv : cond-mat/0007048 . Bibcode :2000PhRvL..85.4626C. CiteSeerX  10.1.1.242.6797 . doi :10.1103/physrevlett.85.4626. PMID  11082612. S2CID 15372152. 2013-05-12 にオリジナルからアーカイブ。2011-04-12 に取得。
• Pu, Cun-Lai; Wen-; Pei, Jiang; Michaelson, Andrew (2012). 「ネットワーク制御可能性の堅牢性分析」(PDF) . Physica A . 391 (18): 4420–4425. Bibcode :2012PhyA..391.4420P. doi :10.1016/j.physa.2012.04.019. 2016-10-13 にオリジナル(PDF)からアーカイブ。2013-09-18に取得。
• SN Dorogovtsev および JFF Mendes、「ネットワークの進化: 生物学的ネットワークからインターネットと WWW へ」、オックスフォード大学出版局、2003 年、ISBN 0-19-851590-1 
• リンク: ネットワークの新しい科学、A.-L. Barabási (Perseus Publishing、ケンブリッジ)
• 『スケールフリーネットワーク』、G. カルダレッリ（オックスフォード大学出版局、オックスフォード）
• ネットワーク科学、将来の陸軍への応用のためのネットワーク科学委員会、国立研究会議。2005年。全米アカデミー出版（2005年）ISBN 0-309-10026-7 
• ネットワーク科学速報、USMA (2007) ISBN 978-1-934808-00-9 
• ネットワークの構造とダイナミクスMark Newman、Albert-László Barabási、Duncan J. Watts (プリンストン プレス、2006) ISBN 0-691-11357-2 
• 複雑ネットワーク上の動的プロセス、アラン・バラット、マルク・バルテルミー、アレッサンドロ・ヴェスピニャーニ（ケンブリッジ大学出版、2008年）ISBN 978-0-521-87950-7 
• ネットワークサイエンス：理論と応用、テッド・G・ルイス（Wiley、2009年3月11日）ISBN 0-470-33188-7 
• ネクサス：小さな世界と画期的なネットワーク理論、マーク・ブキャナン（WWノートン＆カンパニー、2003年6月）ISBN 0-393-32442-7 
• 6つの度合い: つながる時代の科学、ダンカン・J・ワッツ（WWノートン・アンド・カンパニー、2004年2月17日）ISBN 0-393-32542-3