劉亞東，覃 森

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

0 引 言

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

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

1 相異性指標定義及算法描述

1.1 相異性指標定義

(1)

圖1 節(jié)點鄰居集合關系的文氏圖

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

(2)

(3)

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

1.2 評價指標模塊度Q和標準化互信息NMI

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

(4)

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

標準化互信息(Normalized Mutual Information，NMI)是度量社團檢測結果與真實社團結果相近程度的一個重要衡量指標[12]，其定義如下：

(5)

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

1.3 算法描述

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

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

(2)判斷社團的個數(shù)是否增加，若有增加則計算出此時網絡的模塊度；

(3)重復步驟1和步驟2直到網絡中所有的邊都被刪除；

(4)找到最大模塊度對應的劃分結果，即為網絡的最佳社團結構。

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

2 實驗結果與分析

2.1 計算機模擬網絡與真實網絡

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

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

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

2.2 社團檢測過程示例

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

圖2 計算機模擬的小型網絡

2.3 實驗結果分析

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

圖3 3種指標在不同網絡中的模塊度變化情況

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

將本文算法應用到LFR基準網絡中，網絡被劃分為4個社團，具體劃分情況如圖4所示。

圖4 LFR基準網絡社團結構圖

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

圖5 Zachary網絡社團結構圖

將本文算法應用到Football網絡中，網絡被劃分為12個社團，具體劃分情況如圖6所示。

圖6 Football網絡社團結構圖

社團劃分的準確程度采用的評價指標是標準化互信息NMI，本文算法與GN算法、FastNewman算法在LFR基準網絡、Zachary網絡和Football網絡中劃分結果的NMI值如表1所示。

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

從表1可以看出：在LFR基準網絡中，3種算法的NMI值均為1.000，說明劃分結果與真實的社團情況一致；在Football網絡中，本文算法的NMI值高于GN算法和FastNewman算法，在Zachary網絡中，本文算法的NMI值高于FastNewman算法。綜上，本文算法的劃分準確度更高一些。

3 結束語

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