什么聚类算法可以考虑图？

Question

假设我有一个无向加权连通图。我想将具有最高边缘值的顶点组合在一起（顶点度数）。使用聚类算法是一种方法。我可以考虑哪些聚类算法来完成这项任务？我希望这是清楚的;任何澄清问题，请询问。谢谢。

Answer 1

主要有两种方法 - 给你的图作为输入到现有的工具，或使用你对这个图（以及其领域），以创建一个代表，然后在将其应用于机器学习方法的专业知识。

我会用第二种方法启动：

如果只有节点和边（每个节点没有进一步的数据），你首先需要考虑每个节点\边的表示。我将解释有关节点，但它应该在边缘情况下应该类似。

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

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

注意，您可以决定一个节点是其自身的朋友。

第二种方法，这是相当类似于第一个，是使用边缘的权重向量：

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用于在图表中查找社区。再次，在networkx包中有一个很好的python implementation。