louvain_communities#

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

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

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

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

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

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

其中:math:m`是图的大小，:math:`k_{i,in}`是从:math:`i`到:math:`C`中节点的链接权重的总和，:math:`k_i`是与节点:math:`i`相关的链接权重的总和，:math:Sigma_{tot}`是与:math:C`中节点相关的链接权重的总和，:math:gamma`是分辨率参数。

对于有向情况，模块度增益可以根据[Rd180461fb6d3-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}\]

其中:math:k_i^{out}，\(k_i^{in}`是节点:math:`i`的外部和内部加权度，:math:\)Sigma_{tot}^{in}`，:math:`Sigma_{tot}^{out}`是与:math:`C`中节点相关的入站和出站链接的总和。

第一阶段继续进行，直到没有任何单独的移动可以改善模块度。

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

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

注意输入图中的自环。这些被视为先前缩减的社区——就像算法从中途开始一样。因此，大的自环边权重代表强社区，实际上可能很难添加其他节点。如果输入图的自环边权重不代表已经缩减的社区，您可能希望在输入该图之前移除自环。

Parameters:

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

Returns:

列表: 一个集合列表（ G 的划分）。每个集合代表一个社区，包含构成该社区的所有节点。