リンク予測｜ネットワーク科学

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：クラスタ係数と推移性・二部ネットワークと射影　|　関連：推薦システムとネットワーク

要点（BLUF）

リンク予測：現在は繋がっていないノード対のうち、「実は繋がっているはず」「将来繋がる」ものを当てる問題。
近傍ベースの指標が基本：共通近傍数・Jaccard係数・Adamic–Adar指数。共通の友達が多いほど繋がりやすい。
友人推薦・タンパク質相互作用の補完・推薦システムの土台。評価は隠したエッジをどれだけ上位に当てられるか。

概念：見えていないつながりを当てる

観測されたネットワークは不完全です。まだ知り合っていないが将来繋がる2人、実験で見落とされたタンパク質の相互作用。リンク予測は「非エッジのうち、どれが本当はエッジ（になる）か」をスコアづけする問題。基礎は「共通の友達が多いペアは繋がりやすい」という、クラスタ係数（クラスタ係数と推移性）と同じ三角形閉合の原理です。

数式：近傍ベースのスコア

ノード $u,v$ の近傍を $N(u), N(v)$ として、代表的な3つのスコアを定義します。

共通近傍（Common Neighbors）：単純に共通の隣人の数。

\mathrm{CN}(u,v) = |N(u) \cap N(v)|

Jaccard係数：共通近傍を全近傍で正規化（次数の大きさに左右されない）。

J(u,v) = \frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|}

Adamic–Adar指数：共通近傍を「その近傍の希少さ」で重みづけ。次数の低い共通近傍ほど強い証拠とみなす。

\mathrm{AA}(u,v) = \sum_{w \in N(u) \cap N(v)} \frac{1}{\log \deg(w)}

直観は「2人がマイナーな趣味の友達を共有しているほど、本人どうしも親しい可能性が高い」。みんなと繋がるハブを共有しても情報が薄い、という発想です。

コードで確認

import networkx as nx
import numpy as np

G = nx.karate_club_graph()
pairs = [(0,8), (0,33), (1,32), (2,33)]

print("共通近傍数:")
for u, v in pairs:
    print(f"  ({u},{v}): {len(list(nx.common_neighbors(G,u,v)))}")

print("Adamic-Adar 指数:")
for u, v, s in nx.adamic_adar_index(G, pairs):
    print(f"  ({u},{v}): {s:.3f}")

# 既存エッジは非エッジよりスコアが高い傾向（予測が効く証拠）
rng = np.random.default_rng(0)
existing = list(G.edges())[:50]
nonedge = list(nx.non_edges(G))
ne_sample = [nonedge[i] for i in rng.choice(len(nonedge), 50, replace=False)]
aa_exist = np.mean([s for _,_,s in nx.adamic_adar_index(G, existing)])
aa_non   = np.mean([s for _,_,s in nx.adamic_adar_index(G, ne_sample)])
print(f"既存エッジ平均AA={aa_exist:.3f} > 非エッジ平均AA={aa_non:.3f}")

実行結果：

共通近傍数:
  (0,8): 1
  (0,33): 4
  (1,32): 2
  (2,33): 6
Adamic-Adar 指数:
  (0,8): 0.434
  (0,33): 2.711
  (1,32): 1.156
  (2,33): 4.719
既存エッジ平均AA=1.023 > 非エッジ平均AA=0.279

ペア (2,33) は共通近傍6・AA指数4.7と高スコアで、「繋がっていそう」と判定されます。決定的なのは最後の行：実際に存在するエッジの平均スコア（1.02）が、ランダムな非エッジ（0.28）より明確に高い。近傍ベースのスコアが本物のリンクを見分けられることの数値的証拠です。

数式の直観的意味

3つのスコアは「共通近傍をどう重みづけるか」の違いです。共通近傍は素の数、Jaccardは「自分たちの交友圏に対する割合」（次数の大小を打ち消す）、Adamic–Adarは「希少な共通の知人ほど高評価」（ $1/\log\deg(w)$ がハブの寄与を割り引く）。 $\log$ が入るのは、次数が大きい共通近傍の影響を緩やかに減衰させるため。リンク予測の評価は、既知エッジの一部を隠してテストエッジとし、スコア上位に隠したエッジがどれだけ入るか（AUC や precision@k）で測ります。

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

近傍ベースは「共通近傍ゼロ」のペアを予測できない：遠いノード対には無力。経路ベース（Katz指数）や埋め込みベースが必要です。
評価でデータ漏洩に注意：テストで隠すエッジは、スコア計算のグラフから必ず除くこと。残すとカンニングになります。
クラス不均衡：非エッジは膨大、エッジはわずか。素の精度でなく AUC や precision@k で評価します。

対応シミュレーション

本文のコードがそのまま検証用です。GNN など埋め込みベースのリンク予測は機械学習へ（薄リンク）。