ネットワーク理論
ネットワークがどのようにリンクされているかは、解析の解釈の上で重要である。 ネットワークは以下の4つのカテゴリに分類される。
Clique/Complete Graph(完全グラフ):完全にリンクされたネットワークで、すべてのノードが他のすべてのノードにリンクしている。この場合、すべてのノードが他のノードからの入り口と出口を有する点で対称的である。
Giant Component(大きいコンポーネント):ネットワーク内のほとんどのノードとリンクしている一つのノード。
Weakly Connected Component(弱い関連性を持つコンポーネント):エッジの方向性を無視した場合に、どのノードからも他のノードへの道が存在する。
Strongly Connected Component(強い関連性を持つコンポーネント):どのノードからも他のノードへの直接の道が存在する。
ネットワークを測定する別の手段として直径が使われる。ネットワークの直径は、ネットワーク内の最短距離のうち最も長いものとして定義される。 これは、ネットワーク内の最も離れた2つのノード間の最短距離となる。 言い換えれば、各ノードから他のすべてのノードまでの最短距離を計算すると、直径はすべての距離のうち最も長いものとなる。 直径は、ネットワークの線形的な大きさを表す。
ネットワークモデルは、複雑ネットワーク内に起こる相互作用の理解に役立つ。また、ランダムグラフから生成されたネットワーク構造のモデルは実際の複雑ネットワークと見比べられて使われる。
ネットワーク理論は、複雑なデータを解析する手段としてさまざまな分野で言及される。この理論の最初期の論文は、1736年にレオンハルト・オイラーによって書かれた有名な「七つの橋」の問題である。オイラーの頂点と辺による数学的証明はグラフ理論の基礎となった。グラフ理論は発展して化学に応用された。
1930年代、伝統的なゲシュタルト派の心理学者ヤコブ・モレノはアメリカで社会学を発展させ、1933年4月にソシオグラムを医療学者の会で発表した。モレノは「ソシオグラムの出現以前はあるグループでの対人関係の構造が正確にどのようなものか、誰も分かりませんでした。」と発表した。ソシオグラムの例が左の図で、小学1年生の社会的構造の表象である。男子と女子はそれぞれ同性が友達だったが、例外の1人の男子が女子を好きだと言ったが、相互的な関係ではないことが分かる(図を参照)。ソシオグラムは多くの用途を見出しており、社会ネットワーク解析という分野に発展している。
ネットワーク理論における確率論は、ポール・エルドシュとアルフレッド・レニーのランダムグラフに関する8つの有名なグラフ理論の論文から派生した。社会的ネットワークの場合は指数ランダムグラフのモデル(p*)がネットワークで発生する関係の確率空間を表すために使われる。