Example02 / 15
Girvan–Newman 算法
对空手道网络运行 Girvan–Newman（反复删除边介数最大的边，每次删边后重新计算边介数）， 记录每一层划分的社团数与模块度，选出 Q 最大的一层；再把第一次分裂（2 个社团）与真实两派比较。 输出：Q 在 5 个社团时达到最大（约 0.40）；第一次分裂只有个别节点与真实分派不同。
Output输出图
Output文字输出
社团数 2 Q = 0.360 社团数 3 Q = 0.349 社团数 4 Q = 0.363 社团数 5 Q = 0.401 社团数 6 Q = 0.393 社团数 7 Q = 0.376 社团数 8 Q = 0.358 社团数 9 Q = 0.342 社团数 10 Q = 0.333 最佳：5 个社团，Q = 0.401 第一次分裂中与真实分派不一致的节点: [2, 8]
Code代码
# 对空手道网络运行 Girvan–Newman（反复删除边介数最大的边，每次删边后重新计算边介数），
# 记录每一层划分的社团数与模块度，选出 Q 最大的一层；再把第一次分裂（2 个社团）与真实两派比较。
# 输出：Q 在 5 个社团时达到最大（约 0.40）；第一次分裂只有个别节点与真实分派不同。
import networkx as nx
import matplotlib.pyplot as plt
K = nx.karate_club_graph()
G = nx.Graph(K.edges())
truth = {n: K.nodes[n]["club"] for n in K}
levels = [] # [(社团数, Q, 划分), ...]
for comms in nx.community.girvan_newman(G):
comms = [set(c) for c in comms]
levels.append((len(comms), nx.community.modularity(G, comms), comms))
if len(comms) >= 10:
break
for n_c, q, _ in levels:
print("社团数 %2d Q = %.3f" % (n_c, q))
best = max(levels, key=lambda x: x[1])
print("最佳：%d 个社团，Q = %.3f" % (best[0], best[1]))
first = levels[0][2]
side_hi = first[0] if 0 in first[0] else first[1] # 教练 0 号所在的一侧
wrong = [n for n in G if (n in side_hi) != (truth[n] == "Mr. Hi")]
print("第一次分裂中与真实分派不一致的节点:", wrong)
plt.plot([x[0] for x in levels], [x[1] for x in levels], "o-")
plt.xlabel("number of communities")
plt.ylabel("modularity Q")
plt.title("Girvan–Newman on karate club")
plt.show()Run在浏览器中运行
首次加载 Python 环境约需 20–40 秒；可以修改参数后重新运行。