復(fù)雜網(wǎng)絡(luò)中的模塊密度中心性方法

復(fù)雜網(wǎng)絡(luò)中的模塊密度中心性方法

1模塊化中心性方法中心是網(wǎng)絡(luò)分析最基本的元素之一。長期以來，網(wǎng)絡(luò)研究人員提出了許多中心指標(biāo)，以確定網(wǎng)絡(luò)中的哪個節(jié)點比其他節(jié)點重要。在社會網(wǎng)絡(luò)中，這些指標(biāo)被廣泛應(yīng)用于驗證者在網(wǎng)絡(luò)中的角色，以便研究人員分析和理解網(wǎng)絡(luò)中其他類型的網(wǎng)絡(luò)。例如，網(wǎng)絡(luò)存儲方法可能是節(jié)點本身，但節(jié)點之間最短路徑的方法可能是相對于節(jié)點之間最短路徑的方法，如介質(zhì)方法和相鄰方法。此外，還有基于網(wǎng)絡(luò)效率和圖矩陣光譜特征的中心方法。這些方法通常與簡單的動態(tài)過程相結(jié)合。近來,對結(jié)構(gòu)化中心性方法頗為關(guān)注[6～8],因為這些中心性方法更能從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)上來判定節(jié)點的重要性.文獻(xiàn)提出了一種結(jié)構(gòu)化模塊中心性方法.這種中心性方法度量了每一個節(jié)點到它分配社團(tuán)上的貢獻(xiàn).這種貢獻(xiàn)通過屬于模塊矩陣最大幅度(絕對值)的特征值對應(yīng)的特征向量元素幅度被表示.事實上,模塊中心性方法緊密地關(guān)聯(lián)于由模塊方法(稱之為Q)檢測出的社團(tuán).在社團(tuán)檢測中,近來研究已經(jīng)證明模塊方法不能檢測出小于一種內(nèi)在尺度的社團(tuán).這主要是因為網(wǎng)絡(luò)的社團(tuán)劃分高敏感于網(wǎng)絡(luò)中邊的總數(shù)目.其結(jié)果,社團(tuán)劃分相對于網(wǎng)絡(luò)總邊數(shù)的敏感性反過來影響了模塊中心性方法的解和穩(wěn)定性.模塊中心性方法依據(jù)節(jié)點鄰居數(shù)目判定節(jié)點的重要性多于依據(jù)節(jié)點的位置和功能,這使得可能忽略一類節(jié)點,例如橋節(jié)點.而且,事實已經(jīng)證明了依據(jù)節(jié)點鄰邊的數(shù)目不足以判定節(jié)點的重要性.另外,對任意一個網(wǎng)絡(luò),模塊矩陣的最大幅度特征值要么是正的最大特征值,要么是負(fù)的最小特征值.然而,屬于負(fù)的最小絕對值的特征向量包含著較少關(guān)于一個網(wǎng)絡(luò)“社團(tuán)”信息,這使得度量節(jié)點的貢獻(xiàn)到網(wǎng)絡(luò)的“反社團(tuán)”上.在社團(tuán)檢測中,為了克服和解決模塊方法的解極限,文獻(xiàn)提出了模塊密度(稱之為D)替代了模塊矩陣.同時,通過使用一個核矩陣,給出了模塊密度和核方法之間的等價關(guān)系.本文中,首先把模塊密度函數(shù)表達(dá)成核矩陣和節(jié)點矩陣跡的形式.隨后我們將模塊密度函數(shù)轉(zhuǎn)變成核矩陣的特征譜分的表達(dá)方式.通過模塊密度函數(shù)的優(yōu)化進(jìn)程,基于屬于核矩陣的最大特征值的特征向量,我們提出了一種新的中心性方法,稱為模塊密度中心性方法.2bonacich’s特征向量中心性思想指派給網(wǎng)絡(luò)中每一個節(jié)點數(shù)值的函數(shù)稱為一種中心性方法.有許多不同的概念用來計算這種中心性方法.我們在最初社會網(wǎng)絡(luò)歷史背景下展示一組被提出的中心性方法,包括了最近由Wang等提出的模塊中心性方法.這些標(biāo)準(zhǔn)方法是在一個無向、無權(quán)重、擁有N個節(jié)點和K條邊的圖中給出的.通過一個N×N鄰接矩陣A來描述這個圖,如果節(jié)點i和節(jié)點j之間存在一條邊,這個矩陣A的元素Aij等于1,否則等于0.介數(shù)中心性方法(betweennesscentralityCB)的定義是通過假設(shè)信息僅僅沿著最短路徑來傳播.如果njk是連接節(jié)點j和k之間最短路徑數(shù)目,njk(i)是連接節(jié)點j和k之間包含著節(jié)點的最短路徑數(shù)目,結(jié)果節(jié)點i的介數(shù)中心性定義為鄰近中心性方法(ClosenesscentralityCC):一個節(jié)點i的鄰近中心性是基于最小距離或最短路徑dij來定義的,即從節(jié)點i到節(jié)點j穿過邊的最小數(shù)目,并被定義為其中Li是從i到所有其他節(jié)點的平均距離.Bonacich’s特征向量中心性方法(Bonacich’seigenvectorcentralityCλ)基于一個節(jié)點的中心性值是由鄰接頂點的值決定這樣一種思想,這種方法不僅考慮到它的鄰居節(jié)點中心性值,而且考慮到一個節(jié)點在圖中的位置.節(jié)點i的特征向量中心性定義為這就直接引導(dǎo)出了眾所周知的特征向量計算問題λS=AS,并且最大特征值對應(yīng)的特征向量就是這個向量中心性(Cλ=S).信息中心性方法(informationcentralityCI)被定義為通過從圖中移除某個頂點及連接它的邊后,引起該圖效率E(G)的相對衰退.那么一個頂點i的信息中心性值被定義為其中一個圖G的效率被定義為G′是通過從原始圖中移除頂點i及其連接的邊后獲得的擁有N個頂點和K-ki邊的圖.模塊中心性(modularitycentralityCM)是基于這樣一種思想:節(jié)點通過一種“力量”被綁定到它們分配的社團(tuán)上,這種“力量”表示了節(jié)點屬于它們社團(tuán)的重要性.Q值被表達(dá)成其中p是非重疊社團(tuán)數(shù)目,βj是模塊矩陣第j個特征值,uj是屬于βj的特征向量,xk是節(jié)點矩陣的第k列向量.取β=max(|βj|),如果ui是屬于β的特征向量uj的第i個元素,那么節(jié)點i的模塊中心性被定義為3節(jié)點權(quán)重的確定為發(fā)現(xiàn)檢測社團(tuán)結(jié)構(gòu)有效方法,模塊密度函數(shù)被提了出來.通過一種過渡操作核矩陣,論證了模塊密度函數(shù)和目標(biāo)核k函數(shù)的等價關(guān)系.核k函數(shù)是標(biāo)準(zhǔn)k方法的推廣,用來將非線性輸入空間中的數(shù)據(jù)映射到一種線性高維空間中去,而并不需要知道關(guān)聯(lián)于輸入空間映射函數(shù)的詳細(xì)表達(dá).核k方法已經(jīng)被廣泛應(yīng)用于模式識別中.通過應(yīng)用過渡操作核矩陣,能有效計算非線性輸入空間中的數(shù)據(jù)在高維特征線性空間中的主要成分.模塊密度函數(shù)D是所有社團(tuán)平均模塊度的總和.對每一個社團(tuán),平均模塊度等于它的入度減去它的出度,這里入度等于社團(tuán)內(nèi)邊數(shù)的2倍除以該社團(tuán)內(nèi)節(jié)點數(shù),出度等于這個社團(tuán)內(nèi)節(jié)點同這個社團(tuán)外部節(jié)點的連接邊數(shù)除以該社團(tuán)內(nèi)節(jié)點數(shù).D值越大表示社團(tuán)劃分越好,反之亦然.接下來,我們將模塊密度函數(shù)作為目標(biāo)函數(shù),利用核k函數(shù)的分解來表達(dá)模塊密度函數(shù).給出一組數(shù)據(jù)向量U={ui}Ni=1,ui∈Rn以及一個N×N核矩陣其中I是單位矩陣,B是一個對角的度矩陣,其元素為并且σ是一個被選擇足夠大的實數(shù)以便這個核矩陣K始終處于正定,為尋找{Uc}pc=1個不重疊社團(tuán),函數(shù)D和核k函數(shù)H被表達(dá)成在等式(9)中,H被詳細(xì)定義為其中H=H({Uc}pc=1)并且,|Uc|是子集Uc的勢,?是一個把U中的數(shù)據(jù)向量映射到一個高維空間中的函數(shù).在文獻(xiàn)中,Dhillon等為了進(jìn)一步推廣了這個核k方法,為每一個數(shù)據(jù)向量ui引入了一個權(quán)重,標(biāo)識為w(ui),以便能利用存在的譜分方法優(yōu)化這種核k函數(shù).這個變化了的核k函數(shù)稱之為權(quán)重核k方法,被定義為其中.那么式(11)可以被轉(zhuǎn)換成其中Φ是所有?(ui)向量組成的矩陣.對任何給出的正半定核矩陣K,Dhillon等指出ΦTΦ能夠等于這個核矩陣.W是所有權(quán)重w(ui)的對角矩陣,并且Y是一個正交的N×p數(shù)據(jù)向量矩陣,即YTY=Ip,如果ui屬于子集,那么它的元素,否則Yic=0.顯而易見,如果每一個節(jié)點向量權(quán)重w(ui)等于1,式(11)涵蓋了式(10)的標(biāo)準(zhǔn)定義.與此同時,在式(12)中,W可變成一個單位矩陣.結(jié)果我們可以通過如下等式計算D函數(shù)其中L=(N-p)σ-trace(K).注意到trace(K)是一個常數(shù),并且σ正如文獻(xiàn)中顯示的那樣是一個不依賴任何常量和變量的獨立變量.因此,一旦社團(tuán)的數(shù)目確定,一個得出的重要結(jié)論如下:D值的優(yōu)化進(jìn)程僅僅依賴于trace(YTKY)值的增長.4模塊密度中心性方法相似于網(wǎng)絡(luò)的各種矩陣,例如模塊矩陣、Laplace矩陣、鄰接矩陣,這個核矩陣也包含著一個網(wǎng)絡(luò)結(jié)構(gòu)基本信息.為了獲得關(guān)于一個網(wǎng)絡(luò)有用的社團(tuán)結(jié)構(gòu)信息,我們將D值表達(dá)成這個核矩陣的特征譜分形式,這引導(dǎo)出了我們的中心性方法.對于任何網(wǎng)絡(luò),因為這個核矩陣是正定定義,所以這個核矩陣的所有特征值大于零.為了方便,將式(13)簡單寫成將核矩陣表達(dá)成K=VGVT形式,其中V=(v1|v2|,...)是核矩陣的特征向量矩陣并且G是特征值Gii=λi的對角矩陣,式(14)能被轉(zhuǎn)換成其中yc是節(jié)點矩陣Y的第c列向量.希望最大化這個D值.如果這個矩陣Y的元素沒有限制除了上面提到的行和列的基本條件,可以通過選擇矩陣Y中與屬于最大特征值的特征向量成比例的列,將D值最大化.因此,關(guān)于一個網(wǎng)絡(luò)的最優(yōu)的社團(tuán)結(jié)構(gòu)信息被存儲在屬于最大特征值的特征向量中.與此同時,這個特征向量的元素的絕對值暗示了對應(yīng)節(jié)點在屬于這個社團(tuán)中所處的“力度”.對應(yīng)于該向量最大絕對值的元素的節(jié)點對這個社團(tuán)有最大的貢獻(xiàn),見式(15),反之亦然.可選地,假設(shè)我們移動一個節(jié)點從它分配的社團(tuán)到另外一個社團(tuán),如果對它分配的社團(tuán)沒有發(fā)生一個大的補(bǔ)償,那么對應(yīng)于這個特征向量最大絕對值的元素的節(jié)點將不能夠被移動,而那些對應(yīng)于該向量較小絕對值元素的節(jié)點在相對無補(bǔ)償?shù)厍闆r下能被從它分配的社團(tuán)移動到另外一個社團(tuán).因此,屬于這個特征向量元素的絕對值的基本意義暗示了這些節(jié)點,作為它們在整個網(wǎng)絡(luò)中所處的位置結(jié)果,對這個網(wǎng)絡(luò)整個社團(tuán)上要么是正的要么是負(fù)的堅實的貢獻(xiàn).結(jié)果這個特征向量元素的絕對值定義了一種刻畫節(jié)點在整個網(wǎng)絡(luò)中的中心性指標(biāo).我們稱這個中心性方法為模塊密度中心性方法.應(yīng)當(dāng)注意到σ的選擇能改變這個核矩陣K的最大特征值.然而,一旦網(wǎng)絡(luò)確定,僅當(dāng)σ的選擇足夠大以便核矩陣K始終處于正定,屬于最大特征值的特征向量就是一個常量.另外,應(yīng)當(dāng)注意到復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)不僅包含非重疊社團(tuán)而且也可能包含模糊社團(tuán).對于模糊社團(tuán)中的節(jié)點,模塊密度中心性方法能夠度量這類節(jié)點的累加貢獻(xiàn).因此,模塊密度中心性方法刻畫了節(jié)點到它們分配的社團(tuán),無論是在非重疊社團(tuán)或模糊社團(tuán)上的重要性.用標(biāo)準(zhǔn)符號CK去表示模塊密度中心性并且定義它等于屬于最大特征值的特征向量元素絕對值.讓λ=max(λi),i=1,2,...,N.向量v是屬于λ的特征向量,那么,節(jié)點i的模塊密度中心性值就是向量v的第i個元素的絕對值,即|vi|.5實驗與結(jié)果分析本節(jié)中給出許多例子來展示方法的應(yīng)用以及在大型網(wǎng)絡(luò)數(shù)據(jù)分析中的統(tǒng)計分布特性.5.1中心性和中心性模塊密度中心性方法在極端的情形下與其他標(biāo)準(zhǔn)方法是一致的:例如它給出一個星型網(wǎng)絡(luò)中心性節(jié)點最大的重要性,以及一個完全圖中節(jié)點相等的重要性.然而,這種一致性在某些情形下被打破,例如橋節(jié)點連接一個網(wǎng)絡(luò)幾個主要部分.橋節(jié)點通常在網(wǎng)絡(luò)扮演著重要角色.在一個網(wǎng)絡(luò)中,不是所有節(jié)點的影響力是相同的.不同節(jié)點的移除對這個網(wǎng)絡(luò)有不同的影響.如果移除一個末端節(jié)點,對整個網(wǎng)絡(luò)沒有什么影響,對應(yīng)地這個網(wǎng)絡(luò)中剩余節(jié)點中心性指標(biāo)級別不應(yīng)發(fā)生改變.而刪除橋節(jié)點,整個網(wǎng)絡(luò)就會分成幾個不連續(xù)的部分,對網(wǎng)絡(luò)的影響很大.通過考慮各方法的解和穩(wěn)定性兩個方面,來展示這種情形.考慮兩個無環(huán)圖(樹),如圖1中的T1和T2.在T1中,5種中心性方法得出的節(jié)點中心性值如表1所示,這里節(jié)點的中心性值根據(jù)CK值的降序排列.雖然五種中心性方法對T1的中央節(jié)點2都分配了最高的中心性,然而有許多值得提及的差異.正如表2中顯示的那樣,CK分配最高的中心性等級給節(jié)點2,第二中心性等級給橋節(jié)點1,3,第三中心性等級給節(jié)點4,5,并且能夠從剩余的節(jié)點中分辨出節(jié)點10,11,12(第4等級).具有一些明顯差異的其他方法是CM,CI和Cλ,一方面,它們都分配第二中心性等級給節(jié)點4,5,第三中心性等級給橋節(jié)點1,3,扭轉(zhuǎn)了CK的解.另外,CB分配第一中心性等級給節(jié)點2,第二中心性等級給節(jié)點1,3,4,5并且沒有從剩余的節(jié)點中分辨出節(jié)點10,11,12.僅僅CB沒有其他方法給出的解.樹T2中節(jié)點的等級如表3所示.雖然末端節(jié)點12從圖T1中被移除,正如表3中所示,沒有影響基于CK,CI方法在圖T2中給出節(jié)點的等級,但影響了基于CM,Cλ和CB方法在圖T2中給出節(jié)點的等級.特別地,節(jié)點2仍然位于圖T2的中央,但CM改變了節(jié)點2的等級,從最高等級變到第二等級.Cλ改變了節(jié)點4,5從第二等級到最高等級,以及將節(jié)點1,3從第三等級改變到第二等級.CB改變了節(jié)點1,3從第二等級到第三等級.Cλ和CB沒有從剩下的節(jié)點中分辨出節(jié)點10,11.因此,在解和穩(wěn)定上,CK比起CM,Cλ和CB更相似于CI.5.2各方法之間的差異作為一個有環(huán)圖的例子,研究了由LindaWolfe收集的真實網(wǎng)絡(luò)數(shù)據(jù)并且已經(jīng)作為一個標(biāo)準(zhǔn)數(shù)據(jù)集收錄在UCINET中.這個數(shù)據(jù)集記錄了一群20只猴子之間的相互作用,這里相互作用定義為在河流領(lǐng)域上的聯(lián)合存在.其結(jié)果圖如圖2所示,包含了6個孤立節(jié)點和14個節(jié)點的連接體,標(biāo)準(zhǔn)中心性方法已經(jīng)運(yùn)用到猴子個體研究.因此,能夠在這個標(biāo)準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集中進(jìn)行各標(biāo)準(zhǔn)方法的比較.表4是獲得20只猴子節(jié)點的中心性值.雖然所有的方法都給猴子3指派最高等級以及給6個孤立猴子指派了最低等級,但CM和其他方法之間存在著巨大差異.正如表4中所示,CK,CI和CC都給猴子12指派第二等級,給猴子13和15指派第三等級.相反地,CM給猴子12指派了倒數(shù)第二等級,給猴子13和15指派了倒數(shù)第三等級.對該網(wǎng)絡(luò),這主要是因為屬于最大絕對特征值對應(yīng)的是負(fù)的最小特征值,而最小負(fù)的特征值對應(yīng)的特征向量包含了這個網(wǎng)絡(luò)(圖2)的“反社團(tuán)”信息.事實上,這類特征向量元素的絕對值定義了一種非尋常的中心性方法,所謂的“外”中心性方法,這種中心性方法僅僅在某種特定環(huán)境下可用.如果考慮到特定環(huán)境,他們的研究可能更加合理.因此,CM為猴子11指派第二等級,為猴子9指派第三等級就不足為奇了.對這個標(biāo)準(zhǔn)數(shù)據(jù)集,由CK產(chǎn)生的20個猴子節(jié)點的等級相似于由CI和CC產(chǎn)生的等級.如表4所示,盡管節(jié)點獲得的值是不同的,例如處于第一等級的節(jié)點,即猴子3,有CK=0.3602,CI=0.3751和CC=0.1431.在圖3中繪制了各方法相對它們最大數(shù)值標(biāo)準(zhǔn)化了的每一個節(jié)點的中心性值.這些節(jié)點作為基于CK標(biāo)準(zhǔn)化等級值的函數(shù)進(jìn)行排序.從圖3可看出,CK的大體舉動相似于CI和CC的通常舉動.CM相對于其他方法則顯示出反常舉動:在等級5,等級12和等級14出現(xiàn)的3個峰值分別對應(yīng)于節(jié)點14,節(jié)點11和節(jié)點9,對于CM來說暗示了這3只猴子的等級較高.5.3模塊密度中心性網(wǎng)絡(luò)的構(gòu)建研究人員常常感興趣于在大型網(wǎng)絡(luò)分類中所有節(jié)點中心性值的分布情況.因此,在大型圖的節(jié)點中研究了模塊密度中心性在統(tǒng)計上是如何分布的.為了減少統(tǒng)計上的波動,計算了定義在(微分)分布P(CK)上的累積分布P(CK):其中p(X)dX表示在區(qū)間X,X+dX上發(fā)現(xiàn)一個擁有模塊密度中心性等級的節(jié)點的概率,N(X)dX表示在區(qū)間X,X+dX上擁有一個模塊密度中心性等級節(jié)點的數(shù)目,N表示這個圖中節(jié)點的總數(shù)目.首先,考慮兩類人工生成圖,即:Erd¨os-R′enyi(ER)隨機(jī)圖,以及一個給定的度分布隨機(jī)圖.生成了有著N=600個節(jié)點和K=3000條邊的ER隨機(jī)圖,并且生成了擁有N=800個節(jié)點以及服從指數(shù)γ=3冪律的度分布隨機(jī)圖.圖4是在這兩種情況下獲得的模塊密度累積分布,用圓表示.在圖4(a)中的虛線是與這些點相匹配的Gauss分布,而在圖4(b)的雙對數(shù)坐標(biāo)圖中,虛直線是與指數(shù)u=1.84相匹配的P(CK)～(CK)-u冪律分布.較后的結(jié)果暗示了,在一個擁有冪律的度分布隨機(jī)圖中,模塊密度中心性也服從一個冪律來分布.對這個例子,發(fā)現(xiàn):p(CK)～(CK)-2.84.同時考慮來自現(xiàn)實世界的兩個大型網(wǎng)絡(luò).第一個網(wǎng)絡(luò)描述了包含重要鐵路和火車站的印度“大概鐵路”火車時間表.這個網(wǎng)絡(luò)有N=587個節(jié)點表示火車站以及K=579條邊代表鐵路.這個網(wǎng)絡(luò)的度分布符合指數(shù)分布,其結(jié)果相對單調(diào).模塊中心性和介數(shù)中心性的分布較大偏離于擁有相同邊的隨機(jī)網(wǎng)絡(luò)分布,暗示了印度鐵路網(wǎng)絡(luò)有一些結(jié)構(gòu)沒有被這些方法捕獲.圖5(a)是在該網(wǎng)絡(luò)得到的模塊密度分布.這種分布行為正如在圖4(a)中ER隨機(jī)圖表現(xiàn)的那樣,CK展示了單尺度