安曉丹 張曉琴 曹付元

1(山西大學數(shù)學科學學院 山西 太原 030006)2(山西財經大學統(tǒng)計學院 山西 太原 030006)3(山西大學計算機與信息技術學院 山西 太原 030006)

0 引 言

自然界有許多復雜網絡，如社會網絡、技術網絡和生物網絡等。這些網絡大部分都會呈現(xiàn)出社區(qū)結構，即社區(qū)內部連邊分布較密集，社區(qū)間的連邊分布較分散。社區(qū)發(fā)現(xiàn)對挖掘復雜網絡的結構、預測對象的行為特征、提取網絡的有用信息具有重要的研究意義。

網絡的一個重要類型是二分網絡，現(xiàn)實中許多真實的二分網絡，例如用戶-產品購買關系網[1-2]、新陳代謝網絡[3]和疾病-基因網絡[4]等。二分網絡可以體現(xiàn)出一些深層網絡結構特點，對網絡結構特性的研究具有非常重要的作用[5]。

目前，主要有兩種二分網絡社區(qū)劃分方法，一種是將其轉化到單模網絡上進行聚類、分析。如Melamed D[6]的雙映射方法，但是這些方法會損失大量的網絡信息。為降低映射過程的信息損失，張嬙嬙等[7]對兩個網絡的資源分布矩陣聚類分析。另外一種是直接在二分網絡上進行劃分，這些方法可以較有效地保留原網絡大部分信息。如Barber等[8]提出的BRIM算法。周旸等[9]針對傳統(tǒng)譜方法在二分網絡社區(qū)發(fā)現(xiàn)中的缺點，提出了基于最優(yōu)特征向量的譜二分社團檢測方法。Tang等[10]將譜聚類算法的思想推廣到二分網絡，提出了聯(lián)合譜聚類算法。鄒凌君等[11]通過構建廣義后綴樹，提出了一種可以發(fā)現(xiàn)重疊社區(qū)的社區(qū)發(fā)現(xiàn)方法。Lehmann等[12]將K-clique算法[13]推廣到了二分網絡，提出了bi-clique二分網絡社區(qū)發(fā)現(xiàn)算法。bi-clique算法的主要優(yōu)點是可以發(fā)現(xiàn)重疊社區(qū)和不同連接密度的社區(qū)；缺點是只挖掘了那些密度超過指定閾值的二分網絡[14]。

為了度量社區(qū)劃分結果，Newman[15]提出了適合單模網絡的模塊度指標，因為該模塊度依賴于零模型，因此在一些網絡上存在分辨率限制。在二分網絡上，Guimera等[16]、Barber[8]和Murata[17]基于Newman的單模網絡模塊度，提出了二分網絡的模塊度。雖然二分網絡的模塊度受到廣泛應用，但Xu等[18]和Li等[19]指出以上模塊度也存在一定的分辨率限制。

為緩解模塊度在某些網絡上的分辨率限制和算法精度不高的問題，本文提出一種二分網絡評價指標。同時，利用密度傳播和最優(yōu)化評價指標，提出一種可自主識別社區(qū)的二分網絡發(fā)現(xiàn)算法，并通過實驗驗證該算法的有效性。

1 二分網絡的相關介紹

1.1 二分網絡的概念

二分網絡有兩種類型的節(jié)點，且只有不同類型節(jié)點間有連邊。二分網絡可以表示為簡單無向圖G(X,Y,E)。X、Y分別表示二分網絡的兩類節(jié)點，E表示X和Y節(jié)點間的連邊。

設X型和Y型節(jié)點個數(shù)分別為m和n，由于X(Y)型節(jié)點間沒有連邊，因此二分網絡的鄰接矩陣可以表示為：

式中：

0m×m、0n×n分別為m階、n階零矩陣；

1.2 二分網絡的互信息指標

二分網絡的互信息指標[16]被用來比較兩種社區(qū)劃分結果的一致性，假設有兩種社區(qū)劃分C和D，其互信息定義如下：

式中:

M表示網絡總連邊數(shù)；

NC和ND分別為C和D劃分的社區(qū)個數(shù)；

若劃分C與D完全一致時，ICD=1；

若劃分C與D不相關時，ICD=0。

1.3 Murata的模塊度

假設網絡的總邊數(shù)為M，Vl和Vm分別是X和Y型節(jié)點的社區(qū)(Vl∈VX,Vm∈VY)，鄰接矩陣A中的元素為aij。連接Vl和Vm的邊與網絡總邊數(shù)的比可表示為：

進一步定義矩陣B，B中的元素由elm組成，那么矩陣的第l行所有元素和bl為：

Murata的模塊度定義如下：

1.4 Barber的二分網絡模塊度

鑒于二分網絡同類節(jié)點間沒有連邊的特點，Barber將節(jié)點xi與xj的連邊概率矩陣定義如下:

式中：

1.5 BRIM算法

BRIM算法是Barber采用遞歸的方法得到的社區(qū)劃分方法，具體如下：

定義指標矩陣：

式中:R、T分別為m×c、n×c的矩陣，c為社區(qū)個數(shù)。那么，Barber的模塊度可寫為：

1.6 邊集聚算法

Zhang等[20]對聚類系數(shù)做了修正，定義了如下的邊集聚系數(shù)：

式中：m是X型節(jié)點i的鄰居，n是Y型節(jié)點j的鄰居。如果鄰居m和n相互連接，則qijmn=1，否則為0。θijmn與qijmn相反。km是節(jié)點m的度，kn是節(jié)點n的度，ki是節(jié)點i的度，kj是節(jié)點j的度。這個算法如同GN算法[21-22]，計算每條邊的集聚系數(shù)，但是去掉集聚系數(shù)最小的邊。

1.7 資源分布算法

吳亞晶等[23]提出的資源分布算法，通過構建二分網絡的資源分布矩陣，然后對資源分布矩陣進行K均值聚類，并采用F統(tǒng)計量確定最終聚類結果。

2 連邊密度傳播算法

以往二分網絡的模塊度是從社區(qū)中整體連邊角度構造，本文由社區(qū)內節(jié)點的連邊角度，考慮節(jié)點的連邊密度，將提出一種社區(qū)的平均密度評價指標。并通過密度傳播和最優(yōu)化平均密度，得到二分網絡的社區(qū)發(fā)現(xiàn)算法。

2.1 社區(qū)的平均密度

對給定二分網絡進行社區(qū)劃分，使得社區(qū)內部連接相對較密集，社區(qū)間的連接相對較分散。若社區(qū)中的節(jié)點與其所在社區(qū)內的節(jié)點連邊越多，則與其他社區(qū)節(jié)點的連邊越少，即這個二分網絡的社區(qū)結構越好。依據(jù)此思想本文定義了二分網絡的平均密度，為給出此平均密度的定義，先定義社區(qū)內節(jié)點的連邊密度。

(1)

式中：

ki為X型節(jié)點xi的度；

j為Y型節(jié)點下標；

p為二分網絡中Y型節(jié)點的總數(shù)；

yj為Y型節(jié)點中的節(jié)點；

aij為鄰接矩陣A中的元素；

同理，對于第S個社區(qū)內Y型節(jié)點yj的連邊密度定義為節(jié)點yj在S社區(qū)內的連邊比例，具體定義為：

(2)

式中：q為二分網絡中X型節(jié)點的總數(shù)；i為X型節(jié)點下標。

社區(qū)S中節(jié)點的平均連邊密度定義為：

(3)

式中：|XS|表示社區(qū)S中X型節(jié)點個數(shù)；|YS|表示社區(qū)S中Y型節(jié)點個數(shù)。式(3)可簡寫為：

式中：i為社區(qū)中第i個節(jié)點；為與i節(jié)點相對的另一種類型節(jié)點。

二分網絡社區(qū)的平均密度定義為K個社區(qū)的平均密度，具體定義為：

(4)

式中：K表示社區(qū)劃分個數(shù)。

由式(4)可知，社區(qū)的平均密度越大，其社區(qū)內部節(jié)點連接越緊密，那么，社區(qū)劃分效果也相對越好。因此，可以利用社區(qū)的平均密度刻畫社區(qū)劃分結果的好壞。當社區(qū)中的節(jié)點連邊均與社區(qū)內部的節(jié)點連邊時，社區(qū)的平均密度D達到最大值1，此時的劃分社區(qū)結果最好；當社區(qū)內的節(jié)點的連邊均與社區(qū)外的節(jié)點連邊時，社區(qū)的平均密度D達到最小值0，此時的社區(qū)結構最差。

2.2 算法設計

利用社區(qū)的平均密度劃分社區(qū)，可通過優(yōu)化社區(qū)平均密度的方法進行社區(qū)發(fā)現(xiàn)。本文提出的連邊密度傳播算法(EDPR)，首先，初始化其中一類節(jié)點的社區(qū)；然后，將節(jié)點密度大于參數(shù)θ的另一類節(jié)點加入到社區(qū)中；最后，通過節(jié)點連接密度D(xi)和D(yj)不斷更新節(jié)點標簽，使社區(qū)的平均密度D達到最大，即可獲得二分網絡的最終社區(qū)劃分結果。具體算法如下：

輸入：二分網絡G(X,Y,E)的鄰接矩陣A和參數(shù)θ。

輸出：二分網絡社區(qū)發(fā)現(xiàn)最終結果F1,F2,…,Fk。

Step1初始化X型節(jié)點社區(qū)，將X型節(jié)點中節(jié)點xi分別分配到一個社區(qū)中，令xi∈Gi，t=0，D=0；

Step2將Y型節(jié)點yj分配到與其有連邊的Gi社區(qū)中；

Step3根據(jù)式(1)重新更新X型節(jié)點的社區(qū)，將節(jié)點xi分配到使得D(xi)>θ的社區(qū)中，并更新為Gi，且將X型節(jié)點從原先所屬的社區(qū)中刪去；

Step4由式(2)分別計算Y類型節(jié)點yj在社區(qū)Gi中的節(jié)點密度D(yj)，并將節(jié)點yj分配到使得式(2)最大的Gi社區(qū)中；

Step5根據(jù)式(4)計算社區(qū)的平均密度D，若D(t+1)

Step6迭代更新，直到二分網絡的平均密度D最大，即為社區(qū)劃分的最終結果F1,F2,…,Fk。

算法的Step 3為了確保X型節(jié)點社區(qū)更新，從第二次迭代開始變?yōu)楦鶕?jù)式(1)尋找使得D(xi)最大的社區(qū)Gi，并更新xi的標簽。

2.3 分辨率限制的證明

雖然Barber和Murata的模塊度得到了廣泛應用，但是這兩個模塊度指標存在一些分辨率限制。本文提出的二分網絡的平均密度D能夠克服模塊度在一個完全圖上的分辨率限制，主要通過一個具體的實例說明。

如圖1所示，二分網絡是由一個完全圖Kn,n組成，該完全圖是由n個X型節(jié)點和n個Y型節(jié)點(n≥2)和n2條邊組成。這個二分網絡中共有2n個節(jié)點和n2條邊。

(a) (b)圖1 由完全圖Kn,n組成的二分網絡

考慮如下兩個社區(qū)劃分結果：

P0：整個二分網絡視為一個社區(qū)，如圖1(a)所示。

P1：將二分網絡劃分為兩個社區(qū)C1和C2，社區(qū)C1中X型節(jié)點和Y型節(jié)點均有n1個，社區(qū)C2中X型節(jié)點和Y型節(jié)點均有n2個,n1+n2=n。如圖1(b)所示。

由圖1可以很明顯得出，劃分P0要比P1好，然而，對于以上兩個劃分結果，用Barber和Murata的模塊度計算求得的模塊度值均為0[18]。因此利用Barber和Murata的模塊度無法評價這兩種劃分的好壞。

本文提出的二分網絡的平均密度D，對P0和P1兩個劃分評價的計算：

3 實驗結果與分析

在人工網絡和真實網絡上驗證EDPR算法的性能，同三種較經典的算法(BRIM算法、邊集聚系數(shù)算法和資源分布算法)比較模塊度和社區(qū)平均密度值。

3.1 人工網絡實驗

為檢驗EDPR算法在給定網絡結構下，社區(qū)劃分的準確性，特在8個人工二分網絡上進行測試。其中每個網絡中節(jié)點的度均為k=64，k=kin+kout,kin表示節(jié)點與社區(qū)中節(jié)點連邊個數(shù)，kout=0,1,…,7表示節(jié)點與其他社區(qū)節(jié)點的連邊數(shù)。具體的網絡信息如表1所示。

表1 構建的人工網絡信息

分別在人工二分網絡上，應用EDPR算法聚類，并與BRIM算法、邊集聚系數(shù)算法和資源分布算法的聚類結果比較，互信息指標作為評價指標。如圖2所示，EDPR算法總能準確自主地劃分這8個人工二分網絡的社區(qū)。由于EDPR算法始終尋找使得節(jié)點連邊數(shù)最大的社區(qū)，所以在每次實驗中，EDPR算法總能精確的將節(jié)點分配到與其連接最緊密的社區(qū)中，求得互信息指標為1，故劃分準確性均為1。EDPR算法不僅準確性比其他三種算法都高，而且可以自主地確定社區(qū)劃分個數(shù)。其中，邊集聚系數(shù)算法在人工網絡數(shù)據(jù)集上的劃分準確性出現(xiàn)了較大的波動，且在kout=4時，正確率僅為0.533 8。資源分布算法和BRIM算法在kout=0,1,…,7的網絡上雖無明顯波動，但其正確率也不及EDPR算法。

圖2 四種算法分類正確率比較

3.2 真實網絡上的實驗

本節(jié)分別在3個真實數(shù)據(jù)：Moreno Crime(http://konect.uni-koblenz.de/networks/moreno_crime)、Southern Women Data[24]和Scotland Data[25]上驗證EDPR算法的準確度。并與3種經典算法—BRIM、邊集聚系數(shù)算法、資源分布算法比較模塊度和社區(qū)平均密度值。

實驗1：

Southern Women Data是由Divas等收集的1930年的密西西比州，由18位婦女和14個活動組成的數(shù)據(jù)，被廣泛地應用于對二分網絡社區(qū)發(fā)現(xiàn)算法準確性的檢測中。

社區(qū)分布圖如圖3所示，將數(shù)據(jù)集中的婦女用圓形表示，編號為1～18，活動用矩形表示編號為1～14，圖中的連邊表示婦女參加了相應的活動。Southern Women Data數(shù)據(jù)集上，EDPR算法將其劃分為2個社區(qū)，其中，第一類為活動{1,2,3,4,5,6,7,8}與婦女{1,2,3,4,5,6,7,8,9}，第二類為活動{9,10,11,12,13,14}與婦女{10,11,12,13,14,15,16,17,18}。計算得此劃分模塊度和社區(qū)平均密度值分別為0.333 2和0.870 1。圖3中，不同的灰度表示不同的社區(qū)。

圖3 在數(shù)據(jù)集Southern Women上的社區(qū)劃分

在Southern Women數(shù)據(jù)集上，分別采用邊集聚系數(shù)、BRIM和資源分布算法劃分社區(qū)，并計算對應的模塊度和社區(qū)平均密度值。進行多次實驗，取平均值同EDPR比較，比較結果如表2所示。

由表2可知，在Southern Women數(shù)據(jù)集上，由EDPR算法求得的模塊度和社區(qū)平均密度值，都比其他三種算法求得的值略高，表明所劃分的社區(qū)結構更加明顯，劃分準確性也相對較高。

實驗2：

Moreno Crime數(shù)據(jù)集，是由551起刑事案件和與刑事案件有關的829名人員，1 476條連邊構成。網絡中一類節(jié)點表示案件中的一個受害者、目擊者或嫌疑人，另一類節(jié)點是相應的案件。

在Moreno Crime數(shù)據(jù)集上，EDPR將其分為185個社區(qū)，例如人員{1,93,694,756}與案件{1,2,3,4}為一個社區(qū)；人員{77,205}與案件{98,127}分為一個社區(qū)；案件{108,109,180,279,593,709,814}與人員{163,164,165,166,167,168}為一個社區(qū)；相應的模塊度和社區(qū)平均密度值分別為0.971 0和0.907 7。

分別采用邊集聚系數(shù)、資源分布和BRIM 3種算法劃分社區(qū)，同時計算3種算法對應的模塊度和社區(qū)平均密度。比較結果如表3所示。

由表3可知，在Moreno Crime數(shù)據(jù)集上，EDPR算法的精確度高于三種經典算法，能夠較好地識別社區(qū)。

實驗3:

Scotland Data是一個較典型的二分網絡數(shù)據(jù)集，該數(shù)據(jù)集描述了蘇格蘭早期108家連鎖企業(yè)和136位股東之間的任職情況。將該數(shù)據(jù)表示成一個二分網絡，網絡中的兩類節(jié)點代表公司和股東，節(jié)點間連邊表示該股東在公司任職。

在Scotland Data數(shù)據(jù)集上，EDPR將其分為25個社區(qū)，例如公司{11,28}與股東{2,48,59,60}為一個社區(qū)；公司{63,93,103,104}與股東{3,16,36,131}分為一個社區(qū)；公司{78,66,95}與股東{82,85,132,120,121}為一個社區(qū)；相應模塊度和社區(qū)平均密度值分別為0.627 0和0.721 2。

分別采用邊集聚系數(shù)、資源分布2種算法劃分社區(qū)，同時計算2種算法對應的模塊度和社區(qū)平均密度值。進行多次實驗，取其最大的模塊度值同EDPR比較。在Scotland Data數(shù)據(jù)集上模塊度和社區(qū)平均密度值比較結果如表4所示。

表4 Scotland Data數(shù)據(jù)集上的比較

由表4可知，在Scotland Data數(shù)據(jù)集上，EDPR算法求得的模塊度和社區(qū)平均密度值更大，表現(xiàn)更佳。說明EDPR算法可較好地挖掘社區(qū)結構，社區(qū)劃分準確性相對更高。

4 結 語

本文從社區(qū)的節(jié)點出發(fā)，構造了節(jié)點的連邊密度和社區(qū)的平均密度，同時驗證了社區(qū)的平均密度作為評價指標，可克服模塊度在特定網絡上的分辨率限制。并提出了一種二分網絡發(fā)現(xiàn)算法——連邊密度傳播算法(EDPR)，通過實驗驗證該算法可較好地發(fā)現(xiàn)社區(qū)，劃分準確度也較高。希望在今后可以對多模數(shù)據(jù)做進一步研究。