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

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

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

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

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

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

1 算法介紹

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

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

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

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

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

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

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

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

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

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

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

定義2（鄰域N（p））：點(diǎn)p的鄰域?yàn)椋?/p>

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

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

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

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

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

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

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

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

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

算法描述如下：

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

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

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

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

2 實(shí)例驗(yàn)證

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

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

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

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

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

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

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

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

我們?cè)囍鴮⒆闱蚓銟凡烤W(wǎng)絡(luò)計(jì)算的模塊與實(shí)驗(yàn)確定的聚類相匹配。使用超幾何測(cè)量法作為最佳匹配標(biāo)準(zhǔn)，通過最小化計(jì)算組和實(shí)驗(yàn)組之間的隨機(jī)重疊概率Polof，我們可以確定模塊的最佳匹配實(shí)驗(yàn)復(fù)合體。

Pol定義為[9]：

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

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

3 算法評(píng)價(jià)

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

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

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

參考文獻(xiàn)：

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

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

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

[4] 周水庚， 周傲英， 曹晶. 基于數(shù)據(jù)分區(qū)的DBSCAN算法[J]. 計(jì)算機(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ò)社團(tuán)發(fā)現(xiàn)中的應(yīng)用[J]. 計(jì)算機(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