相同分辨率参数下Leiden聚类结果为何非确定性？

我在iGraph中使用Leiden算法时发现，使用相同的resolution_parameter重复聚类会得到不同结果。以下是调试代码及运行结果：

# Do the initial clustering
clustering = do_leiden_clustering(G, resolution_parameter=initial_resolution, n_iterations=n_iterations)
best_num_clusters, best_modularity, best_membership = len(clustering), clustering.modularity, clustering.membership
print(f"best_num_clusters = {best_num_clusters}")
num_clusters = best_num_clusters

i = 0
# Continue until there is a difference between current and previous clustering results.
while num_clusters == best_num_clusters:
    clustering = do_leiden_clustering(G, resolution_parameter=initial_resolution, n_iterations=n_iterations)
    num_clusters, best_modularity, best_membership = len(clustering), clustering.modularity, clustering.membership
    print(f"{i} num_clusters = {num_clusters}")

    if num_clusters != best_num_clusters:
        # best_num_clusters = num_clusters
        print(f"{i} End because num_clusters = {num_clusters} != {best_num_clusters}!")
        break
    i += 1

运行结果：

best_num_clusters = 2
0 num_clusters = 2
1 num_clusters = 2
2 num_clusters = 2
3 num_clusters = 2
4 num_clusters = 2
5 num_clusters = 1
5 End because num_clusters = 1 != 2!

由于聚类簇数发生变化，说明聚类结果具有非确定性，请问这是什么原因？

原因分析 #

• 算法内置随机性：Leiden算法的核心流程包含随机步骤，比如初始化阶段随机分配节点的社区标签，或者迭代时随机选择节点处理顺序。这些随机操作会引导算法走向不同的局部最优解，当网络存在多个得分相近的社区划分时，最终结果就会出现差异。
• 模块化得分的多峰性：当前resolution_parameter下，若网络存在多种社区划分的模块化得分几乎一致，算法在不同运行中可能收敛到这些不同的最优解，进而产生不同的簇数量。你遇到的2簇和1簇结果，说明这两种划分的模块化得分可能非常接近，算法随机选择了其中一种。
• 迭代收敛的不确定性：如果设置的n_iterations参数较小，算法可能未完全收敛就终止，不同运行的终止状态也可能存在差异。不过从你的结果来看，前5次都稳定得到2簇，第6次得到1簇，这种情况更倾向于前两种原因。

内容的提问来源于stack exchange，提问作者Prakriti Paul