← ネットワーク科学 一覧

🎓 レベル：発展　|　重要度：B（推奨）

📎 前提：次数中心性と次数分布・モジュラリティ最大化　|　関連：Erdős–Rényiランダムグラフ

要点（BLUF）

• configurationモデル：与えられた次数列をそのまま保ったまま、エッジをランダムに張り替えたグラフ集団。
• 「観測された構造（三角形・コミュニティ）は、次数分布だけで説明できる量を超えているか」を判定するヌルモデル。
• モジュラリティ $Q$ の定義に登場する期待値 $k_i k_j / 2m$ は、まさにこのモデルの結線確率。

概念：何と比べれば「構造がある」と言えるか

「このネットワークには三角形が多い」「コミュニティがある」と言うとき、何と比べて多いのかが問題です。ER（Erdős–Rényiランダムグラフ）と比べるのは不公平 — ER は次数分布が違いすぎます。フェアな比較相手は「次数分布は同じだが、それ以外はランダム」なグラフ。これが configuration モデルで、構造の有意性を測る「ものさし（ヌルモデル）」になります。

モデルの定義

各ノード $i$ にその次数 $k_i$ 本の「スタブ（半エッジ）」を生やし、スタブ同士をランダムに対にして繋ぎます。

• 次数列 $\{k_1, \dots, k_n\}$ は厳密に保存される。
• それ以外（誰と誰が繋がるか）は一様ランダム。
• 多重辺・自己ループが生じうる（単純グラフが必要なら除去するか張り直す）。

このモデルで、ノード $i,j$ 間にエッジが期待される本数は

次数の積に比例します。この式こそ、モジュラリティ $Q$（モジュラリティ最大化）の引き算項の正体です。$Q$ は「実際のエッジ $-$ configuration モデルでの期待エッジ」を測っていたのです。

コードで確認

import networkx as nx
import numpy as np

G0 = nx.karate_club_graph()
deg_seq = [d for _, d in G0.degree()]

triangles = []
for seed in range(50):
    cm = nx.configuration_model(deg_seq, seed=seed)  # 次数列を保ってランダム結線
    cm = nx.Graph(cm)                                # 多重辺をまとめる
    cm.remove_edges_from(nx.selfloop_edges(cm))      # 自己ループ除去
    triangles.append(nx.transitivity(cm))

print("元グラフの推移性          :", round(nx.transitivity(G0), 4))
print("次数保存ヌルモデルの推移性 :", round(np.mean(triangles), 4), "(50回平均)")
print("元の次数列              :", sorted(deg_seq, reverse=True)[:8], "...")

実行結果：

元グラフの推移性          : 0.2557
次数保存ヌルモデルの推移性 : 0.1597 (50回平均)
元の次数列              : [17, 16, 12, 10, 9, 6, 6, 5] ...

同じ次数列でランダムに繋ぎ直すと推移性は約0.16。実際の空手クラブは0.26で、ヌルモデルより有意に三角形が多い。つまり「このネットワークの三角形の多さは、次数分布だけでは説明できない＝本物の構造（コミュニティ）がある」と結論できます。これがヌルモデルによる仮説検定の発想です。

数式の直観的意味

$k_i k_j / 2m$ が「期待エッジ数」になる理由は、スタブの組合せで考えると見えます。$i$ の $k_i$ 本のスタブそれぞれが、全 $2m$ 本のスタブのうち $j$ のスタブ（$k_j$ 本）と繋がる確率を足し上げると $k_i k_j / 2m$。要するに「次数が高いノードどうしは、ランダムでも繋がりやすい」。その「ランダムでも当然」の分を差し引いて初めて、コミュニティや同類選好という「ランダムを超えた構造」が見えてきます。

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

• 単純化で次数が少し減る：多重辺・自己ループを除去すると、保存したはずの次数がわずかに崩れます。厳密に保つにはエッジスワップ（double edge swap）を使います。
• ヌルモデルは1つではない：次数を保つ（configuration）か、次数分布だけ保つか、ブロック構造も保つか。何を保存するかで「何を有意とみなすか」が変わります。
• 期待値であって特定のグラフではない：$k_ik_j/2m$ は集団平均。1回の実現は揺らぎます。だから上のコードは50回平均しています。

対応シミュレーション

本文のコードがそのまま検証用です。この期待値を使う指標は モジュラリティ最大化。

関連

• 前提：次数中心性と次数分布・モジュラリティ最大化
• 別のヌルモデル：Erdős–Rényiランダムグラフ
• 上位ハブ：ランダムグラフモデル 目次