模块度

modularity(G, communities, weight='weight', resolution=1)

返回给定图划分的模块度。

模块度在 [1] 中定义为

\[Q = \frac{1}{2m} \sum_{ij} \left( A_{ij} - \gamma\frac{k_ik_j}{2m}\right) \delta(c_i,c_j)\]

其中 \(m\) 是边数（或如 [5] 中所述的所有边权重的总和），\(A\) 是 G 的邻接矩阵，\(k_i\) 是节点 \(i\) 的（加权）度，\(\gamma\) 是分辨率参数，\(\delta(c_i, c_j)\) 表示如果 \(i\) 和 \(j\) 属于同一社区则为 1，否则为 0。

根据 [2]（并通过代数验证）可简化为

\[Q = \sum_{c=1}^{n} \left[ \frac{L_c}{m} - \gamma\left( \frac{k_c}{2m} \right) ^2 \right]\]

其中求和遍历所有社区 \(c\)，\(m\) 是边数，\(L_c\) 是社区 \(c\) 内的链接数，\(k_c\) 是社区 \(c\) 中节点的度数总和，\(\gamma\) 是分辨率参数。

分辨率参数在组内边和组间边之间设置了一个任意的权衡。可以通过使用多个 gamma 值分析同一网络然后结合结果来发现更复杂的聚类模式 [3]。尽管如此，通常非常简单地使用 gamma=1。关于 gamma 选择的更多信息可在 [4] 中找到。

实际计算模块度使用的是第二个公式。对于有向图，第二个公式将 \(k_c\) 替换为 \(k^{in}_c k^{out}_c\)。

参数:

GNetworkX 图

communitieslist 或包含节点集的 iterable 对象

这些节点集必须代表图 G 的节点划分。

weightstring 或 None，可选 (默认值=”weight”)

用作权重的边属性。如果为 None 或边没有该属性，则该边的权重为 1。

resolutionfloat (默认值=1)

如果分辨率小于 1，模块度倾向于较大的社区。大于 1 则倾向于较小的社区。

返回:

Qfloat

划分的模块度。

抛出异常:

NotAPartition

如果 communities 不是图 G 的节点划分。

参考文献

[1]

M. E. J. Newman《网络：引论》，第 224 页。牛津大学出版社，2011。

[2]

Clauset, Aaron, Mark EJ Newman, and Cristopher Moore。“在非常大的网络中寻找社区结构。”Phys. Rev. E 70.6 (2004)。<https://arxiv.org/abs/cond-mat/0408187>

[3]

Reichardt 和 Bornholdt。“社区检测的统计力学”Phys. Rev. E 74, 016110, 2006。https://doi.org/10.1103/PhysRevE.74.016110

[4]

M. E. J. Newman，“社区检测中模块度优化与最大似然方法之间的等价性”Phys. Rev. E 94, 052315, 2016。https://doi.org/10.1103/PhysRevE.94.052315

[5]

Blondel, V.D. 等。“大型网络中社区的快速展开”J. Stat. Mech 10008, 1-12 (2008)。https://doi.org/10.1088/1742-5468/2008/10/P10008

示例

>>> G = nx.barbell_graph(3, 0)
>>> nx.community.modularity(G, [{0, 1, 2}, {3, 4, 5}])
0.35714285714285715
>>> nx.community.modularity(G, nx.community.label_propagation_communities(G))
0.35714285714285715