基于密度峰值法的復(fù)雜網(wǎng)絡(luò)聚類增長維度研究

許 英，羅夢迪

(新疆財(cái)經(jīng)大學(xué) 統(tǒng)計(jì)與數(shù)據(jù)科學(xué)學(xué)院，烏魯木齊 830012)

復(fù)雜網(wǎng)絡(luò)作為復(fù)雜系統(tǒng)的結(jié)構(gòu)化表示，因其與萬維網(wǎng)、交通、生物和社會系統(tǒng)等許多實(shí)際系統(tǒng)之間存在的相關(guān)性，受到了許多研究領(lǐng)域?qū)W者的關(guān)注。大量的真實(shí)網(wǎng)絡(luò)表現(xiàn)出來的鮮明特征都明顯有別于隨機(jī)網(wǎng)絡(luò)和規(guī)則網(wǎng)絡(luò)，這種特征被稱為小世界或無標(biāo)度性。在開創(chuàng)性工作中，Song等人[1]發(fā)現(xiàn)各種真實(shí)復(fù)雜網(wǎng)絡(luò)在所有長度標(biāo)度下具有分形和自相似特性，其中盒覆蓋法被用于計(jì)算復(fù)雜網(wǎng)絡(luò)的分形維數(shù)。Shanker等人利用聚類增長方法研究了復(fù)雜網(wǎng)絡(luò)的分形問題[2-3]。隨后，分形問題在網(wǎng)絡(luò)科學(xué)中也得到了廣泛的研究[4-10]，復(fù)雜網(wǎng)絡(luò)分形研究的幾何法最主要的工作之一就是計(jì)算網(wǎng)絡(luò)的分形維度，而網(wǎng)絡(luò)的分形維度的計(jì)算問題最終可歸結(jié)為在給定盒子尺度下，計(jì)算能夠覆蓋網(wǎng)絡(luò)所需的最小盒子數(shù)量的問題。兩種獨(dú)立的方法：盒覆蓋方法[11-18]和聚類增長方法[19-20]被廣泛用于計(jì)算復(fù)雜網(wǎng)絡(luò)的分形維度。近年來，大量的研究對這兩種方法進(jìn)行了擴(kuò)展，并且對復(fù)雜網(wǎng)絡(luò)的多重分形特征進(jìn)行了分析。

本文主要專注于聚類增長方法的研究。聚類增長方法的思想是隨機(jī)選擇種子，并計(jì)算以種子為中心，半徑為r的超球體內(nèi)的節(jié)點(diǎn)數(shù)M(r).為改善統(tǒng)計(jì)量，將所有節(jié)點(diǎn)依次設(shè)置為種子重復(fù)計(jì)算，最終得到在相同半徑r內(nèi)的平均節(jié)點(diǎn)數(shù)M(r).復(fù)雜網(wǎng)絡(luò)維數(shù)的估計(jì)值是通過對統(tǒng)計(jì)數(shù)據(jù)的雙對數(shù)刻度進(jìn)行線性回歸而獲得的。Bo等人[21]提出了一種基于緊密度CC的方法來測量復(fù)雜網(wǎng)絡(luò)的分形維度，即選擇最重要的節(jié)點(diǎn)作為種子。在本文中，主要關(guān)注種子在整個網(wǎng)絡(luò)中心位置的選擇，利用密度峰值聚類方法來測量復(fù)雜網(wǎng)絡(luò)的分形維度?；谶@種方法，選出中心節(jié)點(diǎn)作為種子計(jì)算半徑為r的超球面內(nèi)的節(jié)點(diǎn)數(shù)的平均值M(r).通過與原始方法和基于緊密度CC方法的比較，發(fā)現(xiàn)使用基于密度峰值法的方法可以更好地獲得復(fù)雜網(wǎng)絡(luò)的分形維度。

1 方法

1.1 局部隨機(jī)游走距離

給定一個無向無權(quán)的網(wǎng)絡(luò)G=(V，E)，其中V是節(jié)點(diǎn)集合，E是邊集合。隨機(jī)游走是一個重要的過程，可以代表隨機(jī)步行者經(jīng)過的一系列節(jié)點(diǎn)。轉(zhuǎn)移概率矩陣P，Pij=aij/k表示留在節(jié)點(diǎn)i的隨機(jī)步行者在下一步將步行到j(luò)的可能性，其中A=(aij)是網(wǎng)絡(luò)的鄰接矩陣，ki表示節(jié)點(diǎn)i的度。Liu等人[22]提出了一種基于局部隨機(jī)游走(LRW)的節(jié)點(diǎn)距離度量，其時間復(fù)雜度低于其他基于隨機(jī)游走的距離度量。

給定一個從節(jié)點(diǎn)i開始的隨機(jī)游走者，這個游走者在t步之后到達(dá)節(jié)點(diǎn)j的概率表示為πij(t).該系統(tǒng)演化方程可表示為πi(t)=PTπi(t-1)，其初始系統(tǒng)狀態(tài)為πi(0)=ei，第i個位置為1其余位置為0.一個隨機(jī)游走者經(jīng)過t步后的訪問，LRW指數(shù)可以定義如下：

(1)

其中|E|是網(wǎng)絡(luò)的邊數(shù)。

疊加的隨機(jī)游走SRW度量是t步時間內(nèi)LRW的疊加，它描述了隨機(jī)游走者是從起始節(jié)點(diǎn)的連續(xù)釋放。該方程式定義為：

(2)

節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的局部隨機(jī)游走距離(LRWD)定義如下：

(3)

因此，可以基于以上公式計(jì)算網(wǎng)絡(luò)的距離矩陣D={dij}，顯然距離D是對稱的。如果隨機(jī)游走的步數(shù)受到限制，距離函數(shù)就是一個度量。如果t≤|E|/2，則容易證明dij(t)+djk(t)≥dik(t).在以下實(shí)驗(yàn)中，將網(wǎng)絡(luò)的直徑設(shè)置為隨機(jī)游走步長t，通常小于n.

1.2 確定網(wǎng)絡(luò)的種子

Rodriguez等人[23]提出了一種聚類方法，該思想基于以下觀點(diǎn)：聚類中心被具有較低局部密度的鄰居包圍，并且它們與具有較高局部密度的任何點(diǎn)之間的距離都相對較大，Liu等人[24]推廣了該方法以估計(jì)復(fù)雜網(wǎng)絡(luò)的中心。

對于每個節(jié)點(diǎn)i計(jì)算ρi和δi，其中ρi是節(jié)點(diǎn)i的局部密度，δi是節(jié)點(diǎn)i與較高密度的節(jié)點(diǎn)之間的距離，這兩個量都取決于節(jié)點(diǎn)之間的距離dij.網(wǎng)絡(luò)的距離矩陣D={dij}可由方程(3)計(jì)算，節(jié)點(diǎn)i的局部密度ρi可定義為：

(4)

其中dc是一個修正參數(shù)，控制權(quán)重降解率，由文獻(xiàn)[24]，dc的選擇對密度峰值聚類法的最后結(jié)果不是至關(guān)重要的，這里選擇dc為dij的平均值。具體來說，ρi表示與節(jié)點(diǎn)i的距離接近于dc的節(jié)點(diǎn)的數(shù)量。

節(jié)點(diǎn)i和任何其他具有更高密度節(jié)點(diǎn)的最小距離是δi，被定義為：

(5)

注意，聚類的中心被確定為ρi和δi異常大的節(jié)點(diǎn)，在此基礎(chǔ)上，網(wǎng)絡(luò)的中心總是出現(xiàn)在決策圖的右上角。

但是對聚類中心的選取需要人為干預(yù)，其中包含了主觀因素，不同的人可能會選擇不同的點(diǎn)作為聚類中心，因此，定義一個對ρi和δi綜合考慮的量γi：

γi=ρiδi

(6)

顯然，γi值越大，越有可能是聚類中心。對γi進(jìn)行降序排序，非聚類中心的γi的值分布比較平穩(wěn)，而從非聚類中心過渡到聚類中心時，γi的值會有一個明顯的跳躍，此時就能通過數(shù)值更加準(zhǔn)確的找到聚類中心，避免主觀因素所造成的選擇誤差。

1.3 分形維度的計(jì)算

大多數(shù)現(xiàn)實(shí)世界的網(wǎng)絡(luò)都具有異構(gòu)拓?fù)涮卣?，聚類增長法是一種研究復(fù)雜網(wǎng)絡(luò)分形和自相似特性的成功的分析技術(shù)。但是在已有的聚類增長方法中，原始方法沒有研究網(wǎng)絡(luò)邊界節(jié)點(diǎn)的影響，基于緊密度CC的方法忽略了其他重要節(jié)點(diǎn)的影響。從理論上講，如果一個節(jié)點(diǎn)位于復(fù)雜網(wǎng)絡(luò)的外圍，則節(jié)點(diǎn)的數(shù)目M(r)將緩慢增加，然后在r增加到固定點(diǎn)時非?？斓卦黾?。因此，M(r)vsr的雙對數(shù)標(biāo)度的線性回歸可能不遵循冪律，并導(dǎo)致表征復(fù)雜網(wǎng)絡(luò)的分形特性失敗。如果選擇一個種子且其位置位于整個網(wǎng)絡(luò)的中心，雖然不會發(fā)生上述現(xiàn)象，但是中心的選擇可能會存在偏差?；谶@種觀察，提出了一種基于密度峰值法的經(jīng)過改進(jìn)的復(fù)雜網(wǎng)絡(luò)聚類增長維度研究的方法。

基于上述密度峰值聚類法選擇種子節(jié)點(diǎn)，進(jìn)行以下步驟，即可得到復(fù)雜網(wǎng)絡(luò)G的分形維度:

步驟1：用式(3)計(jì)算復(fù)雜網(wǎng)絡(luò)的距離矩陣，用式(4)-式(6)計(jì)算ρi、δi和γi確定中心節(jié)點(diǎn)；

步驟2：選擇上述中心節(jié)點(diǎn)作為種子，令初始半徑r1=1，從各個種子開始計(jì)算半徑為r1=1的超球中的節(jié)點(diǎn)數(shù)M(r1)；

步驟3：用r2=r1+1，r3=r2+1，…來代替r1重復(fù)步驟2，直到所有的節(jié)點(diǎn)都被某些半徑所覆蓋；

步驟4：繪制M(r)和半徑r的雙對數(shù)圖，通過擬合直線的斜率得到網(wǎng)絡(luò)的分形維數(shù)。

注意，M(r)被認(rèn)為是r的函數(shù)：

M(r)～rdf，

(7)

其中M(r)是以種子節(jié)點(diǎn)為中心，r為半徑的超球體內(nèi)的節(jié)點(diǎn)數(shù)，df是復(fù)雜網(wǎng)絡(luò)的分形維度。由于分形維度是利用密度峰值聚類法的中心得到的，因此將該方法稱為基于密度峰值的方法。也可以使用其他的中心來測量復(fù)雜網(wǎng)絡(luò)的分形維度，例如把所有節(jié)點(diǎn)當(dāng)成種子的方法(原始方法)和基于緊密度CC的方法。下面驗(yàn)證基于密度峰值方法的有效性，并將該方法應(yīng)用于一些真實(shí)世界的復(fù)雜網(wǎng)絡(luò)和NW小世界網(wǎng)絡(luò)的測量。同時，與原始方法、基于緊密度CC的方法進(jìn)行了比較。

2 仿真實(shí)驗(yàn)

本文采用R軟件進(jìn)行仿真，選取四個典型社交網(wǎng)絡(luò)進(jìn)行分析：(1)Karate網(wǎng)絡(luò)是社會網(wǎng)絡(luò)分析中廣為分析的網(wǎng)絡(luò)，網(wǎng)絡(luò)有34個點(diǎn)和78條邊，；(2)Dolphins 網(wǎng)絡(luò)是2003年新西蘭附近的62只海豚之間關(guān)系網(wǎng)絡(luò)，共有62個節(jié)點(diǎn)和159條邊；(3)Yeast網(wǎng)絡(luò)時酵母菌蛋白質(zhì)相互作用網(wǎng)絡(luò)，共有2 361個節(jié)點(diǎn)和7 182條邊；(4)Netscience網(wǎng)絡(luò)是網(wǎng)絡(luò)科學(xué)領(lǐng)域科學(xué)家合作網(wǎng)絡(luò)，共有379個點(diǎn)和914條邊。

首先，利用密度峰值法確定四個真實(shí)世界網(wǎng)絡(luò)的中心節(jié)點(diǎn)作為計(jì)算分形維度的種子，如圖1所示。

圖1 根據(jù)密度峰值法確定四個真實(shí)世界網(wǎng)絡(luò)的種子決策

在本節(jié)中，首先要證明選擇的種子是否在復(fù)雜網(wǎng)絡(luò)的分形特性方面起著重要作用。這里使用上述四個真實(shí)社交網(wǎng)絡(luò)，這些網(wǎng)絡(luò)的一些基本信息顯示在表1中，其中列出了網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)N、邊數(shù)M和基于密度峰值方法、基于緊密度方法和原始方法獲得的分形維度df以及均方誤差。

表1 四個真實(shí)世界網(wǎng)絡(luò)基本信息、分形維度和均方誤差的比較

圖2 通過三種方法獲得四個真實(shí)世界網(wǎng)絡(luò)的M(r)與r的對數(shù)-對數(shù)圖

以上結(jié)果表明，確定節(jié)點(diǎn)的核心位置對于計(jì)算復(fù)雜網(wǎng)絡(luò)的維度也至關(guān)重要。如果將本文方法的步驟1中所選的中心節(jié)點(diǎn)替換為緊密中心性最大的節(jié)點(diǎn)或所有節(jié)點(diǎn)，即可獲得基于緊密度的方法和原始方法。

為了評估本文所提出的方法的性能，分別介紹了該方法、基于緊密度的方法和原始方法在小世界網(wǎng)絡(luò)分形分析中的性能。小世界網(wǎng)絡(luò)由N=1 000，2 000，3 000，3 500個節(jié)點(diǎn)組成的網(wǎng)格構(gòu)成，每個節(jié)點(diǎn)最初有個2m鄰居，對于每一對原來未連接的節(jié)點(diǎn)，以概率p添加一條邊來連接這兩個節(jié)點(diǎn)，該小世界網(wǎng)絡(luò)記為NW(1,N,2m,p)，在這個過程中，重邊和自環(huán)被排除在外。利用該模型構(gòu)造了四個不同加邊概率p和初始度2m的網(wǎng)絡(luò)。用本文提出基于密度峰值方法、基于緊密度的方法和原始方法測量網(wǎng)絡(luò)的分形維度和均方誤差如表2所示，從中可以看出，對于幾乎所有考慮的NW小世界網(wǎng)絡(luò)，基于密度峰值方法要優(yōu)于其他方法，雖然本文的方法對第四個NW網(wǎng)絡(luò)的均方誤差并不比緊密度優(yōu)，但是均方誤差也已經(jīng)足夠小，認(rèn)為這個結(jié)果也是很好的。結(jié)果還表明，網(wǎng)絡(luò)的維度與網(wǎng)絡(luò)結(jié)構(gòu)密切相關(guān)，如網(wǎng)絡(luò)的連邊概率p和初始度2m.

表2 四個小世界網(wǎng)絡(luò)基本信息、分形維度和均方誤差的比較

3 結(jié)論

在經(jīng)典的聚類增長方法中，測量復(fù)雜網(wǎng)絡(luò)的維度時，需要選擇所有節(jié)點(diǎn)作為種子來減少統(tǒng)計(jì)誤差?，F(xiàn)實(shí)世界的網(wǎng)絡(luò)大多具有異質(zhì)性的拓?fù)浣Y(jié)構(gòu)，更傾向于選擇網(wǎng)絡(luò)的外圍節(jié)點(diǎn)作為種子節(jié)點(diǎn)。因此，在這種情況下不可能得到一個合理的結(jié)果。當(dāng)選擇網(wǎng)絡(luò)的多個中心節(jié)點(diǎn)作為種子節(jié)點(diǎn)時，可以很好地觀察到網(wǎng)絡(luò)的縮放特性。本文考慮了密度峰值法來選擇那些γi大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)。結(jié)果表明，該方法在處理復(fù)雜網(wǎng)絡(luò)的分形維度問題時是有效的。需要注意的是，復(fù)雜網(wǎng)絡(luò)的分形只能在一定的尺度范圍內(nèi)觀察到，利用本文提出的方法，可以很容易地得到真實(shí)網(wǎng)絡(luò)和NW小世界網(wǎng)絡(luò)的分形維度。此外結(jié)果還表明，在計(jì)算復(fù)雜網(wǎng)絡(luò)的分形維度時，每個節(jié)點(diǎn)的中心性也很重要。