Leiden算法如何预设社区数量？附Louvain算法预设实现示例

我在处理组合问题时采用社区检测方法，需要预先设定社区数量。在communities包的Louvain算法中可以实现该功能，示例代码如下：

# ! pip install communities

import numpy as np
from communities.algorithms import louvain_method

A = np.array([[1, 1, 0, 0, 0, 0, 1, 0], 
              [1, 0, 0, 1, 0, 0, 0, 0], 
              [0, 1, 1, 0, 0, 1, 0, 0],
              [0, 0, 1, 1, 0, 0, 0, 0],
              [0, 1, 0, 0, 0, 1, 0, 0], 
              [0, 0, 1, 0, 1, 0, 0, 0],
              [0, 1, 0, 1, 0, 0, 1, 0], 
              [0, 1, 0, 1, 1, 0, 1, 1], 
              [1, 0, 0, 0, 0, 0, 0, 1], 
              [0, 1, 0, 0, 1, 0, 0, 0]])

A_sq = np.matmul(A,A.transpose())

nbr_communities = 3
communities, _ = louvain_method(A_sq, nbr_communities)


print("len communities = ", len(communities), "nbr_communities=", nbr_communities)
print(communities,"\n")
for com in communities:
  print(A[list(com)], "\n")

但我在cdlib或networkx库中未找到Leiden算法的类似预设社区数量的参数，请问是否有支持该功能的Leiden算法实现，或其他可达成此需求的方法？

一、支持预设社区数的Leiden算法实现 #

可以直接使用leidenalg库结合igraph，通过约束模块度分区类来限制社区数量：

1. 先安装依赖：

   pip install leidenalg igraph
   

2. 示例代码：

   import igraph as ig
   import leidenalg as la
   import numpy as np
   
   # 复用示例中的邻接矩阵
   A = np.array([[1, 1, 0, 0, 0, 0, 1, 0], 
                 [1, 0, 0, 1, 0, 0, 0, 0], 
                 [0, 1, 1, 0, 0, 1, 0, 0],
                 [0, 0, 1, 1, 0, 0, 0, 0],
                 [0, 1, 0, 0, 0, 1, 0, 0], 
                 [0, 0, 1, 0, 1, 0, 0, 0],
                 [0, 1, 0, 1, 0, 0, 1, 0], 
                 [0, 1, 0, 1, 1, 0, 1, 1], 
                 [1, 0, 0, 0, 0, 0, 0, 1], 
                 [0, 1, 0, 0, 1, 0, 0, 0]])
   A_sq = np.matmul(A, A.transpose())
   
   # 转换为igraph对象
   g = ig.Graph.Adjacency((A_sq > 0).tolist())
   nbr_communities = 3
   
   # 用约束模块度分区限制社区数量
   partition = la.find_partition(g, la.ConstrainedModularityVertexPartition, 
                                 max_communities=nbr_communities)
   
   # 输出结果
   print(f"实际社区数量: {len(partition)}")
   for idx, comm in enumerate(partition):
       print(f"社区{idx+1}: {comm}")
   

二、其他替代实现方法 #

• Louvain结果后调整：先用标准Louvain算法得到初始社区，再通过合并社区（比如按模块度增益从高到低合并、或合并规模最小的社区），直到社区数量等于目标值。
• 谱聚类直接设定聚类数：适用于邻接矩阵形式的图数据，sklearn的谱聚类支持直接指定聚类数量：

  from sklearn.cluster import SpectralClustering
  import numpy as np
  
  A_sq = np.matmul(A, A.transpose())
  nbr_communities = 3
  
  sc = SpectralClustering(n_clusters=nbr_communities, affinity='precomputed')
  labels = sc.fit_predict(A_sq)
  
  # 整理为社区列表格式
  communities = [np.where(labels == i)[0].tolist() for i in range(nbr_communities)]
  print("目标社区数量下的划分结果:\n", communities)
  

内容的提问来源于stack exchange，提问作者Daniel Schwegler