次数、平均次数、次数分布、隣接行列は、ネットワーク理論において重要な概念です。それぞれについて説明します。
次数 (Degree)
- ノードの次数とは、そのノードに接続されているリンクの数のこと
- 無向ネットワークでは、各ノードの次数は接続されているリンクの総数になる
- 有向ネットワークでは、以下に分けられる
- 入次数（そのノードへ向かうリンクの数）
- 出次数（そのノードから出ていくリンクの数）
平均次数 (Average Degree)
- 平均次数 ⟨k⟩ は、ネットワーク全体のノードの次数の平均値
- 有向ネットワークでは、平均入次数と平均出次数が等しくなる
- 無向ネットワークでは、平均次数は以下の式で計算される
- ⟨k⟩ = (2 × リンクの総数) ÷ ノードの総数
次数分布 (Degree Distribution)
- 次数分布 P(k) は、ネットワーク内でランダムに選択したノードが次数 k を持つ確率
- 多くの現実のネットワークでは、次数分布がべき乗則に従う
- これはスケールフリーネットワークと呼ばれる
隣接行列 (Adjacency Matrix)
- ネットワークの構造を表現する行列
- N 個のノードを持つネットワークの隣接行列 A は、N × N の正方行列で表される
- 隣接行列を使用することで、ネットワークの数学的な表現が可能になり、行列演算を用いたネットワーク分析が行える
最短経路 (Shortest Path)
- ネットワーク内の2つのノード間を結ぶ最短のパスのこと
- パスの長さは、通過するリンクの数（ホップ数）や、リンクに割り当てられた重みの合計で測る
- 最短経路を見つけるアルゴリズムとしては、Dijkstra法やBellman-Ford法など
ネットワーク直径 (Network Diameter)
- ネットワーク内の任意の2つのノード間の最短経路の長さの最大値
- つまり、ネットワーク内で最も離れた2つのノード間の最短経路の長さ
- ネットワーク直径は、ネットワークのサイズや情報伝達の効率性を示す指標の1つ
平均経路長 (Average Path Length)
- ネットワーク内の全ノードペア間の最短経路長の平均値
- ネットワーク内の典型的なノード間の距離を表し、ネットワークの「スモールワールドネットワーク性」を示す指標の1つ
- 平均経路長が小さいネットワークでは、情報がより迅速に伝達されると考えられる
循環 (Cycle)
- ネットワーク内で始点と終点が同じノードであるパスのこと
- あるノードから出発し、他のノードを経由して元のノードに戻ってくるパスを指す
Euler経路 (Eulerian Path)
- ネットワーク内の全てのリンクを一度だけ通過するパスのこと
- 始点と終点が異なる場合はEuler道 (Eulerian Trail)
- 始点と終点が同じ場合はEuler閉路 (Eulerian Circuit)
Hamilton経路 (Hamiltonian Path)
- ネットワーク内の全てのノードを一度だけ通過するパスのこと
- 始点と終点が異なる場合はHamilton道 (Hamiltonian Trail)
- 始点と終点が同じ場合はHamilton閉路 (Hamiltonian Circuit)
幅優先探索アルゴリズム (Breadth-First Search Algorithm, BFS)
- 幅優先探索は、グラフやネットワークの探索アルゴリズムの1つ
- ある始点ノードから出発し、そのノードに隣接する全てのノードを探索してから、さらにその隣接ノードに隣接する全てのノードを探索するという過程を繰り返す
- この探索方法では、始点ノードからの距離が近いノードから順に探索されます。幅優先探索は、最短経路問題や連結成分の発見などに利用される
連結成分 (Connected Component)
- 無向グラフにおいて、
- 連結成分とは、グラフ内の任意の2つのノードが少なくとも1つのパスで結ばれているノードの集合のこと
- 連結成分内のノードは互いに到達可能であり、異なる連結成分のノード間には到達可能なパスが存在しない
- 有向グラフの場合は
- 強連結成分と弱連結成分に分けられます。
- 強連結成分：任意の2つのノード間に双方向のパスが存在する部分グラフ
- 弱連結成分：有向グラフを無向グラフとみなした場合の連結成分
- 強連結成分と弱連結成分に分けられます。
クラスター係数 (Clustering Coefficient)
- ネットワーク内のノードがどの程度密にクラスター化しているかを測る指標
多重グラフ、単純グラフ
- 多重グラフは、2つのノード間に複数のリンクが存在することを許すグラフ
- 単純グラフは、2つのノード間に最大1つのリンクしか存在せず、自己ループも許されないグラフ
完全グラフ
- 全てのノードがお互いにリンクで直接つながっているグラフ
- n個のノードを持つ完全グラフは、n(n-1)/2本のリンクを持つ
重みつきネットワーク
- リンクに重みが割り当てられたネットワーク
- 重みは、リンクの強度、距離、コストなどを表現するために使用される
大域的クラスター係数
- ネットワーク内に存在する三角形の数を、可能な三角形の総数で割った値として定義される
- これは、ネットワーク全体がどの程度クラスター化しているかを表す
巨大連結成分
- ランダムグラフにおいて、ノード数が増加するにつれて突然出現する最大の連結成分を巨大連結成分と呼ぶ
- これは、ランダムグラフのリンク確率がある臨界値を超えると出現する
亜臨界領域、臨界点、超臨界領域
- ランダムグラフにおいて、リンク確率が臨界値より小さい領域を亜臨界領域、臨界値を臨界点、臨界値より大きい領域を超臨界領域と呼ぶ
- 亜臨界領域では巨大連結成分が存在せず、超臨界領域では巨大連結成分が出現する
連結領域
- ランダムグラフにおいて、リンク確率が大きくなるにつれて、孤立したノードや小さな連結成分が減少し、大きな連結成分が形成される領域を連結領域と呼ぶ