ネットワーク理論

ネットワーク理論（ネットワークりろん）は、通信、コンピュータ、生物、ソーシャルなどの複雑ネットワークを研究する分野。ネットワークは、ノードやエッジが属性（例：名前）を持つグラフとして定義される。数学のグラフ理論、物理学の統計力学、コンピュータサイエンスのデータマイニングと情報視覚化、統計からの推論モデリング、社会学の社会構造などの理論や手法が使われる。
概論・歴史.
ネットワーク理論は、複雑なデータを解析する手段としてさまざまな分野で言及される。この理論の最初期の論文は、1736年にレオンハルト・オイラーによって書かれた有名な「七つの橋」の問題である。オイラーの頂点と辺による数学的証明はグラフ理論の基礎となった。グラフ理論は発展して化学に応用された。
1930年代、伝統的なゲシュタルト派の心理学者ヤコブ・モレノはアメリカで社会学を発展させ、1933年4月にソシオグラムを医療学者の会で発表した。モレノは「ソシオグラムの出現以前はあるグループでの対人関係の構造が正確にどのようなものか、誰も分かりませんでした。」と発表した。ソシオグラムの例が左の図で、小学1年生の社会的構造の表象である。男子と女子はそれぞれ同性が友達だったが、例外の1人の男子が女子を好きだと言ったが、相互的な関係ではないことが分かる（図を参照）。ソシオグラムは多くの用途を見出しており、社会ネットワーク解析という分野に発展している。
ネットワーク理論における確率論は、ポール・エルドシュとアルフレッド・レニーのランダムグラフに関する8つの有名なグラフ理論の論文から派生した。社会的ネットワークの場合は指数ランダムグラフのモデル（p*）がネットワークで発生する関係の確率空間を表すために使われる。ネットワーク確率論に対する別のアプローチは確率マトリックスである。確率マトリックスは、ネットワークのサンプルに見られるエッジの過去の有無に基づいて、ネットワーク全体に発生するエッジの確率をモデルにする。
1998年にとは、PCANSモデルを用いたメタネットワークの概念を発表し、すべての組織は3つのドメイン：個人・タスク・リソースから構成されるとした。該当の論文によると、ネットワークは複数のドメインにまたがって発生し、相互に関連する。この分野は、ダイナミックネットワーク解析と呼ばれる分野に発展した。
最近の動向としては、ネットワーク理論を使って位相幾何学を数学的に表す取り組みが注目を浴びている。ダンカン・ワッツは、数学的表現を持つネットワーク上で実験データを使ってスモールワールド現象を発表した。バラバーシ・アルベルト・ラースローとは、スケールフリーのネットワークを実現させた。これは多数の接続を持つハブ頂点を含む広義のネットワークトポロジーであり、他のすべてのノードと接続の数の比率が一定に保たれるように成長する。インターネットなどの多くのネットワークはこの側面を維持しているように見えるが、他のネットワークではこの比率はノードの長いテール分布に近似する。
プロパティ.
多くのネットワークには、その特性の解析に使われる性質がある。 これらの特性（プロパティ）は多くの場合、ネットワークモデルを定義することで特定のモデルとの対比の解析に使われる。 ネットワーク科学で使われる用語の定義の多くは、グラフ理論でも使われる。
密度.
ネットワークの密度formula_1は、二項係数formula_2によって得られる、可能なすべての辺の数に対する辺の数formula_3の比率として定義される：formula_4。もう1つの表し方として、formula_5が単方向性である場合は以下のように表せる ：formula_6。この方法では、関係が単方向であるため測定が可能である。
大きさ.
ネットワークの大きさは、ノードformula_7の数か、もしくは（一般的ではないが）エッジformula_3の数で表す。エッジformula_3の数は formula_10 (木) から formula_11 (完全グラフ)までさまざまである。
平均次数.
ノードの次数formula_12とは、そのノードに接続している辺の数である。 ネットワークの密度にも密接に関連する平均次数は、formula_13である。 ERランダムグラフモデルでは、formula_14 を計算できる。ここでは、formula_15は2つのノードが繋がっている確率である。
平均距離.
平均距離（Average path length）は、すべてのノードのペア間の最短距離を見つけて加算し、ペアの総数で割ることで算出される。 これは、ネットワークのあるノードから別のノードに到達するまでの平均のステップの数を表している。
直径.
ネットワークを測定する別の手段として直径が使われる。ネットワークの直径は、ネットワーク内の最短距離のうち最も長いものとして定義される。 これは、ネットワーク内の最も離れた2つのノード間の最短距離となる。 言い換えれば、各ノードから他のすべてのノードまでの最短距離を計算すると、直径はすべての距離のうち最も長いものとなる。 直径は、ネットワークの線形的な大きさを表す。
クラスター係数.
クラスター係数とは、「all-my-friends-know-each-other（すべての友達が互いを知っている）」特性を表す。 「友人の友人は友人である」とも表現される。 ノードのクラスター係数とは、ノードが近隣のノードと互いに実際に存在しているリンクと、可能なリンクの最大数の比率である。 ネットワーク全体でのクラスタ係数は、全ノードのクラスター係数の平均である。 ネットワークのクラスター係数が高いことは、スモール・ワールドであることの指標でもある。formula_16番目のノードのクラスター係数はformula_17と表される。ここでは、formula_18はformula_16番目のノードの隣人の数であり、formula_20はこれらの隣人間のリンクの数である。 隣人間の可能なリンクの最大数は以下のように表される：<math>{\binom {k}{2}} =