modularity#

modularity(G, communities, weight='weight', resolution=1)[source]#

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

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

Q = \frac{1}{2 m} \sum_{i j} (A_{i j} - γ \frac{k_{i} k_{j}}{2 m}) δ (c_{i}, c_{j})

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

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

Q = \sum_{c = 1}^{n} [\frac{L_{c}}{m} - γ {(\frac{k_{c}}{2 m})}^{2}]

其中总和遍历所有社区:math:c， $m ‘ 是边的数量， : m a t h : ‘ L_{c} ‘ 是社区 : m a t h : ‘ c ‘ 的内部链接数量， : m a t h : ‘ k_{c} ‘ 是社区 : m a t h : ‘ c ‘ 中节点的度数总和， : m a t h :$ 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