ネットワーク科学

ネットワーク科学（ネットワークかがく、テンプレート:Lang-en-short）は、電気通信ネットワーク、コンピュータネットワーク、生物学的ネットワーク、認知的ネットワークや意味ネットワーク、社会的ネットワークなどの複雑ネットワークを研究対象とする学問分野であり、個別の要素や主体をノード（あるいは頂点）として表し、要素や主体間のつながりをリンク（あるいは辺）として捉える。この分野は、数学のグラフ理論、物理学の統計力学、計算機科学のデータマイニングや情報可視化、統計学の推測モデリング、社会学の社会構造といった理論と手法を取り入れている。アメリカ国立研究評議会は、ネットワーク科学を「物理的・生物学的・社会的現象のネットワーク表現の研究であり、これらの現象の予測モデルにつながるもの」と定義している。

背景と歴史

ネットワークの研究は、複雑な関係データを分析する手段として、さまざまな学問分野で発展してきた。この分野で最も古い論文として知られているのは、レオンハルト・オイラーが1736年に著した有名なケーニヒスベルクの橋の問題である。オイラーによる頂点と辺の数学的記述は、ネットワーク構造における対関係の性質を研究する数学の一分野であるグラフ理論の礎となった。グラフ理論の分野はその後も発展を続け、化学への応用も見出された。

ハンガリーの数学者・教授であったデネス・ケーニヒは、1936年に『有限および無限グラフの理論』と題するグラフ理論に関する最初の書物を著した。

モレノによる小学1年生クラスのソシオグラム。

1930年代、ゲシュタルト心理学の系譜に連なる心理学者ヤコブ・モレノがアメリカ合衆国に渡った。彼はソシオグラムを考案し、1933年4月、医学者の会議でこれを公表した。モレノは「ソシオメトリーの登場以前は、集団の対人関係構造が『正確に』どのようなものかを知る者はいなかった」と主張した。このソシオグラムは、ある小学校の児童集団の社会構造を表したものであった。男子は男子同士、女子は女子同士で友人関係を結んでいたが、ただ一人の男子だけが、ある女子を好きだと述べていた例外があった。その気持ちは相手に返されていなかった。この社会構造のネットワーク表現は非常に興味深いものとされ、ニューヨーク・タイムズ紙にも掲載された。このソシオグラムはその後さまざまな応用を見出し、社会ネットワーク分析という分野へと発展していった。

ネットワーク科学における確率論は、グラフ理論から派生する形で、ポール・エルデシュとレーニ・アルフレードによるランダムグラフに関する8本の著名な論文とともに発展した。社会ネットワークについては、指数ランダムグラフモデル（あるいはp*）が、社会ネットワークにおいて2者間の結びつきが生じる確率空間を表現するための記法的枠組みとして用いられる。ネットワークの確率構造に対する別のアプローチとして、ネットワーク確率行列があり、これはあるネットワークの標本において辺が過去に存在したか否かに基づいて、ネットワーク中に辺が生じる確率をモデル化するものである。

2000年前後、さまざまなネットワーク位相構造を記述する新たな数学的枠組みをもたらす発見が相次ぎ、ネットワークへの関心が爆発的に高まった。これが「ネットワーク科学」という用語の由来となった。バラバーシ・アルベルト・ラースローとレカ・アルバートは、WWWから細胞に至るまで、多くの現実のネットワークが持つスケールフリーネットワーク性を発見した。スケールフリー性とは、現実のネットワークにおいて、次数の小さい多数の頂点とハブが共存するという事実を捉えたものであり、両者はこのスケールフリーな状態の起源を説明する動的モデルを提示した。とりわけ社会的ネットワークは、弱い意味でのスケールフリー性を示す傾向がある。ダンカン・ワッツとスティーヴン・ストロガッツは、ネットワークに関する実証データと数学的表現とを整合させ、スモールワールド・ネットワークを記述した。

ネットワークの分類

決定論的ネットワーク

決定論的ネットワークの定義は、確率論的ネットワークの定義と対比して定義される。重みなしの決定論的ネットワークでは、辺は存在するかしないかのいずれかであり、通常は辺の非存在を0、存在を1で表す。重み付きの決定論的ネットワークでは、辺の値がそれぞれの辺の重み、たとえば結びつきの強さの水準を表す。

確率論的ネットワーク

確率論的ネットワークでは、各辺に付随する値がその辺の存在の見込みを表す。たとえば、ある辺の値が0.9であれば、その辺が存在する確率は0.9であるという。

ネットワークの特性

多くの場合、ネットワークにはその性質や特徴を分析するために計算できる特定の属性がある。これらのネットワーク特性の振る舞いはしばしばネットワークモデルを規定し、あるモデルが他のモデルとどのように対比されるかを分析するために用いられる。ネットワーク科学で用いられる他の用語の定義の多くは、グラフ理論の用語一覧で見ることができる。

規模

ネットワークの規模とは、ノード数 $N$、あるいは（頻度は下がるが）辺の数 $E$ を指すことがあり、これは（多重辺のない連結グラフの場合）$N-1$（木構造）から $E_{max}$（完全グラフ）までの範囲を取り得る。単純グラフ（各頂点対の間に高々1本の（無向）辺しか存在せず、頂点が自分自身とはつながらないネットワーク）の場合、$E_{max}=(\genfrac{}{}{0ex}{}{N}{2})=N(N-1)/2$ となる。有向グラフ（自己結合ノードなし）では $E_{max}=N(N-1)$、自己結合を許す有向グラフでは $E_{max}=N^2$ となる。頂点対の間に複数の辺が存在しうるグラフの場合、$E_{max}=\mathrm{\infty }$ となる。

密度

ネットワークの密度 $D$ は、$N$ 個のノードを持つネットワークにおいて存在しうる辺の数に対する実際の辺の数 $E$ の比を0から1の間で正規化したものとして定義される。ネットワーク密度は、ネットワーク中に存在する「任意の」辺の割合の指標であり、次のように計算できる。 $D=\frac{E-E_{\mathrm{m}\mathrm{i}\mathrm{n}}}{E_{\mathrm{m}\mathrm{a}\mathrm{x}}-E_{\mathrm{m}\mathrm{i}\mathrm{n}}}$ ここで $E_{\mathrm{m}\mathrm{i}\mathrm{n}}$ と $E_{\mathrm{m}\mathrm{a}\mathrm{x}}$ は、それぞれ $N$ 個のノードを持つ連結ネットワークにおける辺の最小数と最大数である。単純グラフの場合、$E_{\mathrm{m}\mathrm{a}\mathrm{x}}$ は二項係数 $(\genfrac{}{}{0ex}{}{N}{2})$ で与えられ、$E_{\mathrm{m}\mathrm{i}\mathrm{n}}=N-1$ であるから、密度は $D=\frac{E-(N-1)}{E_{\mathrm{m}\mathrm{a}\mathrm{x}}-(N-1)}=\frac{2(E-N+1)}{N(N-3)+2}$ となる。別の式として $D=\frac{T-2N+2}{N(N-3)+2},$ があり、ここで結びつき $T$ は単方向のものである（Wasserman & Faust 1994）。これは単方向の関係を測定できるため、ネットワーク密度をより適切に把握できる。

平面ネットワーク密度

辺同士の交差がないネットワークの密度 $D$ は、$N$ 個のノードを持つネットワークにおいて存在しうる辺の数（交差する辺を持たないグラフで与えられ $(E_{max}=3N-6)$）に対する辺の数 $E$ の比として定義され、$D=\frac{E-N+1}{2N-5}.$ となる。

平均次数

ノードの次数 $k$ とは、そのノードに接続する辺の数である。ネットワークの密度と密接に関連するのが平均次数であり、$⟨k⟩=\frac{2E}{N}$（有向グラフの場合は $⟨k⟩=\frac{E}{N}$。前者の係数2は、無向グラフの各辺が2つの異なる頂点の次数に寄与することに由来する）である。ERランダムグラフモデル（$G(N,p)$）では、$⟨k⟩$ の期待値（任意の頂点の $k$ の期待値に等しい）を計算できる。ランダムに選ばれた頂点はネットワーク中に利用可能な他の $N-1$ 個の頂点を持ち、確率 $p$ でそれぞれと接続する。したがって、$𝔼[⟨k⟩]=𝔼[k]=p(N-1)$ となる。

次数分布

次数分布 $P(k)$ は、インターネットや社会ネットワークのような現実のネットワークと理論モデルの双方にとって基本的な特性である。ネットワークの次数分布 P(k) は、そのネットワーク中で次数 k を持つノードの割合として定義される。最も単純なネットワークモデル、たとえば（エルデシュ・レーニィモデルによる）ランダムグラフでは、n 個のノードそれぞれが確率 p（あるいは 1 − p）で独立に接続される（あるいはされない）ため、次数 k は二項分布に従う（n が大きい極限ではポアソン分布となる）。しかし、WWWからタンパク質相互作用ネットワークに至るまで、現実のほとんどのネットワークは著しく右に歪んだ次数分布を持つ。すなわち、大多数のノードは低次数である一方、「ハブ」と呼ばれる少数のノードが高次数を持つ。このようなスケールフリーネットワークでは、次数分布はおおむね冪乗則に従う。$P(k)\sim k^{-\gamma }$ ここで γ は次数指数と呼ばれる定数である。このようなスケールフリーネットワークは、次数分布の二次モーメントが発散することに起因する、予期しない構造的・動的性質を持つ。

平均最短経路長（特性経路長）

平均最短経路長は、すべてのノードの対の間の最短経路を求め、そのすべての経路の長さ（経路長とは、経路に含まれる中間の辺の数、すなわちグラフ内の2頂点 $u,v$ 間の距離 $d_{u,v}$ のこと）の平均を取ることで計算される。これにより、ネットワークのある一員から別の一員に到達するために平均して何ステップ必要かがわかる。あるランダムネットワークモデルの頂点数 $N$ の関数として見た平均最短経路長の期待値（すなわち平均最短経路長のアンサンブル平均）の振る舞いは、そのモデルがスモールワールド効果を示すかどうかを規定する。もし $O(\ln N)$ に従ってスケールするならば、そのモデルはスモールワールド・ネットワークを生成する。対数を超える速さで増大する場合、そのモデルはスモールワールドを生成しない。$O(\ln \ln N)$ となる特殊な場合は超スモールワールド効果として知られる。

ネットワークの直径

ネットワークグラフを測定するもう一つの方法として、ネットワークの直径を、そのネットワーク中で計算されたすべての最短経路のうち最長のものとして定義できる。これはネットワーク中で最も離れた2つのノード間の最短距離である。言い換えれば、あるノードから他のすべてのノードへの最短経路長を計算した上で、直径はそれらすべての経路長のうち最長のものとなる。直径はネットワークの線形的な大きさを代表する指標である。もしノードA-B-C-Dが接続されているならば、A→Dへ向かう経路の直径は3（3ホップ、3リンク）となる。テンプレート:要出典

クラスタ係数

クラスタ係数は「自分の友人同士も互いに知り合いである」という性質の指標である。これは時に「友人の友人はまた友人である」と説明される。より正確には、あるノードのクラスタ係数とは、そのノードの隣接ノード同士を結ぶ既存のリンク数と、そのようなリンクとして可能な最大数との比である。ネットワーク全体のクラスタ係数は、すべてのノードのクラスタ係数の平均である。ネットワークのクラスタ係数が高いことは、そのネットワークがスモールワールドであることのもう一つの指標である。

$i$ 番目のノードのクラスタ係数は

$C_i=\frac{2e_i}{k_i(k_i-1)},$

で与えられる。ここで $k_i$ は $i$ 番目のノードの隣接ノード数、$e_i$ はそれらの隣接ノード間の結びつきの数である。隣接ノード間に存在しうる結びつきの最大数は、

$(\genfrac{}{}{0ex}{}{k}{2})=\frac{k(k-1)}{2}.$

で与えられる。

確率論的な観点から見ると、局所クラスタ係数の期待値は、同じノードの任意の2つの隣接ノード間にリンクが存在する見込みである。

連結性

ネットワークがどのように連結しているかは、ネットワークがどのように分析・解釈されるかに大きく関わる。ネットワークは次の4つのカテゴリーに分類される。

• クリーク／完全グラフ：すべてのノードが他のすべてのノードと接続している、完全に連結したネットワーク。これらのネットワークは、すべてのノードが他のすべてのノードから入リンクと出リンクを持つという意味で対称的である。
• 巨大成分：ネットワーク中のほとんどのノードを含む単一の連結成分。
• 弱連結成分：辺の向きを無視すれば、任意のノードから他の任意のノードへの経路が存在するようなノードの集合。
• 強連結成分：任意のノードから他の任意のノードへの有向経路が存在するようなノードの集合。

ノードの中心性

テンプレート:Main 中心性指標は、あるネットワークモデルにおいて最も重要なノードを特定しようとするランキングを生み出す。異なる中心性指標は、「重要性」という言葉に対して異なる文脈を反映している。たとえば媒介中心性は、あるノードが他の多くのノードの間の橋渡しをしている場合にそのノードを重要とみなす。対照的に固有値中心性は、他の多くの重要なノードからリンクされているノードを重要とみなす。文献中にはこうした指標が何百も提案されている。

中心性指標は、最も重要なノードを特定する上でしか正確ではない。この指標は、それ以外のネットワークのノードについては、意味を持つことがほとんど、あるいはまったくない。また、これらの指標が示す結果は、想定された重要性の文脈の中でのみ正確であり、それ以外の文脈では「見誤る」傾向がある。たとえば、2つの別々のコミュニティがあり、それぞれの中で最も若手のメンバー同士を結ぶ辺だけが両者の唯一のつながりであるとする。一方のコミュニティから他方への移動は必ずこのリンクを経由しなければならないため、この2人の若手メンバーは高い媒介中心性を持つことになる。しかし、彼らは若手であるため（おそらく）自分のコミュニティ内の「重要な」ノードとの結びつきは少なく、そのため固有値中心性はかなり低くなる。

ノードの影響力

テンプレート:Main 中心性指標の限界から、より一般的な指標の開発が進められてきた。 その2つの例として、 ランダムウォークの多様性を用いて、あるノードからネットワークの残りの部分にどれだけ到達しやすいかを測るアクセシビリティ、 そして、あるノードによって生じる感染力の期待値から導かれる期待力（expected force）がある。 これらの指標はいずれも、ネットワークの構造のみから意味のある形で計算できる。

コミュニティ構造

図1：内部の結びつきが密な3つのノード集団と、集団間の疎な結びつきからなる、コミュニティ構造を示す小さなネットワークの模式図。

ネットワーク中のノードは、コミュニティを表すグループに分割されることがある。文脈によって、コミュニティは互いに独立している場合もあれば、重なり合う場合もある。典型的には、こうしたコミュニティ内のノードは同じコミュニティ内の他のノードと強く結びついている一方、コミュニティ外のノードとは弱くしか結びついていない。特定のネットワークのコミュニティ構造を記述するグラウンド・トゥルースが存在しない場合、教師あり・教師なしのクラスタリング手法を用いて可能なコミュニティ構造を推定するさまざまなアルゴリズムが開発されてきた。

ネットワークモデル

ネットワークモデルは、実証的な複雑ネットワーク内部の相互作用を理解するための土台となる。さまざまなランダムグラフ生成モデルが、現実世界の複雑ネットワークと比較するために用いられるネットワーク構造を生み出す。

エルデシュ・レーニィのランダムグラフモデル

このエルデシュ・レーニィモデルは テンプレート:Math 個のノードで生成されている。すべての テンプレート:Mvar 個のノードからなる完全グラフの各辺について乱数が生成され、与えられた確率と比較される。乱数が テンプレート:Mvar より小さければ、そのモデル上に辺が形成される。

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

エルデシュ・レーニィモデル $G(n,p)$ を生成するには、ノードの総数 テンプレート:Mvar と、ランダムに選んだ2つのノードが辺を持つ確率 テンプレート:Mvar という2つのパラメータを指定する必要がある。

このモデルは特定のノードに偏りなく生成されるため、次数分布は二項分布に従う。ランダムに選んだ頂点 $v$ について、

$P(\mathrm{deg}(v)=k)=(\genfrac{}{}{0ex}{}{n-1}{k})p^k(1-p{)}^{n-1-k}.$

となる。

このモデルにおいてクラスタ係数はほとんど確実に テンプレート:Math である。$G(n,p)$ の振る舞いは3つの領域に分けられる。

劣臨界 $np<1$：すべての成分は単純かつ非常に小さく、最大の成分の大きさは $|C_1|=O(\log n)$ である。

臨界 $np=1$：$|C_1|=O(n^{\frac{2}{3}})$ である。

超臨界 $np>1$：$|C_1|\approx yn$ であり、ここで $y=y(np)$ は方程式 $e^{-pny}=1-y$ の正の解である。

最大の連結成分は複雑性が高い。それ以外の成分はすべて単純かつ小さく $|C_2|=O(\log n)$ である。

構成モデル

構成モデルは、次数列、あるいは次数分布（後にこれを用いて次数列を生成する）を入力として受け取り、次数列以外のあらゆる点でランダムに接続されたグラフを生成する。つまり、ある次数列が与えられたとき、そのグラフは、その次数列を満たすすべてのグラフの集合の中から一様ランダムに選ばれる。ランダムに選ばれた頂点の次数 $k$ は、整数値をとる独立同分布の確率変数である。$𝔼[k^2]-2𝔼[k]>0$ のとき、構成グラフは無限の大きさを持つ巨大連結成分を含む。残りの成分は有限の大きさを持ち、これはサイズ分布の概念によって定量化できる。ランダムに抽出されたノードが大きさ $n$ の成分に属している確率 $w(n)$ は、次数分布の畳み込みべきによって与えられる。$$w(n)=\{\begin{array}{cc}\frac{𝔼[k]}{n-1}{u}_1^{\ast n}(n-2),& n>1,\\ u(0)& n=1,\end{array}$$ここで $u(k)$ は次数分布を表し、$u_1(k)=\frac{(k+1)u(k+1)}{𝔼[k]}$ である。巨大成分は、すべての辺のうち臨界割合 $p_c$ をランダムに取り除くことで破壊できる。この過程はランダムネットワーク上のパーコレーションと呼ばれる。次数分布の二次モーメントが有限、すなわち $𝔼[k^2]<\mathrm{\infty }$ であるとき、この臨界辺割合は $p_c=1-\frac{𝔼[k]}{𝔼[k^2]-𝔼[k]}$ で与えられ、巨大成分内の平均頂点間距離 $l$ は、ネットワークの総サイズに対して対数的にスケールする。すなわち $l=O(\log N)$ である。

有向構成モデルでは、あるノードの次数は入次数 $k_{\text{in}}$ と出次数 $k_{\text{out}}$ という2つの数で与えられ、したがって次数分布は2変量となる。入辺と出辺の期待数は一致するため、$𝔼[k_{\text{in}}]=𝔼[k_{\text{out}}]$ となる。有向構成モデルが巨大成分を含むための必要十分条件は、$$2𝔼[k_{\text{in}}]𝔼[k_{\text{in}}{k}_{\text{out}}]-𝔼[k_{\text{in}}]𝔼[k_{\text{out}}^2]-𝔼[k_{\text{in}}]𝔼[k_{\text{in}}^2]+𝔼[k_{\text{in}}^2]𝔼[k_{\text{out}}^2]-𝔼[k_{\text{in}}{k}_{\text{out}}{]}^2>0.$$である。なお $𝔼[k_{\text{in}}]$ と $𝔼[k_{\text{out}}]$ は等しいため、この不等式の中では互いに置き換えて用いることができる点に注意する。ランダムに選ばれた頂点が大きさ $n$ の成分に属する確率は、次のように与えられる。$$h_{\text{in}}(n)=\frac{𝔼[k_{in}]}{n-1}{\tilde{u}}_{\text{in}}^{\ast n}(n-2),n>1,{\tilde{u}}_{\text{in}}=\frac{k_{\text{in}}+1}{𝔼[k_{\text{in}}]}\sum _{k_{\text{out}}\ge 0}u(k_{\text{in}}+1,k_{\text{out}}),$$これは入成分についてのものであり、

$h_{\text{out}}(n)=\frac{𝔼[k_{\text{out}}]}{n-1}{\tilde{u}}_{\text{out}}^{\ast n}(n-2),n>1,{\tilde{u}}_{\text{out}}=\frac{k_{\text{out}}+1}{𝔼[k_{\text{out}}]}\sum _{k_{\text{in}}\ge 0}u(k_{\text{in}},k_{\text{out}}+1),$

は出成分についてのものである。

ワッツ・ストロガッツ・スモールワールドモデル

ワッツ・ストロガッツ・モデルは、その構造を実現するために「配線し直し（リワイヤリング）」の概念を用いる。モデルの生成器は、元の格子構造の各辺を順に走査していく。1本の辺は、与えられたリワイヤリング確率に従って、接続する頂点を変える場合がある。この例では $⟨k⟩=4$ である。

ワッツ・ストロガッツ・モデルは、スモールワールド性を持つグラフを生成するランダムグラフ生成モデルである。

ワッツ・ストロガッツ・モデルを生成するには、まず初期格子構造を用いる。ネットワーク中の各ノードは、最初は最も近い $⟨k⟩$ 個の隣接ノードにリンクしている。もう一つのパラメータとしてリワイヤリング確率が指定される。各辺は、確率 $p$ でグラフ中のランダムな辺として配線し直される。このモデルで配線し直されるリンクの期待数は $pE=pN⟨k⟩/2$ である。

ワッツ・ストロガッツ・モデルは非ランダムな格子構造から出発するため、非常に高いクラスタ係数と、それに伴う高い平均経路長を持つ。配線し直しが行われるたびに、高く連結したクラスタ間にショートカットが生まれやすくなる。リワイヤリング確率が高くなるにつれて、クラスタ係数は平均経路長よりもゆっくりと減少していく。その結果、クラスタ係数がわずかに低下するだけで、ネットワークの平均経路長を大きく減少させることができる。p の値が大きいほど、より多くの辺が配線し直され、結果としてワッツ・ストロガッツ・モデルはランダムネットワークに近づいていく。

バラバシ・アルバート（BA）優先的選択モデル

バラバシ・アルバートモデルは、優先的選択、すなわち「富める者はますます富む」効果を示すために用いられるランダムネットワークモデルである。このモデルでは、辺はより高次数のノードに接続される可能性が高い。 ネットワークは m₀ 個のノードからなる初期ネットワークから始まる。m₀ ≥ 2 であり、初期ネットワーク中の各ノードの次数は少なくとも1でなければならない。さもなければ、そのノードはネットワークの残りの部分から常に切り離されたままになってしまう。

BAモデルでは、新しいノードが1つずつネットワークに追加されていく。各新規ノードは、既存のノードがすでに持つリンク数に比例した確率で、$m$ 個の既存ノードに接続される。形式的には、新規ノードがノード i に接続される確率 p_i は

$p_i=\frac{k_i}{\sum _j{k}_j},$

で与えられる。ここで k_i はノード i の次数である。多くリンクされたノード（「ハブ」）はさらに多くのリンクを急速に蓄積する傾向がある一方、リンク数がわずかなノードは新しいリンクの接続先として選ばれにくい。新しいノードは、すでに多くリンクされたノードに接続する「選好」を持つ。

BAモデルの次数分布は冪乗則に従う。対数対数目盛では、冪乗則の関数は直線になる。

BAモデルから得られる次数分布はスケールフリーであり、特に大きな次数については次の形の冪乗則になる。

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

ハブは高い媒介中心性を示し、これによりノード間に短い経路が存在できる。その結果、BAモデルは非常に短い平均経路長を持つ傾向がある。このモデルのクラスタ係数も0に近づく傾向がある。

バラバシ・アルバートモデルは無向ネットワーク向けに開発されたもので、スケールフリー性の普遍性を説明することを目的としており、さまざまな種類のネットワークや応用に適用されてきた。このモデルの有向版はプライスモデルであり、これは引用ネットワークのみを対象として開発された。

非線形優先的選択

非線形優先的選択（NLPA）では、ネットワーク中の既存のノードは、ノード次数を一定の正のべき乗 $\alpha$ したものに比例して新しい辺を得る。形式的には、ノード $i$ が新しい辺を得る確率は次のように表される。

$p_i=\frac{k_i^{\alpha }}{\sum _j{k}_j^{\alpha }}.$

$\alpha =1$ の場合、NLPAはBAモデルに帰着し、「線形」と呼ばれる。$0<\alpha <1$ の場合、NLPAは「劣線形」と呼ばれ、ネットワークの次数分布は伸長指数分布に近づく傾向がある。$\alpha >1$ の場合、NLPAは「優線形」と呼ばれ、少数のノードがほぼすべての他のノードと接続するようになる。$\alpha <1$ と $\alpha >1$ のいずれの場合も、系のサイズが無限大になる極限ではネットワークのスケールフリー性は失われる。しかし、$\alpha$ が1よりわずかに大きいだけの場合、NLPAは一時的にスケールフリーに見える次数分布をもたらすことがある。

フィットネスモデル

頂点の性質を主要な要素とする別のモデルが、カルダレッリらによって導入されている。ここでは、2つの頂点 $i,j$ の間のリンクは、両頂点のフィットネスの結合関数 $f({\eta }_i,{\eta }_j)$ によって与えられる確率で生成される。 頂点iの次数は次で与えられる。

$k({\eta }_i)=N{\int }_0^{\mathrm{\infty }}f({\eta }_i,{\eta }_j)\rho ({\eta }_j)d{\eta }_j$

$k({\eta }_i)$ が ${\eta }_i$ の可逆かつ単調増加な関数であるならば、 確率分布 $P(k)$ は次で与えられる。

$P(k)=\rho (\eta (k))\cdot {\eta }^{\prime }(k)$

その結果、フィットネス $\eta$ が冪乗則に従って分布していれば、ノードの次数もまた冪乗則に従う。

やや直感には反するが、 $\rho (\eta )=e^{-\eta }$ のような急速に減衰する確率分布と、次のような結合関数

$f({\eta }_i,{\eta }_j)=\mathrm{\Theta }({\eta }_i+{\eta }_j-Z)$

を組み合わせても（$Z$ は定数、$\mathrm{\Theta }$ はヘヴィサイド関数）、 やはりスケールフリーネットワークが得られる。

このモデルは、各ノード $i,j$ のフィットネスとしてGDPを用い、次のような結合関数 を用いることで、国家間の貿易を記述するのに成功裏に応用されてきた。

$\frac{\delta {\eta }_i{\eta }_j}{1+\delta {\eta }_i{\eta }_j}.$

指数ランダムグラフモデル

指数型分布族ランダムグラフモデル（ERGM）は、社会ネットワークやその他のネットワークから得られたデータを分析するための統計モデルの一群である。指数型分布族は、ネットワークに限らず多くの種類のデータを扱う広範なモデルの族である。ERGMは、この族に属し、ネットワークを記述するモデルである。

ここでは、$n$ 個のノードの集合と、ノード対 $ij$ によって添字付けられた結びつき（tie）変数の集合 $\{Y_{ij}:i=1,\dots ,n;j=1,\dots ,n\}$ によって、ランダムグラフ $Y\in 𝒴$ を表す記法を採用する。ここでノード $(i,j)$ が辺で結ばれていれば $Y_{ij}=1$、そうでなければ $Y_{ij}=0$ である。

ERGMの基本的な仮定は、観測されたグラフ $y$ の構造は、観測されたネットワーク（場合によってはノードの属性）の関数である十分統計量のベクトル $s(y)$ によって説明できるというものである。ERGMにおけるグラフ $y\in 𝒴$ の確率は次のように定義される。

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

ここで $\theta$ は $s(y)$ に対応するモデルパラメータのベクトルであり、$c(\theta )=\sum _{y^{\prime }\in 𝒴}\exp ({\theta }^{T}s(y^{\prime }))$ は正規化定数である。

ネットワーク分析

社会ネットワーク分析

社会ネットワーク分析は、社会的な主体間の関係の構造を検討する。これらの主体は個人であることが多いが、集団、組織、国民国家、ウェブサイト、学術出版物などである場合もある。

1970年代以降、ネットワークの実証研究は社会科学において中心的な役割を果たしており、ネットワーク研究に用いられる数学的・統計学的手法の多くは、まず社会学の中で開発されてきた。数多くの応用の中でも、社会ネットワーク分析はイノベーション、ニュース、噂の伝播を理解するために用いられてきた。同様に、疾病と健康関連の行動の両方の広がりを調べるためにも用いられてきた。また、市場の研究にも応用され、交換関係における信頼の役割や、価格設定における社会的メカニズムの役割を調べるために用いられてきた。同様に、政治運動や社会組織への参加動員の研究にも用いられてきた。科学的な意見対立や学術的な威信を概念化するためにも用いられてきた。さらに近年では、ネットワーク分析（およびその近縁分野である通信解析）は軍事情報の分野で大きく用いられるようになり、階層的・指導者なき反乱ネットワークの両方を暴くために使われている。犯罪学では、犯罪組織における有力な人物、犯罪者の動向、共犯関係を特定し、犯罪行為を予測して政策立案を行うために用いられている。

動的ネットワーク分析

動的ネットワーク分析は、複雑な社会技術システムの効果における、異なる種類の主体間の関係構造の変遷を検討するものであり、新しい集団・話題・指導者の出現といった社会的な安定性や変化を反映する。動的ネットワーク分析は、複数種類のノード（主体）と複数種類のリンクから構成されるメタネットワークに焦点を当てる。これらの主体はきわめて多様であり得る。例としては、人物、組織、話題、資源、業務、出来事、場所、信念などが挙げられる。

動的ネットワークの手法は、時間経過に伴うネットワークの傾向や変化を評価したり、新たに現れる指導者を特定したり、人物と思想の共進化を検討したりするのに特に有用である。

生物学的ネットワーク分析

近年、公開されている大量高スループット生物学データが爆発的に増加したことにより、分子ネットワークの分析への関心が高まっている。この文脈での分析は社会ネットワーク分析と密接に関連しているが、ネットワーク中の局所的なパターンに焦点を当てることが多い。たとえば、ネットワークモチーフとは、ネットワーク中に過剰に出現する小さな部分グラフのことである。アクティビティモチーフは、ネットワーク構造から見て過剰に出現する、ノードや辺の属性における同様のパターンである。生物学的ネットワークの分析は、疾患がインターアクトームに与える影響を検討するネットワーク医学の発展をもたらした。

意味ネットワーク分析

意味ネットワーク分析はネットワーク分析の一分野であり、ネットワーク中の単語や概念の間の関係に焦点を当てる。単語はノードとして表され、テキスト中でのそれらの近接性や共起はエッジとして表される。したがって意味ネットワークは知識のグラフィカルな表現であり、神経言語学や自然言語処理の応用で広く用いられている。意味ネットワーク分析は、大規模なテキストを分析して主要なテーマや話題を特定する手法としても用いられており（例えばソーシャルメディアの投稿など）、偏り（例えば報道における）を明らかにしたり、さらにはある研究分野全体を地図化したりするためにも用いられている。

リンク分析

リンク分析はネットワーク分析の一部門であり、対象間の関連性を探るものである。一例として、容疑者と被害者の住所、彼らがかけた電話番号、ある期間中に行った金融取引、そしてこれらの人物間の親族関係を、警察の捜査の一環として調べることが挙げられる。リンク分析は、個々の孤立した情報からは明らかでない、異なる種類の対象間の重要な関係や関連性を提供する。コンピュータ支援による、あるいは完全に自動化されたコンピュータベースのリンク分析は、銀行や保険会社による詐欺検出、通信事業者による通信ネットワーク分析、医療分野における疫学や薬理学、法執行機関による捜査、検索エンジンによる関連性評価（そしてその裏返しとして検索エンジンスパムによるスパムデクシングや事業者による検索エンジン最適化）など、多数の対象間の関係を分析する必要があるあらゆる場面で、ますます用いられるようになっている。

パンデミック分析

SIRモデルは、感染集団の中で世界的なパンデミックの広がりを予測するための、最もよく知られたアルゴリズムの一つである。

感受性者から感染者へ

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

上記の式は、感染集団中の各感受性単位に対する感染の「力」を表しており、テンプレート:Math は当該疾患の感染率に相当する。

感染集団中の感受性者数の変化を追跡すると、

$\mathrm{\Delta }S=\beta \times S\frac{1}{N}\mathrm{\Delta }t$

となる。

感染者から回復者へ

$\mathrm{\Delta }I=\mu I\mathrm{\Delta }t$

時間の経過とともに、感染者数は、指定された回復率（$\mu$ で表されるが、平均感染期間 $\frac{1}{\tau }$ の逆数として差し引かれる）、感染性を持つ個体数 $I$、時間の変化 $\mathrm{\Delta }t$ によって変動する。

感染期間

SIRモデルに関して、ある集団がパンデミックに陥るかどうかは、$R_0$、すなわち「感染した1個体が感染させる平均人数」の値に左右される。

$R_0=\beta \tau =\frac{\beta }{\mu }$

ウェブリンク分析

いくつかのウェブ検索のランキングアルゴリズムは、リンクに基づく中心性指標を用いている。(登場順に) マルキオリのハイパーサーチ、GoogleのPageRank、クラインバーグのHITSアルゴリズム、CheiRankおよびTrustRankアルゴリズムなどがそれにあたる。リンク分析は、ウェブページの集合の構造から情報を理解・抽出するために、情報科学やコミュニケーション科学でも行われている。たとえば、政治家のウェブサイトやブログ間の相互リンクの分析などがそれにあたる。

ページランク

PageRankは、「ノード」すなわちウェブサイトをランダムに選び、ある確率で他のノードへ「ランダムジャンプ」することによって機能する。これらの他のノードへのランダムジャンプによって、周辺に存在し通常であれば容易に評価されないようなウェブページも含めて、ネットワーク全体をくまなく探索することができる。

各ノード $x_i$ のPageRankは、i にリンクしているページ j について、j の外リンク数（「出次数」）の逆数と j の「重要度」すなわちPageRankとを掛け合わせたものの総和として定義される。

$x_i=\sum _{j\to i}\frac{1}{N_j}{x}_j^{(k)}$

ランダムジャンプ

上述の通り、PageRankはインターネット上のすべてのウェブサイトにPageRankを割り当てるためにランダムジャンプを利用する。これらのランダムジャンプによって、幅優先探索や深さ優先探索といった通常の探索手法では見つからないようなウェブサイトも発見される。

PageRankを決定するための前述の式に対する改良として、これらのランダムジャンプの要素が加えられている。ランダムジャンプがなければ、一部のページのPageRankは0になってしまい、望ましくない。

第一の要素は $\alpha$、すなわちランダムジャンプが発生する確率である。それと対をなすのが「減衰係数」、すなわち $1-\alpha$ である。

$R(p)=\frac{\alpha }{N}+(1-\alpha )\sum _{j\to i}\frac{1}{N_j}{x}_j^{(k)}$

これを別の見方で表すと、

$R(A)=\sum \frac{R_B}{B_{\text{(outlinks)}}}+\cdots +\frac{R_n}{n_{\text{(outlinks)}}}$

となる。

中心性指標

グラフ中のノードやリンクの相対的な重要性に関する情報は、社会学などの分野で広く用いられる中心性指標によって得ることができる。中心性指標は、ネットワーク分析が「ネットワーク中のすべて、あるいはほとんどのノードにメッセージや情報を広めるには、どのノードを標的にすべきか」、あるいは逆に「疾病の広がりを抑えるにはどのノードを標的にすべきか」といった問いに答える必要がある場合に不可欠である。形式的に確立された中心性の指標としては、次数中心性、近接中心性、媒介中心性、固有ベクトル中心性、カッツ中心性がある。ネットワーク分析の目的によって、一般にどの種類の中心性指標を用いるべきかが決まる。

• 次数中心性とは、ネットワーク中のあるノードに接続している辺（頂点）の数である。
• 近接中心性は、あるノードとネットワーク中の他のすべてのノードとの間の最短距離（測地線経路）の総和を測定することで、そのノードが他のノードにどれだけ「近い」かを決定する。
• 媒介中心性は、あるノードを通ってネットワーク中の他のノードへ流れるトラフィック量を測定することで、そのノードの相対的な重要性を決定する。これは、ノードの対すべてを結ぶ経路のうち、着目するノードを含む経路の割合を測定することによって行われる。グループ媒介中心性は、あるノード群を通って流れるトラフィック量を測定する。
• 固有ベクトル中心性は、次数中心性をより高度にしたものであり、あるノードの中心性は、そのノードに接続する辺の数だけでなく、それらの辺の質にも依存する。この質の要因は、ネットワークの隣接行列の固有ベクトルによって決定される。
• カッツ中心性は、あるノードと、ネットワーク中の（到達可能な）すべてのノードとの間の測地線経路の総和によって測定される。これらの経路は重み付けされており、そのノードとすぐ近くの隣接ノードを結ぶ経路は、すぐ近くの隣接ノードよりも遠いノードと結ぶ経路よりも高い重みを持つ。

ネットワーク中でのコンテンツの拡散

複雑ネットワーク中のコンテンツは、保存的拡散と非保存的拡散という2つの主要な方法で広がりうる。保存的拡散では、複雑ネットワークに入るコンテンツの総量は、そこを通過する間、一定に保たれる。保存的拡散のモデルは、一定量の水を入れた水差しから、管でつながれた一連の漏斗へと水を注ぐ様子として最もよく表される。水差しは発生源を表し、水は拡散するコンテンツを表す。漏斗と接続する管は、それぞれノードとノード間の接続を表す。水がある漏斗から別の漏斗へと移っていくにつれて、それ以前に水にさらされていた漏斗からは水が即座に消え去る。非保存的拡散では、複雑ネットワークに入り、それを通過する間にコンテンツが変化する。非保存的拡散のモデルは、管でつながれた一連の漏斗を通して、絶え間なく流れ続ける蛇口として最もよく表される。この場合、発生源からの水の量は無限である。また、水にさらされた漏斗は、その水が後続の漏斗へ移っていった後も水にさらされ続ける。非保存モデルは、ほとんどの感染症の伝播を説明するのに最も適している。

SIRモデル

1927年、W. O. カーマックとA. G. マッケンドリックは、感受性者 $S(t)$、感染者 $I(t)$、回復者 $R(t)$ という3つの区画のみを持つ固定集団を考えたモデルを構築した。このモデルで用いられる区画は次の3つのクラスからなる。

• $S(t)$ は、時刻tにおいてまだ疾病に感染していない、すなわち疾病に対して感受性を持つ個体の数を表す。
• $I(t)$ は、疾病に感染しており、感受性を持つ個体に疾病を広げることができる個体の数を表す。
• $R(t)$ は、感染した後に疾病から回復した個体のための区画である。この区画の個体は、再び感染したり、他者に感染を広げたりすることはない。

このモデルの流れは次のように考えることができる。

$𝒮\to ℐ\to ℛ$

固定された集団 $N=S(t)+I(t)+R(t)$ を用いて、カーマックとマッケンドリックは次の方程式を導出した。

$\begin{array}{cc}\frac{dS}{dt}& =-\beta SI\\ \frac{dI}{dt}& =\beta SI-\gamma I\\ \frac{dR}{dt}& =\gamma I\end{array}$

これらの方程式の定式化にあたっては、いくつかの仮定が置かれた。第一に、集団中のある個体は、他のどの個体とも等しい確率で、率 $\beta$（これは疾病の接触率あるいは感染率とみなされる）で疾病に感染すると考えなければならない。したがって、ある感染者は単位時間あたり $\beta N$ 人と接触して疾病を伝播させることができ、感染者が感受性者と接触する割合は $S/N$ である。したがって、単位時間あたり感染者1人につき生じる新規感染者数は $\beta N(S/N)$ となり、新規感染（すなわち感受性者区画から離脱する者）の率は $\beta N(S/N)I=\beta SI$ となる（Brauer & Castillo-Chavez, 2001）。第二・第三の方程式については、感受性者クラスを離脱する集団は感染者クラスに入る集団と等しいと考える。ただし、感染者は単位時間あたり率 $\gamma$（ここで $\gamma$ は平均回復率、すなわち $1/\gamma$ は平均感染期間を表す）で、このクラスを離れて回復者・除去者クラスに入る。これらの過程が同時に生じることは、テンプレート:仮リンクと呼ばれ、集団中の2つの集団間の接触率はそれぞれの集団の大きさに比例するという広く受け入れられた考え方である（Daley & Gani, 2005）。最後に、感染と回復の率は出生・死亡の時間スケールに比べてはるかに速いと仮定されるため、このモデルではこれらの要因は無視される。

このモデルについては、流行モデルのページでさらに読むことができる。

マスター方程式によるアプローチ

マスター方程式は、各時間ステップで新しいノードが1つ追加され、（無作為に、かつ選好なしに選ばれた）既存のノードにリンクされていくような、無向の成長ネットワークの振る舞いを表現できる。初期ネットワークは、時刻 $t=2$ において2つのノードとその間の2本のリンクによって形成される。この構成は、後の計算を単純化するためだけに必要なものであり、時刻 $t=n$ においてネットワークは $n$ 個のノードと $n$ 本のリンクを持つ。

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

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

ここで $p(k,s,t)$ は、時刻 $t+1$ において、ノード $s$ が次数 $k$ を持つ確率であり、$s$ はこのノードがネットワークに加えられた時間ステップである。既存のノード $s$ が時刻 $t+1$ において次数 $k$ を持つに至る経路は2通りしかないことに注意する。

• ノード $s$ が時刻 $t$ において次数 $k-1$ を持ち、確率 $1/t$ で新規ノードによってリンクされる場合。
• すでに時刻 $t$ において次数 $k$ を持ち、新規ノードによってリンクされない場合。

このモデルを整理すると、次数分布は $P(k)=2^{-k}.$ となる。

この成長ネットワークをもとに、次のような単純な規則に従う流行モデルが構築されている。新規ノードが追加され、リンク先の既存ノードを選んだ後、そのたびに、この新規ノードを感染させるかどうかの決定が行われる。この流行モデルのマスター方程式は次のとおりである。

$p_r(k,s,t)=r_t\frac{1}{t}{p}_r(k-1,s,t)+(1-\frac{1}{t})p_r(k,s,t),$

ここで $r_t$ は感染させる（$r_t=1$）か、させない（$r_t=0$）かの決定を表す。このマスター方程式を解くと、次の解が得られる。${\tilde{P}}_r(k)={\left(\frac{r}{2}\right)}^k.$

多層ネットワーク

多層ネットワークとは、複数種類の関係を持つネットワークのことである。現実世界のシステムを多次元ネットワークとしてモデル化する試みは、社会ネットワーク分析、経済学、歴史学、都市・国際交通、生態学、心理学、医学、生物学、商業、気候学、物理学、計算論的神経科学、オペレーションズマネジメント、金融など、さまざまな分野で行われてきた。

ネットワーク最適化

何らかの事柄を行う最適な方法を見つけることに関わるネットワーク問題は、組合せ最適化という名称の下で研究されている。例としては、ネットワークフロー、最短経路問題、輸送問題、輸送配分問題、立地問題、マッチング問題、割当問題、パッキング問題、ルーティング問題、クリティカルパス分析、PERT（プログラム評価・レビュー技法）などが挙げられる。

相互依存ネットワーク

相互依存ネットワークとは、あるネットワーク中のノードの機能が、別のネットワーク中のノードの機能に依存しているようなネットワークのことである。自然界では、ネットワークが孤立して現れることはまれであり、むしろネットワークは通常、より大きなシステムの要素であり、そのシステム中の他の要素と相互作用する。このような複雑な依存関係は、互いに対して自明でない影響を及ぼしうる。よく研究されている例として、インフラネットワークの相互依存関係がある。電力網のノードを構成する発電所は、道路や配管のネットワークを通じて供給される燃料を必要とし、また通信ネットワークのノードを通じても制御されている。輸送ネットワークは電力ネットワークに機能を依存していないが、通信ネットワークは依存している。このようなインフラネットワークでは、電力ネットワークまたは通信ネットワークのいずれかで、ある臨界数のノードが機能不全に陥ると、システム全体にわたる連鎖的な機能不全を引き起こし、システム全体の機能に壊滅的な結果をもたらす可能性がある。もし2つのネットワークを孤立したものとして扱っていたなら、このような重要なフィードバック効果は見過ごされ、ネットワークの頑健性についての予測は大きく過大評価されることになる。

関連項目

• カスケード障害
• 複雑ネットワークとしての気候
• 協働イノベーションネットワーク
• コミュニケーション生態学
• 複雑ネットワーク
• ネットワークにおけるコア・周辺構造
• デュアルフェーズ進化
• エルデシュ・レーニィモデル
• グラフ理論の用語一覧
• 勾配ネットワーク
• 高次圏論
• 免疫ネットワーク説
• 非正規戦争
• ネットワークアナライザ
• ネットワークダイナミクス
• ネットワーク形成
• リスク評価におけるネットワーク理論
• ネットワーク・トポロジー
• 労働経済学におけるネットワーク
• 非線形優先的選択
• パーコレーション
• パーコレーション理論
• 政策ネットワーク分析
• ポリテリー
• 量子複雑ネットワーク
• ランダムネットワーク
• ソーシャルネットワークにおける噂の拡散
• スケールフリーネットワーク
• 逐次動的システム
• サービスネットワーク
• スモールワールドネットワーク
• 構造的カットオフ
• システム理論

さらに読む

• A First Course in Network Science テンプレート:Webarchive, F. Menczer, S. Fortunato, C.A. Davis. (Cambridge University Press, 2020). テンプレート:ISBN. GitHub site テンプレート:Webarchive（チュートリアル・データセット等を含む）
• "Connected: The Power of Six Degrees," https://web.archive.org/web/20111006191031/http://ivl.slis.indiana.edu/km/movies/2008-talas-connected.mov
• テンプレート:Cite journal
• テンプレート:Cite journal
• S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks: From biological networks to the Internet and WWW, Oxford University Press, 2003, テンプレート:ISBN
• Linked: The New Science of Networks, A.-L. Barabási (Perseus Publishing, Cambridge)
• Scale-Free Networks テンプレート:Webarchive, G. Caldarelli (Oxford University Press, Oxford)
• Network Science テンプレート:Webarchive, Committee on Network Science for Future Army Applications, National Research Council. 2005. The National Academies Press (2005)テンプレート:ISBN
• Network Science Bulletin, USMA (2007) テンプレート:ISBN
• The Structure and Dynamics of Networks Mark Newman, Albert-László Barabási, & Duncan J. Watts (The Princeton Press, 2006) テンプレート:ISBN
• Dynamical processes on complex networks, Alain Barrat, Marc Barthelemy, Alessandro Vespignani (Cambridge University Press, 2008) テンプレート:ISBN
• Network Science: Theory and Applications, Ted G. Lewis (Wiley, March 11, 2009) テンプレート:ISBN
• Nexus: Small Worlds and the Groundbreaking Theory of Networks, Mark Buchanan (W. W. Norton & Company, June 2003) テンプレート:ISBN
• Six Degrees: The Science of a Connected Age, Duncan J. Watts (W. W. Norton & Company, February 17, 2004) テンプレート:ISBN