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

姜皓月+石夢彤+關童升+王思奇+陳嘉威+寧雪梅

摘要：復雜網絡聚類方法可以挖掘復雜網絡的結構，對復雜網絡的研究具有重要意義。DBSCAN算法是一種基于密度的聚類算法，主要用于對傳統數據點集進行聚類。由于復雜網絡的特殊性質，對DBSCAN算法進行改進，采用相似度度量法代替傳統算法中的歐式距離度量，對復雜網絡進行聚類。其優點是聚類快速、可以發現任意形狀的聚類、自動確定聚類數以及有效剔除噪聲點。

關鍵詞：復雜網絡；網絡聚類；密度聚類

中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2018）02-0141-03

Complex Network Clustering Based on DBSCAN Algorithm

JIANG Hao-yue， SHI Meng-tong， GUAN Tong-sheng， WANG Si-qi， CHEN Jia-wei， NING Xue-mei

（Beijing Forestry University College of Science， Beijing 100083， China）

Abstract： The method of complex network clustering can excavate the structure of complex network， which is of great significance to the research of complex network.DBSCAN algorithm is a density clustering algorithm， which is used to cluster traditional data points.Due to the special nature of complex network， to improve the DBSCAN algorithm，adopt the method of similarity measure to replace the Euclidean distance measurement in the traditional DBSCAN algorithm to cluster the complex network. .The advantages of this method are clustering fast， finding the clustering of arbitrary shapes， automatically determining the clustering number， and effectively eliminating the noise points.

Key words： complex network； network clustering； density clustering

現實世界中的許多復雜系統直接或間接地以復雜網絡的形式存在[1]，如社交網絡、生物網絡。研究者們通過對網絡性質的深入研究，發現復雜網絡具有集團化的特性。也就是說，整個網絡是由若干個“類”構成的[2]。聚類算法把一組結構未知的數據進行分類，使每一類之間的相似性盡可能小，每一類之內的相似性盡可能大，其目的是尋找數據中有效的結構。因此，利用聚類算法可揭示出復雜網絡中存在的網絡社團結構、發現復雜網絡中隱藏的規律。

DBSCAN是一種基于密度的聚類算法，要求聚類空間中的一定區域內所包含的對象的數目不小于某一給定閾值[3]。DBSCAN算法的優勢是可以發現任意形狀的聚類、自動確定聚類數以及有效剔除噪聲點。因此本文使用DBSCAN算法對復雜網絡進行聚類。由于網絡與數據點集對距離的定義不同，本文用相似度度量代替傳統DBSCAN算法中的距離度量。測試結果表明該算法對復雜網絡的聚類是可行的。

1 算法介紹

DBSCAN算法是一種基于密度的空間數據聚類方法，其中心思想是：對于某一聚類中的每個對象，在給定半徑 （文中用 Eps表示 ）的鄰域內數據對象個數必須大于某個給定值，也就是說，鄰域密度必須超過某一閥值 （文中用MinPts表示）[4]。

為使用此算法進行復雜網絡聚類，在一個網絡D中，進行如下定義：

定義1（相似度Sij）Sij代表網絡中的節點i和j的連接程度，與節點i，j間的距離成反比，具體定義如下[5]：

首先，對于一個無向無權的網絡G =（V，E），G的拉普拉斯算子是矩陣：

[Li，j=1， for i～j-di， for i=j0， otherwise ] （1）

其中i?j表示第i個和第j個節點有邊相連，di是節點的度。矩陣L的指數定義為：

[Kβ≡exp（βL）=limn→∞（I+βLn）n ] （2）

其中β是取值為正的常數，通常在 0.1～0.5之間。而這個極限總是存在，將上式展開如下：

[expβL=I+βL+β22L2+β33！L3+… ] （3）

得到的矩陣Kβ是對稱和正定的。利用Pade逼近方法計算矩陣指數[6]。通過歸一化核心矩陣Kβ，相似度矩陣Sβ可以定義為：

[Sβij=KβijKβiiKβjj ] （4）

定義2（鄰域N（p））：點p的鄰域為：

[Np={q|dist（p，q≤Eps）}]）（Eps為鄰域半徑，為給定的相似度Sij的倒數）

定義3（鄰域密度Dens（p））：點p的鄰域密度是N（p）所包含的點的數目。

定義4（核心點Core Points）網絡中，鄰域密度大于某一給定閾值MinPts的點。

定義5（邊界點Border Points）落在核心點的鄰域內且鄰域密度小于某一給定MinPts的點。endprint

定義6（直接密度可達）若p在q的鄰域內，且q是核心點，則稱p從q直接密度可達。

定義7（密度可達）若有點p1，p2，…，pn，且pi從pi+1直接密度可達，則稱點p1從pn密度可達。

定義8（密度連接）若有點o，且p、q都是從o關于同一[Eps]和MinPts密度可達的，則p和q是密度連接的。

定義9（類Cluster）若p為一核心點，D中所有從 p 密度可達的節點和p構成的集合稱為一個類。

定義10（噪聲點Noise Points）D中不屬于任何一類的點。

算法描述如下：

訪問一個出發點p，若p為核心點，找出所有密度可達的點形成一個類C，并將p標記為已處理。若p為非核心點，暫時將p標記為噪聲點。

找到第一個類C后，重復步驟1，處理C中所有的節點，繼續將C進行擴展[7]。

C中的節點全部訪問過后，用同樣的方法訪問C以外節點。直到所有節點都歸入某個類中或被標記為噪聲點。

算法實現的實例如圖1，圖中八個節點被分為兩類，并以不同顏色標記。

2 實例驗證

2.1 模擬數據

為檢驗算法的準確性與實用性，本文生成1000個包含30個節點的隨機網絡樣本，并將坐標點進行編號。設定點1-10為第Ⅰ類，點11-20為第Ⅱ類，點21-30為噪聲點。同一類內節點有邊相連的概率P1=80%，噪聲點與任意類有邊相連的概率P2=20%，對1000個網絡樣本進行聚類，結果如圖2。

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

調整P2=30%，再次進行測試，結果如圖4，聚類精度為95.3%。

2.2 真實數據

我們利用該算法測試了一些具有已知類結構的網絡，并且可以檢測到這些網絡中的類。

首先測試了具有34個節點的Zachary研究的空手道俱樂部內部成員的關系網絡，結果如圖5 ，方形和圓形的節點代表已知的兩個類，不同顏色的節點代表新劃分的類。有三個節點判斷錯誤，聚類精度為91.176%，節點3、14、20處于兩個社團的交界處，本身具有一定歧義性[8]。

接著我們測試了具有115個節點的足球俱樂部成員關系網絡，結果如圖6：

我們試著將足球俱樂部網絡計算的模塊與實驗確定的聚類相匹配。使用超幾何測量法作為最佳匹配標準，通過最小化計算組和實驗組之間的隨機重疊概率Polof，我們可以確定模塊的最佳匹配實驗復合體。

Pol定義為[9]：

[Pol=n2kN-n2n1-kNn1] （5）

其中n1是新劃分的聚類，n2是已知的聚類結果，k是匹配的節點的數量，N是網絡的大小聚類結果越準確，log（Pol）值越小。最篩選確定終結果較準確的類為：

3 算法評價

本文使用DBSCAN算法的原理對復雜網絡進行聚類。針對復雜網絡的特性，將傳統DBSCAN算法使用的歐式距離度量改為相似度度量。

由于復雜網絡具有小世界性，即網絡間的平均路徑長很小，所以本文的算法的一個優勢是可以很好確定鄰域半徑范圍；與譜聚類方法等算法相比，本算法可以自動確定聚類數；并且還具有可以有效剔除噪聲點、發現任意形狀的聚類的優點。

由于算法對輸入參數較為敏感，不同的參數對結果的影響較大，所以需要對網絡的相似度矩陣有所觀察后方能得到較準確的結果。并且由于算法是對密度進行劃分的，當空間密度分布不均勻時，聚類結果較差且參數較難選擇。

參考文獻：

[1] 李建， 鄭曉艷. 復雜網絡算法聚類綜述[J]. 電腦知識與技術， 2009， 11（5）：37-41.

[2] 汪小帆， 李翔， 陳關榮. 復雜網絡的理論及其應用[M]. 北京： 清華大學出版社， 2006： 162.

[3] 王偉東， 蘆金撣， 張講社. 基于視覺原理的密度聚類算法[J]. 工程數學學報， 2005， 22（2）：349-352.

[4] 周水庚， 周傲英， 曹晶. 基于數據分區的DBSCAN算法[J]. 計算機研究與發展， 2000， 37（10）：1153-1159.

[5] Zhang S，Ning X M， Zhang X S. Graph kernels， hierarchical clustering， and network community structure： experiments and comparative analysis[J]. Eur. Phys. J. B， 2007： 57， 67-74

[6] mathworks[EB/OL].http：//www.mathworks.com/.

[7] 楊芳勛. DBSCAN 算法在電子郵件網絡社團發現中的應用[J]. 計算機科學， 2017， 44（6A）：591-593.

[8] 汪小帆， 李翔， 陳關榮. 復雜網絡的理論及其應用[M]. 北京： 清華大學出版社， 2006： 166.

[9] Shihua Zhang， Xuemei Ning， Xiangsun Zhang. Identification of functional modules in a PPI network by clique percolation clustering[J]. Computational Biology and Chemistry， 2006（30）：445-451.endprint