姜皓月+石夢彤+關(guān)童升+王思奇+陳嘉威+寧雪梅

摘要：復(fù)雜網(wǎng)絡(luò)聚類方法可以挖掘復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)，對復(fù)雜網(wǎng)絡(luò)的研究具有重要意義。DBSCAN算法是一種基于密度的聚類算法，主要用于對傳統(tǒng)數(shù)據(jù)點集進(jìn)行聚類。由于復(fù)雜網(wǎng)絡(luò)的特殊性質(zhì)，對DBSCAN算法進(jìn)行改進(jìn)，采用相似度度量法代替?zhèn)鹘y(tǒng)算法中的歐式距離度量，對復(fù)雜網(wǎng)絡(luò)進(jìn)行聚類。其優(yōu)點是聚類快速、可以發(fā)現(xiàn)任意形狀的聚類、自動確定聚類數(shù)以及有效剔除噪聲點。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；網(wǎng)絡(luò)聚類；密度聚類

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：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

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

DBSCAN是一種基于密度的聚類算法，要求聚類空間中的一定區(qū)域內(nèi)所包含的對象的數(shù)目不小于某一給定閾值[3]。DBSCAN算法的優(yōu)勢是可以發(fā)現(xiàn)任意形狀的聚類、自動確定聚類數(shù)以及有效剔除噪聲點。因此本文使用DBSCAN算法對復(fù)雜網(wǎng)絡(luò)進(jìn)行聚類。由于網(wǎng)絡(luò)與數(shù)據(jù)點集對距離的定義不同，本文用相似度度量代替?zhèn)鹘y(tǒng)DBSCAN算法中的距離度量。測試結(jié)果表明該算法對復(fù)雜網(wǎng)絡(luò)的聚類是可行的。

1 算法介紹

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

為使用此算法進(jìn)行復(fù)雜網(wǎng)絡(luò)聚類，在一個網(wǎng)絡(luò)D中，進(jìn)行如下定義：

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

首先，對于一個無向無權(quán)的網(wǎng)絡(luò)G =（V，E），G的拉普拉斯算子是矩陣：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義9（類Cluster）若p為一核心點，D中所有從 p 密度可達(dá)的節(jié)點和p構(gòu)成的集合稱為一個類。

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

算法描述如下：

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

找到第一個類C后，重復(fù)步驟1，處理C中所有的節(jié)點，繼續(xù)將C進(jìn)行擴展[7]。

C中的節(jié)點全部訪問過后，用同樣的方法訪問C以外節(jié)點。直到所有節(jié)點都?xì)w入某個類中或被標(biāo)記為噪聲點。

算法實現(xiàn)的實例如圖1，圖中八個節(jié)點被分為兩類，并以不同顏色標(biāo)記。

2 實例驗證

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

為檢驗算法的準(zhǔn)確性與實用性，本文生成1000個包含30個節(jié)點的隨機網(wǎng)絡(luò)樣本，并將坐標(biāo)點進(jìn)行編號。設(shè)定點1-10為第Ⅰ類，點11-20為第Ⅱ類，點21-30為噪聲點。同一類內(nèi)節(jié)點有邊相連的概率P1=80%，噪聲點與任意類有邊相連的概率P2=20%，對1000個網(wǎng)絡(luò)樣本進(jìn)行聚類，結(jié)果如圖2。

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

調(diào)整P2=30%，再次進(jìn)行測試，結(jié)果如圖4，聚類精度為95.3%。

2.2 真實數(shù)據(jù)

我們利用該算法測試了一些具有已知類結(jié)構(gòu)的網(wǎng)絡(luò)，并且可以檢測到這些網(wǎng)絡(luò)中的類。

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

接著我們測試了具有115個節(jié)點的足球俱樂部成員關(guān)系網(wǎng)絡(luò)，結(jié)果如圖6：

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

Pol定義為[9]：

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

其中n1是新劃分的聚類，n2是已知的聚類結(jié)果，k是匹配的節(jié)點的數(shù)量，N是網(wǎng)絡(luò)的大小聚類結(jié)果越準(zhǔn)確，log（Pol）值越小。最篩選確定終結(jié)果較準(zhǔn)確的類為：

3 算法評價

本文使用DBSCAN算法的原理對復(fù)雜網(wǎng)絡(luò)進(jìn)行聚類。針對復(fù)雜網(wǎng)絡(luò)的特性，將傳統(tǒng)DBSCAN算法使用的歐式距離度量改為相似度度量。

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

由于算法對輸入?yún)?shù)較為敏感，不同的參數(shù)對結(jié)果的影響較大，所以需要對網(wǎng)絡(luò)的相似度矩陣有所觀察后方能得到較準(zhǔn)確的結(jié)果。并且由于算法是對密度進(jìn)行劃分的，當(dāng)空間密度分布不均勻時，聚類結(jié)果較差且參數(shù)較難選擇。

參考文獻(xiàn)：

[1] 李建， 鄭曉艷. 復(fù)雜網(wǎng)絡(luò)算法聚類綜述[J]. 電腦知識與技術(shù)， 2009， 11（5）：37-41.

[2] 汪小帆， 李翔， 陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)的理論及其應(yīng)用[M]. 北京： 清華大學(xué)出版社， 2006： 162.

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

[4] 周水庚， 周傲英， 曹晶. 基于數(shù)據(jù)分區(qū)的DBSCAN算法[J]. 計算機研究與發(fā)展， 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 算法在電子郵件網(wǎng)絡(luò)社團發(fā)現(xiàn)中的應(yīng)用[J]. 計算機科學(xué)， 2017， 44（6A）：591-593.

[8] 汪小帆， 李翔， 陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)的理論及其應(yīng)用[M]. 北京： 清華大學(xué)出版社， 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