leidenalg 包教程（2）

date
Jun 24, 2022
slug
leidenalg-多重网络社区检测
status
Published
tags
ML
KG
教程
leidenalg
summary
type
Post

Leidenalg 多路复用社区检测

一、引言

在复杂网络分析中，社区检测是关键任务之一。leidenalg 库提供了多路复用（Multiplex）社区检测功能，适用于处理多个图层或切片的网络。本文将介绍如何使用 leidenalg 进行多路复用社区检测。

二、多路复用社区检测基础概念

层（Layer）与切片（Slice）

  • 层（Layer） ：多个图定义在相同顶点集上，但边集不同。每个节点属于同一社区。
  • 切片（Slice） ：图可以有不同的顶点集，节点在不同切片中可属于不同社区。需将切片转换为层才能使用相同算法。

三、层多路复用（Layer Multiplex）

示例：电话与邮件通信图

假设 G_telephone 和 G_email 分别表示朋友间电话和邮件通信图，顶点集相同。可使用 find_partition_multiplex() 函数进行社区检测：

层权重与不同分区类型

  • 层权重（layer_weight） ：可为不同层指定权重，调整层在整体质量中的重要性。如邮件层权重设为 0.5：
  • 不同分区类型 ：可为不同层使用不同分区类型，如为电话图使用 CPMVertexPartition，邮件图使用更高分辨率参数：

负链接处理

当图包含负链接（如冲突或敌意关系）时，可将图分为正负两层，正层权重为正，负层权重为负。例如：

四、二分网络社区检测

二分网络中节点分为两类，如产品和顾客，仅允许两类间链接。可通过创建三个层来检测社区：
  • 层 1 ：所有节点大小为 1，包含相关链接。
  • 层 2 ：仅一类节点大小为 1，无链接。
  • 层 3 ：另一类节点大小为 1，无链接。
将层 2 和层 3 的层权重设为 -1，层 1 权重设为 1，可实现二分网络社区检测。例如：
CPM 方法的公式为：
其中，、 和 分别表示类内连接、类内连接和类间连接的分辨率参数。通过将三个层的权重和分辨率参数设置为上述方式，可以实现对二分网络的社区检测。

五、切片到层的转换

背景与方法

多路复用层有两局限：各图需有相同顶点集；节点只能属于一个社区。为突破此限制，引入切片概念。切片是不同图，可有不同顶点集，节点在不同切片中可属不同社区。通过构建耦合图，将切片转换为层。
notion image
notion image

示例：三个时间切片

假设三个时间切片 G_1、G_2、G_3，耦合图为 1 -- 2 -- 3。转换步骤如下：
  1. 创建耦合图并设置权重：
  1. 转换为层：
  1. 创建各层分区，并优化：
注意 ：通常将切片间层设为 CPMVertexPartition，分辨率参数为 0，节点大小设为 0。

六、时间社区检测

对于时间切片的社区检测，可以使用 find_partition_temporal() 函数。例如：
或者使用 time_slices_to_layers() 函数获取层和分区：

七、总结

本文介绍了 leidenalg 库的多路复用社区检测功能，包括层与切片的概念、层多路复用的实现、负链接与二分网络的处理，以及切片到层的转换方法和时间社区检测。通过这些方法，可更灵活地分析复杂网络的社区结构。

八、参考文献

  1. Mucha, P. J., Richardson, T., Macon, K., Porter, M. A., & Onnela, J.-P. (2010). Community structure in time-dependent, multiscale, and multiplex networks. Science, 328(5980), 876–8. 10.1126/science.1184819
  1. Traag, V. A., & Bruggeman, J. (2009). Community detection in networks with positive and negative links. Physical Review E, 80(3), 036115. 10.1103/PhysRevE.80.036115
  1. Barber, M. J. (2007). Modularity and community detection in bipartite networks. Physical Review E, 76(6), 066102. 10.1103/PhysRevE.76.066102

© Baiye 2022 - 2025