社區(qū)發(fā)現(xiàn)（Community Detection）算法用來(lái)發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，也可以看做是一種聚類算法。
分層聚類
兩兩對(duì)比，最相似的兩個(gè)聚類為一個(gè)中間態(tài)，中間態(tài)再參與兩兩對(duì)比，所以計(jì)算量比較大，用聚類樹(shù)可以直觀形象的表示。
k-means
這個(gè)算法其實(shí)很簡(jiǎn)單，如下圖所示：
從上圖中，我們可以看到，A, B, C, D, E 是五個(gè)在圖中點(diǎn)。而灰色的點(diǎn)是我們的種子點(diǎn)，也就是我們用來(lái)找點(diǎn)群的點(diǎn)。有兩個(gè)種子點(diǎn)，所以K=2。
然后，K-Means的算法如下：
隨機(jī)在圖中取K（這里K=2）個(gè)種子點(diǎn)。
然后對(duì)圖中的所有點(diǎn)求到這K個(gè)種子點(diǎn)的距離，假如點(diǎn)Pi離種子點(diǎn)Si最近，那么Pi屬于Si點(diǎn)群。（上圖中，我們可以看到A,B屬于上面的種子點(diǎn)，C,D,E屬于下面中部的種子點(diǎn)）
接下來(lái)，我們要移動(dòng)種子點(diǎn)到屬于他的“點(diǎn)群”的中心。（見(jiàn)圖上的第三步）
然后重復(fù)第2）和第3）步，直到，種子點(diǎn)沒(méi)有移動(dòng)（我們可以看到圖中的第四步上面的種子點(diǎn)聚合了A,B,C，下面的種子點(diǎn)聚合了D，E）。
這個(gè)算法很簡(jiǎn)單，但是有些細(xì)節(jié)我要提一下，求距離的公式我不說(shuō)了，大家有初中畢業(yè)水平的人都應(yīng)該知道怎么算的。我重點(diǎn)想說(shuō)一下“求點(diǎn)群中心的算法”
LPA
FastUnFolding
GraphTFIDF
SimRank
社區(qū)發(fā)現(xiàn)(Community Detection)算法
社區(qū)發(fā)現(xiàn)算法（三）
