基于連續(xù)Hopfield網(wǎng)絡的復雜網(wǎng)絡社團結(jié)構提取

代婷婷，董延壽，韓 艷

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

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

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

1 算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟4：將s中+1對應的節(jié)點提取出來。

2 結(jié)果

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

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

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

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

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

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

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

圖3 連續(xù)算法提取空手道俱樂部網(wǎng)絡中社團結(jié)構的分類結(jié)果

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

3 討論

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