leidenalg包教程-1


leidenalg包教程

目录

安装

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

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

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

介绍

leidenalg软件包建立在igraph基础之上,有助于网络的社区发现。
leiden是大型网络中社区发现方法的通用算法。

如果只想对给定的图/(G/)进行模块化社区发现可以:

import leidenalg as la
import igraph as ig

partition = la.find_partition(G, la.ModularityVertexPartition) # 模块化顶点分区

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

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

import igraph as ig
import leidenalg as la

# 加载 Zachary 空手道俱乐部图
G = ig.Graph.Famous('Zachary')

# 检测具有模块化的社区
partition = la.find_partition(G, la.ModularityVertexPartition)

# 绘制结果
ig.plot(partition) 

karate_modularity

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

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

partition = la.find_partition(G, la.CPMVertexPartition, resolution_parameter = 0.05);
ig.plot(partition) 

two

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

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

高级技巧

1. 优化器

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

optimiser = la.Optimiser()

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

diff = optimiser.optimise_partition(partition)

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

G = ig.Graph.Erdos_Renyi(100, p=5./100)
partition = la.ModularityVertexPartition(G)
diff = 1
while diff > 0:
  diff = optimiser.optimise_partition(partition)

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

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

diff = optimiser.optimise_partition(partition, n_iterations=10)

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

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

diff = optimiser.move_nodes(partition)
diff = optimiser.merge_nodes(partition)

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

partition = la.ModularityVertexPartition(G)
while optimiser.move_nodes(partition) > 0:
  partition = partition.aggregate_partition()

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

partition = la.ModularityVertexPartition(G)
partition_agg = partition.aggregate_partition()
while optimiser.move_nodes(partition_agg) > 0:
  partition.from_coarse_partition(partition_agg)
  partition_agg = partition_agg.aggregate_partition()

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

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

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

# Set initial partition 设置初始化分区
partition = la.ModularityVertexPartition(G)
refined_partition = la.ModularityVertexPartition(G)
partition_agg = refined_partition.aggregate_partition()

while optimiser.move_nodes(partition_agg):

  # Get individual membership for partition 得到个体分区的资格
  partition.from_coarse_partition(partition_agg, refined_partition.membership)

  # Refine partition 细化分区
  refined_partition = la.ModularityVertexPartition(G)
  optimiser.merge_nodes_constrained(refined_partition, partition)

  # Define aggregate partition on refined partition 在细化分区上定义聚合分区
  partition_agg = refined_partition.aggregate_partition()

  # But use membership of actual partition使用实际分区的资格
  aggregate_membership = [None] * len(refined_partition)
  for i in range(G.vcount()):
    aggregate_membership[refined_partition.membership[i]] = partition.membership[i]
  partition_agg.set_membership(aggregate_membership)

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

for v in G.vs:
  best_comm = max(range(len(partition)),
                  key=lambda c: partition.diff_move(v.index, c))
  partition.move_node(v.index, best_comm)

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

2. Resolution profile 分辨率配置文件

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

一些如CPMVertexPartitionRBConfigurationVertexPartition方法接受的分辨率(解析)参数。虽然某些方法具有某种“天生”的分辨率参数,但实际上却是十分武断的。然而,这里使用的方法(以线性方式依赖于分辨率参数)允许对分辨率参数的范围内进行有效扫描。这些方法可以表述为/(Q = E – /gamma N/)。

CPMVertexPartition中/(E= /sum_c m_c/)表示社区/(c/)中的边的数量,/(N=/sum_c {n_c /choose 2}/)表示期望的社区/(c/)内部的边的总和。如果存在最佳分区/(/gamma_1/)和/(/gamma_2/),那么/(/gamma_1 ≤ /gamma ≤ /gamma_2/)都是最佳分区。

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

G = ig.Graph.Famous('Zachary')
optimiser = la.Optimiser()
profile = optimiser.resolution_profile(G, la.CPMVertexPartition,
                                       resolution_range=(0,1))

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

截屏2021-08-29 00.19.02

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

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

3. 固定(确定)节点

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

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

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

new_membership = list(range(G2.vcount()))
new_membership[:G.vcount()] = partition.membership

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

new_partition = la.CPMVertexPartition(G2, new_membership, resolution_parameter=partition.resolution_parameter)
is_membership_fixed = [i < G.vcount() for i in range(G2.vcount())]

diff = optimiser.optimise_partition(partition, is_membership_fixed=is_membership_fixed)

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

参考链接
未完待续

原创文章,作者:745907710,如若转载,请注明出处:https://blog.ytso.com/268157.html

(0)
上一篇 2022年6月19日
下一篇 2022年6月19日

相关推荐

发表回复

登录后才能评论