生物医学网络科学Biomedical Network Science
Example03 / 15

Louvain、分辨率参数与随机网络的模块度

所属专题
社团结构与社区发现
下载
Notebook · .py
  1. 用 Louvain 在不同分辨率参数 γ 下划分空手道网络，观察社团数和（γ=1 时的）Q 的变化；
  2. 生成 20 个与空手道网络节点数、边数相同的 ER 随机网络，同样用 Louvain 求 Q，计算真实网络 Q 的 z 分数。 输出：γ 越大社团越多；没有真实社团的随机网络 Q 约 0.35，真实网络约 0.42，绝对差距并不大， 说明 Q 的绝对值不能单独证明社团结构显著，需要与零模型的分布比较（z 分数）。 更严格的零模型是保持度序列的随机网络（nx.double_edge_swap），用法见小世界与无标度网络模型的代码示例。

Output输出图

Louvain、分辨率参数与随机网络的模块度：输出图 1

Output文字输出

γ=0.5: 2 个社团, Q(γ=1) = 0.372
γ=1.0: 4 个社团, Q(γ=1) = 0.419
γ=1.5: 5 个社团, Q(γ=1) = 0.382
γ=2.0: 7 个社团, Q(γ=1) = 0.339
真实网络 Q = 0.419；随机网络 Q = 0.347 ± 0.015
z 分数 = 4.6

Code代码

# (a) 用 Louvain 在不同分辨率参数 γ 下划分空手道网络，观察社团数和（γ=1 时的）Q 的变化；
# (b) 生成 20 个与空手道网络节点数、边数相同的 ER 随机网络，同样用 Louvain 求 Q，计算真实网络 Q 的 z 分数。
# 输出：γ 越大社团越多；没有真实社团的随机网络 Q 约 0.35，真实网络约 0.42，绝对差距并不大，
#       说明 Q 的绝对值不能单独证明社团结构显著，需要与零模型的分布比较（z 分数）。
# 更严格的零模型是保持度序列的随机网络（nx.double_edge_swap），用法见小世界与无标度网络模型的代码示例。
import networkx as nx
import numpy as np

K = nx.karate_club_graph()
G = nx.Graph(K.edges())
n, m = G.number_of_nodes(), G.number_of_edges()

n_comm = []                                    # 存下结果用于作图
for gamma in [0.5, 1.0, 1.5, 2.0]:
    comms = nx.community.louvain_communities(G, resolution=gamma, seed=1)
    n_comm.append(len(comms))
    print("γ=%.1f: %d 个社团, Q(γ=1) = %.3f" % (gamma, len(comms), nx.community.modularity(G, comms)))

Q_real = nx.community.modularity(G, nx.community.louvain_communities(G, seed=1))

Q_rand = []
for s in range(20):
    R = nx.gnm_random_graph(n, m, seed=s)
    Q_rand.append(nx.community.modularity(R, nx.community.louvain_communities(R, seed=s)))
Q_rand = np.array(Q_rand)
print("真实网络 Q = %.3f；随机网络 Q = %.3f ± %.3f" % (Q_real, Q_rand.mean(), Q_rand.std()))
print("z 分数 = %.1f" % ((Q_real - Q_rand.mean()) / Q_rand.std()))

# 作图：左为社团数随分辨率 γ 的变化；右为随机网络 Q 的分布与真实网络 Q
import matplotlib.pyplot as plt

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4))
ax1.plot([0.5, 1.0, 1.5, 2.0], n_comm, "o-")
ax1.set_xlabel("resolution gamma"); ax1.set_ylabel("number of communities")
ax1.set_title("Higher resolution -> more communities", fontsize=10)
ax2.hist(Q_rand, bins=8, color="#92c5de", edgecolor="white", label="ER graphs (20)")
ax2.axvline(Q_real, color="#d6604d", lw=2, label="karate club")
ax2.set_xlabel("modularity Q (Louvain)"); ax2.set_ylabel("count"); ax2.legend(fontsize=8)
ax2.set_title("Random graphs also reach Q ~ %.2f; z = %.1f" % (Q_rand.mean(), (Q_real - Q_rand.mean()) / Q_rand.std()), fontsize=10)
plt.tight_layout(); plt.show()

Run在浏览器中运行

首次加载 Python 环境约需 20–40 秒；可以修改参数后重新运行。

Louvain、分辨率参数与随机网络的模块度