社区发现
2017-06-12 本文已影响130人
jacksu在简书
社区发现（Community Detection）算法用来发现网络中的社区结构，也可以看做是一种聚类算法。
分层聚类
两两对比，最相似的两个聚类为一个中间态，中间态再参与两两对比，所以计算量比较大，用聚类树可以直观形象的表示。
clusters.jpg
k-means
这个算法其实很简单，如下图所示：
从上图中，我们可以看到，A, B, C, D, E 是五个在图中点。而灰色的点是我们的种子点，也就是我们用来找点群的点。有两个种子点，所以K=2。
然后，K-Means的算法如下：
随机在图中取K（这里K=2）个种子点。
然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。（上图中，我们可以看到A,B属于上面的种子点，C,D,E属于下面中部的种子点）
接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步）
然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了A,B,C，下面的种子点聚合了D，E）。
这个算法很简单，但是有些细节我要提一下，求距离的公式我不说了，大家有初中毕业水平的人都应该知道怎么算的。我重点想说一下“求点群中心的算法”
