leidenalg 包教程（1）

date

Jun 21, 2022

slug

leidenalg包基础

status

Published

leidenalg 教程

安装

简单来说，可以使用pip install leidenalg直接安装。

也可以使用源码进行安装，安装这个包需要C核心库igraph和python包python-igraph，然后可以通过python setup.py test安装

不建议Windows，使用源代码进行安装。

介绍

leidenalg软件包建立在igraph基础之上，有助于网络的社区发现。leiden是大型网络中社区发现方法的通用算法。如果只想对给定的图$G$进行模块化社区发现可以：

在igraph包中内置了Louvain算法community_multilevel()，可以简单的将无向无权重图进行分区。在leidenalg包中，有一些其他的功能，并且使用的leidena算法比louvain算法性能更好。

例子：Zachary 空手道俱乐部网络

在这种情况下，算法实际上会找到最佳分区，可以使用igraph包中的community_optimal_modularity()来检查,会得到不同的结果。

但是，这样做会得到很多的子社区。下面介绍使用CPMVertexPartition如何将它一分为二：

传递给find_partition的额外参数**kwargs都会传递给给定partition_type。可以传递resolution_parameter、weights 、node_sizes等参数。

除此之外，leidenalg还支持有向图和加权图，可以在一定程度上自定义优化程序，而且还支持处理多路复用图（多元异构图）。

高级技巧

1. 优化器

leidenalg包提供对函数的简单访问find_partition()，但是底层使用Optimiser类完成。显示构建一个Optimiser对象：

函数find_partition()不在执行任何其他操作，仅在提供的分区上调用optimise_partition。

optimise_partition()简单地尝试优化分区，可以反复调用以不断优化

调用可能没有改进当前分区，下一次可能会改进。

进行重复迭代可以调用内置的函数，传入参数：

如果n_iterations<0，优化器会持续下去优化，直到遇到没有改进的分区的迭代。

optimise_partition()的执行过程又是建立在move_nodes()和merge_nodes()算法之上，可以自行调用：

使用以上基本算法实现Louvain算法聚合分区，并在聚合分区上重复使用move_nodes():

尽管这样可以找到最终的聚合分区，但是在各个节点级别上的实际分区仍然不清楚。为了做到这一点，我们需要基于聚合分区更新成员关系，为此我们使用函数 from_coarse_partition()

现在partition_agg包含聚合分区，并且partition包含原始图G的实际分区。partition_agg.quality() == partition.quality() 两个基本等价。

也可以使用merge_nodes()代替move_nodes()，函数的选择取决于特定的替换社区。

在Leiden算法中，可以先细化分区，再聚合。算法可以使用函数数move_nodes_constrained()和 merge_nodes_constrained()来完成：

这些函数又依赖两个关键的基本函数： diff_move()和move_node()。前者计算移动节点时的差异，后者实际移动节点，并更新所有必要的内部管理。函数move_nodes()然后执行：

实际的实现更为复杂，总体是这个思路。

2. Resolution profile 分辨率配置文件

该参数的作用是一种阈值：社区的密度至少要达到，而社区之间的密度要低于，较高的分辨率会导致更多的社区，而较低的分辨率会导致更少的社区

一些如CPMVertexPartition或RBConfigurationVertexPartition方法接受的分辨率（解析）参数。虽然某些方法具有某种“天生”的分辨率参数，但实际上却是十分武断的。然而，这里使用的方法（以线性方式依赖于分辨率参数）允许对分辨率参数的范围内进行有效扫描。这些方法可以表述为。

在CPMVertexPartition中表示社区中的边的数量，表示期望的社区内部的边的总和。如果存在最佳分区和，那么都是最佳分区。

可以使用Optimiser对象构建这样的分辨率参数：

绘制分辨率参数与子社区总边数的关系图，结果如下：

现在，配置文件包含一个指定类型的分区列表（例子中为CPMVertexPartition），用于解析参数发生变化。特别是，profile[i]应该更好直到profile[i+1]，或者有另外的说明，对于profile[i].resolution_parameter和 profile[i+1].resolution_parameter之间的分区的分辨率参数i更好。当然，会有一些变化，因为optimise_partition()会找到不同质量的分区，不同的运行，变化点也可能会有所不同。

此函数会重复调用optimise_partition() ，因此可能需要大量时间。特别是对于改变点附近的分辨率参数，可能有许多可能的分区，因此需要大量运行。

3. 固定（确定）节点

由于某些原因，只更新分区（子社区）的一部分可能是有益的。例如，在一些数据上已经运行了leiden算法，并对结果进行了一些分析，随后又收集了一些新的数据，特别是新的节点，那么保持以前的社区分配不变，而只更新新节点的社区分配，这样做可能是有益的。

可以使用is_membership_fixed参数传入find_partition()来完成分区。

例如，假设我们之前检测到图G的分区，它被扩展到图G2。假设之前退出的节点是相同的，我们可以通过以下方式创建一个新的分区:

然后，我们只能按照如下方式更新新节点的社区分配

在这个例子中，使用了CPMVertexPartition，也可以使用其他VertexPartition。

4. 最大社区规模

在某种情况下，可能需要限制最大子社区的规模，可以通过max_comm_size参数来指定最大子社区规模。此参数可以在优化期间进行设定产生约束，也可以直接传递到find_partition()。

参考

leidenalg

Traag, V. A., Krings, G., & Van Dooren, P. (2013). Significant scales in community structure. Scientific Reports, 3, 2930. 10.1038/srep02930 2

Zanini, F., Berghuis, B. A., Jones, R. C., Robilant, B. N. di, Nong, R. Y., Norton, J., Clarke, Michael F., Quake, S. R. (2019). northstar: leveraging cell atlases to identify healthy and neoplastic cells in transcriptomes from human tumors. BioRxiv, 820928. 10.1101/820928