python - 如何在 python - networkx 包中根据边缘的密度和权重找到网络簇

Question

我使用Python包networkx构建了一个网络，每条边都有一个权重，指示两个节点在相关性方面的接近程度。

如果有一个内置算法可以返回聚类图，并将每个节点分配给它的聚类 ID(1 到 k)，那就太理想了。

如果它可以根据边缘的权重进行聚类，那就更好了，但不是关键......

知道如何做到这一点吗？

Answer 1

您可能想查看包 python-louvain 。有了它，您可以使用函数 best_partition 检测图表中的社区。从功能描述来看:

Compute the partition of the graph nodes which maximises the modularity (or try..) using the Louvain heuristices

This is the partition of highest modularity, i.e. the highest partition of the dendrogram generated by the Louvain algorithm.

在我的示例中，我计算了 karate_club_graph 的社区。 (请注意，即使我的图表没有加权边，我也将 best_partition 与 weight 关键字一起使用 - 我只是展示在您的情况下如何使用该函数.)

import networkx as nx
import community

G = nx.karate_club_graph()
p = community.best_partition(G, weight='weight')
print(p)

输出:

{0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 0, 8: 2, 9: 0, 10: 1, 11: 0, 12: 0, 13: 0, 14: 2, 15: 2, 16: 1, 17: 0, 18: 2, 19: 0, 20: 2, 21: 0, 22: 2, 23: 3, 24: 3, 25: 3, 26: 2, 27: 3, 28: 3, 29: 2, 30: 2, 31: 3, 32: 2, 33: 2}

输出是一个字典(键=节点，值=分区)。分区从 0 到 k-1。如果您需要它们从 1 到 k，您只需将字典值增加到 +1 即可。

for k, v in p.items():
    p[k] = v + 1