代婷婷，韓 艷，虎亞楠

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

1 引言

在社團(tuán)檢測(cè)算法中歷史悠久的、比較經(jīng)典的有Kernighan-Lin算法和譜平分方法[1,2],其次就是Girvan和 Newman[3]在2002年提出的一種通過邊移除按層次分解網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)方法(GN).在后一算法中提到了模塊度，之后模塊度很快成為了衡量社團(tuán)檢測(cè)結(jié)果的通用指標(biāo).隨著研究的不斷推進(jìn)，2014年，Maria C.V. Nascimento[4]提出了一種基于聚類系數(shù)的譜啟發(fā)式算法(SPEC)，該算法克服了啟發(fā)式算法的規(guī)模缺陷，具有很好的性能.2017年，鄧小龍等人[5]提出了基于矢量影響力聚類系數(shù)的高效有向網(wǎng)絡(luò)社團(tuán)檢測(cè)算法.該算法從構(gòu)成社團(tuán)最基礎(chǔ)的三角形極大團(tuán)展開數(shù)學(xué)推導(dǎo)，并且提出一種有向社團(tuán)結(jié)構(gòu)劃分目標(biāo)函數(shù)，具有不錯(cuò)的精確性.2018年，鄭少?gòu)?qiáng)等人[6]提出一種基于聚類系數(shù)的標(biāo)簽傳播算法，對(duì)節(jié)點(diǎn)按度和聚類系數(shù)的大小影響力排序，根據(jù)影響力做初始劃分，再進(jìn)行標(biāo)簽傳播.本文主要是依據(jù)Newman提出的模塊度社團(tuán)劃分評(píng)價(jià)指標(biāo)，提出了一種基于神經(jīng)網(wǎng)絡(luò)的社團(tuán)劃分方法，此方法可以找到最優(yōu)的模塊度函數(shù)值，對(duì)應(yīng)地可以找到最優(yōu)的與實(shí)際網(wǎng)絡(luò)非常接近的劃分.

2 理論與方法

2.1 連續(xù)神經(jīng)網(wǎng)絡(luò)(CNN)

考慮微分方程

(1)

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

定理2[7]假設(shè)A的最大特征值λ>0，則式(2)的從任意初值X(0)出發(fā)的解均收斂于A的最大特征值λ對(duì)應(yīng)的特征向量.

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

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

(2)

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

2.2 離散Hopfield神經(jīng)網(wǎng)絡(luò)(DHNN)算法

離散的Hopfield神經(jīng)網(wǎng)絡(luò)是一個(gè)單層全連接網(wǎng)絡(luò)，有n個(gè)神經(jīng)元節(jié)點(diǎn)，每個(gè)神經(jīng)元的輸出均接到其它神經(jīng)元的輸入.各節(jié)點(diǎn)沒有自反饋,每個(gè)節(jié)點(diǎn)都可處于一種可能的狀態(tài)(1或-1)，即當(dāng)該神經(jīng)元所受的刺激超過其閾值時(shí)，神經(jīng)元就處于興奮狀態(tài)(比如1)，否則神經(jīng)元就始終處于抑制狀態(tài)(比如-1).

對(duì)于以符號(hào)函數(shù)為激活函數(shù)的網(wǎng)絡(luò)，網(wǎng)絡(luò)的方程可寫為

xi(t+1)=sgn[ui(t)]，i=1,2,…,n，

(3)

其中W為連接權(quán)矩陣，θ為閾值向量.將以上Hopfield網(wǎng)絡(luò)簡(jiǎn)記為H=(W,θ).

為了避免求具體解，而只利用符號(hào)解決復(fù)雜網(wǎng)絡(luò)的分類問題，本文提出了另一種新的復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)提取算法—離散Hopfield神經(jīng)網(wǎng)絡(luò)提取社團(tuán)結(jié)構(gòu)算法，簡(jiǎn)稱為DHNN算法.

根據(jù)離散Hopfield神經(jīng)網(wǎng)絡(luò)的形式，可以將連續(xù)神經(jīng)網(wǎng)絡(luò)(2)離散化構(gòu)造離散Hopfield神經(jīng)網(wǎng)絡(luò)模型，最后根據(jù)提出的離散Hopfield神經(jīng)網(wǎng)絡(luò)模型達(dá)到穩(wěn)定狀態(tài)時(shí)穩(wěn)定點(diǎn)中元素的符號(hào)將復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)分為兩類.

將式(2)連續(xù)的微分方程寫成差分的形式，可以得到

所以

x(t+1)=Bx(t)+x(t)-xT(t)Bx(t)x(t).

(4)

將式(2)與式(4)結(jié)合，就可以得到離散的神經(jīng)網(wǎng)絡(luò)模型

x(t+1)=sign(Bx(t)+x(t)-xT(t)Bx(t)x(t)).

(5)

對(duì)于離散的Hopfield神經(jīng)網(wǎng)絡(luò)H=(W,θ),取

θ=x(t)-xT(t)Bx(t)x(t)=0,

則網(wǎng)絡(luò)模型可以變形為

x(t+1)=sign(Bx(t)).

(6)

將式(6)中的模塊度矩陣B拆開就可以得到

(7)

其中，An×n表示復(fù)雜網(wǎng)絡(luò)的鄰接矩陣，X(t)表示一個(gè)取值±1的n維列向量，ki表示節(jié)點(diǎn)i的度，符號(hào)函數(shù)為

3 實(shí)證分析

本文用8個(gè)文獻(xiàn)中廣為引用的數(shù)據(jù)庫對(duì)本文所提出的兩個(gè)社團(tuán)結(jié)構(gòu)提取算法進(jìn)行驗(yàn)證，驗(yàn)證結(jié)果表明，所提出的算法從準(zhǔn)則函數(shù)上看均優(yōu)于其它方法.

3.1 實(shí)驗(yàn)數(shù)據(jù)

(1) 空手道俱樂部網(wǎng)絡(luò)(Zachary’s Karate Club)[10]在社團(tuán)提取問題中是被應(yīng)用最為廣泛的例子之一.空手道俱樂部網(wǎng)絡(luò)由34個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)表示一個(gè)成員，網(wǎng)絡(luò)中的78條邊表示成員之間的社會(huì)交往關(guān)系.由于俱樂部主管和校長(zhǎng)之間發(fā)生矛盾，俱樂部成員就被分成了分別以主管和校長(zhǎng)為中心的兩個(gè)社團(tuán).此網(wǎng)絡(luò)如圖1所示.

圖1 空手道俱樂部網(wǎng)絡(luò)

(2) 其它實(shí)際網(wǎng)絡(luò)：Lusseau提出了海豚關(guān)系網(wǎng)，由62個(gè)節(jié)點(diǎn)159條邊組成.Internet含有22 963個(gè)節(jié)點(diǎn)，Netscience _ coauthor 含有1 589個(gè)節(jié)點(diǎn)，Polbooks 含有105個(gè)節(jié)點(diǎn)，Power_grid含有4 941個(gè)節(jié)點(diǎn)，football含有115個(gè)節(jié)點(diǎn)，Celegans含有297個(gè)節(jié)點(diǎn).這些網(wǎng)絡(luò)的數(shù)據(jù)可在下面的網(wǎng)址下載到：http://www-personal.umich.edu/～mejn/netdata/.

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

3.2.1空手道俱樂部網(wǎng)絡(luò)(Zachary’s Karate Club)實(shí)驗(yàn)結(jié)果分析

在實(shí)驗(yàn)部分，我們將在俱樂部網(wǎng)絡(luò)上分析連續(xù)型神經(jīng)網(wǎng)絡(luò)算法、離散型Hopfield神經(jīng)網(wǎng)絡(luò)算法的分類效果.首先用特征值和特征向量算法、連續(xù)神經(jīng)網(wǎng)絡(luò)算法、離散Hopfield神經(jīng)網(wǎng)絡(luò)提取空手道俱樂部網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，結(jié)果如表1、表2所示.

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

表2 離散算法提取的空手道俱樂部網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的分類結(jié)果

表1、表2列出了特征向量算法、連續(xù)算法和離散Hopfield神經(jīng)網(wǎng)絡(luò)算法在空手道俱樂部網(wǎng)絡(luò)上的仿真結(jié)果.從實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，特征向量算法、連續(xù)算法對(duì)空手道俱樂部網(wǎng)絡(luò)的分類的結(jié)果相同，而離散Hopfield神經(jīng)網(wǎng)絡(luò)算法對(duì)空手道俱樂部網(wǎng)絡(luò)的分類結(jié)果與前兩種算法卻不相同.它將9這個(gè)節(jié)點(diǎn)分到了+1所表示的類中，對(duì)應(yīng)的模塊度函數(shù)的值Q=0.371 8比特征向量算法、連續(xù)算法得到的模塊度函數(shù)值Q=0.371 5大，這里我們是用+1，-1來區(qū)別的.在以模塊度函數(shù)值Q的大小作為社團(tuán)劃分優(yōu)劣的指標(biāo)時(shí)，顯然用離散Hopfield神經(jīng)網(wǎng)絡(luò)算法提取的社團(tuán)結(jié)構(gòu)更優(yōu).三種方法的分類結(jié)果在實(shí)際網(wǎng)絡(luò)上的表現(xiàn)如圖1、圖2所示.

圖2 DHNN算法對(duì)空手道俱樂部網(wǎng)絡(luò)的分類結(jié)果

采用離散Hopfield神經(jīng)網(wǎng)絡(luò)算法提取空手道俱樂部網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)時(shí)，對(duì)于任意給定的初值，網(wǎng)絡(luò)(6)經(jīng)過若干次迭代后網(wǎng)絡(luò)最終收斂到一個(gè)長(zhǎng)度為2的極限環(huán)，并且對(duì)應(yīng)于一個(gè)合理的社團(tuán)結(jié)構(gòu)(community)，得到的目標(biāo)值Q=0.371 8(用+1，-1來區(qū)別)，就是將圖1中淺(黃)色9改為深(紫)色9后得到圖2的結(jié)果對(duì)應(yīng)的目標(biāo)值，而我們用特征值特征向量的算法和連續(xù)算法得到的模塊度函數(shù)值為Q=0.371 5(采用+1，-1來區(qū)別)，即用本文所設(shè)計(jì)的Hopfield神經(jīng)網(wǎng)絡(luò)得到的目標(biāo)值大于特征向量法、連續(xù)算法得到的目標(biāo)值.得到這個(gè)結(jié)果不是偶然的，而是本文的離散Hopfield神經(jīng)網(wǎng)絡(luò)造成的，因?yàn)闊o論運(yùn)行多少次，網(wǎng)絡(luò)劃分的結(jié)果都與特征值算法的結(jié)果相差一個(gè)頂點(diǎn)，而且特征值特征向量算法得到的結(jié)果并不是本文所設(shè)計(jì)的離散Hopfield神經(jīng)網(wǎng)絡(luò)的穩(wěn)定點(diǎn)，要去掉9這個(gè)點(diǎn)后才是網(wǎng)絡(luò)的穩(wěn)定點(diǎn)而且目標(biāo)值才最優(yōu).由此可以看出，本文所提出的離散型Hopfield神經(jīng)網(wǎng)絡(luò)算法在提取復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)時(shí)，不需要計(jì)算模塊度矩陣B的最大特征值對(duì)應(yīng)的特征向量，這顯然為此算法的一個(gè)優(yōu)勢(shì).

3.2.2其它實(shí)際復(fù)雜網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果及分析

前面我們用本文提出的算法在空手道俱樂部網(wǎng)絡(luò)(Zachary’s Karate Club)上進(jìn)行了實(shí)驗(yàn)，并且對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了分析，為了進(jìn)一步證實(shí)本文算法的有效性，我們將用本文的算法在Internet、Netscience _ coauthor、Polbooks、Power_grid、football和Celegans六個(gè)網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn).由于這六個(gè)網(wǎng)絡(luò)的規(guī)模大，含有的節(jié)點(diǎn)數(shù)目很多，所以沒有將實(shí)驗(yàn)分類的結(jié)果一一列出，只是在表5中給出了特征值特征向量算法、連續(xù)算法和離散算法在8種不同實(shí)際網(wǎng)絡(luò)上仿真得到的Q值.其中對(duì)有些網(wǎng)絡(luò)用傳統(tǒng)的特征值算法計(jì)算已經(jīng)無法在個(gè)人電腦中進(jìn)行了，但本文所提出的DHNN算法仍能夠在較短時(shí)間內(nèi)完成.

表3 8種復(fù)雜網(wǎng)絡(luò)在連續(xù)算法和離散算法下的模塊度函數(shù)Q值的比較

觀察表3，我們發(fā)現(xiàn)離散算法與特征向量算法、連續(xù)算法相比有兩個(gè)優(yōu)勢(shì)：首先，在復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)較多的時(shí)候，離散算法可以在家庭用的筆記本電腦上算出復(fù)雜網(wǎng)絡(luò)的模塊度函數(shù)的Q值，而特征向量算法卻不能；其次，用離散算法在每個(gè)復(fù)雜網(wǎng)絡(luò)上得到的模塊度函數(shù)Q值均大于用特征向量算法、連續(xù)算法得到的Q值，這說明本文提出的離散算法在提取復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)時(shí)，算法性能較其它兩種方法更好.

4 結(jié)論與展望

本文提出的兩種算法都是將模塊度函數(shù)Q的值作為評(píng)價(jià)社團(tuán)劃分優(yōu)劣的指標(biāo)，根據(jù)復(fù)雜網(wǎng)絡(luò)的模塊度矩陣的最大特征值對(duì)應(yīng)的特征向量里面元素的符號(hào)將復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)分為兩類.在連續(xù)型神經(jīng)網(wǎng)絡(luò)方法中，我們通過一個(gè)微分方程系統(tǒng)計(jì)算出了復(fù)雜網(wǎng)絡(luò)模塊度矩陣的最大特征值對(duì)應(yīng)的特征向量，與Newman的特征值特征向量算法相比計(jì)算量較小，而且所對(duì)應(yīng)的Q值也較優(yōu).本文提出的算法尚有許多不足之處，比如對(duì)某些規(guī)模龐大的網(wǎng)絡(luò)，劃分的次數(shù)比較多，算法的復(fù)雜度較高，若能降低運(yùn)算次數(shù)則此方法會(huì)更好；另外，此算法的評(píng)價(jià)指標(biāo)比較單一，若再加入一個(gè)評(píng)價(jià)指標(biāo)，社團(tuán)結(jié)構(gòu)的劃分可能會(huì)更合理.在下一步工作中，考慮針對(duì)以上的問題將本文的方法作改進(jìn)和優(yōu)化.