近些年,，復(fù)雜網(wǎng)絡(luò)分析已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的重要研究內(nèi)容之一。復(fù)雜網(wǎng)絡(luò)分析可廣泛應(yīng)用于社會學(xué),、生物學(xué),、信息科學(xué)等眾多領(lǐng)域。在對這些復(fù)雜網(wǎng)絡(luò)進(jìn)行分析的方法之中,，社團(tuán)挖掘是最重要的研究內(nèi)容之一,。在復(fù)雜網(wǎng)絡(luò)中，社團(tuán)又被稱為聚類,，是一組緊密相連的節(jié)點集合,。社團(tuán)檢測往往需要很大的計算量,，雖然BigClam算法針對大規(guī)模網(wǎng)絡(luò)設(shè)計,，但仍不能處理含有20億條邊的數(shù)據(jù)集，社團(tuán)挖掘的質(zhì)量很低,。引申出來復(fù)雜網(wǎng)絡(luò)分析WCC(Weighted Community Clustering)通過復(fù)雜網(wǎng)絡(luò)中社團(tuán)含有的三角數(shù)量來評價社團(tuán)挖掘算法的性能,。在原始的WCC算法中,需要在每次迭代中對所有的社團(tuán)變化計算WCC值,因而計算量非常大。為了減小社團(tuán)變化帶來的WCC計算量,提出一種并行可擴(kuò)展的社團(tuán)挖掘算法,。對應(yīng)用WCC進(jìn)行社團(tuán)評價的方法進(jìn)行分析,提出一種包含預(yù)處理,、初始劃分和劃分改進(jìn)三個階段的并行社團(tuán)挖掘算法。在劃分改進(jìn)中,由于每次社團(tuán)變化都需要計算大量的WCC提升,基于社團(tuán)的統(tǒng)計量提出一種WCC近似計算方法,。大量的真實數(shù)據(jù)集實驗表明,提出的社團(tuán)挖掘算法與相關(guān)算法相比較,不僅社團(tuán)檢測的準(zhǔn)確性更高,而且具有更好的并行可擴(kuò)展性,。

對于給定的無向無權(quán)圖G = （V,E）,，通過最大化WCC值來挖掘圖中的不相交社團(tuán)。 WCC是一種復(fù)雜網(wǎng)絡(luò)社團(tuán)挖掘評價指標(biāo),，該指標(biāo)認(rèn)為真實網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)往往含有大量的三角,。由于社團(tuán)由緊密相連的節(jié)點組成，那么這些節(jié)點構(gòu)成三角的概率要相對較高,，WCC應(yīng)用該特征對圖的節(jié)點集合劃分進(jìn)行量化,。

以上就是WCC算法的介紹，感興趣的朋友可以自己動手實現(xiàn)WCC算法,，體驗他們的不同之處,，在這里我推薦使用GraphScope這個平臺。GraphScope是阿里達(dá)摩院智能計算實驗室研發(fā)并開源的全球首個一站式超大規(guī)模分布式圖計算平臺,，支持多種圖算法,，可以方便地進(jìn)行圖分析和圖計算，并且在性能上也達(dá)到極致,。在圖分析測試 LDBC GraphAnalytics Benchmark 上,，GraphScope 與 PowerGraph 以及其他最新系統(tǒng)比較，幾乎在所有算法和數(shù)據(jù)集的組合中居于領(lǐng)先水平,。從下圖中我們可以看到,，在執(zhí)行單源最短路徑算法（WCC算法）時，GraphScope用時0.52秒,，遠(yuǎn)小于PowerGraph的16.99秒,。

GraphScope 的白皮書、代碼已經(jīng)在 github.com/alibaba/graphscope 開源,，可以直接部署安裝試用,。

部分內(nèi)容來自論文復(fù)雜網(wǎng)絡(luò)基于wcc的并行可擴(kuò)展社團(tuán)挖掘算法