modularity

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

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

模块度在[R6937dc4d2017-1]_中定义为

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

其中:math:m`是边的数量（或[R6937dc4d2017-5]_中所有边权重的总和），:math:`A`是 `G 的邻接矩阵，\(k_i`是:math:`i`的（加权）度，:math:\)gamma`是分辨率参数，:math:`delta(c_i, c_j)`是1如果:math:`i`和:math:`j`在同一个社区，否则为0。

根据[R6937dc4d2017-2]_（并通过一些代数验证），这可以简化为

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

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

分辨率参数设置了一个任意平衡组内边和组间边的权衡。通过使用多个gamma值分析同一网络并结合结果，可以发现更复杂的分组模式[R6937dc4d2017-3]_。尽管如此，通常简单地使用gamma=1是很常见的。关于gamma选择的更多信息在[R6937dc4d2017-4]_中。

第二个公式实际上用于模块度的计算。对于有向图，第二个公式将:math:k_c`替换为:math:`k^{in}_c k^{out}_c。

Parameters:

GNetworkX 图

communities列表或可迭代对象，包含节点集合

这些节点集合必须表示G的节点的分区。

weight字符串或None，可选（默认=”weight”）

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

resolution浮点数（默认=1）

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

Returns:

Q浮点数

分区的模块度。

Raises:

NotAPartition

如果 communities 不是 G 节点的分区。

References

[1]

M. E. J. Newman “Networks: An Introduction”, page 224. Oxford University Press, 2011.

[2]

Clauset, Aaron, Mark EJ Newman, and Cristopher Moore. “Finding community structure in very large networks.” Phys. Rev. E 70.6 (2004). <https://arxiv.org/abs/cond-mat/0408187>

[3]

Reichardt and Bornholdt “Statistical Mechanics of Community Detection” Phys. Rev. E 74, 016110, 2006. https://doi.org/10.1103/PhysRevE.74.016110

[4]

M. E. J. Newman, “Equivalence between modularity optimization and maximum likelihood methods for community detection” Phys. Rev. E 94, 052315, 2016. https://doi.org/10.1103/PhysRevE.94.052315

[5]

Blondel, V.D. et al. “Fast unfolding of communities in large networks” J. Stat. Mech 10008, 1-12 (2008). https://doi.org/10.1088/1742-5468/2008/10/P10008

Examples

>>> 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