代婷婷，董延壽，韓 艷

（昭通學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，云南昭通 657000）

一個(gè)是1998年Watts和Strogatz發(fā)表在Nature上的文章〔1〕揭示了復(fù)雜網(wǎng)絡(luò)的小世界特性；另一個(gè)是1999年Barabási和Albert發(fā)表在Science上的文章〔2〕揭示了復(fù)雜網(wǎng)絡(luò)的無(wú)標(biāo)度性質(zhì)，認(rèn)為網(wǎng)絡(luò)的這種性質(zhì)緣于兩個(gè)缺一不可的演化要素，并據(jù)此提出了一個(gè)網(wǎng)絡(luò)模型，傳統(tǒng)的網(wǎng)絡(luò)模型是建立在隨機(jī)圖基礎(chǔ)上的〔3〕。

對(duì)于復(fù)雜網(wǎng)絡(luò)的研究主要是研究其社團(tuán)結(jié)構(gòu)，關(guān)于復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)提取有很多的算法。Girvan 和 Newman〔4〕在2002年提出了一種通過(guò)邊移除按層次分解網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)方法（GN）。此項(xiàng)研究工作被認(rèn)為是現(xiàn)代社團(tuán)結(jié)構(gòu)研究的開(kāi)創(chuàng)性工作，各研究領(lǐng)域的研究員對(duì)此有著廣泛的興趣。GN算法尋找最可能處于社團(tuán)之間的邊，通過(guò)不斷地將這些邊移除得到網(wǎng)絡(luò)的層次劃分。Radicchi等〔5〕針對(duì)GN算法進(jìn)行了一些改善，提出了一個(gè)新的GN自包含算法。

1 算法

1.1 連續(xù)神經(jīng)網(wǎng)絡(luò)求解矩陣的特征值及特征向量考慮微分方程

其中，A是一個(gè)n×n的實(shí)對(duì)稱(chēng)矩陣，可以將其視為神經(jīng)網(wǎng)絡(luò)的連接權(quán)強(qiáng)度，X∈Rn，視為神經(jīng)網(wǎng)絡(luò)的狀態(tài)，那么方程（1）就描述了一類(lèi)連續(xù)型的全反饋人工神經(jīng)網(wǎng)絡(luò)。Radicchi等〔5〕給出了一種電路模擬方法，當(dāng)A為對(duì)稱(chēng)正定矩陣時(shí)，OJA等〔6〕根據(jù)神經(jīng)網(wǎng)絡(luò)的Hebbian規(guī)則，將方程（1）作為一種無(wú)教師指導(dǎo)的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)過(guò)程，研究了輸入空間提取特征主元的問(wèn)題，證明了方程（1）從任意初始值出發(fā)的解都收斂于A的最大特征值對(duì)應(yīng)的特征向量。這個(gè)可以由下面的定理保證。

定理1假設(shè)A的最大特征值λ＞0，則式（1）的從任意初值X(0)Rn出發(fā)的解均收斂于A的最大特征值λ對(duì)應(yīng)的特征向量〔7〕。

該定理給出了一種新的求解矩陣特征值和特征向量的方法。

1.2 社團(tuán)提取問(wèn)題中的模塊度函數(shù)假定網(wǎng)絡(luò)包含有n個(gè)節(jié)點(diǎn)，對(duì)于一個(gè)網(wǎng)絡(luò)進(jìn)行特殊的劃分，即將網(wǎng)絡(luò)劃分為兩個(gè)組，讓si=1表示節(jié)點(diǎn)i屬于第一組，當(dāng)si=-1時(shí)，表示節(jié)點(diǎn)i屬于第二組。將節(jié)點(diǎn)i和節(jié)點(diǎn)j之間邊的連接數(shù)目表示為Aij（其值取0和1）。若網(wǎng)絡(luò)中有重邊存在，則Aij可以取比1大的值。Aij就是所謂的網(wǎng)絡(luò)鄰接矩陣中的元素，若節(jié)點(diǎn)i和節(jié)點(diǎn)j之間邊的連接是隨機(jī)的，則均值為kikj/2m，ki表示節(jié)點(diǎn)i的度，i=1,2,...,n，m=表示網(wǎng)絡(luò)中邊的總數(shù)目，則文獻(xiàn)〔7〕中的社團(tuán)提取問(wèn)題中模塊度函數(shù)Q可定義為

這里s表示向量，其第i個(gè)元素為si，i=1,2,...,n是個(gè)常數(shù)。而對(duì)稱(chēng)矩陣B稱(chēng)為模塊度矩陣，其元素為：

利用（3）式將矩陣B進(jìn)行化簡(jiǎn)發(fā)現(xiàn)它的行和與列和都為零，因此矩陣B總有特征向量(1,1,1,...)，其對(duì)應(yīng)的特征值為0，這是拉普拉斯圖矩陣的性質(zhì)〔7〕，也是圖分割的基礎(chǔ)。

1.3 連續(xù)神經(jīng)網(wǎng)絡(luò)提取復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的算法（CNN） Newman〔7〕將模塊度函數(shù)Q定義為（2）式，模塊度矩陣B定義為（3）式，若考慮復(fù)雜網(wǎng)絡(luò)為無(wú)向網(wǎng)絡(luò)，則鄰接矩陣A是一個(gè)實(shí)對(duì)稱(chēng)矩陣，從（3）式可知模塊度矩陣B也是一個(gè)實(shí)對(duì)稱(chēng)矩陣，所以根據(jù)Fortunato等〔8〕的闡述，可以利用方程（1）的神經(jīng)網(wǎng)絡(luò)系統(tǒng)求解出模塊度矩陣B的最大特征值對(duì)應(yīng)的特征向量，與此同時(shí)，結(jié)合Newman的特征值特征向量提取社團(tuán)結(jié)構(gòu)的算法的原理，就可以不用計(jì)算模塊度矩陣B的最大特征值對(duì)應(yīng)的特征向量，而直接通過(guò)解微分方程（1），利用微分方程（1）的解中元素的符號(hào)就可以將復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)分為兩類(lèi)。據(jù)此，提出了如下CNN算法。

針對(duì)復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)檢測(cè)問(wèn)題，將Newman的基于模塊度函數(shù)Q的矩陣特征值和特征向量提取復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的算法和神經(jīng)網(wǎng)絡(luò)算法求解矩陣特征值特征向量的算法結(jié)合起來(lái)得到一種新的基于連續(xù)神經(jīng)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)檢測(cè)算法，簡(jiǎn)稱(chēng)CNN算法，模型為：

其中，B為（2）式定義的復(fù)雜網(wǎng)絡(luò)的模塊度矩陣，X∈Rn，由定理1知，從任意初值出發(fā)，方程（3）的解都會(huì)收斂到模塊度矩陣B的最大特征值對(duì)應(yīng)的特征向量。結(jié)合Newman的特征值特征向量算法，就可以根據(jù)方程（3）的解中元素的符號(hào)將復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)提取出來(lái)。

綜上所述，設(shè)復(fù)雜網(wǎng)絡(luò)的鄰接矩陣為A，本文給出的基于CNN的社團(tuán)結(jié)構(gòu)提取算法的步驟如下：

步驟1：計(jì)算復(fù)雜網(wǎng)絡(luò)的模塊度矩陣B，其中的元素為 ，ki表示節(jié)點(diǎn)i的度，ij表示復(fù)雜網(wǎng)絡(luò)的鄰接矩陣A的元素；X(0)=BX(t)-

步驟2：給定任意初值 ，求解XT(t)BX(t)的X(解t)X?；

步驟3：根據(jù)解X?得到社團(tuán)結(jié)構(gòu)標(biāo)簽向量s，其中向量s中的元素如下確定

步驟4：將s中+1對(duì)應(yīng)的節(jié)點(diǎn)提取出來(lái)。

2 結(jié)果

2.1 實(shí)驗(yàn)數(shù)據(jù)在本文中，采用了空手道俱樂(lè)部網(wǎng)絡(luò)（Zachary's Karate Club Network）〔9〕數(shù)據(jù)做實(shí)驗(yàn)。該網(wǎng)絡(luò)數(shù)據(jù)的下載網(wǎng)址是 http：∕www-personal.umich.edu∕～mejn∕netdata∕。

空手道俱樂(lè)部網(wǎng)絡(luò)：在社團(tuán)提取問(wèn)題中空手道俱樂(lè)部網(wǎng)絡(luò)是被應(yīng)用最為廣泛的例子之一?？帐值谰銟?lè)部網(wǎng)絡(luò)由34個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)表示一個(gè)成員，網(wǎng)絡(luò)中的78條邊表示成員之間的社會(huì)交往關(guān)系，由于俱樂(lè)部主管和校長(zhǎng)之間發(fā)生矛盾，俱樂(lè)部成員就被分成了分別以主管和校長(zhǎng)為中心的兩個(gè)社團(tuán)。

2.2 實(shí)驗(yàn)結(jié)果及分析在實(shí)驗(yàn)部分，將在俱樂(lè)部網(wǎng)絡(luò)上分析連續(xù)神經(jīng)網(wǎng)絡(luò)算法的穩(wěn)定性以及分類(lèi)效果，分別選出俱樂(lè)部網(wǎng)絡(luò)中所有的節(jié)點(diǎn)和某幾個(gè)節(jié)點(diǎn)分析CNN算法的穩(wěn)定性，結(jié)果見(jiàn)圖1～2。

圖1 CNN算法在空手道俱樂(lè)部網(wǎng)絡(luò)上的穩(wěn)定性分析

圖2 CNN算法下空手道俱樂(lè)部網(wǎng)絡(luò)上某幾個(gè)點(diǎn)的穩(wěn)定性分析

從圖1可以看出，當(dāng)t=0時(shí)，對(duì)于任意的初始值X(0)，隨著時(shí)間的推移，發(fā)現(xiàn)俱樂(lè)部網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的網(wǎng)絡(luò)狀態(tài)最終收斂到一個(gè)穩(wěn)定狀態(tài)，即收斂到俱樂(lè)部網(wǎng)絡(luò)的模塊度矩陣B的最大特征值對(duì)應(yīng)的特征向量。因此根據(jù)網(wǎng)絡(luò)穩(wěn)定狀態(tài)的符號(hào)提取出俱樂(lè)部網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。從圖2可以更清楚地看到CNN網(wǎng)絡(luò)中的某幾個(gè)狀態(tài)的收斂情況，給定任意的初值X(0)后，只需1.5s,網(wǎng)絡(luò)中的0、2、3、32、33這5個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)演進(jìn)就達(dá)到了穩(wěn)定狀態(tài)。這表明CNN算法的穩(wěn)定性良好。

采用連續(xù)神經(jīng)網(wǎng)絡(luò)算法提取空手道俱樂(lè)部網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，結(jié)果見(jiàn)圖3。

圖3 連續(xù)算法提取空手道俱樂(lè)部網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的分類(lèi)結(jié)果

圖3列出了連續(xù)神經(jīng)網(wǎng)絡(luò)算法在空手道俱樂(lè)部網(wǎng)絡(luò)上的仿真結(jié)果。從實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，特征向量算法、連續(xù)算法對(duì)空手道俱樂(lè)部網(wǎng)絡(luò)的分類(lèi)結(jié)果與特征向量算法的分類(lèi)結(jié)果（Q=0.3715）相同，表明本文中的算法也是合理的。

3 討論

復(fù)雜網(wǎng)絡(luò)是研究復(fù)雜系統(tǒng)的有力工具，很多現(xiàn)實(shí)的系統(tǒng)都可以抽象成復(fù)雜網(wǎng)絡(luò)來(lái)研究，網(wǎng)絡(luò)的節(jié)點(diǎn)對(duì)應(yīng)著系統(tǒng)中的實(shí)體。研究表明，很多真實(shí)網(wǎng)絡(luò)中存在著不同程度的社團(tuán)結(jié)構(gòu)特性，而這種社團(tuán)結(jié)構(gòu)決定著網(wǎng)絡(luò)的某些功能屬性，因此在網(wǎng)絡(luò)中描述和檢測(cè)這些社團(tuán)結(jié)構(gòu)具有重要的實(shí)際意義。本文立足于檢測(cè)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)這個(gè)課題，提出了基于模塊度函數(shù)Q這個(gè)指標(biāo)的社團(tuán)結(jié)構(gòu)提取算法——連續(xù)神經(jīng)網(wǎng)絡(luò)算法，并且將該算法和已有的相關(guān)算法作了比較，表明了此算法的有效性。