谱方法——模块度矩阵的主特征向量

# 构造模块度矩阵 B = A - k k^T / 2m，求最大特征值对应的特征向量 u，
# 按 u 分量的正负号把节点分成两组（谱二分），计算 Q，并与真实两派比较。
# |u_i| 很小的节点处于两组“之间”，归属最不确定。
# 输出：最大特征值为正（网络可分）；只靠一次特征分解，就几乎完全复现了俱乐部的分裂。
import networkx as nx
import numpy as np

K = nx.karate_club_graph()
G = nx.Graph(K.edges())
nodes = sorted(G.nodes())
A = nx.to_numpy_array(G, nodelist=nodes)
k = A.sum(axis=1)
m = A.sum() / 2

B = A - np.outer(k, k) / (2 * m)
vals, vecs = np.linalg.eigh(B)              # 特征值按升序排列
u = vecs[:, -1]
print("最大特征值 β1 = %.3f；B 的行和最大绝对值 = %.1e" % (vals[-1], np.abs(B.sum(axis=1)).max()))

part = [{n for n, x in zip(nodes, u) if x >= 0}, {n for n, x in zip(nodes, u) if x < 0}]
print("两组大小:", [len(p) for p in part], " Q = %.3f" % nx.community.modularity(G, part))
side_hi = part[0] if 0 in part[0] else part[1]
wrong = [n for n in nodes if (n in side_hi) != (K.nodes[n]["club"] == "Mr. Hi")]
print("与真实分派不一致的节点:", wrong)
print("|u| 最小的 3 个节点（处于两派“中间”）:", [nodes[i] for i in np.argsort(np.abs(u))[:3]])

# 作图：左为主特征向量各分量（按真实派别着色）；右为按符号二分的网络
import matplotlib.pyplot as plt

hi = np.array([K.nodes[n]["club"] == "Mr. Hi" for n in nodes])
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4))
order = np.argsort(u)
ax1.bar(range(len(nodes)), u[order], color=np.where(hi[order], "#fdb863", "#8073ac"))
ax1.axhline(0, color="0.3", lw=0.8)
ax1.set_xlabel("nodes sorted by u_i"); ax1.set_ylabel("leading eigenvector u_i")
ax1.plot([], [], "s", color="#fdb863", label="Mr. Hi"); ax1.plot([], [], "s", color="#8073ac", label="Officer")
ax1.legend(fontsize=8); ax1.set_title("Sign of u splits the club (beta1 = %.2f)" % vals[-1], fontsize=10)
pos = nx.spring_layout(G, seed=4)
nx.draw_networkx_edges(G, pos, ax=ax2, edge_color="0.7", alpha=0.4)
nx.draw_networkx_nodes(G, pos, ax=ax2, nodelist=nodes, node_color=u, cmap="PuOr", vmin=-np.abs(u).max(),
                       vmax=np.abs(u).max(), node_size=90, edgecolors=["red" if n in wrong else "0.4" for n in nodes])
ax2.set_title("Node colour = u_i; Q = %.3f, misassigned: %s" % (nx.community.modularity(G, part), wrong), fontsize=10)
ax2.axis("off"); plt.tight_layout(); plt.show()