algorithm - 我可以为图形考虑哪些聚类算法？

Question

假设我有一个无向加权连通图。我想将具有最高边值的顶点组合在一起(顶点度数)。使用聚类算法是一种方法。对于此任务，我可以考虑使用哪些聚类算法？我希望很清楚；任何需要澄清的问题，请询问。谢谢。

Answer 1

有两种主要方法 - 将您的图表作为现有工具的输入，或者使用您对该图表(及其领域)的专业知识来创建表示，然后对其应用机器学习方法。

我将从第二种方法开始:

如果您只有节点和边(每个节点没有更多数据)，您首先需要考虑每个节点\边的表示。我将解释节点，但它应该与边的情况类似。

最简单的方法是将每个节点 n 表示为连接向量:

每个节点将表示为n=(Ia(n),Ib(n),Ic(n),Id(n),Ie(n))，其中Ii (n)=1 如果节点 n 是节点 i 的“ friend ”(邻居)，否则为 0。 (例如a=(0,1,1,0,1))

请注意，您可以决定一个节点是否是它自己的 friend 。

第二种方法与第一种方法非常相似，是使用边的权重向量:

n=(W(a,n),W(b,n),W(c,n),W(d,n),W(e,n)) ，其中W(i,n) 是边(i,n) 的权重。

还有几种表示节点的方法，但这足以对其进行一些计算。

完成此演示文稿后，您可以开始对其应用一些聚类算法。

kmeans被认为非常适合这项任务，并且sklearn has a great implementation .它有一些您可以(并且应该)配置的参数(即距离度量)。

kmeans 的乘积，是k 个不同的非交叉节点组。

如果您想将图形传递给算法并获得一些度量值，可以应用更高级的算法。 community detection用于在图中查找社区。同样，有一个很好的 python implementation在 networkx 包中。