louvain_communities

louvain_communities(G, weight='weight', resolution=1, threshold=1e-07, 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}\cot\sigma_{tot}^{in}+ki^{in}\cdot\sigma_{tot}^{out}}{m^2}\]

哪里 \(k_i^{{out}}\) ， \(k_i^{{in}}\) 是结点的外部和内部加权次数 \(i\) 和 \(\Sigma_{{tot}}^{{in}}\) ， \(\Sigma_{{tot}}^{{out}}\) 中节点的传入链接和传出链接的总和 \(C\) 。

第一阶段将继续进行，直到任何一个单独的动作都不能改善模块化。

第二阶段是建立一个新的网络，其节点现在是第一阶段中发现的社区。为此，新节点之间的链路的权重由对应的两个社区中的节点之间的链路的权重之和给出。一旦这一阶段完成，就可以重新应用第一阶段，创建更大的社区，增加模块化。

执行上述两个阶段，直到没有达到模块化增益(或小于 threshold )。

参数

G网络X图表

weight字符串或无，可选(默认为“权重”)

保存用作权重的数值的边属性的名称。如果没有，则每条边的权重为1。

resolution浮动，可选(默认值=1)

如果分辨率小于1，则该算法倾向于较大的社区。大于1有利于较小的社区

threshold浮点，可选(默认值=0.0000001)

每个级别的模块化增益阈值。如果算法的两个级别之间的模块化增益小于给定阈值，则该算法停止并返回结果社区。

seed整数、随机状态或无（默认）

随机数生成状态的指示器。见 Randomness .

返回

列表

集合列表(分区 G )。每个集合代表一个社区，并包含组成该社区的所有节点。

参见

louvain_partitions

笔记

考虑节点的顺序可能会影响最终输出。在该算法中，使用随机洗牌进行排序。

工具书类

1(1,2)

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

2

特拉格，V.A.，沃尔特曼，L.和范埃克，新泽西州，从卢万到莱顿：保证良好联系的社区。SCI Rep 9,5233(2019)。Https://doi.org/10.1038/s41598-019-41695-z

3

尼古拉斯·杜盖，安东尼·佩雷斯。有向卢万：最大化有向网络中的模块化。 [研究报告] 奥莱昂大学。2015年。哈尔-01231784。Https://hal.archives-ouvertes.fr/hal-01231784

实例

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