分区加权无向图

数据挖掘 聚类 图表
2021-10-10 01:29:05

我有一系列边和权重：

[['a', 'b', 4],
 ['a', 'c', 3],
 ['c', 'a', 2], 
 ...]

我有大约 100,000 条边，权重在 1 到 700 之间，大多数在 100 左右。

我正在考虑使用马尔可夫聚类算法，但是想联系一下，看看这是否最好用。亲和传播呢？无论哪种情况，工作流程是什么？您通常有一种方法来衡量结果的聚类程度。是否有相当于剪影分数？有没有办法可视化集群？

3个回答

即使是简单的互联网搜索，也能发现大量关于图聚类方法和算法的论文。本文很可能是最好的起点，因为它从问题以及解决方案的方法、方法和算法方面对该主题进行了相当全面的概述。其余的您可以通过在线搜索轻松找到。关于图形聚类可视化，我建议您查看我的相关答案- 我很确定我在那里引用的工具也能够可视化图形集群。

所以你需要的是Modularity score。作为一个图聚类的人（我的硕士论文主题，博士研究和我过去 2.5 年的主要研究方向），我建议你以社区检测的名义了解物理学家在复杂网络领域所做的工作。如果你搜索最先提出模块化分数的Mark Newman 教授，你会发现很多该领域的有趣论文。Martin Rosvall的Infomap算法、Vincent Blondel的Louvain算法和Aaron Clauset的CNM算法是一些最知名的算法。

现在最常用的图聚类算法是Vincent Blondel的算法，它同时实现了 NetworkX 和 igraph（如果你是一个 python 人！）。该算法最初用于加权图，可能会回答您的问题。

希望对您有所帮助，祝您好运！

如果您使用的是 python，并且已经使用NetworkX创建了加权图，那么您可以使用python-louvain进行聚类。其中 G 是加权图：

import community 
partition = community.best_partition(G, weight='weight')
其它你可能感兴趣的问题
上一篇用于统计推断的最佳 Python 库 下一篇对 Java 异常进行分类