R igraph 手册页

cluster_leiden {igraph}

R 文档

使用 Traag、van Eck 和 Waltman 的 Leiden 算法查找图的社区结构。

描述

Leiden 算法类似于 Louvain 算法，cluster_louvain，但它更快，并产生更高质量的解决方案。它可以优化模块性和恒定 Potts 模型，该模型不受分辨率限制的影响（参见预印本 http://arxiv.org/abs/1104.3083）。

用法

cluster_leiden(
  graph,
  objective_function = c("CPM", "modularity"),
  weights = NULL,
  resolution_parameter = 1,
  beta = 0.01,
  initial_membership = NULL,
  n_iterations = 2,
  vertex_weights = NULL
)

参数

图	输入图，仅支持无向图。
objective_function	是否使用恒定 Potts 模型 (CPM) 或模块性。必须是 "CPM" 或 "modularity"。
weights	边的权重。它必须是一个正数值向量，NULL 或 NA。如果它是 NULL 并且输入图有一个“weight”边属性，则将使用该属性。如果 NULL 并且不存在此类属性，则边将具有相等的权重。如果该图具有“weight”边属性，但您不想将其用于社区检测，请将其设置为 NA。较大的边权重意味着此函数的更强连接。
resolution_parameter	要使用的分辨率参数。较高的分辨率会导致更多较小的社区，而较低的分辨率会导致较少的较大社区。
beta	影响 Leiden 算法中随机性的参数。这仅影响算法的细化步骤。
initial_membership	如果提供，Leiden 算法将尝试改进此提供的成员资格。如果没有提供参数，则该算法只需从单例分区开始。
n_iterations	迭代 Leiden 算法的迭代次数。每次迭代都可以进一步改进分区。
vertex_weights	Leiden 算法中使用的顶点权重。如果未提供，将根据 objective_function 自动确定。请参阅此函数的详细信息，了解如何解释顶点权重。

详细信息

Leiden 算法包含三个阶段：（1）节点的本地移动，（2）分区的细化，以及（3）基于细化分区的网络聚合，使用非细化分区为聚合网络创建一个初始分区。在 Leiden 算法的本地移动过程中，仅访问其邻域已更改的节点。细化是通过从每个集群内的单例分区重新开始并逐渐合并子集群来完成的。在聚合时，单个集群可以由多个节点表示（这些节点是在细化中识别的子集群）。

Leiden 算法提供了几个保证。Leiden 算法通常是迭代的：一次迭代的输出用作下一次迭代的输入。在每次迭代中，保证所有集群都是连接的并且很好地分离。在没有任何变化的一次迭代之后，保证所有节点和某些部分都在本地最佳分配。最后，渐近地，保证所有集群的所有子集都在本地最佳分配。有关更多详细信息，请参阅 Traag、Waltman 和 van Eck (2019)。

正在优化的目标函数是

\frac{1}{2m} \sum_{ij} (A_{ij} - \gamma n_i n_j)\delta(\sigma_i, \sigma_j)

其中 m 是总边权重，A_{ij} 是边 (i, j) 的权重，\gamma 是所谓的 分辨率参数，n_i 是节点 i 的节点权重，\sigma_i 是节点 i 的集群，并且 \delta(x, y) = 1 仅当 x = y 时，否则为 0。通过设置 n_i = k_i，即节点 i 的度数，并将 \gamma 除以 2m，您可以有效地获得模块性的表达式。

因此，当您将度数作为 vertex_weights 提供，并通过提供作为分辨率参数 \frac{1}{2m} 时，将优化标准模块性，其中 m 是边的数量。如果您没有指定任何 vertex_weights，则正确的顶点权重和 \gamma 的缩放由 objective_function 参数自动确定。

值

cluster_leiden 返回一个 communities 对象，请参阅 communities 手册页面以获取详细信息。

作者

Vincent Traag

参考

Traag, V. A., Waltman, L., & van Eck, N. J. (2019). 从 Louvain 到 Leiden：保证良好连接的社区。Scientific reports, 9(1), 5233. doi: 10.1038/s41598-019-41695-z, arXiv:1810.08473v3 [cs.SI]

参见

有关从结果中提取成员关系、模块化分数等信息，请参见 communities。

其他社区检测算法：cluster_walktrap, cluster_spinglass, cluster_leading_eigen, cluster_edge_betweenness, cluster_fast_greedy, cluster_label_prop cluster_louvain cluster_fluid_communities cluster_infomap cluster_optimal cluster_walktrap

示例

g <- make_graph("Zachary")
# By default CPM is used
r <- quantile(strength(g))[2] / (gorder(g) - 1)
# Set seed for sake of reproducibility
set.seed(1)
ldc <- cluster_leiden(g, resolution_parameter=r)
print(ldc) 
plot(ldc, g)

---