復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的中心性研究

網(wǎng)絡(luò)節(jié)點(diǎn)的重要性可以通過網(wǎng)絡(luò)節(jié)點(diǎn)的中心屬性來衡量。在研究復(fù)雜網(wǎng)絡(luò)時，我們使用了不同的中心定義來描述網(wǎng)絡(luò)的動態(tài)特征，如網(wǎng)絡(luò)攻擊狀態(tài)下的網(wǎng)絡(luò)特征和交通網(wǎng)絡(luò)特征。在此基礎(chǔ)上，本文分析了節(jié)點(diǎn)的相關(guān)性、網(wǎng)絡(luò)最短路徑和模擬流程之間的對應(yīng)關(guān)系。在總結(jié)了實(shí)際網(wǎng)絡(luò)的局域性、信息完整性和動態(tài)性之后，本文討論了基于中心方法和實(shí)際網(wǎng)絡(luò)應(yīng)用的適應(yīng)性，并根據(jù)不同網(wǎng)絡(luò)結(jié)構(gòu)的不同應(yīng)用要求選擇中心評估方法。在同一網(wǎng)絡(luò)模型中，不同的中心評估方法可以應(yīng)用于不同的網(wǎng)絡(luò)模型。1基于最短路徑的隨機(jī)性網(wǎng)絡(luò)節(jié)點(diǎn)當(dāng)前很多網(wǎng)絡(luò)研究都基于Barabási提出的擇優(yōu)連接機(jī)制,尋求合適模型對現(xiàn)實(shí)現(xiàn)象的合理解釋,這些模型都定義網(wǎng)絡(luò)中心節(jié)點(diǎn)是那些在一定條件下?lián)碛写罅窟B接邊的節(jié)點(diǎn),但并不是所有的現(xiàn)實(shí)網(wǎng)絡(luò)的特性都能通過這種簡單的機(jī)制得到合理的解釋.因此,出現(xiàn)了其他一些不同的中心性判斷方法.針對現(xiàn)實(shí)網(wǎng)絡(luò)中出現(xiàn)節(jié)點(diǎn)擁有較小的連接度,卻對網(wǎng)絡(luò)的聯(lián)通性起到關(guān)鍵作用的介數(shù)中心性(BC);引入網(wǎng)絡(luò)流特征,根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)到達(dá)整個網(wǎng)絡(luò)其他所有節(jié)點(diǎn)的難易程度,提出了凝聚中心性(CC);特征值中心性(EC)是考慮節(jié)點(diǎn)已建立連接節(jié)點(diǎn)的重要性對該節(jié)點(diǎn)的影響而提出的;網(wǎng)絡(luò)流中心性(FC)按照流通的方式確定網(wǎng)絡(luò)的幾何中心;基于節(jié)點(diǎn)對網(wǎng)絡(luò)全局信息未知條件下,提出了隨機(jī)行走方法(RDW);根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)在構(gòu)造不同網(wǎng)絡(luò)子圖中的參與程度,提出了子圖中心性(SC).a.節(jié)點(diǎn)度節(jié)點(diǎn)度,即與節(jié)點(diǎn)連接的邊數(shù),也是與該節(jié)點(diǎn)建立連接的節(jié)點(diǎn)數(shù).設(shè)網(wǎng)絡(luò)具有n個節(jié)點(diǎn),k為節(jié)點(diǎn)度,則節(jié)點(diǎn)i的度中心性Cd(i)=k(i)(1)Cd(i)=k(i)(1)b.介數(shù)節(jié)點(diǎn)介數(shù)定義為網(wǎng)絡(luò)中節(jié)點(diǎn)對最短路徑中經(jīng)過節(jié)點(diǎn)i的個數(shù)占所有最短路徑數(shù)的比例.用gst,i表示節(jié)點(diǎn)對s和t最短路徑經(jīng)過i點(diǎn)的路徑數(shù),nst表示節(jié)點(diǎn)s和節(jié)點(diǎn)t之間存在所有最短路徑的路徑數(shù),則節(jié)點(diǎn)i的介數(shù)中心性Cb(i)=2∑s＜tgst?i/nstn(n-1)(2)Cb(i)=2∑s＜tgst?i/nstn(n?1)(2)其中,n(n-1)/2=∑s＜t1n(n?1)/2=∑s＜t1,用來將節(jié)點(diǎn)介數(shù)標(biāo)準(zhǔn)化,使得Cb∈.c.凝聚度與介數(shù)中心性方法類似,提出了另外一種基于最短路的方法——凝聚中心性,它是基于網(wǎng)絡(luò)節(jié)點(diǎn)達(dá)到網(wǎng)絡(luò)其他所有節(jié)點(diǎn)所需路徑綜合的差異性,利用信息在網(wǎng)絡(luò)中的廣播時間長短來確定網(wǎng)絡(luò)節(jié)點(diǎn)的重要性,定義為節(jié)點(diǎn)i到網(wǎng)絡(luò)其他所有節(jié)點(diǎn)最短距離的總和,凝聚度Cc(i)=∑s＜tdst(3)d.網(wǎng)絡(luò)流設(shè)網(wǎng)絡(luò)具有n個節(jié)點(diǎn),則節(jié)點(diǎn)i的網(wǎng)絡(luò)流的定義為Cf(i)=∑s＜tgst,igst(4)式中,gst為網(wǎng)絡(luò)中節(jié)點(diǎn)對(s,t)之間的所有路徑數(shù),不包含回路;gst,i為節(jié)點(diǎn)對(s,t)之間經(jīng)過節(jié)點(diǎn)i的路徑數(shù).e.隨機(jī)行走隨機(jī)行走模型的提出基于一個多數(shù)網(wǎng)絡(luò)的事實(shí),網(wǎng)絡(luò)節(jié)點(diǎn)對網(wǎng)絡(luò)的整體特性是未知的,這樣就使得對整體網(wǎng)絡(luò)選擇最優(yōu)不可能.Newman提出的隨機(jī)行走算法(RDW)為:(a)構(gòu)建關(guān)系矩陣L=D-A.其中,A為目標(biāo)網(wǎng)絡(luò)的鄰接矩陣,D為節(jié)點(diǎn)度組成的對角矩陣.(b)變換矩陣,把L矩陣去掉最后一行和最后一列,變成可逆矩陣.(c)求L矩陣的逆矩陣L-1,在L-1基礎(chǔ)上添加元素全為0的一行一列,構(gòu)成新矩陣T.Tij為T中的元素.隨機(jī)行走算法中網(wǎng)絡(luò)節(jié)點(diǎn)的介數(shù)為Cr(i)=2∑s＜tΙst?in(n-1)(5)其中Ιst?i=12∑jAij|Τis-Τit-Τjs+Τjt|i≠s,i≠tΙst?i=1i=s或i=tf.子圖子圖中心性方法是對節(jié)點(diǎn)度中心性的改進(jìn),基于節(jié)點(diǎn)對所在網(wǎng)絡(luò)局部子圖的參與程度來確定節(jié)點(diǎn)的重要性,節(jié)點(diǎn)i的子圖中心性Cs(i)=∞∑k=0μk(i)k!(6)μk(i)=(Ak)ii(7)式中,A為鄰接矩陣;μk(i)表示以節(jié)點(diǎn)i為起點(diǎn)經(jīng)k個連邊回到節(jié)點(diǎn)i的路徑數(shù)目,路徑包含回路.g.特征向量設(shè)網(wǎng)絡(luò)具有n個節(jié)點(diǎn),A表示網(wǎng)絡(luò)的鄰接矩陣.其中,節(jié)點(diǎn)對(i,j)之間存在連接,則aij=1;否則,aij=0:λ1,λ2,…,λn表示A的特征值,且每個特征值λi對應(yīng)的特征向量為a=(e1,e1,…,en),其關(guān)系可表示為λei=n∑j=1aijej,則特征向量中心性定義為Ce(i)=λ-1n∑j=1aijej(8)前面介紹的7種網(wǎng)絡(luò)中心性判斷方法都可以應(yīng)用到實(shí)際網(wǎng)絡(luò)中發(fā)現(xiàn)網(wǎng)絡(luò)的中心節(jié)點(diǎn),但由于方法的原理和側(cè)重不同,對同一網(wǎng)絡(luò)可能會出現(xiàn)不同的結(jié)果.按照各判斷方法的定義可以劃分為三類:關(guān)聯(lián)性、最短路徑和模擬流問題,如圖1所示.關(guān)聯(lián)性強(qiáng)調(diào)個體之間的直接連接,最短路徑問題表示節(jié)點(diǎn)傳播途徑始終選擇最優(yōu)方式,而模擬流則側(cè)重于對現(xiàn)實(shí)的一個模擬,如引入物理分壓的概念模擬網(wǎng)絡(luò)流問題.2主要網(wǎng)絡(luò)算法網(wǎng)絡(luò)中心性判斷方法的差異主要源于研究者對網(wǎng)絡(luò)本身特征和應(yīng)用要求的不同側(cè)重.前者主要關(guān)注網(wǎng)絡(luò)結(jié)構(gòu)特征,如網(wǎng)絡(luò)的連通性;后者則更注重固定網(wǎng)絡(luò)結(jié)構(gòu)上產(chǎn)生的效率問題,如網(wǎng)絡(luò)信息傳播的深度和廣度以及時間效率.因此,從衡量標(biāo)準(zhǔn)上存在節(jié)點(diǎn)在網(wǎng)絡(luò)局部和全局貢獻(xiàn)的差異,Newman提出隨機(jī)行走算法改變了以往對網(wǎng)絡(luò)整體性質(zhì)已知的假設(shè),引發(fā)基于網(wǎng)絡(luò)節(jié)點(diǎn)對全局信息缺失條件下的研究.另外,對于復(fù)雜網(wǎng)絡(luò)特別是實(shí)際大型網(wǎng)絡(luò)中心性研究,算法的時間復(fù)雜度也是十分重要的問題,現(xiàn)從這些角度對比分析這些方法的異同.2.1子圖中心性方法是普遍的網(wǎng)絡(luò)全局編碼通常按照網(wǎng)絡(luò)中心性方法依照考察節(jié)點(diǎn)連接方式不同劃分為局部和全局方法.以節(jié)點(diǎn)度為主,考察節(jié)點(diǎn)直接連接,在社會網(wǎng)絡(luò)中體現(xiàn)個體的影響力.以最短路為基礎(chǔ)的方法,如介數(shù)、凝聚性以及網(wǎng)絡(luò)流,都是考察網(wǎng)絡(luò)全局性質(zhì).子圖中心性方法是將局部信息擴(kuò)大,體現(xiàn)整體的性質(zhì).在子圖算法中如果把回路為1的權(quán)值設(shè)為1,其他回路的權(quán)值為0,那么子圖中心性方法就同節(jié)點(diǎn)度是一致的.科研合作網(wǎng)絡(luò)、論文引用網(wǎng)絡(luò)及語言網(wǎng)絡(luò)等強(qiáng)調(diào)個體之間的連接,并通過個體的連接來確定節(jié)點(diǎn)的重要性,都適合使用局域性方法;而對病毒傳播網(wǎng)絡(luò)、通訊網(wǎng)絡(luò),交通網(wǎng)絡(luò)及電力網(wǎng)絡(luò)等,節(jié)點(diǎn)的特性能在多個連接之間傳播,需要采用全局分析法.2.2隨機(jī)行駛是網(wǎng)絡(luò)結(jié)構(gòu)的模擬中心性方法中無論是節(jié)點(diǎn)度、凝聚性,還是介數(shù),都是基于整個網(wǎng)絡(luò)結(jié)構(gòu)特征信息完全已知,從節(jié)點(diǎn)自身的連接到整個網(wǎng)絡(luò)分布對決策者都是已知的,并且研究網(wǎng)絡(luò)結(jié)構(gòu)對實(shí)際網(wǎng)絡(luò)的影響力、信息流及交通流等如何控制,屬于靜態(tài)的.而隨機(jī)行走是針對節(jié)點(diǎn)擁有網(wǎng)絡(luò)有限信息的研究,是對現(xiàn)實(shí)網(wǎng)絡(luò)更真實(shí)的模擬,其算法思想來源于電路分壓,即電路節(jié)點(diǎn)只對直接連接點(diǎn)已知.社會學(xué)研究中的很多問題對網(wǎng)絡(luò)結(jié)構(gòu)特征獲取是十分困難的,如社交網(wǎng)絡(luò),還有大規(guī)模網(wǎng)絡(luò)上的局部問題,采用隨機(jī)行走能有效地利用有限信息模擬網(wǎng)絡(luò)性質(zhì).2.3節(jié)點(diǎn)度變化的影響網(wǎng)絡(luò)的動態(tài)性主要體現(xiàn)在網(wǎng)絡(luò)自身節(jié)點(diǎn)和邊的變化,主要形式有節(jié)點(diǎn)的增長、老化,邊的添加、刪除和改變連接.這些變化都會對網(wǎng)絡(luò)的節(jié)點(diǎn)中心性產(chǎn)生直接的影響.這里討論的動態(tài)性還涉及信息在網(wǎng)絡(luò)節(jié)點(diǎn)之間傳播的方式,節(jié)點(diǎn)度代表信息只存在與兩個節(jié)點(diǎn)之間的傳播,沒有擴(kuò)散性,而介數(shù)、網(wǎng)絡(luò)流和隨機(jī)行走都是典型的廣播式傳播.3中央方法采用適當(dāng)?shù)南到y(tǒng)和補(bǔ)充3.1主要關(guān)鍵指標(biāo)對網(wǎng)絡(luò)節(jié)點(diǎn)重要性的應(yīng)用研究主要可以分為兩類.一類是社會網(wǎng)絡(luò)分析法,該方法假設(shè)網(wǎng)絡(luò)的重要性等于節(jié)點(diǎn)的顯著性,通過直接連接數(shù)來體現(xiàn);另一類通過節(jié)點(diǎn)刪除法來判斷節(jié)點(diǎn)的重要性,其基礎(chǔ)為若刪除一個節(jié)點(diǎn)給網(wǎng)絡(luò)帶來的連通性破壞大,則該節(jié)點(diǎn)重要性高.在實(shí)際應(yīng)用中,由于不同方法對節(jié)點(diǎn)的重要性排序結(jié)果不同,關(guān)鍵節(jié)點(diǎn)的發(fā)現(xiàn)效率存在差異,因此,對方法的選擇是十分重要的,結(jié)合前面的分析,將網(wǎng)絡(luò)結(jié)構(gòu)特征和應(yīng)用要求相結(jié)合,選取了三組關(guān)鍵的指標(biāo)對實(shí)際網(wǎng)絡(luò)進(jìn)行劃分,與方法之間建立一個匹配關(guān)系,如圖2(見下頁)所示.其中,網(wǎng)絡(luò)指標(biāo)分為局域性、動態(tài)性和信息透明度,結(jié)合三者可以對實(shí)際網(wǎng)絡(luò)選取合理的方法.通?？紤]節(jié)點(diǎn)局部連接、靜態(tài)網(wǎng)絡(luò),并且網(wǎng)絡(luò)結(jié)構(gòu)已知,會選擇度分布來衡量節(jié)點(diǎn)的重要性.在對網(wǎng)絡(luò)的實(shí)證研究中,重要性的衡量標(biāo)準(zhǔn)與網(wǎng)絡(luò)實(shí)際應(yīng)用是密切相關(guān)的,很多實(shí)證網(wǎng)絡(luò)中用節(jié)點(diǎn)度和度分布來統(tǒng)計(jì)網(wǎng)絡(luò)的性質(zhì),沒有考慮應(yīng)用的要求.如人際關(guān)系網(wǎng)絡(luò)中,個體的大量連接可以凝聚較強(qiáng)的影響力,但是那些與影響力大的個體建立連接的人,因此也提升了自身的影響力,更典型的例子就是橋連接的重要性如何衡量.普通情況下,考慮算法實(shí)現(xiàn)的復(fù)雜度,如果只需要對網(wǎng)絡(luò)的節(jié)點(diǎn)屬性進(jìn)行統(tǒng)計(jì),可以采用節(jié)點(diǎn)度.介數(shù)、凝聚性是建立在最短路徑的基礎(chǔ)上,對于信息傳播、交通網(wǎng)絡(luò)及電力網(wǎng)絡(luò)等,它們都是按照最優(yōu)方案執(zhí)行,并且在出現(xiàn)堵塞的情況下,會出現(xiàn)流量的擴(kuò)散,導(dǎo)致整個網(wǎng)絡(luò)受影響,這些網(wǎng)絡(luò)中心性可以采用介數(shù)和凝聚性,他們之間的區(qū)別就在于應(yīng)用中是強(qiáng)調(diào)個體在信息傳播中承擔(dān)的信息量,還是個體對信息廣播的速度.如果實(shí)際網(wǎng)絡(luò)不需要建立在最優(yōu)方案的基礎(chǔ)上,考慮全局信息,可以選擇網(wǎng)絡(luò)流和特征向量,強(qiáng)調(diào)網(wǎng)絡(luò)中的可達(dá)性.子圖和隨機(jī)行走用于特別的實(shí)際需要,子圖將局部信息有權(quán)值擴(kuò)展到全局網(wǎng)絡(luò)中,可以應(yīng)用到社團(tuán)和蛋白質(zhì)網(wǎng)絡(luò)中衡量元素的參與程度,如表1所示.3.2節(jié)點(diǎn)度和介數(shù)盡管不同方法在對同一網(wǎng)絡(luò)進(jìn)行分析的時候可能出現(xiàn)不同的結(jié)果,但是,各種方法之間并不是完全獨(dú)立的,它們之間存在不同強(qiáng)度的關(guān)聯(lián)性.在經(jīng)典網(wǎng)絡(luò)模型中,節(jié)點(diǎn)度和介數(shù)有很強(qiáng)的關(guān)聯(lián)性,除少數(shù)橋節(jié)點(diǎn),其他節(jié)點(diǎn)序相對一致;在現(xiàn)實(shí)網(wǎng)絡(luò)的實(shí)證研究中,對蛋白質(zhì)網(wǎng)絡(luò)、科研合作網(wǎng)絡(luò)和演員合作網(wǎng)絡(luò),各種方法之間顯示了一定的關(guān)聯(lián)性,但較經(jīng)典網(wǎng)絡(luò)模型要弱.因此,實(shí)際網(wǎng)絡(luò)考察中需要綜合利用不同方法,或者提出一些相互之間轉(zhuǎn)換的機(jī)制,如將網(wǎng)絡(luò)橋節(jié)點(diǎn)按照所連接區(qū)域最大度數(shù)轉(zhuǎn)換成為其連接度,將介數(shù)統(tǒng)一到節(jié)點(diǎn)度中,既能突出特殊節(jié)點(diǎn),又能保證計(jì)算簡單.4網(wǎng)絡(luò)兩性判斷方法匹配復(fù)雜網(wǎng)絡(luò)的中心性判斷方法由于定義中對網(wǎng)絡(luò)