在使用 python-louvain 缩放图的边权重后，什么会导致社区检测到不同的结果？

Question

我注意到，如果我使用相同的值更改图中的所有边权重，则community.best_partition并不总是导致相同的社区。

我在所有情况下都使用相同的随机状态，图形完全相同，只是不是所有边权重都等于 1，例如它们可能等于 5。模块化的定义抵消了这个乘以邻接矩阵的因素当我阅读算法时，我找不到应该改变结果的步骤。是否有导致这种差异的原因？

import networkx as nx
import community

from sklearn.metrics import adjusted_rand_score


def main():
    g = nx.davis_southern_women_graph()
    nodes = g.nodes()
    clusters_init = community.best_partition(g, random_state=10)
    print("modularity with initial clusters = %.15f" % community.modularity(clusters_init, g))

    labels_init = [clusters_init[n] for n in nodes]
    for num in range(1, 9):

        for u, v in g.edges():
            g[u][v]["weight"] = num

        clusters = community.best_partition(g, random_state=10)
        labels = [clusters[n] for n in nodes]
        print("value of edge weight = %d," % num, "modularity = %.15f," % community.modularity(clusters, g),
              "modularity with initial clusters = %.15f," % community.modularity(clusters_init, g),
              "adjusted rand score = %.3f" % adjusted_rand_score(labels_pred=labels, labels_true=labels_init))


if __name__ == "__main__":
    main()

初始集群的模块化 = 0.334869334679965

边缘权重值 = 1，模块化 = 0.334869334679965，初始集群的模块化 = 0.334869334679965，调整后的兰特分数 = 1.000

边缘权重值 = 2，模块化 = 0.334869334679965，初始集群的模块化 = 0.334869334679965，调整后的兰特分数 = 1.000

边缘权重值 = 3，模块化 = 0.334869334679965，初始集群的模块化 = 0.334869334679965，调整后的兰特分数 = 1.000

边缘权重值 = 4，模块化 = 0.334869334679965，初始集群的模块化 = 0.334869334679965，调整后的兰特分数 = 1.000

边缘权重值 = 5，模块化 = 0.332470647645499，初始集群的模块化 = 0.334869334679965，调整后的兰特分数 = 0.676

边缘权重值 = 6，模块化 = 0.334869334679965，初始集群的模块化 = 0.334869334679965，调整后的兰特分数 = 1.000

边缘权重值 = 7，模块化 = 0.332470647645499，初始集群的模块化 = 0.334869334679965，调整后的兰特分数 = 0.676

边缘权重值 = 8，模块化 = 0.334869334679965，初始集群的模块化 = 0.334869334679965，调整后的兰特分数 = 1.000

Answer 1

Louvain 是一种基于模块化的方法，本质上是不确定的。Louvain 的许多实现都耍花招，试图让 Louvain 看起来是确定性的。只是猜测，代码可能会在处理边缘的顺序中包含边缘权重。更改该顺序可能会更改检测到的簇。例如，仅更改顶点 ID（不会更改图的结构）会导致不同的聚类。Louvain、Leiden 和一般模块化的非确定性本质得到了很好的研究。谷歌搜索会发现许多论文。