馬 健，劉 峰，李紅輝，樊建平

(北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院， 北京 100044)

社區(qū)結(jié)構(gòu)(community)是復(fù)雜網(wǎng)絡(luò)所呈現(xiàn)的重要特征之一，從某種意義上說(shuō)，整個(gè)網(wǎng)絡(luò)由若干社區(qū)構(gòu)成，具有社區(qū)內(nèi)部節(jié)點(diǎn)之間連接比較密集，不同社區(qū)節(jié)點(diǎn)之間連接比較稀疏的特點(diǎn)[1]。復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問(wèn)題就是要揭示出復(fù)雜網(wǎng)絡(luò)中存在的各個(gè)社區(qū)。從社區(qū)之間是否重疊的角度來(lái)看,社區(qū)結(jié)構(gòu)是可以重疊的。例如人類(lèi)社會(huì)關(guān)系網(wǎng)中的一個(gè)人可以擁有多個(gè)朋友圈，Internet中，一個(gè)路由器可以連接不同的局域網(wǎng)，在神經(jīng)網(wǎng)絡(luò)中，一個(gè)神經(jīng)元可以屬于不同的神經(jīng)系統(tǒng)。

重疊社區(qū)的發(fā)現(xiàn)算法可以分為：基于派系過(guò)濾算法(Clique Percolation Method, CPM)的重疊社區(qū)發(fā)現(xiàn)算法，它將網(wǎng)絡(luò)看作是完全連通子圖(clique)的集合[2-3]?；趦?yōu)化函數(shù)的重疊社區(qū)發(fā)現(xiàn)算法[4-5]，其中，Lancichinetti等[4]提出了LFM (Local Fitness Method)算法，該算法既可以發(fā)現(xiàn)層次社區(qū)又可以發(fā)現(xiàn)重疊社區(qū)。基于邊的重疊社區(qū)發(fā)現(xiàn)算法[6-7]，基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法，Gregory等[8]提出了重疊社區(qū)發(fā)現(xiàn)算法(Community Overlap PRopagation Algorithm， COPRA)。Wu等[9]提出了基于均衡多標(biāo)簽傳播的重疊社團(tuán)發(fā)現(xiàn)算法(Balanced Multi-Label Propagation Algorithm, BMLPA)算法，定義了粗糙核的概念對(duì)節(jié)點(diǎn)的標(biāo)簽進(jìn)行初始化，通過(guò)更改標(biāo)簽更新時(shí)的參數(shù)改進(jìn)算法。張昌理等[10]提出了多標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)算法COPRA-EP，算法利用節(jié)點(diǎn)信息熵和節(jié)點(diǎn)的局部相關(guān)性進(jìn)行研究。Cui等[11]從網(wǎng)絡(luò)中發(fā)現(xiàn)所有最大子圖，然后通過(guò)兩個(gè)相鄰最大子圖的聚類(lèi)系數(shù)來(lái)合并它們。Mohan等[12]提出了一個(gè)分布式和可擴(kuò)展的模型來(lái)最大化信息的擴(kuò)散，通過(guò)將圖劃分為社區(qū)并尋找每個(gè)社區(qū)中有影響的節(jié)點(diǎn)來(lái)檢測(cè)社區(qū)，模型使用PageRank算法在每個(gè)社區(qū)中尋找有影響的節(jié)點(diǎn)。孫道平等[13]提出了一種算法計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)的聚類(lèi)系數(shù)，并選擇具有最大聚類(lèi)系數(shù)的節(jié)點(diǎn)來(lái)更新其在傳播過(guò)程中的標(biāo)簽。Chen等[14]提出了基于節(jié)點(diǎn)層次和標(biāo)簽傳播增益的重疊社區(qū)發(fā)現(xiàn)算法，算法提出了新的多標(biāo)簽更新規(guī)則，設(shè)計(jì)節(jié)點(diǎn)之間標(biāo)簽傳播增益得到重疊社區(qū)。Xie等[15]提出了一種SLPA算法。

本文提出了一種基于PageRank和節(jié)點(diǎn)聚類(lèi)系數(shù)的重疊標(biāo)簽傳播算法(Community Overlap PRopagation Algorithm based on PageRank and Clustering coefficient,COPRAPC)。該算法在傳播節(jié)點(diǎn)的社區(qū)標(biāo)簽時(shí)按節(jié)點(diǎn)影響力的大小進(jìn)行排序，并且根據(jù)節(jié)點(diǎn)的聚類(lèi)系數(shù)決定傳播的閾值，最后通過(guò)一系列實(shí)驗(yàn)進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明所提出的重疊社區(qū)檢測(cè)算法是可行且有效的。

1 COPRA算法

1.1 COPRA算法描述

COPRA算法(見(jiàn)圖1)在標(biāo)簽傳播算法(Label Propagation Algorithm， LPA)算法基礎(chǔ)上改進(jìn)解決重疊社區(qū)發(fā)現(xiàn)的問(wèn)題，每個(gè)節(jié)點(diǎn)擁有多個(gè)標(biāo)簽(label)和隸屬度(belonging coefficients)，所有隸屬度的和等于1，標(biāo)簽采用同步更新的方式，用每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的標(biāo)簽更新該節(jié)點(diǎn)，屬于相同社區(qū)標(biāo)簽的隸屬度相加并標(biāo)準(zhǔn)化，如式(1)所示，隸屬度小于1/v的標(biāo)簽將從標(biāo)簽列表中刪除，閾值v用來(lái)控制一個(gè)節(jié)點(diǎn)所屬的社區(qū)數(shù)。COPRA標(biāo)簽傳播算法的時(shí)間復(fù)雜度為O(vmlog(vm/n))，當(dāng)v取較小值時(shí)，整個(gè)算法復(fù)雜度為線性時(shí)間復(fù)雜度。

(1)

(a) 第1次迭代(a) Iteration 1 (b) 第2次迭代(b) Iteration 2

(c) 第3次迭代(c) Iteration 3 (d) 第4次迭代(d) Iteration 4圖1 COPRA 算法Fig.1 COPRA algorithm

1.2 評(píng)價(jià)函數(shù)

Qov是Nicosia等將Q函數(shù)擴(kuò)展提出的能夠評(píng)價(jià)重疊社區(qū)的評(píng)價(jià)函數(shù)[16]。Qov越大，社區(qū)結(jié)構(gòu)越明顯。

(2)

其中，

δ(Ci,Cj,C)=F(αi,c,αj,c)

f(x)=2px-p,p=30

EQ是評(píng)估重疊社區(qū)的另一個(gè)度量標(biāo)準(zhǔn)，EQ值越大，社區(qū)的結(jié)構(gòu)越明顯。表達(dá)式如下[3]：

(3)

Lancichinetti等將標(biāo)準(zhǔn)互信息(Normalized Mutual Information, NMI)擴(kuò)展為能夠評(píng)價(jià)重疊社區(qū)的一種評(píng)價(jià)指標(biāo)[2]。

(4)

2 COPRAPC算法

2.1 算法思想及描述

COPRAPC算法和其他重疊標(biāo)簽傳播算法的不同之處在于算法采用不同的閾值來(lái)限制每個(gè)節(jié)點(diǎn)擁有最多標(biāo)簽的數(shù)量值，每個(gè)節(jié)點(diǎn)可能出現(xiàn)在多個(gè)社區(qū)中，社區(qū)邊緣節(jié)點(diǎn)擁有較小聚類(lèi)系數(shù)一般是重疊節(jié)點(diǎn)，社區(qū)內(nèi)部節(jié)點(diǎn)擁有大聚類(lèi)系數(shù)往往是非重疊節(jié)點(diǎn)，社區(qū)邊緣節(jié)點(diǎn)比社區(qū)內(nèi)部屬于更多的社區(qū)。小的聚類(lèi)系數(shù)做閾值可以保留節(jié)點(diǎn)更多的標(biāo)簽，而大的聚類(lèi)系數(shù)可以刪除節(jié)點(diǎn)更多的標(biāo)簽，重疊的節(jié)點(diǎn)可以比非重疊的節(jié)點(diǎn)保留更多的標(biāo)簽。此外，復(fù)雜網(wǎng)絡(luò)的小世界特性決定了節(jié)點(diǎn)具有較高聚類(lèi)系數(shù)，從而避免了傳播過(guò)程中節(jié)點(diǎn)的標(biāo)簽對(duì)過(guò)多的問(wèn)題。

COPRAPC算法采用同步更新策略。對(duì)于同步策略來(lái)說(shuō)，可以比異步方式提供更穩(wěn)定的結(jié)果，但是同步方案需要更多的迭代次數(shù)。

在COPRA算法中，每個(gè)節(jié)點(diǎn)都有一個(gè)標(biāo)簽，在傳播過(guò)程中，節(jié)點(diǎn)標(biāo)簽在沒(méi)有特定序列的情況下更新。這種隨機(jī)策略導(dǎo)致運(yùn)行結(jié)果不穩(wěn)定。如圖1(c)中所示的COPRA算法中，在這次迭代之后，節(jié)點(diǎn)a、b、c和d已經(jīng)形成了一個(gè)社區(qū)。如果算法選擇節(jié)點(diǎn)e或g，用節(jié)點(diǎn)a的標(biāo)簽替換它的標(biāo)簽，然后更新節(jié)點(diǎn)f的標(biāo)簽，那么，所有節(jié)點(diǎn)都使用c作為它們的標(biāo)簽，所有的節(jié)點(diǎn)將被劃分為一個(gè)社區(qū)，結(jié)果導(dǎo)致整個(gè)網(wǎng)絡(luò)在一個(gè)社區(qū)中。如果首先更新節(jié)點(diǎn)f的標(biāo)簽，將得到正確的分區(qū)結(jié)果。

圖2顯示了兩個(gè)非重疊社區(qū)C1和C2迭代之后，如果節(jié)點(diǎn)d,e,f被分配到社區(qū)C2，此時(shí)更新節(jié)點(diǎn)g，將得到正確的社區(qū)分區(qū)，但如果更新節(jié)點(diǎn)b或c的標(biāo)簽并選擇節(jié)點(diǎn)d和e作為它的標(biāo)簽，所有節(jié)點(diǎn)將擁有相同的標(biāo)簽，結(jié)果是所有節(jié)點(diǎn)被劃分到相同的社區(qū)。

圖2 COPRAPC算法實(shí)例Fig.2 Example of COPRAPC propagation

上述兩個(gè)例子說(shuō)明COPRA算法對(duì)節(jié)點(diǎn)更新序列很敏感，不是所有這些節(jié)點(diǎn)都具有相同的優(yōu)先級(jí)。在社區(qū)之間的節(jié)點(diǎn)的影響力總是比社區(qū)內(nèi)部的節(jié)點(diǎn)要低。PageRank值反映了這個(gè)特性，本文使用排名方法PageRank算法[17]對(duì)節(jié)點(diǎn)進(jìn)行排序。首先，將無(wú)向圖轉(zhuǎn)換為有向圖，將無(wú)向圖中的邊轉(zhuǎn)換為具有兩個(gè)相反方向的弧。PageRank的較小值往往位于社區(qū)中心，PageRank值小的節(jié)點(diǎn)優(yōu)先于PageRank值較大的節(jié)點(diǎn)，即

(5)

其中，α參數(shù)為0.85，v′是節(jié)點(diǎn)v的鄰居，degress(v′)為節(jié)點(diǎn)v′的度。

節(jié)點(diǎn)的PageRank值:PR(a)=0.146 6,PR(b)=0.147 6,PR(c)=0.147 6,PR(d)=0.152 0,PR(e)=0.152 0,PR(f)=0.107 6,PR(g)=0.146 6。節(jié)點(diǎn)在以下序列中更新它們的標(biāo)簽：f、a、g、b、c、d和e，可以很容易地得到正確的結(jié)果。

2.2 修改傳播門(mén)限參數(shù)

在COPRA算法中，使用標(biāo)簽列表(c,b)表示每個(gè)節(jié)點(diǎn)擁有的標(biāo)簽，其中c表示一個(gè)標(biāo)簽(label)，b表示隸屬度。如果b<1/v，從節(jié)點(diǎn)標(biāo)簽列表中刪除(c,b)。在重疊的社區(qū)中，每個(gè)節(jié)點(diǎn)可能屬于多個(gè)社區(qū)。參數(shù)v控制重疊的社區(qū)數(shù)目。也就是說(shuō)，參數(shù)v限制節(jié)點(diǎn)所屬的社區(qū)最大數(shù)量。如果v太大，則可能導(dǎo)致網(wǎng)絡(luò)中節(jié)點(diǎn)的標(biāo)簽對(duì)過(guò)少，節(jié)點(diǎn)容易被劃分到一個(gè)社區(qū)，如果v太小，則會(huì)導(dǎo)致網(wǎng)絡(luò)中節(jié)點(diǎn)的標(biāo)簽對(duì)過(guò)多。參數(shù)v的選擇能夠影響標(biāo)簽傳播算法重疊社區(qū)發(fā)現(xiàn)的準(zhǔn)確性，由于每個(gè)節(jié)點(diǎn)所屬社區(qū)數(shù)目是不相同的，因此，本文提出了一種新的標(biāo)簽傳播算法，根據(jù)不同的節(jié)點(diǎn)選擇不同的參數(shù)。

在網(wǎng)絡(luò)中，節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)和可能存在最多邊數(shù)的比值為節(jié)點(diǎn)vi的聚類(lèi)系數(shù)[18]，每個(gè)節(jié)點(diǎn)vi鄰居節(jié)點(diǎn)之間可能最多是ki×(ki-1)/2條邊。節(jié)點(diǎn)vi的聚類(lèi)系數(shù)如式(6)所示。

(6)

其中，Ei表示連接到節(jié)點(diǎn)vi的每個(gè)相鄰節(jié)點(diǎn)的邊數(shù)，ki表示節(jié)點(diǎn)vi所有相鄰節(jié)點(diǎn)的個(gè)數(shù)。聚類(lèi)系數(shù)Ci總是在0至1之間。

COPRAPC算法允許社區(qū)重疊，每個(gè)節(jié)點(diǎn)可能出現(xiàn)在多個(gè)社區(qū)中。社區(qū)邊緣節(jié)點(diǎn)總是重疊節(jié)點(diǎn)，社區(qū)中間節(jié)點(diǎn)往往是非重疊節(jié)點(diǎn)，重疊節(jié)點(diǎn)聚類(lèi)系數(shù)往往小于非重疊節(jié)點(diǎn)，重疊節(jié)點(diǎn)的聚類(lèi)系數(shù)較小通常處在社區(qū)的邊緣，非重疊社區(qū)的節(jié)點(diǎn)都在社區(qū)中間聚類(lèi)系數(shù)較大，換句話(huà)說(shuō)，一個(gè)社區(qū)邊緣節(jié)點(diǎn)擁有小聚類(lèi)系數(shù)可能比社區(qū)中間擁有大聚類(lèi)系數(shù)屬于更多的社區(qū)。更高的閾值可以刪除節(jié)點(diǎn)更多的標(biāo)簽，重疊的節(jié)點(diǎn)可以比非重疊的節(jié)點(diǎn)保留更多的標(biāo)簽。

v是一個(gè)與節(jié)點(diǎn)無(wú)關(guān)的參數(shù)。相反，聚類(lèi)系數(shù)參數(shù)是一個(gè)與節(jié)點(diǎn)相關(guān)的參數(shù)，算法設(shè)置參數(shù)μ，當(dāng)節(jié)點(diǎn)的聚類(lèi)系數(shù)大于μ，閾值設(shè)為節(jié)點(diǎn)的聚類(lèi)系數(shù)，反之，使用先前的值1/v。這樣做的目的是聚類(lèi)系數(shù)大的節(jié)點(diǎn)一般在社區(qū)內(nèi)部，往往不是重疊節(jié)點(diǎn)，這樣的節(jié)點(diǎn)設(shè)置的門(mén)限高，可以去除較多的標(biāo)簽，而聚類(lèi)系數(shù)小的節(jié)點(diǎn)一般在社區(qū)的邊緣，容易成為重疊節(jié)點(diǎn)，設(shè)置的門(mén)限較低可以增加標(biāo)簽的數(shù)量。但對(duì)于聚類(lèi)系數(shù)非常小的節(jié)點(diǎn)，閾值過(guò)低容易產(chǎn)生空的標(biāo)簽集合，這時(shí)就用原來(lái)的門(mén)限值1/v。

COPRAPC算法描述：

1)初始時(shí)，給每個(gè)節(jié)點(diǎn)賦予唯一的社區(qū)標(biāo)簽(cx,1)。

2)對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)按其PageRank值排序。

3)每個(gè)節(jié)點(diǎn)x通過(guò)最大鄰居的數(shù)量來(lái)更新它的標(biāo)簽。屬于相同社區(qū)的標(biāo)簽的隸屬度相加并標(biāo)準(zhǔn)化，為了避免最后所有節(jié)點(diǎn)都劃分到同一個(gè)社區(qū)，COPRAPC算法使用節(jié)點(diǎn)的聚類(lèi)系數(shù)來(lái)限制每個(gè)節(jié)點(diǎn)擁有最多標(biāo)簽的數(shù)量值。如果節(jié)點(diǎn)的聚類(lèi)系數(shù)小于參數(shù)μ，仍然使用原來(lái)的1/v，如果一個(gè)節(jié)點(diǎn)的所有標(biāo)簽隸屬度都小于傳播參數(shù)，那么隨機(jī)選擇一個(gè)最大值鄰居的標(biāo)簽作為該節(jié)點(diǎn)的標(biāo)簽。最后，當(dāng)每個(gè)標(biāo)簽包含的節(jié)點(diǎn)數(shù)不變，算法迭代結(jié)束，否則，重復(fù)步驟3。

4)將所有標(biāo)簽相同的節(jié)點(diǎn)劃分為同一個(gè)社區(qū)。

5)將得到的社區(qū)進(jìn)行刪除其他社區(qū)的子集，不相連的社區(qū)分裂成更小的社區(qū)。

COPRAPC算法的形式化語(yǔ)言如算法1和算法2所示。

算法1 計(jì)算節(jié)點(diǎn)的聚類(lèi)系數(shù)

算法2 COPRAPC算法

2.3 復(fù)雜度分析

1)初始化標(biāo)簽的時(shí)間復(fù)雜度為O(n)。

2)設(shè)計(jì)算單個(gè)節(jié)點(diǎn)PageRank值的迭代次數(shù)為t，矩陣相乘時(shí)間復(fù)雜度為O(n2)，所以計(jì)算單個(gè)節(jié)點(diǎn)的PageRank值的時(shí)間復(fù)雜度為O(n2×t)，計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)的PageRank值的時(shí)間復(fù)雜度為O(n3×t)，根據(jù)節(jié)點(diǎn)排序更新序列的時(shí)間復(fù)雜度為O(n)。

3 實(shí)驗(yàn)分析

為了驗(yàn)證所提出的COPRAPC算法，將它與幾個(gè)重疊社區(qū)的發(fā)現(xiàn)算法進(jìn)行比較:CPM, LFM, BMLPA和COPRA。

Lancichinetti的NMI已被廣泛用于發(fā)現(xiàn)重疊社區(qū)，因此本文在實(shí)驗(yàn)中采用擴(kuò)展的NMI作為度量標(biāo)準(zhǔn)。實(shí)驗(yàn)獨(dú)立運(yùn)行COPRA算法20次實(shí)驗(yàn)數(shù)據(jù)，得到平均結(jié)果。COPRAPC算法由于標(biāo)簽選擇的隨機(jī)性，本文獨(dú)立運(yùn)行了10次數(shù)據(jù)集取平均結(jié)果。CPM算法，k=4, BMPLA 算法，p=0.75。

3.1 LFR基準(zhǔn)網(wǎng)絡(luò)

LFR基準(zhǔn)網(wǎng)絡(luò)，該網(wǎng)絡(luò)由Lancichinetti等提出，是一類(lèi)更接近真實(shí)網(wǎng)絡(luò)的人工網(wǎng)絡(luò)，該網(wǎng)絡(luò)節(jié)點(diǎn)及社區(qū)模型度呈冪律分布，具有真實(shí)世界的網(wǎng)絡(luò)特性。N表示節(jié)點(diǎn)數(shù)目，d表示節(jié)點(diǎn)平均度數(shù)，k表示節(jié)點(diǎn)最大度，minc表示最小社區(qū)規(guī)模，maxc表示最大社區(qū)規(guī)模，t1表示節(jié)點(diǎn)度的冪率分布指數(shù)，t2表示社區(qū)規(guī)模的冪率分布指數(shù)，混合參數(shù)mu，on表示重疊節(jié)點(diǎn)的個(gè)數(shù)，om表示重疊節(jié)點(diǎn)所屬的社區(qū)個(gè)數(shù)，表1和表2為L(zhǎng)FR基準(zhǔn)網(wǎng)絡(luò)的參數(shù)。表1中的社區(qū)分別表示稠密小社區(qū)(Dense Small, DS)，稠密大社區(qū)(Dense Large, DL)，稀疏小社區(qū)(Sparse Small, SS)，稀疏大社區(qū)(Sparse Large, SL)。表1中實(shí)驗(yàn)節(jié)點(diǎn)的聚類(lèi)系數(shù)都較大，因此設(shè)置μ=0。

表1 重疊社區(qū)的LFR基準(zhǔn)網(wǎng)絡(luò)參數(shù)

表2 非重疊社區(qū)的LFR基準(zhǔn)網(wǎng)絡(luò)參數(shù)

圖3顯示該算法在實(shí)驗(yàn)中表現(xiàn)良好。隨著參數(shù)on的增大，重疊節(jié)點(diǎn)的數(shù)量越來(lái)越多。COPRAPC性能較優(yōu)。

(a) DS網(wǎng)絡(luò)的NMI值(a) NMI identified by DS networks

(b) SS網(wǎng)絡(luò)的NMI值(b) NMI identified by SS networks

(c) DL網(wǎng)絡(luò)的NMI值(c) NMI identified by DL networks

(d) SL網(wǎng)絡(luò)的NMI值(d) NMI identified by SL networks圖3 CPM, LFM, COPRA, BMLPA and COPRAPC算法的NMI對(duì)比結(jié)果Fig.3 The NMI identified by CPM, LFM, COPRA, BMLPA and COPRAPC

表2中的實(shí)驗(yàn)數(shù)據(jù)集節(jié)點(diǎn)的聚類(lèi)系數(shù)較小，因此設(shè)μ=0.1。

上述是一個(gè)具有非重疊節(jié)點(diǎn)的社區(qū)網(wǎng)絡(luò)。隨著參數(shù)mu的增加，當(dāng)值mu=0.4時(shí)社區(qū)的結(jié)構(gòu)變得模糊，圖4顯示該算法在這些網(wǎng)絡(luò)中表現(xiàn)良好。

(a) Network a的NMI值(a) NMI identified by network a

(b) Network b的NMI值(b) NMI identified by network b圖4 CPM, LFM, COPRA, BMLPA and COPRAPC算法的NMI對(duì)比結(jié)果Fig.4 The NMI identified by CPM, LFM, COPRA, BMLPA and COPRAPC

3.2 真實(shí)世界網(wǎng)絡(luò)

本文在幾個(gè)真實(shí)世界復(fù)雜網(wǎng)絡(luò)上對(duì)算法進(jìn)行測(cè)試，實(shí)驗(yàn)采用的數(shù)據(jù)分別是：Newman提供的空手道俱樂(lè)部網(wǎng)絡(luò)(Zachary′s club network)、海豚網(wǎng)絡(luò)(dolphin social network)、美國(guó)大學(xué)足球聯(lián)盟網(wǎng)絡(luò) (American college football)、爵士音樂(lè)網(wǎng)絡(luò)(Jazz music)、政治書(shū)籍(political books)和郵件網(wǎng)絡(luò)(the E-mail network of human interactions)。表3為實(shí)驗(yàn)用到的真實(shí)網(wǎng)絡(luò)參數(shù)。實(shí)驗(yàn)中，設(shè)置參數(shù)μ=0.2。表4和表5分別給出了解情況種算法在個(gè)真實(shí)世界網(wǎng)絡(luò)中的Qov和EQ值。

表3 真實(shí)世界網(wǎng)絡(luò)參數(shù)

在基準(zhǔn)網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)中，算法的社區(qū)發(fā)現(xiàn)結(jié)果是穩(wěn)定的，基于此思想的算法相比其他標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)算法有明顯的提高，和其他重疊算法相比也有較好的挖掘結(jié)果，這也說(shuō)明了基于PageRank和節(jié)點(diǎn)聚類(lèi)系數(shù)的思路是可行的。

表4 CPM LFM, COPRA, BMLPA and COPRAPC算法的Qov值Tab.4 The Qov values identified by CPM, LFM, COPRA, and COPRAPC

表5 CPM, LFM, COPRA, BMLPA and COPRAC算法的EQ值Tab.5 The EQ values identified by CPM, LFM, COPRA, and COPRAPC

3.3 算法效率比較

改變LFR基準(zhǔn)程序的參數(shù)，可以得到不同規(guī)模的人工網(wǎng)絡(luò),在這些網(wǎng)絡(luò)上分別運(yùn)行社區(qū)發(fā)現(xiàn)算法,可以得到算法運(yùn)行時(shí)間的一般規(guī)律,從而能知道各個(gè)算法在效率上的差異。本節(jié)使用的LFR程序參數(shù)N=1000～10 000,k=20,kmax=50,cmin=20,cmax=100,t1=2,t2=2,on=0,om=2。圖5顯示了COPRA, BMLPA和COPRAPC算法的執(zhí)行時(shí)間，由于CPM，LFM算法的運(yùn)行時(shí)間較長(zhǎng)，本文不做比較。COPRAPC算法具有合理的時(shí)間復(fù)雜度。此外，算法的時(shí)間效率和時(shí)間復(fù)雜度方面，標(biāo)簽傳播算法具有明顯的優(yōu)勢(shì)，本算法的時(shí)間在同類(lèi)算法中也是可接受的。

圖5 算法運(yùn)行效率對(duì)比的實(shí)驗(yàn)結(jié)果 Fig.5 Experiment results of runtime efficiency

4 結(jié)論

本文提出了一種改進(jìn)的重疊社區(qū)發(fā)現(xiàn)算法，即基于節(jié)點(diǎn)的PageRank值排序和節(jié)點(diǎn)的聚類(lèi)系數(shù)標(biāo)簽傳播算法。節(jié)點(diǎn)標(biāo)簽的傳播不按隨機(jī)順序，而是按照指定節(jié)點(diǎn)的PageRank值的順序傳播，設(shè)定節(jié)點(diǎn)聚類(lèi)系數(shù)閾值對(duì)標(biāo)簽進(jìn)行更新，進(jìn)而實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的劃分和網(wǎng)絡(luò)重疊節(jié)點(diǎn)的發(fā)現(xiàn)。在許多人工網(wǎng)絡(luò)和真實(shí)世界網(wǎng)絡(luò)的實(shí)驗(yàn)中，基于此思想的算法都取得了相比其他同類(lèi)算法更好的效果，這也說(shuō)明了該思路的可行性，同時(shí)該算法具有穩(wěn)定的社區(qū)發(fā)現(xiàn)結(jié)果。并且該算法的時(shí)間效率和復(fù)雜度也在可接受的范圍內(nèi)。