蔡威林，葛 斌

（安徽理工大學(xué),計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232000）

近年來(lái)，各領(lǐng)域的大量科研人員投入到對(duì)網(wǎng)絡(luò)學(xué)科的深入研究中，社會(huì)網(wǎng)絡(luò)[1]、電商網(wǎng)絡(luò)[2]、生物網(wǎng)絡(luò)[3]、電力網(wǎng)絡(luò)[4]等都是復(fù)雜網(wǎng)絡(luò)的例子。網(wǎng)絡(luò)社區(qū)檢測(cè)作為復(fù)雜網(wǎng)絡(luò)研究的一個(gè)重要方向,越來(lái)越引起研究者的關(guān)注[5]。

復(fù)雜網(wǎng)絡(luò)中，節(jié)點(diǎn)通過(guò)邊連接成成對(duì)，一些節(jié)點(diǎn)相對(duì)緊密地連接在一起并聚集成簇或堆，這就是所謂的社區(qū)結(jié)構(gòu)[6]。隨著社交網(wǎng)絡(luò)中數(shù)據(jù)復(fù)雜性逐漸增大，網(wǎng)絡(luò)中節(jié)點(diǎn)之間的相關(guān)性逐漸增加，同一社區(qū)的節(jié)點(diǎn)通常具有相似的屬性[7]和特征[8](如背景、職業(yè)或興趣)，社區(qū)結(jié)構(gòu)逐漸復(fù)雜，社區(qū)檢測(cè)變得及其困難。傳統(tǒng)的計(jì)算方法，例如：GN算法[9]，F(xiàn)N算法[10]，LPA算法[11]，無(wú)法滿足現(xiàn)有網(wǎng)絡(luò)的檢測(cè)計(jì)算，需要新的方法解釋網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間的相似程度，從而劃分出相應(yīng)的社區(qū)，對(duì)節(jié)點(diǎn)加以區(qū)分。

1 相關(guān)工作

近年來(lái)，許多學(xué)者對(duì)節(jié)點(diǎn)相似性開(kāi)展了深入研究。例如，文獻(xiàn)[12]提出基于相似度的動(dòng)態(tài)演化符號(hào)，加入最短路徑使得相似度隨著時(shí)間變化。文獻(xiàn)[13]提出的IES算法,它基于信息熵和余弦相似度，以節(jié)點(diǎn)對(duì)社區(qū)的相似度進(jìn)行判別。文獻(xiàn)[14]提出FCSL算法，它把余弦相似度和共享連接相結(jié)合尋找節(jié)點(diǎn)相似性。文獻(xiàn)[15]提出LPA-S算法，在標(biāo)簽傳播過(guò)程中將公共鄰居考慮進(jìn)節(jié)點(diǎn)間的相似度計(jì)算，標(biāo)簽跟隨相似度傳播。文獻(xiàn)[16]提出一種局部相似性度量，并結(jié)合層次聚類用于社區(qū)結(jié)構(gòu)發(fā)現(xiàn)，克服了傳統(tǒng)局部相似性度量在某些情形下對(duì)節(jié)點(diǎn)相似性的低估傾向。文獻(xiàn)[17]引入相似度來(lái)衡量節(jié)點(diǎn)間連接強(qiáng)度，改進(jìn)具有高影響力的種子節(jié)點(diǎn)選取方法，提高了社區(qū)檢測(cè)算發(fā)的準(zhǔn)確度。文獻(xiàn)[18]提出CDASS算法，通過(guò)定義公共鄰居相似度，劃分節(jié)點(diǎn)在社區(qū)結(jié)構(gòu)中位置，將相似節(jié)點(diǎn)分配給同一社區(qū)。文獻(xiàn)[19]提出了一種新的基于非負(fù)矩陣分解和圖優(yōu)化的網(wǎng)絡(luò)社區(qū)檢測(cè)算法根據(jù)屬性配置文件構(gòu)造了節(jié)點(diǎn)的屬性相似矩陣。文獻(xiàn)[20]提出了根據(jù)不同的鄰居節(jié)點(diǎn)類型分配不同的邊緣權(quán)重影響因子來(lái)計(jì)算節(jié)點(diǎn)相似性。

現(xiàn)階段的研究雖然結(jié)合相似度的方法進(jìn)行判斷節(jié)點(diǎn)社區(qū)劃分，但都沒(méi)有考慮節(jié)點(diǎn)狀態(tài)變化。根據(jù)文獻(xiàn)[21]提出在民航網(wǎng)絡(luò)中引入節(jié)點(diǎn)狀態(tài)可以提高網(wǎng)絡(luò)安全運(yùn)行，文獻(xiàn)[22]提出將實(shí)時(shí)節(jié)點(diǎn)狀態(tài)運(yùn)用在物聯(lián)網(wǎng)節(jié)點(diǎn)中，提高節(jié)點(diǎn)有效檢測(cè)范圍，發(fā)現(xiàn)加入節(jié)點(diǎn)狀態(tài)因素在網(wǎng)絡(luò)數(shù)據(jù)可以更好的分析網(wǎng)絡(luò)。因此，節(jié)點(diǎn)狀態(tài)的變化可以考慮在節(jié)點(diǎn)相似度的計(jì)算中。網(wǎng)絡(luò)中節(jié)點(diǎn)的狀態(tài)取決于其鄰居的當(dāng)前狀態(tài)，并且每個(gè)節(jié)點(diǎn)的狀態(tài)只能在兩種狀態(tài)中選擇:0 和1。0 表示節(jié)點(diǎn)未激活，1 表示節(jié)點(diǎn)已激活。因而我們可以為每個(gè)節(jié)點(diǎn)定義一個(gè)稱為變化指數(shù)的量，如下所示:

其中Te(i)表示節(jié)點(diǎn)vi的鄰居中狀態(tài)為1的節(jié)點(diǎn)數(shù)，di表示節(jié)點(diǎn)vi的度。

本文提出一種基于節(jié)點(diǎn)狀態(tài)變化的社區(qū)查找方法，并將其稱為動(dòng)態(tài)相似度算法(TCS)。在開(kāi)始定義了變化指數(shù)，然后計(jì)算節(jié)點(diǎn)鄰居和自身的相似性，最后結(jié)合余弦相似性理論完成社區(qū)查找。

2 相似度算法

假設(shè)網(wǎng)絡(luò)模型可以表示為G=（V，E）.包含N個(gè)節(jié)點(diǎn)和M條邊的連通網(wǎng)絡(luò)其中V={v1,v2,v3,…,vN}表示節(jié)點(diǎn)集，E={e1,e2,e3,…eM}是邊集。我們利用鄰接矩陣來(lái)描述網(wǎng)絡(luò)的連接模式。節(jié)點(diǎn)vi和vj之間的連接強(qiáng)度由矩陣a的元素(Aij)表示。i,j是V中任意的兩個(gè)節(jié)點(diǎn)，當(dāng)兩個(gè)節(jié)點(diǎn)直接相連時(shí)Aij=1,否則Aij=0。

2.1 余弦相似度

早期常用的相似性度量包括Jaccard 相似性、余弦相似性和RA 指數(shù)。余弦相似性是是用向量空間中兩個(gè)向量夾角的余弦值作為衡量?jī)蓚€(gè)個(gè)體間差異的大小的度量。余弦值越接近1，就表明夾角越接近0 度，也就是兩個(gè)向量越相似。對(duì)于節(jié)點(diǎn)vi和vj,其相似性公式如下：

其中G(vi)和G(vj)表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的鄰居集,d(vi),d(vj)表示節(jié)點(diǎn)vi，vj的度。相似性度量范圍從0 到1。

以往的以余弦相似度為代表的相似性度量方法有效地解決了相鄰節(jié)點(diǎn)的問(wèn)題，計(jì)算對(duì)象間的距離，用于數(shù)據(jù)聚類，但不能準(zhǔn)確、全面地管理節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系。為了得到更準(zhǔn)確的劃分結(jié)果，本文提出了一種基于節(jié)點(diǎn)狀態(tài)變化的方法，作為節(jié)點(diǎn)間相似程度的度量方法。

2.2 節(jié)點(diǎn)相似性

首先，每個(gè)節(jié)點(diǎn)都可以假設(shè)為源節(jié)點(diǎn)，而鄰居節(jié)點(diǎn)會(huì)根據(jù)節(jié)點(diǎn)狀態(tài)的變化進(jìn)而產(chǎn)生不一樣的時(shí)序影響，故我們需要考慮到節(jié)點(diǎn)自身和其鄰居節(jié)點(diǎn)在時(shí)間段的總體變化，因此定義一個(gè)計(jì)算節(jié)點(diǎn)的所有鄰居的影響稱為節(jié)點(diǎn)變化指數(shù)。其公式如下：

其中，G(vi)表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集合，TE(i)表示節(jié)點(diǎn)vi的變化指數(shù)。

其次，在社交網(wǎng)絡(luò)中選擇源節(jié)點(diǎn)，源節(jié)點(diǎn)可以影響其鄰居節(jié)點(diǎn)，最后到達(dá)整個(gè)網(wǎng)絡(luò)。我們選擇一個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn)，可以根據(jù)節(jié)點(diǎn)狀態(tài)變化計(jì)算節(jié)點(diǎn)之間的相似度。因此，在余弦相似度的基礎(chǔ)上結(jié)合基于節(jié)點(diǎn)變化指數(shù)的結(jié)果，本文定以了一個(gè)節(jié)點(diǎn)之間的相似性度量稱為動(dòng)態(tài)節(jié)點(diǎn)相似度，其公式為：

其中，TS(vi）表示節(jié)點(diǎn)變化指數(shù)，d(vi),d(vj)表示節(jié)點(diǎn)vi，vj的度。

上述計(jì)算過(guò)程描述如下：

Step1:輸入一個(gè)網(wǎng)絡(luò)G=(V,E)；

Step2:根據(jù)公式(1)產(chǎn)生N 個(gè)不同的變化指數(shù)TE；

Step3:根據(jù)公式(3)計(jì)算每一對(duì)節(jié)點(diǎn)之間的節(jié)點(diǎn)變化指數(shù)TS；

Step4:根據(jù)公式(4)計(jì)算每一對(duì)節(jié)點(diǎn)間的動(dòng)態(tài)相似度TCS；

Step5:刪除當(dāng)前網(wǎng)絡(luò)相似度最低的邊;

Step6:根據(jù)公式(5)計(jì)算當(dāng)前網(wǎng)絡(luò)的模塊性Q和標(biāo)準(zhǔn)歸一化NMI;

Step7:重復(fù)2-6 操作，直到當(dāng)前網(wǎng)絡(luò)模塊性Q或標(biāo)準(zhǔn)歸一化NMI 最大；

Step8:輸出當(dāng)前網(wǎng)絡(luò)的社區(qū)劃分。

算法過(guò)程中，首先計(jì)算每對(duì)節(jié)點(diǎn)之間的動(dòng)態(tài)相似度，然后刪除網(wǎng)絡(luò)中相似度最低的節(jié)點(diǎn)對(duì)的邊。把模塊性Q 和標(biāo)準(zhǔn)歸一化NMI 作為當(dāng)前網(wǎng)絡(luò)劃分的標(biāo)準(zhǔn)，重復(fù)上述刪除邊的操作，直到模塊性Q 或標(biāo)準(zhǔn)歸一化NMI 取得最大值。最后停止計(jì)算，輸出當(dāng)前的社區(qū)劃分，并記錄模塊性Q 或標(biāo)準(zhǔn)歸一化NMI的值。對(duì)于模塊性Q 或標(biāo)準(zhǔn)歸一化NMI 會(huì)在3.1 小節(jié)詳細(xì)介紹。

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

本文使用的社交網(wǎng)絡(luò)包括空手道俱樂(lè)部網(wǎng)絡(luò)(Karate)、海豚俱樂(lè)部(Dolphins)、美國(guó)大學(xué)生2000賽季美式足球聯(lián)賽網(wǎng)絡(luò)(Footballs)、美國(guó)政治書籍網(wǎng)絡(luò)(Books)通過(guò)所提出的相似性度量來(lái)尋找數(shù)據(jù)集中的社區(qū)結(jié)構(gòu)，得出社區(qū)劃分結(jié)果。然后根據(jù)測(cè)量標(biāo)準(zhǔn)模塊性(Q,Modularity)值和標(biāo)準(zhǔn)歸一化(NMI,Normalized Mutual Information)值進(jìn)行評(píng)估，從而判斷其性能。作為比較，我們還將幾種經(jīng)典的社區(qū)檢測(cè)方法應(yīng)用于上述數(shù)據(jù)集。

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

1.第一個(gè)評(píng)價(jià)指標(biāo)為模塊性(Q)，它是評(píng)價(jià)社區(qū)檢測(cè)的經(jīng)典方法，被廣泛采用來(lái)表示特定分區(qū)的社區(qū)結(jié)構(gòu)的強(qiáng)度，以此用來(lái)衡量社區(qū)劃分的好壞。因此，Q的值越大說(shuō)明社區(qū)的結(jié)構(gòu)越清晰。形式上，模塊性（Q）可以定義為：

其中，di，dj表示節(jié)點(diǎn)vi,vj的度數(shù)，如果節(jié)點(diǎn)vi,vj在同一個(gè)社區(qū)，則函數(shù)(ci,cj)等于1，否則函數(shù)等于0。當(dāng)所有節(jié)點(diǎn)都?xì)w屬同一個(gè)社區(qū)的時(shí)候，Q=0。

2.第二個(gè)評(píng)價(jià)指標(biāo)為標(biāo)準(zhǔn)歸一化(NMI)。在社區(qū)檢測(cè)問(wèn)題中，標(biāo)準(zhǔn)歸一化可以檢測(cè)社區(qū)和真實(shí)社區(qū)之間的相似性?？紤]兩個(gè)分區(qū)A={A1,…,Aa}，B={B1,…,Bb}并使用C來(lái)表示混淆矩陣。該矩陣的每個(gè)元素Cij表示同時(shí)屬于團(tuán)體A共和團(tuán)體B的公共節(jié)點(diǎn)的數(shù)量。形式上，NMI 定義為：

其中|A|和|B|分別是分區(qū)A 和B 中社區(qū)數(shù)。Ci和Cj分別表示矩陣的第1 行元素之和和第1 列元素之和。當(dāng)一個(gè)網(wǎng)絡(luò)的兩個(gè)分區(qū)相同時(shí)，我們有NMI=1,兩個(gè)分區(qū)完全獨(dú)立時(shí)，NMI=0。

3.2 實(shí)驗(yàn)結(jié)果與分析

在四個(gè)數(shù)據(jù)集上分別對(duì)LPA、GN、FN、TCS這四種算法進(jìn)行實(shí)驗(yàn)，計(jì)算模塊性Q 和標(biāo)準(zhǔn)歸一化NMI 并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行綜合評(píng)估與分析，實(shí)驗(yàn)結(jié)果得到的數(shù)據(jù)如表1 所示。

表1 各算法在數(shù)據(jù)集下的模塊性和NMI的值

圖1 為各算法模塊性結(jié)果詳細(xì)對(duì)比情況，可以看到TCS算法在Karate、Footballs、Books 三個(gè)數(shù)據(jù)集下模塊性Q的值均高于經(jīng)典算法，說(shuō)明TCS算法確定社區(qū)劃分得到的社區(qū)結(jié)構(gòu)更加清晰。而在Dolphins 數(shù)據(jù)集中節(jié)點(diǎn)與邊比值較大，GN算法的邊介數(shù)計(jì)算方法比TCS算法的動(dòng)態(tài)節(jié)點(diǎn)相似度更容易分析網(wǎng)絡(luò)，故GN算法取得的值較高。但總的來(lái)說(shuō)，TCS算法的模塊性還是高于經(jīng)典算法的，說(shuō)明其可以發(fā)現(xiàn)更加清晰的社區(qū)結(jié)構(gòu)。

圖1 各算法模塊性Q

圖2 為各算法標(biāo)準(zhǔn)歸一化NMI的值詳細(xì)對(duì)比情況，可以看到TCS算法在四個(gè)數(shù)據(jù)集下標(biāo)準(zhǔn)歸一化NMI的值與經(jīng)典算法的值是非常相近，因?yàn)門CS算法與其他經(jīng)典的算法相比，都是通過(guò)刪除邊的操作來(lái)進(jìn)行社區(qū)劃分，最后得到的社區(qū)情況相差不大，故各算法的值都非常相近。但總的來(lái)說(shuō)，TCS算法的劃分社區(qū)和真實(shí)社區(qū)還是有較高的相似度，且絲毫不弱于其他經(jīng)典算法。

圖2 各算法標(biāo)準(zhǔn)歸一化NMI

4 總結(jié)

本文提出了一種新的網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)相似性度量方法。以往的研究考慮了相似性在社交網(wǎng)絡(luò)中的應(yīng)用，但是都沒(méi)有考慮到節(jié)點(diǎn)狀態(tài)變化使節(jié)點(diǎn)相似性發(fā)生變化。基于節(jié)點(diǎn)狀態(tài)變化對(duì)相似度的影響，定義變化指數(shù)(TE)來(lái)表示網(wǎng)絡(luò)中節(jié)點(diǎn)變化，通過(guò)節(jié)點(diǎn)變化指數(shù)(TS)來(lái)定義網(wǎng)絡(luò)節(jié)點(diǎn)之間的總體變化。在此基礎(chǔ)上，結(jié)合余弦相似度得到動(dòng)態(tài)相似度算法(TCS)來(lái)表示網(wǎng)絡(luò)中節(jié)點(diǎn)之間的相似度。我們將所提出的算法應(yīng)用于社交網(wǎng)絡(luò)，比較評(píng)價(jià)指標(biāo)模塊性Q 和標(biāo)準(zhǔn)歸一化NMI，實(shí)驗(yàn)結(jié)果表明TCS算法取得的社區(qū)劃分效果均優(yōu)于經(jīng)典算法，得到了社區(qū)結(jié)構(gòu)強(qiáng)度更高，與真實(shí)社區(qū)更相似的社區(qū)劃分。因此，驗(yàn)證了提出TCS算法的有效性,證明基于節(jié)點(diǎn)狀態(tài)變化的社區(qū)檢測(cè)是可行的。

本文研究的都是無(wú)向網(wǎng)絡(luò)，而現(xiàn)實(shí)不僅存在無(wú)向網(wǎng)絡(luò)，更是存在著有向網(wǎng)絡(luò)。在將來(lái)，我們將致力于推廣我們處理有向網(wǎng)絡(luò)的方法，探索節(jié)點(diǎn)狀態(tài)對(duì)于有向網(wǎng)絡(luò)社區(qū)檢測(cè)的意義。