基于節(jié)點(diǎn)相異性指標(biāo)的網(wǎng)絡(luò)社團(tuán)檢測算法

劉亞東，覃 森

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

0 引 言

近年來，隨著機(jī)器學(xué)習(xí)和深度學(xué)習(xí)的快速發(fā)展，人們能更快更好地了解復(fù)雜世界。復(fù)雜網(wǎng)絡(luò)將現(xiàn)實(shí)中的實(shí)體抽象為網(wǎng)絡(luò)中的節(jié)點(diǎn)，網(wǎng)絡(luò)中的邊對應(yīng)于實(shí)體之間的關(guān)系。隨著研究的深入，學(xué)者們發(fā)現(xiàn)：可以將整個網(wǎng)絡(luò)看成由若干個社團(tuán)構(gòu)成，同一社團(tuán)內(nèi)的連邊連接緊密，而不同社團(tuán)之間的連邊連接稀疏[1]。復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的檢測對分析網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和層次結(jié)構(gòu)、理解社團(tuán)的形成過程、發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)的內(nèi)在演化規(guī)律等具有十分重要的意義；此外，社團(tuán)結(jié)構(gòu)檢測也有重要的現(xiàn)實(shí)意義，如在科研合作網(wǎng)絡(luò)中，把方向、興趣和研究內(nèi)容相關(guān)的科學(xué)家劃分到同一個社團(tuán)中，可以向某位科學(xué)家推薦同一社團(tuán)內(nèi)其他成員以促進(jìn)他們之間的合作，從而推動科研的發(fā)展。

1927年，S.A.Rice[2]開始對政治網(wǎng)絡(luò)進(jìn)行社團(tuán)結(jié)構(gòu)的調(diào)查研究，到1995年，R.S.Weiss和E.Jacobson[3]第一次提出較為完善的社團(tuán)結(jié)構(gòu)檢測方法，在2002年，M.E.J.Newman等[4]提出一種基于邊介數(shù)的社團(tuán)檢測算法(Girvan-Newman，GN)，通過從網(wǎng)絡(luò)中不斷移除介數(shù)最大的邊來確定網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)。GN算法的提出掀起了社團(tuán)檢測研究的熱潮，許多領(lǐng)域的學(xué)者從不同角度相繼提出了不同的社團(tuán)檢測算法，主要可以分為基于模塊度優(yōu)化的算法、基于傳播思想的算法、基于分級聚類的算法?；谀K度優(yōu)化的算法主要包括貪婪算法[5]和極值優(yōu)化算法[6]等；基于傳播思想的算法主要包括標(biāo)簽傳播算法(Label Propagation Algorithm，LPA)[7]和在此基礎(chǔ)改進(jìn)的COPRA算法[8]等；基于分級聚類的算法主要包括基于鄰居節(jié)點(diǎn)相異性的社團(tuán)發(fā)現(xiàn)新算法[9]和基于多層節(jié)點(diǎn)相似度的社區(qū)發(fā)現(xiàn)算法[10]等。目前，網(wǎng)絡(luò)社團(tuán)檢測算法仍然存在諸多問題，如節(jié)點(diǎn)相異性構(gòu)造、相異性指標(biāo)的選擇、算法劃分精確度低、時間復(fù)雜度高等問題。針對節(jié)點(diǎn)相異構(gòu)造和算法精確度低，本文定義了3種相異性指標(biāo)，并結(jié)合相異性指標(biāo)，提出基于節(jié)點(diǎn)相異性指標(biāo)的網(wǎng)絡(luò)社團(tuán)檢測算法。

1 相異性指標(biāo)定義及算法描述

1.1 相異性指標(biāo)定義

(1)

圖1 節(jié)點(diǎn)鄰居集合關(guān)系的文氏圖

式中，Γi-j表示節(jié)點(diǎn)i的鄰居但不屬于節(jié)點(diǎn)j的鄰居的集合,Γi表示節(jié)點(diǎn)i的鄰居集合，|Γi∪Γj|表示節(jié)點(diǎn)i和節(jié)點(diǎn)j所有鄰居節(jié)點(diǎn)的個數(shù)。節(jié)點(diǎn)鄰居集合關(guān)系如圖1所示。

(2)

(3)

式中，Γij=Γi-j+Γj-i=(Γi∪Γj)-(Γi∩Γj)，k(z)表示節(jié)點(diǎn)z的度，a∈Γ(i)，b∈Γ(j)，k(a)+k(b)表示節(jié)點(diǎn)i和j的所有鄰居的度之和，m表示網(wǎng)絡(luò)的邊數(shù)，2m代表網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度之和，節(jié)點(diǎn)相異性越大越可能出現(xiàn)在不同社團(tuán)中。2-鄰居相異性指標(biāo)是衡量A和B互不認(rèn)識對方朋友的朋友人數(shù)在A和B兩層朋友中所占的比例，全局2-鄰居相異性指標(biāo)是衡量A和B互不認(rèn)識對方朋友的朋友人數(shù)在整個朋友關(guān)系網(wǎng)中所占的比例。

1.2 評價指標(biāo)模塊度Q和標(biāo)準(zhǔn)化互信息NMI

模塊度是衡量社團(tuán)檢測算法劃分結(jié)果的一個指標(biāo)，通常模塊度的值越大劃分出的結(jié)果越好。模塊度是指網(wǎng)絡(luò)中連接社團(tuán)內(nèi)部節(jié)點(diǎn)的邊所占的比例與另外一個隨機(jī)網(wǎng)絡(luò)中連接社團(tuán)內(nèi)部節(jié)點(diǎn)的邊所占比例的期望值相減得到的差值[11]，其定義如下：

(4)

式中，m表示網(wǎng)絡(luò)的邊數(shù)，aij表示網(wǎng)絡(luò)鄰接矩陣中的元素，當(dāng)i和j相連時aij=1，否則為0，δ表示隸屬函數(shù)，當(dāng)節(jié)點(diǎn)i和j屬于同一個社團(tuán)時δij=1，否則為0。Q的取值范圍為[-0.5,1.0)，在實(shí)際應(yīng)用中Q的最大值一般為0.3～0.7。

標(biāo)準(zhǔn)化互信息(Normalized Mutual Information，NMI)是度量社團(tuán)檢測結(jié)果與真實(shí)社團(tuán)結(jié)果相近程度的一個重要衡量指標(biāo)[12]，其定義如下：

(5)

式中，E表示實(shí)際社團(tuán)情況，F(xiàn)表示算法檢測的社團(tuán)情況，CE和CF分別表示E和F的真實(shí)社團(tuán)數(shù)目，mij表示混亂矩陣M中的元素，mi·表示混亂矩陣中第i行的總和，m·j表示混亂矩陣中第j列的總和，n表示網(wǎng)絡(luò)的節(jié)點(diǎn)個數(shù)，NMI的取值范圍為0～1，其值越大表明劃分越準(zhǔn)確。

1.3 算法描述

把網(wǎng)絡(luò)中連通分支個數(shù)視為社團(tuán)個數(shù)，初始狀態(tài)下的網(wǎng)絡(luò)視為一個社團(tuán)，基于節(jié)點(diǎn)相異性指標(biāo)的網(wǎng)絡(luò)社團(tuán)檢測算法流程如下：

(1)計算網(wǎng)絡(luò)中有連邊的節(jié)點(diǎn)間相異性值，找到相異性值最大的2個節(jié)點(diǎn)，刪除兩者之間的邊；

(2)判斷社團(tuán)的個數(shù)是否增加，若有增加則計算出此時網(wǎng)絡(luò)的模塊度；

(3)重復(fù)步驟1和步驟2直到網(wǎng)絡(luò)中所有的邊都被刪除；

(4)找到最大模塊度對應(yīng)的劃分結(jié)果，即為網(wǎng)絡(luò)的最佳社團(tuán)結(jié)構(gòu)。

算法開始時，計算有連邊的節(jié)點(diǎn)間相異性值，對于有m條邊的網(wǎng)絡(luò)來說，時間復(fù)雜度為O(m)，刪除相異性值最高的2節(jié)點(diǎn)之間的邊(可能不止1條)，再計算網(wǎng)絡(luò)中剩余所有邊2節(jié)點(diǎn)間的相異性值，直到所有的邊都被刪除，所以，總的時間復(fù)雜度不會超過O(m2)。

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

2.1 計算機(jī)模擬網(wǎng)絡(luò)與真實(shí)網(wǎng)絡(luò)

(1)LFR基準(zhǔn)網(wǎng)絡(luò)[13]是目前復(fù)雜網(wǎng)絡(luò)領(lǐng)域中社團(tuán)檢測常用的人工模擬計算機(jī)生成網(wǎng)絡(luò)。本文采用的基準(zhǔn)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為128，節(jié)點(diǎn)的平均度為16，節(jié)點(diǎn)的最大度為16，最大社團(tuán)和最小社團(tuán)包含的節(jié)點(diǎn)數(shù)均為32，混合參數(shù)為0.1，網(wǎng)絡(luò)的社團(tuán)個數(shù)為4。

(2)Zachary網(wǎng)絡(luò)是測驗(yàn)社團(tuán)檢測算法最為常用的典型實(shí)際網(wǎng)絡(luò)，由W.Zachary對美國一所大學(xué)空手道俱樂部進(jìn)行2年觀測后構(gòu)建的，包含34個節(jié)點(diǎn)，78條邊，每個節(jié)點(diǎn)代表1個俱樂部成員，邊表示2個成員間有交往關(guān)系。由于某種原因，該網(wǎng)絡(luò)分成2個小型俱樂部。

(3)Football網(wǎng)絡(luò)由M.E.J.Newman和M.Girvan收集的美國高校足球聯(lián)賽數(shù)據(jù)構(gòu)建的一個真實(shí)復(fù)雜網(wǎng)絡(luò)，包含115個節(jié)點(diǎn)，613條邊，每個節(jié)點(diǎn)代表1支高校球隊，節(jié)點(diǎn)之間的邊表示2支球隊至少有過1場比賽，全部的球隊分為12個聯(lián)盟。

2.2 社團(tuán)檢測過程示例

以全局2-鄰居相異性指標(biāo)為例來說明1個由15個節(jié)點(diǎn)、34條邊組成的小型網(wǎng)絡(luò)的社團(tuán)檢測過程。根據(jù)1.3節(jié)的算法流程計算全局2-鄰居相異性指標(biāo)。計算網(wǎng)絡(luò)中34條邊對應(yīng)節(jié)點(diǎn)間相異性值，得到網(wǎng)絡(luò)中節(jié)點(diǎn)8和11間的相異性值在整個網(wǎng)絡(luò)中最大，為0.632 4，將8和11之間的邊刪除，此時社團(tuán)的個數(shù)并未增加；計算剩余有連邊的節(jié)點(diǎn)間相異性值，通過比較相異性值得到節(jié)3和10之間的相異性最大，為0.530 3，刪除3和10之間的邊，得到2個社團(tuán)，分別為1,2,3,4,5,6,7,8,9和10,11,12,13,14,15，模塊度為0.439 4；再計算余下有邊相連節(jié)點(diǎn)間的相異性值，通過計算和比較得到節(jié)點(diǎn)2和5之間的相異性最大，為0.390 6，刪除節(jié)點(diǎn)2和5之間的邊，得到3個社團(tuán)，分別為1,2,3,4和5,6,7,8,9及10,11,12,13,14,15，模塊度為0.543 3；繼續(xù)計算，直到網(wǎng)絡(luò)中所有邊都斷開。最后，通過比較不同劃分下的模塊度，得到當(dāng)社團(tuán)數(shù)為3時的模塊度最大，對應(yīng)的劃分結(jié)果如圖2所示。

圖2 計算機(jī)模擬的小型網(wǎng)絡(luò)

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

在LFR基準(zhǔn)網(wǎng)絡(luò)、Zachary網(wǎng)絡(luò)和Football網(wǎng)絡(luò)中，使用本文算法，得到3種指標(biāo)在不同網(wǎng)絡(luò)中的模塊度隨社團(tuán)個數(shù)的變化情況如圖3所示。圖3中，指標(biāo)1、指標(biāo)2、指標(biāo)3分別代表單層鄰居相異性、2-鄰居相異性和全局2-鄰居相異性。

圖3 3種指標(biāo)在不同網(wǎng)絡(luò)中的模塊度變化情況

從圖3可以看出：在LFR基準(zhǔn)網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)被劃分為4個社團(tuán)時，3種相異性指標(biāo)的模塊度均達(dá)到最大，為0.650 4，這與LFR基準(zhǔn)網(wǎng)絡(luò)有4個社團(tuán)的情況相符。在football網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)被劃分為11個社團(tuán)時，單層鄰居相異性和2-鄰居相異性指標(biāo)的模塊度值達(dá)到最大，分別為0.581 3和0.600 2；當(dāng)網(wǎng)絡(luò)被劃分為12個社團(tuán)時，全局2-鄰居相異性指標(biāo)的模塊度值達(dá)到最大，為0.582 1，雖然說使用2-鄰居相異性指標(biāo)得到的最大模塊度在3個指標(biāo)中的值最大，但Football網(wǎng)絡(luò)的真實(shí)情況是12個社團(tuán)，所以說三者中全局2-鄰居相異性指標(biāo)更符合真實(shí)情況。在Zachary網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)被劃分15個社團(tuán)時，單層鄰居相異性指標(biāo)的模塊度值達(dá)到最大，這與Zachary網(wǎng)絡(luò)2個社團(tuán)的真實(shí)情況相差較大；當(dāng)網(wǎng)絡(luò)被劃分為5個社團(tuán)時，2-鄰居相異性指標(biāo)的模塊度值達(dá)到最大，為0.349 0，當(dāng)網(wǎng)絡(luò)被劃分為2個社團(tuán)時模塊度值接近于0；對于全局2-鄰居相異性指標(biāo)，當(dāng)網(wǎng)絡(luò)被劃分為2個社團(tuán)時模塊度為0.371 8。從3個相異性指標(biāo)在模擬網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)劃分的社團(tuán)情況來看，采用全局2-鄰居相異性指標(biāo)檢測出的社團(tuán)個數(shù)與真實(shí)情況吻合度最高，所以，下面實(shí)驗(yàn)結(jié)果中，無特殊說明，得到的結(jié)果是均采用全局2-鄰居相異性指標(biāo)。

將本文算法應(yīng)用到LFR基準(zhǔn)網(wǎng)絡(luò)中，網(wǎng)絡(luò)被劃分為4個社團(tuán)，具體劃分情況如圖4所示。

圖4 LFR基準(zhǔn)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)圖

將本文算法應(yīng)用到Zachary網(wǎng)絡(luò)中，網(wǎng)絡(luò)被劃分為2個社團(tuán)，與真實(shí)情況對比發(fā)現(xiàn)：只有節(jié)點(diǎn)10被錯誤劃分，具體劃分情況如圖5所示。

圖5 Zachary網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)圖

將本文算法應(yīng)用到Football網(wǎng)絡(luò)中，網(wǎng)絡(luò)被劃分為12個社團(tuán)，具體劃分情況如圖6所示。

圖6 Football網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)圖

社團(tuán)劃分的準(zhǔn)確程度采用的評價指標(biāo)是標(biāo)準(zhǔn)化互信息NMI，本文算法與GN算法、FastNewman算法在LFR基準(zhǔn)網(wǎng)絡(luò)、Zachary網(wǎng)絡(luò)和Football網(wǎng)絡(luò)中劃分結(jié)果的NMI值如表1所示。

表1 不同算法劃分的NMI值比較

從表1可以看出：在LFR基準(zhǔn)網(wǎng)絡(luò)中，3種算法的NMI值均為1.000，說明劃分結(jié)果與真實(shí)的社團(tuán)情況一致；在Football網(wǎng)絡(luò)中，本文算法的NMI值高于GN算法和FastNewman算法，在Zachary網(wǎng)絡(luò)中，本文算法的NMI值高于FastNewman算法。綜上，本文算法的劃分準(zhǔn)確度更高一些。

3 結(jié)束語

本文定義了3種相異性指標(biāo)：單層鄰居相異性、2-鄰居相異性和全局2-鄰居相異性，并結(jié)合這3種相異性提出了基于節(jié)點(diǎn)相異性指標(biāo)的網(wǎng)絡(luò)社團(tuán)檢測算法，通過實(shí)驗(yàn)對比發(fā)現(xiàn)采用全局2-鄰居相異性指標(biāo)的劃分結(jié)果最好，本文算法的準(zhǔn)確度優(yōu)于GN算法和Fast Newman算法。但是，本文實(shí)驗(yàn)中所選用的都是非重疊社團(tuán)結(jié)構(gòu)網(wǎng)絡(luò)，后續(xù)研究將嘗試把本文算法應(yīng)用到重疊社團(tuán)網(wǎng)絡(luò)中。