graph - 不同大小的簇邻接矩阵

Question

我为不同大小的有向图创建了邻接矩阵。我有大约 30,000 个矩阵，每个矩阵都在一个单独的文本文件中。我如何对它们进行集群，是否有可用的工具。表示用于聚类的有向图的最佳方法是什么。

谢谢你。

Answer 1

我会尝试 k-means 和 voronoi-diagrams。它可以通过使用最小生成树和寻找最长边来计算。然后，您可以使用 mst 边缘作为中心，使用传统的 k-means 计算不同的集群。另一种可能性是分层集群，例如空间填充曲线。参见例如：https ://stats.stackexchange.com/questions/1475/visualization-software-for-clustering 。

Answer 2

你到底想达到什么目的？对相似的矩阵进行分组，对吗？使用 k-means，您将不会在这里获得太多乐趣。邻接矩阵是二元的；将它们解释为巨大的向量并在它们上计算 Lp 范数距离（例如欧几里得距离），然后计算平均矩阵 - 这就是 k-means 所做的 - 对我来说听起来并不明智。另外，你很可能会被维度的诅咒所困扰。高维数将使所有矩阵看起来都相似。

对于几乎任何聚类算法，您作为“领域专家”必须回答的第一个问题是：是什么让两个邻接矩阵相似？一旦您将其形式化，您将能够运行许多聚类算法，包括经典的单链路聚类、DBSCAN 或 OPTICS。

Answer 3

您可以在此处找到有关图形特征/统计的一些想法：http: //networkx.lanl.gov/reference/algorithms.html