基于節(jié)點(diǎn)重要性和模塊度優(yōu)化的社團(tuán)劃分算法

張夢(mèng)園,李玲娟

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,江蘇 南京 210023)

0 引 言

對(duì)復(fù)雜網(wǎng)絡(luò)的深入研究發(fā)現(xiàn),現(xiàn)實(shí)世界中許多系統(tǒng)都能抽象為網(wǎng)絡(luò),如人與人之間的社交網(wǎng)絡(luò)、自然界的食物鏈網(wǎng)絡(luò)、蛋白質(zhì)相互作用網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)由具有一定組織性和極大隨機(jī)性的節(jié)點(diǎn)構(gòu)成[1]。根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)之間的連邊是否存在權(quán)值,復(fù)雜網(wǎng)絡(luò)可以分為無權(quán)網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò),加權(quán)網(wǎng)絡(luò)相比無權(quán)網(wǎng)絡(luò)能夠反映更加豐富的信息,同時(shí)賦予復(fù)雜網(wǎng)絡(luò)更加明確的物理意義。

社團(tuán)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要特征,社團(tuán)內(nèi)各個(gè)節(jié)點(diǎn)間連接緊密,而社團(tuán)之間只有一些稀疏的連接[2]。發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)能為進(jìn)一步理解網(wǎng)絡(luò)所代表的真實(shí)世界系統(tǒng)的結(jié)構(gòu)和功能提供捷徑。經(jīng)典的社團(tuán)劃分算法有基于模塊度優(yōu)化的、基于標(biāo)簽傳播的、基于局部擴(kuò)展的、基于深度學(xué)習(xí)的等等[3-5]。針對(duì)加權(quán)網(wǎng)絡(luò)的社團(tuán)劃分算法還相對(duì)較少,通?？紤]引入邊的權(quán)值來對(duì)已有的經(jīng)典的無權(quán)網(wǎng)絡(luò)劃分算法進(jìn)行改進(jìn)。典型的基于模塊度優(yōu)化的加權(quán)復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分算法有WGN[6]、WFN[7-8]、CNM[9]、BGLL等。

其中的BGLL[10]算法分為兩個(gè)階段,第一階段不斷將節(jié)點(diǎn)移入(即并入)使模塊度增益最大的社團(tuán),直至節(jié)點(diǎn)的移動(dòng)不會(huì)再導(dǎo)致模塊度增加;第二階段將得到的社團(tuán)作為新的節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)進(jìn)行重構(gòu),在重構(gòu)的網(wǎng)絡(luò)上重復(fù)第一階段。BGLL算法在第二階段對(duì)網(wǎng)絡(luò)重構(gòu),極大地縮小了網(wǎng)絡(luò)規(guī)模,算法的迭代會(huì)越來越快,因此具有很好的時(shí)間效率,但由于第一階段迭代遍歷節(jié)點(diǎn)是無序的,沒有考慮節(jié)點(diǎn)自身在網(wǎng)絡(luò)中的地位,因此可能會(huì)使最終劃分結(jié)果的準(zhǔn)確度不佳,仍有改進(jìn)的空間。

該文考慮在無向加權(quán)網(wǎng)絡(luò)的社團(tuán)劃分算法BGLL中引入節(jié)點(diǎn)重要性來調(diào)整其遍歷次序,以提高算法劃分結(jié)果的準(zhǔn)確度。首先,設(shè)計(jì)了一種基于節(jié)點(diǎn)自身信息及其鄰居節(jié)點(diǎn)信息的加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要性計(jì)算方法WNI (weighted network node importance);然后,融合WNI和BGLL算法,設(shè)計(jì)了一種基于節(jié)點(diǎn)重要性和模塊度優(yōu)化的加權(quán)網(wǎng)絡(luò)社團(tuán)劃分算法(weighted network community division algorithm based on node importance and modularity optimization),命名為IMWCD。IMWCD算法將BGLL算法每輪合并后重構(gòu)的網(wǎng)絡(luò)中的所有節(jié)點(diǎn)按照重要性升序排序,并作為下一輪遍歷的順序,以此為基礎(chǔ)實(shí)現(xiàn)加權(quán)網(wǎng)絡(luò)的社團(tuán)劃分。

1 相關(guān)知識(shí)

1.1 網(wǎng)絡(luò)的圖表示

一個(gè)真實(shí)的加權(quán)網(wǎng)絡(luò)可以抽象表示為圖G=(V,E,W)的形式,其中V表示節(jié)點(diǎn)集,E表示邊集,W表示邊的權(quán)值,節(jié)點(diǎn)數(shù)n=|V|,邊數(shù)m=|E|,E中每一條邊都有V中的一對(duì)點(diǎn)與之對(duì)應(yīng),wij表示任意有邊相連的節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的權(quán)值。對(duì)于無向網(wǎng)絡(luò)而言,任意點(diǎn)對(duì)(i,j)和(j,i)表示同一條邊,對(duì)應(yīng)邊的權(quán)值wij=wji;對(duì)于有向網(wǎng)絡(luò),節(jié)點(diǎn)之間的連邊具有方向性,如(i,j)唯一表示由節(jié)點(diǎn)i指向節(jié)點(diǎn)j的邊。與網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)v直接相連的邊的數(shù)目稱為該節(jié)點(diǎn)的度dv。

1.2 節(jié)點(diǎn)重要性

有研究表明,網(wǎng)絡(luò)中重要性較大的節(jié)點(diǎn)相比其他節(jié)點(diǎn)更能影響網(wǎng)絡(luò)的結(jié)構(gòu)和功能[11],重要性越大的節(jié)點(diǎn)越傾向于成為社團(tuán)的中心。因此,節(jié)點(diǎn)重要性度量方法對(duì)于發(fā)現(xiàn)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)具有重要的意義。評(píng)價(jià)網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的方法有很多,如介數(shù)中心性、度中心性、PageRank等?；诰W(wǎng)絡(luò)全局屬性的介數(shù)中心性評(píng)價(jià)方法認(rèn)為:經(jīng)過某個(gè)節(jié)點(diǎn)的最短路徑數(shù)量越多,則該節(jié)點(diǎn)越重要[12],這種評(píng)價(jià)方法需要計(jì)算所有節(jié)點(diǎn)對(duì)之間的距離,時(shí)間復(fù)雜度過高。度中心性是最簡(jiǎn)單的節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo),直接反映與當(dāng)前節(jié)點(diǎn)相連的鄰居數(shù)量(即節(jié)點(diǎn)的度),節(jié)點(diǎn)的度越大,與之直接相連的鄰居節(jié)點(diǎn)越多,該節(jié)點(diǎn)越重要[13];這種評(píng)價(jià)方法具有計(jì)算復(fù)雜度低的優(yōu)點(diǎn),但只考慮了待評(píng)估節(jié)點(diǎn)的局部信息,沒有考慮鄰居節(jié)點(diǎn)的信息或節(jié)點(diǎn)在網(wǎng)絡(luò)中所處環(huán)境等因素,可能導(dǎo)致計(jì)算結(jié)果誤差較大。PageRank[14]是谷歌搜索引擎的核心算法,考慮的是待評(píng)估頁(yè)面的鄰居頁(yè)面信息對(duì)待評(píng)估頁(yè)面重要性的影響,認(rèn)為如果一個(gè)頁(yè)面被大量其他頁(yè)面所指向,則此頁(yè)面是重要的。

1.3 BGLL算法

BGLL算法是一種層次性貪婪算法,基于模塊度優(yōu)化的思想,自底向上地不斷合并網(wǎng)絡(luò)中的社團(tuán),取模塊度最大時(shí)的劃分狀態(tài)作為最終的劃分結(jié)果。BGLL算法首先將網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)初始化為一個(gè)社團(tuán),社團(tuán)編號(hào)為節(jié)點(diǎn)編號(hào)。之后的工作分為兩個(gè)階段。

第一階段:對(duì)于每個(gè)節(jié)點(diǎn),考察其所有鄰居節(jié)點(diǎn),嘗試將此節(jié)點(diǎn)移入其鄰居節(jié)點(diǎn)所在社團(tuán),并計(jì)算移入后的模塊度增益,如果計(jì)算得出的所有增益為負(fù),則節(jié)點(diǎn)仍處于原始社團(tuán),否則選擇將節(jié)點(diǎn)移入模塊度增益最大的社團(tuán)內(nèi)。遍歷網(wǎng)絡(luò)中所有節(jié)點(diǎn),直到?jīng)]有節(jié)點(diǎn)移動(dòng),即移動(dòng)任意節(jié)點(diǎn)都不會(huì)再導(dǎo)致模塊度的增加,此時(shí)第一階段結(jié)束。其中,模塊度增益定義如下:

(1)

其中,∑in表示社團(tuán)內(nèi)部所有邊的權(quán)值之和,ki,in表示節(jié)點(diǎn)i與所在社團(tuán)內(nèi)的節(jié)點(diǎn)的連邊的權(quán)值之和,ki為節(jié)點(diǎn)i在網(wǎng)絡(luò)中的所有連邊的權(quán)值之和,∑tot表示節(jié)點(diǎn)i所在社團(tuán)內(nèi)的各個(gè)節(jié)點(diǎn)與網(wǎng)絡(luò)中所有節(jié)點(diǎn)連邊的權(quán)值之和,m為網(wǎng)絡(luò)中所有邊的權(quán)值之和。

第二階段:將網(wǎng)絡(luò)圖進(jìn)行重構(gòu),規(guī)則如下:將第一階段劃分出的社團(tuán)作為新的節(jié)點(diǎn),社團(tuán)編號(hào)作為新的節(jié)點(diǎn)編號(hào)。新的節(jié)點(diǎn)之間連邊的權(quán)值為兩個(gè)原社團(tuán)之間連邊的權(quán)值之和,處在同一個(gè)社團(tuán)內(nèi)的節(jié)點(diǎn)使得新形成的節(jié)點(diǎn)有指向自己的自環(huán)邊,且權(quán)值為社團(tuán)內(nèi)所有連邊的權(quán)值之和。將第二階段重構(gòu)的網(wǎng)絡(luò)圖作為第一階段的輸入重新進(jìn)行迭代,直至網(wǎng)絡(luò)不再改變即模塊度最大時(shí)算法停止。

2 加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要性計(jì)算方法WNI設(shè)計(jì)

如前文所述,節(jié)點(diǎn)重要性能反映節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位,重要性越大的節(jié)點(diǎn)越有可能成為社團(tuán)的中心。合理使用節(jié)點(diǎn)重要性可以使社團(tuán)劃分算法的劃分過程更具有方向性和目的性,從而獲得更準(zhǔn)確的劃分結(jié)果。

該文借鑒度中心性和PageRank的評(píng)價(jià)思想,對(duì)加權(quán)網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性做出如下的量化定義:

Ip=Ip'+IN

(2)

其中,Ip表示節(jié)點(diǎn)p的重要性,Ip'表示根據(jù)節(jié)點(diǎn)p自身權(quán)值信息計(jì)算得到的重要性,IN表示根據(jù)節(jié)點(diǎn)p的鄰居節(jié)點(diǎn)信息計(jì)算得到的重要性。

Ip'的定義如下:

(3)

(4)

其中,wmin表示網(wǎng)絡(luò)中邊的最小權(quán)值,wmax表示網(wǎng)絡(luò)中邊的最大權(quán)值。歸一化可以防止網(wǎng)絡(luò)規(guī)模過大時(shí),直接計(jì)算邊的權(quán)值之和可能導(dǎo)致的數(shù)據(jù)溢出問題。

IN的定義如下:

(5)

其中,wjp表示節(jié)點(diǎn)j和節(jié)點(diǎn)p之間的權(quán)值,‖N(j)‖表示節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)數(shù)目,wk表示節(jié)點(diǎn)j的鄰邊中第k條邊的權(quán)值。

以圖1所示的簡(jiǎn)單加權(quán)網(wǎng)絡(luò)為例,其中節(jié)點(diǎn)v1擁有最多的連邊且與之相連的邊的權(quán)值在整個(gè)網(wǎng)絡(luò)中占比最大,該節(jié)點(diǎn)應(yīng)該是網(wǎng)絡(luò)中最重要的節(jié)點(diǎn)。對(duì)于節(jié)點(diǎn)v2和v3,除了考察其自身的Iv',它們的共同鄰居v1對(duì)節(jié)點(diǎn)v3的重要性貢獻(xiàn)較大,則v3應(yīng)比v2擁有更高的重要性值。

圖1 簡(jiǎn)單加權(quán)網(wǎng)絡(luò)

可見,節(jié)點(diǎn)v1的重要性Iv1最大,計(jì)算結(jié)果與實(shí)際相符,說明該文設(shè)計(jì)的加權(quán)網(wǎng)絡(luò)的節(jié)點(diǎn)重要性計(jì)算方法WNI是合理有效的。

3 IMWCD算法設(shè)計(jì)與分析

如前文所述,BGLL算法第一階段節(jié)點(diǎn)的遍歷次序隨機(jī),沒有考慮節(jié)點(diǎn)自身屬性信息及其所處環(huán)境信息,從而可能使最終的社團(tuán)劃分結(jié)果的準(zhǔn)確度不夠高。為了解決這個(gè)問題,該文設(shè)計(jì)了基于節(jié)點(diǎn)重要性和模塊度優(yōu)化的加權(quán)網(wǎng)絡(luò)社團(tuán)劃分算法IMWCD。

3.1 設(shè)計(jì)思路

IMWCD采用WNI方法計(jì)算節(jié)點(diǎn)重要性,將BGLL算法每次迭代中第一階段的節(jié)點(diǎn)遍歷順序由隨機(jī)遍歷調(diào)整為按節(jié)點(diǎn)重要性的升序遍歷,以便綜合利用全局和局部信息來提升算法的準(zhǔn)確度。

3.2 IMWCD算法總體流程

算法總體流程可描述如下:

輸入:網(wǎng)絡(luò)圖G=(V,E,W);

輸出:加權(quán)網(wǎng)絡(luò)社團(tuán)。

算法步驟:

Step1:初始化網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)i∈V為一個(gè)社團(tuán),社團(tuán)編號(hào)為節(jié)點(diǎn)編號(hào);

Step2:根據(jù)式(2)至式(5)計(jì)算每個(gè)節(jié)點(diǎn)的重要性,并將所有節(jié)點(diǎn)按照重要性升序排列成節(jié)點(diǎn)序列l(wèi)ist;

//迭代更新階段:

Step3:考察list中的首個(gè)節(jié)點(diǎn);

Step4:遍歷當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn),計(jì)算當(dāng)前節(jié)點(diǎn)移入其鄰居節(jié)點(diǎn)所在社團(tuán)后的模塊度增益,記錄模塊度增益的最大值和對(duì)應(yīng)的社團(tuán)編號(hào);

Step5:若最大模塊度增益大于零,將當(dāng)前節(jié)點(diǎn)移入模塊度增益最大的社團(tuán);否則當(dāng)前節(jié)點(diǎn)仍留在原始社團(tuán)。繼續(xù)考察list中的下一個(gè)節(jié)點(diǎn);

Step6:重復(fù)Step4、Step5,直至當(dāng)前網(wǎng)絡(luò)中沒有節(jié)點(diǎn)需要移動(dòng);

Step7:計(jì)算Step6結(jié)束后整個(gè)網(wǎng)絡(luò)的模塊度,并與上一輪的網(wǎng)絡(luò)模塊度對(duì)比,如果網(wǎng)絡(luò)模塊度未增大,則當(dāng)前的劃分結(jié)果為最終劃分結(jié)果,算法終止;否則,執(zhí)行Step8;

//網(wǎng)絡(luò)重構(gòu)階段:

Step8:將Step6中檢測(cè)出的每個(gè)社團(tuán)分別作為一個(gè)節(jié)點(diǎn),對(duì)網(wǎng)絡(luò)進(jìn)行重構(gòu),將社團(tuán)內(nèi)的所有邊的權(quán)值之和作為新節(jié)點(diǎn)指向自身的自環(huán)邊的權(quán)值,新節(jié)點(diǎn)之間的權(quán)值為兩個(gè)原社團(tuán)之間連邊的權(quán)值之和。將重構(gòu)網(wǎng)絡(luò)作為輸入,重復(fù)Step2至Step7進(jìn)行新一輪迭代。

IMWCD算法的具體流程如圖2所示。

圖2 IMWCD算法的具體流程

3.3 IMWCD算法分析

(1)實(shí)例分析。

在加權(quán)網(wǎng)絡(luò)圖中,權(quán)值代表了不同節(jié)點(diǎn)間聯(lián)系的緊密程度,而根據(jù)社團(tuán)結(jié)構(gòu)的定義,社團(tuán)內(nèi)部節(jié)點(diǎn)間聯(lián)系緊密,社團(tuán)之間聯(lián)系稀疏。以圖3所示的簡(jiǎn)單加權(quán)網(wǎng)絡(luò)為例來模擬IMWCD算法對(duì)加權(quán)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的劃分過程,檢驗(yàn)其社團(tuán)劃分效果。

圖3 加權(quán)網(wǎng)絡(luò)

用公式(2)至公式(5)計(jì)算每個(gè)節(jié)點(diǎn)的重要性,得到I1=2.266,I2=3.312,I3=1.753,I4=3.373,I5=1.942,I6=2.306,I7=2.066,按照節(jié)點(diǎn)重要性升序排列得到節(jié)點(diǎn)序列L={3,5,7,1,6,2,4}。

將網(wǎng)絡(luò)中的7個(gè)節(jié)點(diǎn)初始化為7個(gè)單獨(dú)的社團(tuán),編號(hào)與節(jié)點(diǎn)序號(hào)對(duì)應(yīng),分別為C1至C7。

迭代更新階段:首先考察節(jié)點(diǎn)序列L中的節(jié)點(diǎn)3(稱為目標(biāo)節(jié)點(diǎn)),其鄰居節(jié)點(diǎn)所在社團(tuán)集合為{1,2,4},根據(jù)公式(1)分別計(jì)算將節(jié)點(diǎn)3移入其鄰居節(jié)點(diǎn)所在社團(tuán)Ci前后的模塊度增益ΔQi,分別為:ΔQ1=0.020 2,ΔQ2=0.061 8,ΔQ4=0.025 5,則選擇將節(jié)點(diǎn)3移入社團(tuán)C2。同理,依次遍歷剩下的節(jié)點(diǎn),以模塊度增益最大且為正值為原則,將節(jié)點(diǎn)移入相應(yīng)社團(tuán),具體情況如表1所示。

表1 第一次遍歷的情況

由表1可知,第一次遍歷產(chǎn)生了三個(gè)社團(tuán),分別為C2(3),C4(1,2,4),C6(5,6,7)。因?yàn)橛泄?jié)點(diǎn)移動(dòng),所以再次從節(jié)點(diǎn)序列L的節(jié)點(diǎn)3開始新的遍歷,其當(dāng)前所屬社團(tuán)為C2,鄰居社團(tuán)只有C4,將其移入C4的模塊度增益ΔQ4=0.107 4,因?yàn)棣4>0,所以將其移入社團(tuán)C4;繼續(xù)依次遍歷L中其余節(jié)點(diǎn),計(jì)算得出這些節(jié)點(diǎn)的移動(dòng)不會(huì)使模塊度增加(具體計(jì)算過程不再贅述),因此在本輪遍歷過程中節(jié)點(diǎn)3移入C4,C2消失,C6不變。即結(jié)果有2個(gè)社團(tuán),分別是C4(1,2,3,4),C6(5,6,7)。

因?yàn)橛泄?jié)點(diǎn)移動(dòng),所以要繼續(xù)從節(jié)點(diǎn)序列L的節(jié)點(diǎn)3開始新的遍歷,再次執(zhí)行迭代更新,計(jì)算得出所有節(jié)點(diǎn)變動(dòng)后的模塊度增益均小于零(具體計(jì)算過程不再贅述),即所有節(jié)點(diǎn)不需再移動(dòng),迭代更新階段結(jié)束,劃分出的社團(tuán)結(jié)構(gòu)如圖4所示。此時(shí)的網(wǎng)絡(luò)模塊度Q=0.428 2。

圖4 迭代更新結(jié)果

網(wǎng)絡(luò)重構(gòu)階段:將迭代更新檢測(cè)出的社團(tuán)作為節(jié)點(diǎn),對(duì)網(wǎng)絡(luò)進(jìn)行重構(gòu),重構(gòu)的網(wǎng)絡(luò)如圖5所示。為了便于理解,新網(wǎng)絡(luò)的節(jié)點(diǎn)號(hào)用對(duì)應(yīng)的社團(tuán)號(hào)表示,兩個(gè)節(jié)點(diǎn)分別是C4和C6。

圖5 網(wǎng)絡(luò)重構(gòu)結(jié)果

對(duì)重構(gòu)后的網(wǎng)絡(luò),用公式(2)至公式(5)計(jì)算每個(gè)節(jié)點(diǎn)的重要性得到IC4=2.026,IC6=1.460,升序排列的節(jié)點(diǎn)序列為L(zhǎng)={C6,C4},重復(fù)迭代更新階段,此時(shí)兩個(gè)節(jié)點(diǎn)互為鄰居,C6移動(dòng)到C4所在社團(tuán)后的模塊度增益是ΔQC6=-0.428 3,C4移動(dòng)到C6所在社團(tuán)后的模塊度增益是ΔQC4=-0.428 3,都小于零,即都不需再移動(dòng),迭代更新結(jié)束,此時(shí)網(wǎng)絡(luò)模塊度為Q'=0.428 2,與上一輪迭代更新結(jié)束時(shí)的網(wǎng)絡(luò)模塊度Q相同,算法終止。最終劃分出的兩個(gè)社團(tuán)編號(hào)分別為C4和C6。不難看出節(jié)點(diǎn)4和節(jié)點(diǎn)6在最初的節(jié)點(diǎn)重要性升序序列中確實(shí)處于高位,因此最終劃分的社團(tuán)以節(jié)點(diǎn)4和6為中心,符合實(shí)際情況,驗(yàn)證了WNI和IMWCD的有效性。

(2)時(shí)間復(fù)雜度分析。

在節(jié)點(diǎn)重要性計(jì)算過程中,根據(jù)節(jié)點(diǎn)自身權(quán)值信息計(jì)算重要性的時(shí)間復(fù)雜度為O(dn);d為網(wǎng)絡(luò)的平均度值,n為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù);基于鄰居節(jié)點(diǎn)信息計(jì)算重要性的時(shí)間復(fù)雜度為O(dn),按節(jié)點(diǎn)重要性升序排序節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n),因此對(duì)于節(jié)點(diǎn)重要性計(jì)算以及節(jié)點(diǎn)重要性排序的算法復(fù)雜度為O(dn+dn+n),即O((2d+1)n);傳統(tǒng)BGLL算法考察每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn),時(shí)間復(fù)雜度為O(dn),計(jì)算節(jié)點(diǎn)移動(dòng)的模塊度變化的時(shí)間復(fù)雜度為O(n),移動(dòng)節(jié)點(diǎn)的復(fù)雜度為O(n),網(wǎng)絡(luò)重構(gòu)階段的時(shí)間復(fù)雜度為O(m),m為網(wǎng)絡(luò)中的邊數(shù)。因此BGLL算法的時(shí)間復(fù)雜度為O(dn+n+n+m),即O((d+2)n+m)。實(shí)際大規(guī)模網(wǎng)絡(luò)圖為稀疏圖,因此BGLL的時(shí)間復(fù)雜度近似O((d+2)n)。綜上,IMWCD算法的總復(fù)雜度為O((2d+1)n+(d+2)n+m),近似為O(3(d+1)n),算法總的時(shí)間復(fù)雜度仍然是接近線性的。

4 性能測(cè)試實(shí)驗(yàn)及結(jié)果分析

該文分別在LFR人工基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集和三個(gè)真實(shí)加權(quán)網(wǎng)絡(luò)數(shù)據(jù)集上對(duì)所設(shè)計(jì)的IMWCD算法的性能進(jìn)行測(cè)試,并與BGLL算法和CNM算法做對(duì)比。其中,CNM算法首先將有N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)初始化為n個(gè)社團(tuán),然后計(jì)算社團(tuán)兩兩合并前后的模塊度增益,用堆結(jié)構(gòu)來構(gòu)造模塊度增量矩陣,選擇模塊度增益最大的社團(tuán)進(jìn)行合并,并更新模塊度增量矩陣,直至網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都?xì)w到一個(gè)社團(tuán)。該算法針對(duì)稀疏網(wǎng)絡(luò)的時(shí)間復(fù)雜度為O(mlogn),其中m為邊數(shù),n為節(jié)點(diǎn)數(shù)。

(1)實(shí)驗(yàn)數(shù)據(jù)集。

(a)LFR人工基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集。

實(shí)驗(yàn)使用的LFR人工基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集參數(shù)見表2。

表2 LFR基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集參數(shù)

表中,N表示網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量;k表示節(jié)點(diǎn)的平均度;maxk表示節(jié)點(diǎn)的最大度值;maxc表示最大社團(tuán)規(guī)模;minc表示最小社團(tuán)規(guī)模;u表示混合系數(shù),u越大,社團(tuán)結(jié)構(gòu)越不明顯。為了能夠?qū)訖?quán)社團(tuán)劃分算法做驗(yàn)證,在數(shù)據(jù)集生成過程中,對(duì)于同一個(gè)社團(tuán)內(nèi)的連邊隨機(jī)生成[0.5,1]的權(quán)值,不同社團(tuán)之間的邊隨機(jī)生成(0,0.5)的權(quán)值。

(b)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集。

實(shí)驗(yàn)使用的三個(gè)較大規(guī)模真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集分別是1995至1999年間高能物理研究領(lǐng)域(High-energy theory)和天體物理研究領(lǐng)域(Astrophysics)的科學(xué)家合作網(wǎng)絡(luò),以及1995至2005年間凝聚態(tài)(Condensedmatter)研究領(lǐng)域的科學(xué)家合作網(wǎng)絡(luò)。以下分別簡(jiǎn)稱H-th、A-ph、C-mat。邊的權(quán)值表示科學(xué)家們的合作次數(shù)。數(shù)據(jù)集的統(tǒng)計(jì)特征如表3所示。

表3 數(shù)據(jù)集統(tǒng)計(jì)情況

(2)評(píng)價(jià)指標(biāo)。

用標(biāo)準(zhǔn)化互信息NMI[15]來衡量算法對(duì)LFR人工基準(zhǔn)網(wǎng)絡(luò)的社團(tuán)劃分準(zhǔn)確度,NMI值越大,表明算法劃分精度越高;用模塊度Q來衡量算法對(duì)真實(shí)加權(quán)網(wǎng)絡(luò)的社團(tuán)劃分質(zhì)量,Q值越大,表明社團(tuán)劃分的模塊化越強(qiáng),劃分效果越好。

(3)結(jié)果分析。

(a)基于LFR人工基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果。

使用三種算法分別對(duì)網(wǎng)絡(luò)N1和N2進(jìn)行劃分,NMI的計(jì)算結(jié)果如表4所示。

表4 三種算法的NMI值

從表4可以看出,相同混合系數(shù)下,隨著節(jié)點(diǎn)數(shù)增多,各算法的NMI值略有下降。相同節(jié)點(diǎn)數(shù)的情況下,隨著混合系數(shù)的增加,網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)越來越模糊,三個(gè)算法的表現(xiàn)也逐漸變差,但所設(shè)計(jì)的IMWCD算法的NMI值始終高于其他兩個(gè)算法,社團(tuán)劃分的準(zhǔn)確性優(yōu)于其他對(duì)比算法。

(b)基于真實(shí)加權(quán)網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)。

表5給出了三種加權(quán)網(wǎng)絡(luò)社團(tuán)劃分算法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集H-th、A-ph、C-mat上分別運(yùn)行十次得到的平均模塊度Q值。

表5 真實(shí)加權(quán)網(wǎng)絡(luò)數(shù)據(jù)集社團(tuán)劃分結(jié)果

從表5可以看出,IMWCD算法在三個(gè)較大規(guī)模的真實(shí)加權(quán)網(wǎng)絡(luò)數(shù)據(jù)集上的模塊度Q值都大于其他兩個(gè)算法,驗(yàn)證了IMWCD算法在劃分準(zhǔn)確度方面的優(yōu)勢(shì)。

5 結(jié)束語

考慮到節(jié)點(diǎn)重要性對(duì)社團(tuán)劃分過程具有更明確的指示作用,以及BGLL算法迭代更新過程中的節(jié)點(diǎn)遍歷順序會(huì)影響算法劃分結(jié)果的準(zhǔn)確度,設(shè)計(jì)了一種基于節(jié)點(diǎn)重要性和模塊度優(yōu)化的加權(quán)網(wǎng)絡(luò)社團(tuán)劃分算法。綜合節(jié)點(diǎn)自身權(quán)值信息和其鄰居節(jié)點(diǎn)信息計(jì)算節(jié)點(diǎn)的重要性,以節(jié)點(diǎn)重要性的升序?yàn)锽GLL算法的節(jié)點(diǎn)遍歷順序。理論分析和在人工網(wǎng)絡(luò)及真實(shí)加權(quán)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明了IMWCD算法在保持線性時(shí)間復(fù)雜度的同時(shí),克服了BGLL算法節(jié)點(diǎn)順序敏感問題,劃分結(jié)果的準(zhǔn)確度有所提升,能夠?qū)訖?quán)復(fù)雜網(wǎng)絡(luò)進(jìn)行有效的社團(tuán)劃分。