ネットワーク理論

ウィキペディア

ネットワーク理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/07/23 00:05 UTC 版)

インターネットのネットワーク

ネットワークの例

ネットワーク理論（ネットワークりろん）は、通信、コンピュータ、生物、ソーシャルなどの複雑ネットワークを研究する分野。ネットワークは、ノードやエッジが属性（例：名前）を持つグラフとして定義される。数学のグラフ理論、物理学の統計力学、コンピュータサイエンスのデータマイニングと情報視覚化、統計からの推論モデリング、社会学の社会構造などの理論や手法が使われる。

概論・歴史

七つの橋の問題。

ネットワーク理論は、複雑なデータを解析する手段としてさまざまな分野で言及される。この理論の最初期の論文は、1736年にレオンハルト・オイラーによって書かれた有名な「七つの橋」の問題である。オイラーの頂点と辺による数学的証明はグラフ理論の基礎となった。グラフ理論は発展して化学に応用された。

小学一年生のソシオグラム。

1930年代、伝統的なゲシュタルト派の心理学者ヤコブ・モレノはアメリカで社会学を発展させ、1933年4月にソシオグラムを医療学者の会で発表した。モレノは「ソシオグラムの出現以前はあるグループでの対人関係の構造が正確にどのようなものか、誰も分かりませんでした。」と発表した。ソシオグラムの例が左の図で、小学1年生の社会的構造の表象である。男子と女子はそれぞれ同性が友達だったが、例外の1人の男子が女子を好きだと言ったが、相互的な関係ではないことが分かる（図を参照）。ソシオグラムは多くの用途を見出しており、社会ネットワーク解析という分野に発展している。

ネットワーク理論における確率論は、ポール・エルドシュとアルフレッド・レニーのランダムグラフに関する8つの有名なグラフ理論の論文から派生した。社会的ネットワークの場合は指数ランダムグラフのモデル（p*）がネットワークで発生する関係の確率空間を表すために使われる。ネットワーク確率論に対する別のアプローチは確率マトリックスである。確率マトリックスは、ネットワークのサンプルに見られるエッジの過去の有無に基づいて、ネットワーク全体に発生するエッジの確率をモデルにする。

1998年にデイビッド・クラックハートとキャサリン・カーリーは、PCANSモデルを用いたメタネットワークの概念を発表し、すべての組織は3つのドメイン：個人・タスク・リソースから構成されるとした。該当の論文によると、ネットワークは複数のドメインにまたがって発生し、相互に関連する。この分野は、ダイナミックネットワーク解析と呼ばれる分野に発展した。

最近の動向としては、ネットワーク理論を使って位相幾何学を数学的に表す取り組みが注目を浴びている。ダンカン・ワッツは、数学的表現を持つネットワーク上で実験データを使ってスモールワールド現象を発表した。バラバーシ・アルベルト・ラースローとレカ・アルベルトは、スケールフリーのネットワークを実現させた。これは多数の接続を持つハブ頂点を含む広義のネットワークトポロジーであり、他のすべてのノードと接続の数の比率が一定に保たれるように成長する。インターネットなどの多くのネットワークはこの側面を維持しているように見えるが、他のネットワークではこの比率はノードの長いテール分布に近似する。

プロパティ

多くのネットワークには、その特性の解析に使われる性質がある。 これらの特性（プロパティ）は多くの場合、ネットワークモデルを定義することで特定のモデルとの対比の解析に使われる。 ネットワーク科学で使われる用語の定義の多くは、グラフ理論でも使われる。

密度

無向ネットワークの密度 $D$

This Erdős–Rényi model is generated with N=5 nodes. For each edge in the complete graph formed by all N nodes, a random number is generated and compared to a given probability. If the random number is greater than p, an edge is formed on the model.

Paul ErdősとAlfréd Rényiの名前にちなんだErdős-Rényiモデルは、エッジが等しい確率のノード間に設定されたランダムグラフを生成する。 確率方法で、さまざまなプロパティを満たすグラフの存在を証明したり、多くのグラフに対してあるプロパティが持つ重要性を厳密に定義したりできる。Erdős-Rényiモデルを生成するには2つのパラメータが必要である。1つは、生成されたグラフ内のノード数 N と、ある2つのノード間でリンク p を形成する確率である。E をエッジ数の期待値とすると、 式 ⟨k⟩ = 2 ⋅ E / N = p ⋅ (N − 1) を使って定数 ⟨k⟩ を導き出せる。

Erdős-Rényiモデルには、他のグラフと比べるといくつかの興味深い特徴がある。 このモデルは特定のノードにバイアスをかけずに生成されるため、次数分布は次の式のように二項式となる：

$P(k)={n-1 \choose k}p^{k}(1-p)^{n-1-k}$

The Watts-Strogatz model uses the concept of rewire to achieve its structure.

ワッツ・ストロガッツのランダムグラフモデルは、スモール・ワールド特性を持つグラフを生成するモデルである。このモデルを生成するためにはまず格子構造が必要である。ネットワークの各ノードは、当初は、その $\langle k\rangle$

Barabasi Albertモデルの生成

BAモデルは、優先的アタッチメント（preferential attachment）または「富裕層がより豊かになる」現象を実証できるランダムネットワークモデル。 このモデルでは、エッジはそれより高い度合いのノードに接続する可能性が高い。ネットワークは最初はm₀ 個のノードを持ち、m₀ ≥ 2でネットワークの各ノードの次数は 1以上でなければならない。そうでないと、ネットワークの残りの部分から常に孤立した状態になる。

BAモデルでは、新しいノードが1つずつネットワークに追加される。 各新しいノードは、既存のノードが既に持つリンクの数に比例する確率で、既存のノード $m$

The degree distribution of the BA Model, which follows a power law. In loglog scale the power law function is a straight line.

BAモデルから得られる次数分布はスケールフリーであり、べき乗則で表される：

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

この節の加筆が望まれています。 （2017年1月）

関連項目

• グラフ理論
• 複雑ネットワーク