ネットワーク科学（ネットワークかがく、）は、電気通信ネットワーク、コンピュータネットワーク、生物学的ネットワーク、認知的ネットワークや意味ネットワーク、社会的ネットワークなどの複雑ネットワークを研究対象とする学問分野であり、個別の要素や主体をノード（あるいは頂点）として表し、要素や主体間のつながりをリンク（あるいは辺）として捉える。この分野は、数学のグラフ理論、物理学の統計力学、計算機科学のデータマイニングや情報可視化、統計学の推測モデリング、社会学の社会構造といった理論と手法を取り入れている。アメリカ国立研究評議会は、ネットワーク科学を「物理的・生物学的・社会的現象のネットワーク表現の研究であり、これらの現象の予測モデルにつながるもの」と定義している。
背景と歴史
ネットワークの研究は、複雑な関係データを分析する手段として、さまざまな学問分野で発展してきた。この分野で最も古い論文として知られているのは、レオンハルト・オイラーが1736年に著した有名なケーニヒスベルクの橋の問題である。オイラーによる頂点と辺の数学的記述は、ネットワーク構造における対関係の性質を研究する数学の一分野であるグラフ理論の礎となった。グラフ理論の分野はその後も発展を続け、化学への応用も見出された。
ハンガリーの数学者・教授であったデネス・ケーニヒは、1936年に『有限および無限グラフの理論』と題するグラフ理論に関する最初の書物を著した。
1930年代、ゲシュタルト心理学の系譜に連なる心理学者ヤコブ・モレノがアメリカ合衆国に渡った。彼はソシオグラムを考案し、1933年4月、医学者の会議でこれを公表した。モレノは「ソシオメトリーの登場以前は、集団の対人関係構造が『正確に』どのようなものかを知る者はいなかった」と主張した。このソシオグラムは、ある小学校の児童集団の社会構造を表したものであった。男子は男子同士、女子は女子同士で友人関係を結んでいたが、ただ一人の男子だけが、ある女子を好きだと述べていた例外があった。その気持ちは相手に返されていなかった。この社会構造のネットワーク表現は非常に興味深いものとされ、ニューヨーク・タイムズ紙にも掲載された。このソシオグラムはその後さまざまな応用を見出し、社会ネットワーク分析という分野へと発展していった。
ネットワーク科学における確率論は、グラフ理論から派生する形で、ポール・エルデシュとレーニ・アルフレードによるランダムグラフに関する8本の著名な論文とともに発展した。社会ネットワークについては、指数ランダムグラフモデル（あるいはp*）が、社会ネットワークにおいて2者間の結びつきが生じる確率空間を表現するための記法的枠組みとして用いられる。ネットワークの確率構造に対する別のアプローチとして、ネットワーク確率行列があり、これはあるネットワークの標本において辺が過去に存在したか否かに基づいて、ネットワーク中に辺が生じる確率をモデル化するものである。
2000年前後、さまざまなネットワーク位相構造を記述する新たな数学的枠組みをもたらす発見が相次ぎ、ネットワークへの関心が爆発的に高まった。これが「ネットワーク科学」という用語の由来となった。バラバーシ・アルベルト・ラースローとレカ・アルバートは、WWWから細胞に至るまで、多くの現実のネットワークが持つスケールフリーネットワーク性を発見した。スケールフリー性とは、現実のネットワークにおいて、次数の小さい多数の頂点とハブが共存するという事実を捉えたものであり、両者はこのスケールフリーな状態の起源を説明する動的モデルを提示した。とりわけ社会的ネットワークは、弱い意味でのスケールフリー性を示す傾向がある。ダンカン・ワッツとスティーヴン・ストロガッツは、ネットワークに関する実証データと数学的表現とを整合させ、スモールワールド・ネットワークを記述した。
ネットワークの分類 決定論的ネットワーク 決定論的ネットワークの定義は、確率論的ネットワークの定義と対比して定義される。重みなしの決定論的ネットワークでは、辺は存在するかしないかのいずれかであり、通常は辺の非存在を0、存在を1で表す。重み付きの決定論的ネットワークでは、辺の値がそれぞれの辺の重み、たとえば結びつきの強さの水準を表す。
確率論的ネットワーク 確率論的ネットワークでは、各辺に付随する値がその辺の存在の見込みを表す。たとえば、ある辺の値が0.9であれば、その辺が存在する確率は0.9であるという。
ネットワークの特性 多くの場合、ネットワークにはその性質や特徴を分析するために計算できる特定の属性がある。これらのネットワーク特性の振る舞いはしばしばネットワークモデルを規定し、あるモデルが他のモデルとどのように対比されるかを分析するために用いられる。ネットワーク科学で用いられる他の用語の定義の多くは、グラフ理論の用語一覧で見ることができる。
規模 ネットワークの規模とは、ノード数 、あるいは（頻度は下がるが）辺の数 を指すことがあり、これは（多重辺のない連結グラフの場合）（木構造）から （完全グラフ）までの範囲を取り得る。単純グラフ（各頂点対の間に高々1本の（無向）辺しか存在せず、頂点が自分自身とはつながらないネットワーク）の場合、 となる。有向グラフ（自己結合ノードなし）では 、自己結合を許す有向グラフでは となる。頂点対の間に複数の辺が存在しうるグラフの場合、 となる。
密度 ネットワークの密度 は、 個のノードを持つネットワークにおいて存在しうる辺の数に対する実際の辺の数 の比を0から1の間で正規化したものとして定義される。ネットワーク密度は、ネットワーク中に存在する「任意の」辺の割合の指標であり、次のように計算できる。
ここで と は、それぞれ 個のノードを持つ連結ネットワークにおける辺の最小数と最大数である。単純グラフの場合、 は二項係数 で与えられ、 であるから、密度は
となる。別の式として があり、ここで結びつき は単方向のものである（Wasserman & Faust 1994）。これは単方向の関係を測定できるため、ネットワーク密度をより適切に把握できる。
平面ネットワーク密度 辺同士の交差がないネットワークの密度 は、 個のノードを持つネットワークにおいて存在しうる辺の数（交差する辺を持たないグラフで与えられ ）に対する辺の数 の比として定義され、 となる。
平均次数 ノードの次数 とは、そのノードに接続する辺の数である。ネットワークの密度と密接に関連するのが平均次数であり、（有向グラフの場合は 。前者の係数2は、無向グラフの各辺が2つの異なる頂点の次数に寄与することに由来する）である。ERランダムグラフモデル（）では、 の期待値（任意の頂点の の期待値に等しい）を計算できる。ランダムに選ばれた頂点はネットワーク中に利用可能な他の 個の頂点を持ち、確率 でそれぞれと接続する。したがって、 となる。
次数分布
次数分布 は、インターネットや社会ネットワークのような現実のネットワークと理論モデルの双方にとって基本的な特性である。ネットワークの次数分布 P(k) は、そのネットワーク中で次数 k を持つノードの割合として定義される。最も単純なネットワークモデル、たとえば（エルデシュ・レーニィモデルによる）ランダムグラフでは、n 個のノードそれぞれが確率 p（あるいは 1 − p）で独立に接続される（あるいはされない）ため、次数 k は二項分布に従う（n が大きい極限ではポアソン分布となる）。しかし、WWWからタンパク質相互作用ネットワークに至るまで、現実のほとんどのネットワークは著しく右に歪んだ次数分布を持つ。すなわち、大多数のノードは低次数である一方、「ハブ」と呼ばれる少数のノードが高次数を持つ。このようなスケールフリーネットワークでは、次数分布はおおむね冪乗則に従う。 ここで γ は次数指数と呼ばれる定数である。このようなスケールフリーネットワークは、次数分布の二次モーメントが発散することに起因する、予期しない構造的・動的性質を持つ。
平均最短経路長（特性経路長） 平均最短経路長は、すべてのノードの対の間の最短経路を求め、そのすべての経路の長さ（経路長とは、経路に含まれる中間の辺の数、すなわちグラフ内の2頂点 間の距離 のこと）の平均を取ることで計算される。これにより、ネットワークのある一員から別の一員に到達するために平均して何ステップ必要かがわかる。あるランダムネットワークモデルの頂点数 の関数として見た平均最短経路長の期待値（すなわち平均最短経路長のアンサンブル平均）の振る舞いは、そのモデルがスモールワールド効果を示すかどうかを規定する。もし に従ってスケールするならば、そのモデルはスモールワールド・ネットワークを生成する。対数を超える速さで増大する場合、そのモデルはスモールワールドを生成しない。 となる特殊な場合は超スモールワールド効果として知られる。
ネットワークの直径 ネットワークグラフを測定するもう一つの方法として、ネットワークの直径を、そのネットワーク中で計算されたすべての最短経路のうち最長のものとして定義できる。これはネットワーク中で最も離れた2つのノード間の最短距離である。言い換えれば、あるノードから他のすべてのノードへの最短経路長を計算した上で、直径はそれらすべての経路長のうち最長のものとなる。直径はネットワークの線形的な大きさを代表する指標である。もしノードA-B-C-Dが接続されているならば、A→Dへ向かう経路の直径は3（3ホップ、3リンク）となる。
クラスタ係数 クラスタ係数は「自分の友人同士も互いに知り合いである」という性質の指標である。これは時に「友人の友人はまた友人である」と説明される。より正確には、あるノードのクラスタ係数とは、そのノードの隣接ノード同士を結ぶ既存のリンク数と、そのようなリンクとして可能な最大数との比である。ネットワーク全体のクラスタ係数は、すべてのノードのクラスタ係数の平均である。ネットワークのクラスタ係数が高いことは、そのネットワークがスモールワールドであることのもう一つの指標である。
番目のノードのクラスタ係数は
で与えられる。ここで は 番目のノードの隣接ノード数、 はそれらの隣接ノード間の結びつきの数である。隣接ノード間に存在しうる結びつきの最大数は、
で与えられる。
確率論的な観点から見ると、局所クラスタ係数の期待値は、同じノードの任意の2つの隣接ノード間にリンクが存在する見込みである。
連結性 ネットワークがどのように連結しているかは、ネットワークがどのように分析・解釈されるかに大きく関わる。ネットワークは次の4つのカテゴリーに分類される。 クリーク／完全グラフ：すべてのノードが他のすべてのノードと接続している、完全に連結したネットワーク。これらのネットワークは、すべてのノードが他のすべてのノードから入リンクと出リンクを持つという意味で対称的である。 巨大成分：ネットワーク中のほとんどのノードを含む単一の連結成分。 弱連結成分：辺の向きを無視すれば、任意のノードから他の任意のノードへの経路が存在するようなノードの集合。 強連結成分：任意のノードから他の任意のノードへの有向経路が存在するようなノードの集合。
ノードの中心性
中心性指標は、あるネットワークモデルにおいて最も重要なノードを特定しようとするランキングを生み出す。異なる中心性指標は、「重要性」という言葉に対して異なる文脈を反映している。たとえば媒介中心性は、あるノードが他の多くのノードの間の橋渡しをしている場合にそのノードを重要とみなす。対照的に固有値中心性は、他の多くの重要なノードからリンクされているノードを重要とみなす。文献中にはこうした指標が何百も提案されている。
中心性指標は、最も重要なノードを特定する上でしか正確ではない。この指標は、それ以外のネットワークのノードについては、意味を持つことがほとんど、あるいはまったくない。また、これらの指標が示す結果は、想定された重要性の文脈の中でのみ正確であり、それ以外の文脈では「見誤る」傾向がある。たとえば、2つの別々のコミュニティがあり、それぞれの中で最も若手のメンバー同士を結ぶ辺だけが両者の唯一のつながりであるとする。一方のコミュニティから他方への移動は必ずこのリンクを経由しなければならないため、この2人の若手メンバーは高い媒介中心性を持つことになる。しかし、彼らは若手であるため（おそらく）自分のコミュニティ内の「重要な」ノードとの結びつきは少なく、そのため固有値中心性はかなり低くなる。
ノードの影響力
中心性指標の限界から、より一般的な指標の開発が進められてきた。 その2つの例として、 ランダムウォークの多様性を用いて、あるノードからネットワークの残りの部分にどれだけ到達しやすいかを測るアクセシビリティ、 そして、あるノードによって生じる感染力の期待値から導かれる期待力（expected force）がある。 これらの指標はいずれも、ネットワークの構造のみから意味のある形で計算できる。
コミュニティ構造
ネットワーク中のノードは、コミュニティを表すグループに分割されることがある。文脈によって、コミュニティは互いに独立している場合もあれば、重なり合う場合もある。典型的には、こうしたコミュニティ内のノードは同じコミュニティ内の他のノードと強く結びついている一方、コミュニティ外のノードとは弱くしか結びついていない。特定のネットワークのコミュニティ構造を記述するグラウンド・トゥルースが存在しない場合、教師あり・教師なしのクラスタリング手法を用いて可能なコミュニティ構造を推定するさまざまなアルゴリズムが開発されてきた。
ネットワークモデル ネットワークモデルは、実証的な複雑ネットワーク内部の相互作用を理解するための土台となる。さまざまなランダムグラフ生成モデルが、現実世界の複雑ネットワークと比較するために用いられるネットワーク構造を生み出す。
エルデシュ・レーニィのランダムグラフモデル
ポール・エルデシュとレーニ・アルフレードにちなんで名付けられたエルデシュ・レーニィモデルは、辺が等しい確率でノード間に設定されるランダムグラフを生成するために用いられる。さまざまな性質を満たすグラフの存在を証明するための確率的手法に用いることができるほか、ある性質がほとんどすべてのグラフについて成り立つとはどういうことかを厳密に定義するためにも用いられる。
エルデシュ・レーニィモデル を生成するには、ノードの総数 と、ランダムに選んだ2つのノードが辺を持つ確率 という2つのパラメータを指定する必要がある。
このモデルは特定のノードに偏りなく生成されるため、次数分布は二項分布に従う。ランダムに選んだ頂点 について、
となる。
このモデルにおいてクラスタ係数はほとんど確実に である。 の振る舞いは3つの領域に分けられる。
劣臨界 ：すべての成分は単純かつ非常に小さく、最大の成分の大きさは である。
臨界 ： である。
超臨界 ： であり、ここで は方程式 の正の解である。
最大の連結成分は複雑性が高い。それ以外の成分はすべて単純かつ小さく である。
構成モデル 構成モデルは、次数列、あるいは次数分布（後にこれを用いて次数列を生成する）を入力として受け取り、次数列以外のあらゆる点でランダムに接続されたグラフを生成する。つまり、ある次数列が与えられたとき、そのグラフは、その次数列を満たすすべてのグラフの集合の中から一様ランダムに選ばれる。ランダムに選ばれた頂点の次数 は、整数値をとる独立同分布の確率変数である。 のとき、構成グラフは無限の大きさを持つ巨大連結成分を含む。残りの成分は有限の大きさを持ち、これはサイズ分布の概念によって定量化できる。ランダムに抽出されたノードが大きさ の成分に属している確率 は、次数分布の畳み込みべきによって与えられる。ここで は次数分布を表し、 である。巨大成分は、すべての辺のうち臨界割合 をランダムに取り除くことで破壊できる。この過程はランダムネットワーク上のパーコレーションと呼ばれる。次数分布の二次モーメントが有限、すなわち であるとき、この臨界辺割合は で与えられ、巨大成分内の平均頂点間距離 は、ネットワークの総サイズに対して対数的にスケールする。すなわち である。
有向構成モデルでは、あるノードの次数は入次数 と出次数 という2つの数で与えられ、したがって次数分布は2変量となる。入辺と出辺の期待数は一致するため、 となる。有向構成モデルが巨大成分を含むための必要十分条件は、である。なお と は等しいため、この不等式の中では互いに置き換えて用いることができる点に注意する。ランダムに選ばれた頂点が大きさ の成分に属する確率は、次のように与えられる。これは入成分についてのものであり、
は出成分についてのものである。
ワッツ・ストロガッツ・スモールワールドモデル
ワッツ・ストロガッツ・モデルは、スモールワールド性を持つグラフを生成するランダムグラフ生成モデルである。
ワッツ・ストロガッツ・モデルを生成するには、まず初期格子構造を用いる。ネットワーク中の各ノードは、最初は最も近い 個の隣接ノードにリンクしている。もう一つのパラメータとしてリワイヤリング確率が指定される。各辺は、確率 でグラフ中のランダムな辺として配線し直される。このモデルで配線し直されるリンクの期待数は である。
ワッツ・ストロガッツ・モデルは非ランダムな格子構造から出発するため、非常に高いクラスタ係数と、それに伴う高い平均経路長を持つ。配線し直しが行われるたびに、高く連結したクラスタ間にショートカットが生まれやすくなる。リワイヤリング確率が高くなるにつれて、クラスタ係数は平均経路長よりもゆっくりと減少していく。その結果、クラスタ係数がわずかに低下するだけで、ネットワークの平均経路長を大きく減少させることができる。p の値が大きいほど、より多くの辺が配線し直され、結果としてワッツ・ストロガッツ・モデルはランダムネットワークに近づいていく。
バラバシ・アルバート（BA）優先的選択モデル
バラバシ・アルバートモデルは、優先的選択、すなわち「富める者はますます富む」効果を示すために用いられるランダムネットワークモデルである。このモデルでは、辺はより高次数のノードに接続される可能性が高い。 ネットワークは m0 個のノードからなる初期ネットワークから始まる。m0 ≥ 2 であり、初期ネットワーク中の各ノードの次数は少なくとも1でなければならない。さもなければ、そのノードはネットワークの残りの部分から常に切り離されたままになってしまう。
BAモデルでは、新しいノードが1つずつネットワークに追加されていく。各新規ノードは、既存のノードがすでに持つリンク数に比例した確率で、 個の既存ノードに接続される。形式的には、新規ノードがノード i に接続される確率 pi は
で与えられる。ここで ki はノード i の次数である。多くリンクされたノード（「ハブ」）はさらに多くのリンクを急速に蓄積する傾向がある一方、リンク数がわずかなノードは新しいリンクの接続先として選ばれにくい。新しいノードは、すでに多くリンクされたノードに接続する「選好」を持つ。
BAモデルから得られる次数分布はスケールフリーであり、特に大きな次数については次の形の冪乗則になる。
ハブは高い媒介中心性を示し、これによりノード間に短い経路が存在できる。その結果、BAモデルは非常に短い平均経路長を持つ傾向がある。このモデルのクラスタ係数も0に近づく傾向がある。
バラバシ・アルバートモデルは無向ネットワーク向けに開発されたもので、スケールフリー性の普遍性を説明することを目的としており、さまざまな種類のネットワークや応用に適用されてきた。このモデルの有向版はプライスモデルであり、これは引用ネットワークのみを対象として開発された。
非線形優先的選択
非線形優先的選択（NLPA）では、ネットワーク中の既存のノードは、ノード次数を一定の正のべき乗 したものに比例して新しい辺を得る。形式的には、ノード が新しい辺を得る確率は次のように表される。
の場合、NLPAはBAモデルに帰着し、「線形」と呼ばれる。 の場合、NLPAは「劣線形」と呼ばれ、ネットワークの次数分布は伸長指数分布に近づく傾向がある。 の場合、NLPAは「優線形」と呼ばれ、少数のノードがほぼすべての他のノードと接続するようになる。 と のいずれの場合も、系のサイズが無限大になる極限ではネットワークのスケールフリー性は失われる。しかし、 が1よりわずかに大きいだけの場合、NLPAは一時的にスケールフリーに見える次数分布をもたらすことがある。
フィットネスモデル 頂点の性質を主要な要素とする別のモデルが、カルダレッリらによって導入されているCaldarelli G., A. Capocci, P. De Los Rios, M.A. Muñoz, Physical Review Letters 89, 258702 (2002)。ここでは、2つの頂点 の間のリンクは、両頂点のフィットネスの結合関数 によって与えられる確率で生成される。 頂点iの次数は次で与えられるServedio V.D.P., G. Caldarelli, P. Buttà, Physical Review E 70, 056126 (2004)。
が の可逆かつ単調増加な関数であるならば、 確率分布 は次で与えられる。
その結果、フィットネス が冪乗則に従って分布していれば、ノードの次数もまた冪乗則に従う。
やや直感には反するが、 のような急速に減衰する確率分布と、次のような結合関数
を組み合わせても（ は定数、 はヘヴィサイド関数）、 やはりスケールフリーネットワークが得られる。
このモデルは、各ノード のフィットネスとしてGDPを用い、次のような結合関数Garlaschelli D., M I Loffredo Physical Review Letters 93, 188701 (2004)Cimini G., T. Squartini, D. Garlaschelli and A. Gabrielli, Scientific Reports 5, 15758 (2015) を用いることで、国家間の貿易を記述するのに成功裏に応用されてきた。
指数ランダムグラフモデル
指数型分布族ランダムグラフモデル（ERGM）は、社会ネットワークやその他のネットワークから得られたデータを分析するための統計モデルの一群である。指数型分布族は、ネットワークに限らず多くの種類のデータを扱う広範なモデルの族である。ERGMは、この族に属し、ネットワークを記述するモデルである。
ここでは、 個のノードの集合と、ノード対 によって添字付けられた結びつき（tie）変数の集合 によって、ランダムグラフ を表す記法を採用する。ここでノード が辺で結ばれていれば 、そうでなければ である。
ERGMの基本的な仮定は、観測されたグラフ の構造は、観測されたネットワーク（場合によってはノードの属性）の関数である十分統計量のベクトル によって説明できるというものである。ERGMにおけるグラフ の確率は次のように定義される。
ここで は に対応するモデルパラメータのベクトルであり、 は正規化定数である。
ネットワーク分析
社会ネットワーク分析 社会ネットワーク分析は、社会的な主体間の関係の構造を検討するWasserman, Stanley and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.。これらの主体は個人であることが多いが、集団、組織、国民国家、ウェブサイト、学術出版物などである場合もある。
1970年代以降、ネットワークの実証研究は社会科学において中心的な役割を果たしており、ネットワーク研究に用いられる数学的・統計学的手法の多くは、まず社会学の中で開発されてきたNewman, M.E.J. Networks: An Introduction. Oxford University Press. 2010, 。数多くの応用の中でも、社会ネットワーク分析はイノベーション、ニュース、噂の伝播を理解するために用いられてきた。同様に、疾病と健康関連の行動の両方の広がりを調べるためにも用いられてきた。また、市場の研究にも応用され、交換関係における信頼の役割や、価格設定における社会的メカニズムの役割を調べるために用いられてきた。同様に、政治運動や社会組織への参加動員の研究にも用いられてきた。科学的な意見対立や学術的な威信を概念化するためにも用いられてきた。さらに近年では、ネットワーク分析（およびその近縁分野である通信解析）は軍事情報の分野で大きく用いられるようになり、階層的・指導者なき反乱ネットワークの両方を暴くために使われている。犯罪学では、犯罪組織における有力な人物、犯罪者の動向、共犯関係を特定し、犯罪行為を予測して政策立案を行うために用いられている。
動的ネットワーク分析 動的ネットワーク分析は、複雑な社会技術システムの効果における、異なる種類の主体間の関係構造の変遷を検討するものであり、新しい集団・話題・指導者の出現といった社会的な安定性や変化を反映するGross, T. and Sayama, H. (Eds.). 2009. Adaptive Networks: Theory, Models and Applications. Springer.Holme, P. and Saramäki, J. 2013. Temporal Networks. Springer.Xanthos, Aris, Pante, Isaac, Rochat, Yannick, Grandjean, Martin (2016). Visualising the Dynamics of Character Networks. In Digital Humanities 2016: Jagiellonian University & Pedagogical University, Kraków, pp. 417–419.。動的ネットワーク分析は、複数種類のノード（主体）と複数種類のリンクから構成されるメタネットワークに焦点を当てる。これらの主体はきわめて多様であり得る。例としては、人物、組織、話題、資源、業務、出来事、場所、信念などが挙げられる。
動的ネットワークの手法は、時間経過に伴うネットワークの傾向や変化を評価したり、新たに現れる指導者を特定したり、人物と思想の共進化を検討したりするのに特に有用である。
生物学的ネットワーク分析 近年、公開されている大量高スループット生物学データが爆発的に増加したことにより、分子ネットワークの分析への関心が高まっている。この文脈での分析は社会ネットワーク分析と密接に関連しているが、ネットワーク中の局所的なパターンに焦点を当てることが多い。たとえば、ネットワークモチーフとは、ネットワーク中に過剰に出現する小さな部分グラフのことである。アクティビティモチーフは、ネットワーク構造から見て過剰に出現する、ノードや辺の属性における同様のパターンである。生物学的ネットワークの分析は、疾患がインターアクトームに与える影響を検討するネットワーク医学の発展をもたらした。
意味ネットワーク分析