基于CFSFDP算法的復(fù)雜網(wǎng)絡(luò)聚類

王馨妍 郭怡君 寧雪梅

摘要：針對復(fù)雜網(wǎng)絡(luò)的特殊性質(zhì)導(dǎo)致社區(qū)挖掘質(zhì)量較低的問題，提出一種相似度度量方法代替?zhèn)鹘y(tǒng)的歐氏距離，從而將密度聚類CFSFDP（clustering bvfast search andfind of density peaks）算法應(yīng)用到復(fù)雜網(wǎng)絡(luò)聚類中去。首先，利用Pade逼近方法計(jì)算復(fù)雜網(wǎng)絡(luò)的拉普拉斯算子矩陣指數(shù);接著，歸一化核心矩陣得到相似度矩陣，并求倒數(shù)得出復(fù)雜網(wǎng)絡(luò)各節(jié)點(diǎn)間距離;最后，借鑒CFSFDP算法思想，將節(jié)點(diǎn)自身鄰域密度、與其他鄰域密度較高節(jié)點(diǎn)的距離結(jié)合作為判斷依據(jù)，得出聚類中心并剔除噪聲點(diǎn)，再將其余節(jié)點(diǎn)與距離最近的聚類中心劃分為一類。在人工模擬數(shù)據(jù)和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明：所提算法聚類準(zhǔn)確率較高，以超幾何定律為最佳匹配標(biāo)準(zhǔn)的已知組與實(shí)驗(yàn)組的隨機(jī)重疊概率較高，算法可用于挖掘高質(zhì)量的復(fù)雜網(wǎng)絡(luò)社區(qū)。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò);社區(qū)挖掘;密度聚類;CFSFDP算法;相似度

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2019）33-0278-04

1概述

現(xiàn)實(shí)世界中的許多復(fù)雜系統(tǒng)均可以轉(zhuǎn)化成復(fù)雜網(wǎng)絡(luò)，比如自然界中的生物系統(tǒng)，群體生態(tài)系統(tǒng)，人類社會中的經(jīng)濟(jì)系統(tǒng)等州。在實(shí)際中，大部分的網(wǎng)絡(luò)都具有一定的社區(qū)結(jié)構(gòu)，即這些復(fù)雜網(wǎng)絡(luò)可以自然的分成一些節(jié)點(diǎn)組，同一節(jié)點(diǎn)組內(nèi)的節(jié)點(diǎn)連接緊密，相互作用較強(qiáng)，不同節(jié)點(diǎn)組間的節(jié)點(diǎn)連接稀疏，相互作用較弱。網(wǎng)絡(luò)的這種拓?fù)涮匦员环Q為社區(qū)結(jié)構(gòu)，相應(yīng)地，每個(gè)節(jié)點(diǎn)組被稱為一個(gè)社區(qū)。社區(qū)結(jié)構(gòu)體現(xiàn)了網(wǎng)絡(luò)中連邊關(guān)系的局部聚集特性，同樣體現(xiàn)了網(wǎng)絡(luò)中連邊的分布不均勻性。網(wǎng)絡(luò)中同一社區(qū)內(nèi)的節(jié)點(diǎn)通常是功能相似或者性質(zhì)相似，因此社區(qū)結(jié)構(gòu)與網(wǎng)絡(luò)的功能結(jié)構(gòu)和組織密切相關(guān)，通常對應(yīng)著不同的功能單位。例如：萬維網(wǎng)是通過超鏈接連接網(wǎng)頁從而形成的一個(gè)個(gè)社區(qū)，由于超鏈接的緊密連接，每一個(gè)社區(qū)的內(nèi)容都有著相近的話題。隨著社會的發(fā)展，復(fù)雜網(wǎng)絡(luò)成為越來越普遍的現(xiàn)象，因而如何將紛繁龐雜的網(wǎng)絡(luò)高效聚類，劃分為有現(xiàn)實(shí)意義的社區(qū)，成了當(dāng)前多學(xué)科研究的重要問題，對研究人類社會與自然界有著至關(guān)重要的作用。

聚類算法根據(jù)元素相似性劃分類別，有很多種不同的策略。K-means和K-medoids算法以到達(dá)聚類中心的最小距離定義目標(biāo)函數(shù)，但是由于數(shù)據(jù)點(diǎn)始終被分到距離最近的聚類中心，這些方法無法檢測到非球星的簇。在基于分布的算法中，準(zhǔn)確性取決于實(shí)驗(yàn)概率表示數(shù)據(jù)的能力。基于密度的DB-SCAN算法能夠發(fā)現(xiàn)任意形狀的簇并識別噪聲點(diǎn)，但是選擇的密度閾值可能是非平凡的，均值平移聚類方法可避免這樣的缺點(diǎn)，但是計(jì)算成本較高且只適用于一組坐標(biāo)定義的數(shù)據(jù)。

本文提出了一種新型的基于密度聚類算法的復(fù)雜網(wǎng)絡(luò)聚類算法，定義相似度矩陣求解節(jié)點(diǎn)間距離代替?zhèn)鹘y(tǒng)歐氏距離，從而將密度聚類方法應(yīng)用到復(fù)雜網(wǎng)絡(luò)聚類分析中，首先分析網(wǎng)絡(luò)對應(yīng)的相似度矩陣，確定距離、密度，進(jìn)而引用CFSFDP算法確定社區(qū)劃分。CFSFDP算法與K-medoids算法類似，他僅僅基于數(shù)據(jù)點(diǎn)之間的距離，與DBSCAN和均值平移算法一樣，能夠直觀地確定聚類數(shù)，發(fā)現(xiàn)非球型簇，并識別噪聲點(diǎn)。另外，CFSFDP算法不需要將數(shù)據(jù)嵌入進(jìn)向量空間。本文基于此算法，可有效將復(fù)雜網(wǎng)絡(luò)聚類。

2基于CFSFDP的復(fù)雜網(wǎng)絡(luò)聚類算法

3實(shí)驗(yàn)結(jié)果分析

3.1模擬數(shù)據(jù)

為檢驗(yàn)算法的準(zhǔn)確性、實(shí)用性與一般性，人工模擬生成10000個(gè)包含30個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)樣本，并進(jìn)行編號。設(shè)節(jié)點(diǎn)1-10為第1類，節(jié)點(diǎn)11-20為第II類，節(jié)點(diǎn)21-30為噪聲點(diǎn)。同一類內(nèi)節(jié)點(diǎn)之間有邊相連的概率為P1=80%，每個(gè)噪聲點(diǎn)與任意類有邊相連的概率P2=20%，對10000個(gè)網(wǎng)絡(luò)樣本進(jìn)行聚類，聚類結(jié)果如圖2所示：

分類錯誤的節(jié)點(diǎn)出現(xiàn)的頻率如圖3所示，聚類精度為98.031%。

3.2在ZacharyKarateClub數(shù)據(jù)集上的測試

Zachary Katie Club網(wǎng)絡(luò)㈣是通過對一個(gè)美國大學(xué)空手道俱樂部進(jìn)行觀測而構(gòu)建出的一個(gè)社會網(wǎng)絡(luò)，網(wǎng)絡(luò)包含34個(gè)節(jié)點(diǎn)和78條邊，其中節(jié)點(diǎn)表示俱樂部中的成員，而邊表示成員之間存在的友誼關(guān)系。測試結(jié)果如圖4所示，其中不同顏色的節(jié)點(diǎn)代表已知的劃分類，不同形狀的節(jié)點(diǎn)代表實(shí)驗(yàn)組測試結(jié)果，在本數(shù)據(jù)集上的聚類準(zhǔn)確率達(dá)到100%。

3.3在Dolphin Social Network數(shù)據(jù)集上的測試

Dolphin數(shù)據(jù)集是D.Lusseau等人使用長達(dá)7年的時(shí)間觀察新西蘭Doubtful Sound海峽62只海豚群體的交流情況而得到的海豚社會關(guān)系網(wǎng)絡(luò)。這個(gè)網(wǎng)絡(luò)具有62個(gè)節(jié)點(diǎn)，159條邊。節(jié)點(diǎn)表示海豚，而邊表示海豚間的頻繁接觸。

聚類結(jié)果如圖5所示，準(zhǔn)確率為88.710%，有7個(gè)處于邊緣的點(diǎn)劃分錯誤，但是存在一定的節(jié)點(diǎn)本身歧義性的干擾。

3.4在American CoHege Football數(shù)據(jù)集上的測試

College Football網(wǎng)絡(luò)是Newman根據(jù)美國大學(xué)生足球聯(lián)賽而創(chuàng)建的一個(gè)復(fù)雜的社會網(wǎng)絡(luò)。該網(wǎng)絡(luò)包含115個(gè)節(jié)點(diǎn)和616條邊，其中網(wǎng)絡(luò)中的結(jié)點(diǎn)代表足球隊(duì)，兩個(gè)結(jié)點(diǎn)之間的邊表示兩只球隊(duì)之間進(jìn)行過一場比賽。參賽的115支大學(xué)生代表隊(duì)被分為12個(gè)聯(lián)盟，比賽的流程是聯(lián)盟內(nèi)部的球隊(duì)先進(jìn)行小組賽，然后再是聯(lián)盟之間球隊(duì)的比賽。這表明聯(lián)盟內(nèi)部的球隊(duì)之間進(jìn)行的比賽次數(shù)多于聯(lián)盟之間的球隊(duì)之間進(jìn)行的比賽的次數(shù)。

聯(lián)盟即可表示為該網(wǎng)絡(luò)的真實(shí)社區(qū)結(jié)構(gòu)，測試結(jié)果如圖6所示，準(zhǔn)確率為92.174%。

12個(gè)類的log（Pol）值如圖7所示，除了第六類大于-17.00之外，其余類的聚類結(jié)果與已知結(jié)果的匹配度都較好。

4算法評價(jià)

本文基于CFsFDP算法對復(fù)雜網(wǎng)絡(luò)進(jìn)行聚類，利用相似度度量代替?zhèn)鹘y(tǒng)的歐式距離，從而將傳統(tǒng)的cFSFDP算法運(yùn)用到網(wǎng)絡(luò)聚類中去。

雖然復(fù)雜網(wǎng)絡(luò)具有小世界性，網(wǎng)絡(luò)間的平均路徑長較小，但是本算法可以很好地確定鄰域半徑。另外，本文算法不僅剔除了噪聲點(diǎn)，還減少了聚類結(jié)果的局限性，能確定任意形狀和維度的類，具有很強(qiáng)的現(xiàn)實(shí)意義。利用真實(shí)數(shù)據(jù)集進(jìn)行分析比對時(shí)，可以證實(shí)本文算法有效性較強(qiáng)，劃分的復(fù)雜網(wǎng)絡(luò)有較好的準(zhǔn)確性，較符合當(dāng)今研究需求。

算法的缺點(diǎn)是對參數(shù)較敏感，不同的參數(shù)會導(dǎo)致不同的聚類結(jié)果，需要觀察對比，選擇最優(yōu)結(jié)果。此外，因?yàn)槊芏染垲惖奶匦裕?dāng)空間密度分布極度不均勻時(shí)，聚類結(jié)果較差。