← ネットワーク科学 一覧

🎓 レベル：基礎　|　重要度：A（必須）

📎 前提：グラフとは　|　関連：次数・道・連結成分・グラフラプラシアンとスペクトル

要点（BLUF）

• グラフの2大表現は 隣接行列（$n \times n$ の行列）と 隣接リスト（各ノードの隣人リスト）。
• 隣接行列は「2点が繋がっているか」を $O(1)$ で答えるが $O(n^2)$ のメモリを食う。隣接リストは疎なグラフで省メモリ。
• 現実のネットワークはたいてい疎（$m \ll n^2$）なので、実装は隣接リスト、理論は隣接行列を使うことが多い。

概念：同じグラフ、2つの持ち方

グラフとは で定義したグラフを計算機で扱うには、データ構造に落とす必要があります。代表的なのが隣接行列と隣接リスト。どちらも同じグラフを表しますが、メモリ使用量と「ある操作の速さ」が真逆のトレードオフになります。

数式による定義：隣接行列

ノードを $1,\dots,n$ と番号づけたとき、隣接行列 $A$ は次で定義される $n \times n$ 行列です。

• 無向グラフでは $A$ は対称（$A_{ij}=A_{ji}$）。
• 重み付きグラフでは $1$ の代わりに重み $w_{ij}$ を入れます。
• 自己ループがなければ対角成分は $0$。

隣接行列の威力は線形代数が使えること。たとえば $A^k$ の $(i,j)$ 成分は、$i$ から $j$ への長さ $k$ の歩道（walk）の本数に等しい。後で学ぶ固有ベクトル中心性やスペクトル解析は、この行列の固有値・固有ベクトルを調べます（グラフラプラシアンとスペクトル）。

隣接リスト

各ノード $v$ について、隣接するノードの集合 $N(v) = \{u : (v,u)\in E\}$ をリストとして持ちます。総メモリは $O(n+m)$。疎なグラフ（$m$ が $n^2$ よりずっと小さい）では圧倒的に省メモリです。

コードで確認

import networkx as nx
import numpy as np

# 無向グラフを作る（5ノード・5エッジ）
G = nx.Graph()
G.add_edges_from([(0,1),(0,2),(1,2),(2,3),(3,4)])

# --- 隣接行列（密行列）---
A = nx.to_numpy_array(G, nodelist=[0,1,2,3,4], dtype=int)
print("隣接行列 A =")
print(A)

# --- 隣接リスト ---
for v in sorted(G.nodes()):
    print(f"ノード{v} の隣接: {sorted(G.neighbors(v))}")

# --- 疎性 ---
print(f"密度 = {nx.density(G):.3f}")
print(f"非ゼロ要素数 = {int(A.sum())} / 全要素数 = {A.size}")

実行結果：

隣接行列 A =
[[0 1 1 0 0]
 [1 0 1 0 0]
 [1 1 0 1 0]
 [0 0 1 0 1]
 [0 0 0 1 0]]
ノード0 の隣接: [1, 2]
ノード1 の隣接: [0, 2]
ノード2 の隣接: [0, 1, 3]
ノード3 の隣接: [2, 4]
ノード4 の隣接: [3]
密度 = 0.500
非ゼロ要素数 = 10 / 全要素数 = 25

行列が対称（$A_{ij}=A_{ji}$）であること、各行の和がそのノードの次数になっていることに注目してください。25 個のセルのうち非ゼロは 10 個。ノード数が増えるほど、この行列はスカスカ（疎）になっていきます。

メモリと計算量のトレードオフ

graph TD
    Q["どちらを使う?"] --> D{"グラフは密? 疎?"}
    D -->|"密 (m ~ n^2)"| M["隣接行列<br/>線形代数が活きる"]
    D -->|"疎 (m << n^2)"| L["隣接リスト<br/>省メモリ・隣人列挙が速い"]

数式の直観的意味

$A^k_{ij}$ が「長さ $k$ の歩道の本数」になるのは、行列積が「中継点をすべて足し合わせる」操作だからです。$A^2_{ij} = \sum_l A_{il}A_{lj}$ は「$i \to l \to j$ と2歩で行ける中継点 $l$ の数」。この性質ゆえに、グラフの到達可能性や経路の数え上げが行列のべき乗で計算できます。

⚠️ よくある誤解・落とし穴

• 大規模グラフで隣接行列を密に持つと破綻する：100万ノードなら $10^{12}$ セル。現実は scipy.sparse の疎行列か隣接リストを使います。
• 有向グラフの隣接行列は非対称：$A_{ij}$ は「$i \to j$ の矢印」。対称化してしまうと向きの情報が消えます。
• ノード番号の付け方で行列は変わるが、グラフとしては同一：行と列を同じ置換で並べ替えても同型（同じグラフ）です。

対応シミュレーション

本文の Python コードがそのまま検証コードです（network-study/simulations/ に同等のスニペットを置けます）。

関連

• 前提：グラフとは
• 次に読む：次数・道・連結成分
• 線形代数の発展：グラフラプラシアンとスペクトル
• 上位ハブ：グラフの基礎 目次