链路预测——共同邻居、资源分配与长度为 3 的路径（L3）

# 随机隐藏 10% 的边作为测试集，用剩余网络为“测试边”和等量“非边”打分，计算 AUROC。
# 指标：CN = |Γ(u)∩Γ(v)|；RA = Σ_{w∈Γ(u)∩Γ(v)} 1/k_w；
#       L3 = Σ_{u-a-b-v} 1/sqrt(k_a k_b)（Kovács 等 2019：蛋白通过互补界面相互作用时，
#       “我的邻居的邻居的邻居”更可能是我的伙伴，而不是“我的邻居的邻居”）。
# 两个合成网络：三角闭合强的 Watts–Strogatz（社交式），以及没有三角闭合偏好的分块二分网络（同组节点共享伙伴、彼此不相连，模拟互补界面）。
# 输出解读：在三角形多的网络中三种指标都很好；在分块二分网络中测试边两端没有共同邻居，CN/RA 的 AUROC
# 不高于 0.5（同侧非边反而可能有共同邻居），L3 明显更好。哪种启发式合适取决于网络的连接机制。
import networkx as nx
import numpy as np

def auroc(pos, neg):
    s = np.concatenate([pos, neg]); y = np.r_[np.ones(len(pos)), np.zeros(len(neg))]
    order = np.argsort(s, kind="mergesort"); ranks = np.empty(len(s)); ranks[order] = np.arange(1, len(s) + 1)
    for val in np.unique(s):                       # 并列取平均秩
        idx = s == val; ranks[idx] = ranks[idx].mean()
    n1, n0 = len(pos), len(neg)
    return (ranks[y == 1].sum() - n1 * (n1 + 1) / 2) / (n1 * n0)

def scores(G, pairs):
    k = dict(G.degree()); out = {"CN": [], "RA": [], "L3": []}
    for u, v in pairs:
        cn = set(G[u]) & set(G[v])
        out["CN"].append(len(cn))
        out["RA"].append(sum(1.0 / k[w] for w in cn))
        l3 = 0.0
        for a in G[u]:
            for b in G[a]:
                if b != u and G.has_edge(b, v) and a != v:
                    l3 += 1.0 / np.sqrt(k[a] * k[b])
        out["L3"].append(l3)
    return {m: np.array(x) for m, x in out.items()}

def experiment(G, name, seed=0):
    rng = np.random.default_rng(seed)
    edges = list(G.edges())
    test_idx = rng.choice(len(edges), size=len(edges) // 10, replace=False)
    test = [edges[i] for i in test_idx]
    Gtr = G.copy(); Gtr.remove_edges_from(test)
    nodes = list(G); neg = set()
    while len(neg) < len(test):
        u, v = rng.choice(nodes, 2, replace=False)
        if not G.has_edge(u, v): neg.add((int(u), int(v)))
    sp_, sn_ = scores(Gtr, test), scores(Gtr, list(neg))
    res = {m: auroc(sp_[m], sn_[m]) for m in ["CN", "RA", "L3"]}
    print(name + "：" + "，".join(f"{m} AUROC = {res[m]:.2f}" for m in res))
    return res

res_ws = experiment(nx.connected_watts_strogatz_graph(1000, 10, 0.1, seed=1), "Watts–Strogatz（三角闭合强）")
# 分块二分网络：左右各 500 个节点、各分 10 组，左组 i 主要连右组 i（模拟“互补界面”：同组蛋白共享伙伴但彼此不连）
rng = np.random.default_rng(2)
B = nx.Graph(); B.add_nodes_from(range(1000))
for u in range(500):
    for v in range(500, 1000):
        same = (u // 50) == ((v - 500) // 50)
        if rng.random() < (0.12 if same else 0.002):
            B.add_edge(u, v)
B = B.subgraph(max(nx.connected_components(B), key=len)).copy()
res_bp = experiment(B, "分块二分网络（无三角形）")

import matplotlib.pyplot as plt
fig, ax = plt.subplots(figsize=(6.4, 4.2))
x = np.arange(2)
for k, (m, c, h) in enumerate([("CN", "0.7", ""), ("RA", "0.45", "//"), ("L3", "C0", "")]):
    ax.bar(x + (k - 1) * 0.26, [res_ws[m], res_bp[m]], 0.26, color=c, hatch=h, label=m)
ax.axhline(0.5, color="k", ls="--", lw=1, label="random (0.5)")
ax.set_xticks(x); ax.set_xticklabels(["Watts–Strogatz\n(many triangles)", "block bipartite\n(complementary)"])
ax.set_ylabel("AUROC on hidden edges"); ax.set_ylim(0, 1.05)
ax.set_title("L3 works when partners share partners, not each other"); ax.legend(fontsize=8, ncol=2)
plt.tight_layout(); plt.show()