louvain_communities#

louvain_communities(G, weight='weight', resolution=1, threshold=1e-07, max_level=None, seed=None)[源]#

使用 Louvain 社区检测算法找到图的最佳划分。

Louvain 社区检测算法是一种简单的方法，用于提取网络的社区结构。这是一种基于模块度优化的启发式方法。[1]

该算法分两步工作。第一步是将每个节点分配到其自身的社区中，然后对于每个节点，尝试通过将每个节点移动到其所有邻居社区来寻找最大的正模块度增益。如果没有获得正增益，则节点保留在其原始社区中。

将孤立节点 \(i\) 移动到社区 \(C\) 所获得的模块度增益可以通过以下公式轻松计算（结合 [1] [2] 和一些代数运算）

\[\Delta Q = \frac{k_{i,in}}{2m} - \gamma\frac{ \Sigma_{tot} \cdot k_i}{2m^2}\]

其中 \(m\) 是图的大小，\(k_{i,in}\) 是从 \(i\) 到 \(C\) 中节点的链接权重之和，\(k_i\) 是与节点 \(i\) 关联的链接权重之和，\(\Sigma_{tot}\) 是与 \(C\) 中节点关联的链接权重之和，\(\gamma\) 是分辨率参数。

对于有向情况，根据 [3]，可以使用以下公式计算模块度增益

\[\Delta Q = \frac{k_{i,in}}{m} - \gamma\frac{k_i^{out} \cdot\Sigma_{tot}^{in} + k_i^{in} \cdot \Sigma_{tot}^{out}}{m^2}\]

其中 \(k_i^{out}\), \(k_i^{in}\) 是节点 \(i\) 的加权出度和加权入度，\(\Sigma_{tot}^{in}\), \(\Sigma_{tot}^{out}\) 是与 \(C\) 中节点关联的入链和出链权重之和。

第一阶段持续进行，直到没有单个移动可以改善模块度为止。

第二阶段包括构建一个新网络，其节点现在是第一阶段中发现的社区。为此，新节点之间的链接权重由相应两个社区中节点之间的链接权重之和给出。一旦此阶段完成，可以重新应用第一阶段，创建具有更高模块度的更大社区。

重复执行上述两个阶段，直到没有获得模块度增益（或小于 threshold，或达到 max_levels）。

请注意输入图中的自环。它们被视为之前已缩减的社区——就像算法过程已从中间开始一样。因此，大的自环边权重代表强大的社区，在实践中可能难以向其中添加其他节点。如果输入图的自环边权重不代表已缩减的社区，您可能需要在输入图之前删除自环。

参数:

GNetworkX 图
weight字符串或 None，可选（默认值=”weight”）: 保存用作权重的数值的边属性的名称。如果为 None，则每条边权重为 1。
resolution浮点数，可选（默认值=1）: 如果 resolution 小于 1，算法倾向于更大的社区。大于 1 则倾向于更小的社区。
threshold浮点数，可选（默认值=0.0000001）: 每个级别的模块度增益阈值。如果算法的两个级别之间的模块度增益小于给定的阈值，则算法停止并返回结果社区。
max_level整数或 None，可选（默认值=None）: 计算的最大级别数（算法步骤数）。必须是正整数或 None。如果为 None，则没有最大级别限制，阈值参数决定停止条件。
seed整数、random_state 或 None（默认值）: 随机数生成状态的指示符。参见随机性。

返回:

另见

注意

考虑节点的顺序可能会影响最终输出。在算法中，顺序是通过随机打乱来实现的。

参考文献

[1] (1,2)

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

[2]

Traag, V.A., Waltman, L. & van Eck, N.J. 从 Louvain 到 Leiden：确保良好连接的社区。Sci Rep 9, 5233 (2019)。https://doi.org/10.1038/s41598-019-41695-z

[3]

Nicolas Dugué, Anthony Perez. 有向 Louvain：最大化有向网络中的模块度。[研究报告] 巴黎奥尔良大学。2015 年。hal-01231784。https://hal.archives-ouvertes.fr/hal-01231784

示例

>>> import networkx as nx
>>> G = nx.petersen_graph()
>>> nx.community.louvain_communities(G, seed=123)
[{0, 4, 5, 7, 9}, {1, 2, 3, 6, 8}]
----

其他后端实现了此函数

cugraphGPU 加速后端。

seed 参数目前被忽略，且尚不支持自环。

额外参数

dtypedtype 或 None，可选: 用于算法中边的数据类型（np.float32, np.float64 或 None）。如果为 None，则 dtype 由边值确定。