基于CFSFDP算法的復雜網絡聚類

王馨妍 郭怡君 寧雪梅

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

關鍵詞：復雜網絡;社區挖掘;密度聚類;CFSFDP算法;相似度

中圖分類號：TP301 文獻標識碼：A

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

1概述

現實世界中的許多復雜系統均可以轉化成復雜網絡，比如自然界中的生物系統，群體生態系統，人類社會中的經濟系統等州。在實際中，大部分的網絡都具有一定的社區結構，即這些復雜網絡可以自然的分成一些節點組，同一節點組內的節點連接緊密，相互作用較強，不同節點組間的節點連接稀疏，相互作用較弱。網絡的這種拓撲特性被稱為社區結構，相應地，每個節點組被稱為一個社區。社區結構體現了網絡中連邊關系的局部聚集特性，同樣體現了網絡中連邊的分布不均勻性。網絡中同一社區內的節點通常是功能相似或者性質相似，因此社區結構與網絡的功能結構和組織密切相關，通常對應著不同的功能單位。例如：萬維網是通過超鏈接連接網頁從而形成的一個個社區，由于超鏈接的緊密連接，每一個社區的內容都有著相近的話題。隨著社會的發展，復雜網絡成為越來越普遍的現象，因而如何將紛繁龐雜的網絡高效聚類，劃分為有現實意義的社區，成了當前多學科研究的重要問題，對研究人類社會與自然界有著至關重要的作用。

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

本文提出了一種新型的基于密度聚類算法的復雜網絡聚類算法，定義相似度矩陣求解節點間距離代替傳統歐氏距離，從而將密度聚類方法應用到復雜網絡聚類分析中，首先分析網絡對應的相似度矩陣，確定距離、密度，進而引用CFSFDP算法確定社區劃分。CFSFDP算法與K-medoids算法類似，他僅僅基于數據點之間的距離，與DBSCAN和均值平移算法一樣，能夠直觀地確定聚類數，發現非球型簇，并識別噪聲點。另外，CFSFDP算法不需要將數據嵌入進向量空間。本文基于此算法，可有效將復雜網絡聚類。

2基于CFSFDP的復雜網絡聚類算法

3實驗結果分析

3.1模擬數據

為檢驗算法的準確性、實用性與一般性，人工模擬生成10000個包含30個節點的隨機網絡樣本，并進行編號。設節點1-10為第1類，節點11-20為第II類，節點21-30為噪聲點。同一類內節點之間有邊相連的概率為P1=80%，每個噪聲點與任意類有邊相連的概率P2=20%，對10000個網絡樣本進行聚類，聚類結果如圖2所示：

分類錯誤的節點出現的頻率如圖3所示，聚類精度為98.031%。

3.2在ZacharyKarateClub數據集上的測試

Zachary Katie Club網絡㈣是通過對一個美國大學空手道俱樂部進行觀測而構建出的一個社會網絡，網絡包含34個節點和78條邊，其中節點表示俱樂部中的成員，而邊表示成員之間存在的友誼關系。測試結果如圖4所示，其中不同顏色的節點代表已知的劃分類，不同形狀的節點代表實驗組測試結果，在本數據集上的聚類準確率達到100%。

3.3在Dolphin Social Network數據集上的測試

Dolphin數據集是D.Lusseau等人使用長達7年的時間觀察新西蘭Doubtful Sound海峽62只海豚群體的交流情況而得到的海豚社會關系網絡。這個網絡具有62個節點，159條邊。節點表示海豚，而邊表示海豚間的頻繁接觸。

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

3.4在American CoHege Football數據集上的測試

College Football網絡是Newman根據美國大學生足球聯賽而創建的一個復雜的社會網絡。該網絡包含115個節點和616條邊，其中網絡中的結點代表足球隊，兩個結點之間的邊表示兩只球隊之間進行過一場比賽。參賽的115支大學生代表隊被分為12個聯盟，比賽的流程是聯盟內部的球隊先進行小組賽，然后再是聯盟之間球隊的比賽。這表明聯盟內部的球隊之間進行的比賽次數多于聯盟之間的球隊之間進行的比賽的次數。

聯盟即可表示為該網絡的真實社區結構，測試結果如圖6所示，準確率為92.174%。

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

4算法評價

本文基于CFsFDP算法對復雜網絡進行聚類，利用相似度度量代替傳統的歐式距離，從而將傳統的cFSFDP算法運用到網絡聚類中去。

雖然復雜網絡具有小世界性，網絡間的平均路徑長較小，但是本算法可以很好地確定鄰域半徑。另外，本文算法不僅剔除了噪聲點，還減少了聚類結果的局限性，能確定任意形狀和維度的類，具有很強的現實意義。利用真實數據集進行分析比對時，可以證實本文算法有效性較強，劃分的復雜網絡有較好的準確性，較符合當今研究需求。

算法的缺點是對參數較敏感，不同的參數會導致不同的聚類結果，需要觀察對比，選擇最優結果。此外，因為密度聚類的特性，當空間密度分布極度不均勻時，聚類結果較差。