復(fù)雜網(wǎng)絡(luò)圖中中心性度量的應(yīng)用

復(fù)雜網(wǎng)絡(luò)圖中中心性度量的應(yīng)用

0節(jié)點(diǎn)中心性的內(nèi)涵許多現(xiàn)實(shí)世界的復(fù)雜系統(tǒng)可以用復(fù)雜的網(wǎng)絡(luò)圖來描述，如社會網(wǎng)絡(luò)、網(wǎng)絡(luò)、蛋白質(zhì)相互作用網(wǎng)絡(luò)、交換網(wǎng)絡(luò)、網(wǎng)絡(luò)等。例如，這些復(fù)雜的網(wǎng)絡(luò)節(jié)點(diǎn)在網(wǎng)絡(luò)中的角色是不同的。近年來，隨著網(wǎng)絡(luò)大規(guī)模的研究，節(jié)點(diǎn)在網(wǎng)絡(luò)中的作用的研究引起了國內(nèi)外科學(xué)家的關(guān)注?；诖耍岢隽嗽S多基于平坦背景的節(jié)點(diǎn)重要性測量方法，如度中心、介數(shù)中心、靠近中心、資源向量中心等。最簡單的基于度的度中心評估方法是描述節(jié)點(diǎn)和相鄰節(jié)點(diǎn)連接網(wǎng)絡(luò)的數(shù)量。在介數(shù)中心的情況下，節(jié)點(diǎn)或網(wǎng)絡(luò)中信息或流的控制能力取決于節(jié)點(diǎn)或網(wǎng)絡(luò)中信息或流的中心點(diǎn)。網(wǎng)絡(luò)附近的中心分析節(jié)點(diǎn)的聚集能力。資源向量中心考慮到網(wǎng)絡(luò)中目標(biāo)節(jié)點(diǎn)的重要性，并確定節(jié)點(diǎn)附近網(wǎng)絡(luò)的重要性，以便確定目標(biāo)節(jié)點(diǎn)的狀態(tài)。通過研究節(jié)點(diǎn)的中心性，我們可以發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)圖中的重要節(jié)點(diǎn)，如社會網(wǎng)絡(luò)的主節(jié)點(diǎn)和通信網(wǎng)絡(luò)中信息傳播的重要節(jié)點(diǎn)。利用節(jié)點(diǎn)中心性度量方法可以計算每個節(jié)點(diǎn)的中心性值,節(jié)點(diǎn)的中心性值較大的節(jié)點(diǎn)較為重要,具有較大的影響力.但是如果一個節(jié)點(diǎn)距離中心性值大的節(jié)點(diǎn)的距離很遠(yuǎn),該節(jié)點(diǎn)受它的某個鄰近節(jié)點(diǎn)的影響可能比受中心性值大的節(jié)點(diǎn)的影響更大.因此網(wǎng)絡(luò)中存在一些具有較大的局部影響力的節(jié)點(diǎn).通過研究復(fù)雜網(wǎng)絡(luò)圖的中心節(jié)點(diǎn)的分布,提出了節(jié)點(diǎn)的局部中心性分析方法,通過局部中心性分析可以找到具有較大局部影響力的節(jié)點(diǎn),這些節(jié)點(diǎn)也是復(fù)雜網(wǎng)絡(luò)圖的重要節(jié)點(diǎn).1節(jié)點(diǎn)中心性的影響研究的復(fù)雜網(wǎng)絡(luò)是無向無權(quán)圖.設(shè)復(fù)雜網(wǎng)絡(luò)圖G=<V,E>,V={v1,v2…vn}是圖G的頂點(diǎn)集,E={e1,e2…en}為圖G的邊集.復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)重要性可以通過節(jié)點(diǎn)的中心性度量,節(jié)點(diǎn)中心性度量有以下方法:度中心性(DegreeCentrality)Cd(vi)=Deg(vi)其中Deg(vi)是頂點(diǎn)vi的度數(shù).當(dāng)節(jié)點(diǎn)vi的度中心度的值越大,這個節(jié)點(diǎn)和其他節(jié)點(diǎn)連接的邊越多,這個節(jié)點(diǎn)能影響的節(jié)點(diǎn)越多.接近中心性(ClosenessCentrality):Cc(vi)=n?1∑j=1ngd(vi,vj)Cc(vi)=n-1∑j=1ngd(vi,vj)其中g(shù)d(vi,vj)是vi到vj的最短距離,n是頂點(diǎn)的個數(shù).接近中心性說明節(jié)點(diǎn)對網(wǎng)絡(luò)中其他節(jié)點(diǎn)的影響力.例如在社會網(wǎng)絡(luò)中,一個節(jié)點(diǎn)和另一個節(jié)點(diǎn)有邊相連,說明這兩個人有朋友關(guān)系.因此,如果一個人能夠把信息在最短時間內(nèi)傳遞給其他所有人(包括自己的朋友和朋友的朋友),則說明這個人在這群人中的影響力最大;接近中心性與節(jié)點(diǎn)vi傳送信息到其他所有節(jié)點(diǎn)的用時總和成反比,即接近中心性越大,用時越小,該節(jié)點(diǎn)的地位更高.介數(shù)中心性(BetweennessCentrality)Cb(vi)=∑j≠i≠kσjk(vi)σjkCb(vi)=∑j≠i≠kσjk(vi)σjk其中σjk是從vj到vk的最短路徑的數(shù)量,σjk(vi)是從vj到vk的最短路徑中經(jīng)過vi的最短路徑的數(shù)量.中間中心性說明節(jié)點(diǎn)對網(wǎng)絡(luò)中信息流動的影響力.一個節(jié)點(diǎn)的中間中心性值越大,通過該節(jié)點(diǎn)的最短路徑的數(shù)目越大.如在一個無向星型圖中,一個中心頂點(diǎn)的中間中心度為1,每一對節(jié)點(diǎn)間的最短路徑都通過這個中心節(jié)點(diǎn);葉結(jié)點(diǎn)的中間中心度為0,不包含在任何一條最短路徑中.此外,度量節(jié)點(diǎn)重要性的方法還有:特征向量中心性等.2復(fù)雜網(wǎng)絡(luò)的中心節(jié)點(diǎn)2.1中心節(jié)點(diǎn)的網(wǎng)絡(luò)圖分布將所有節(jié)點(diǎn)按照頂點(diǎn)的中心性度量從大到小進(jìn)行排序,則前k個節(jié)點(diǎn)為全局中心點(diǎn).比如,將所有節(jié)點(diǎn)按照度中心性從大到小進(jìn)行排序,前k個節(jié)點(diǎn)為全局度中心點(diǎn).文獻(xiàn)指出在復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)間的連接呈現(xiàn)兩種情況:同配性和異配性.同配性是度數(shù)大的節(jié)點(diǎn)傾向于和度數(shù)大的節(jié)點(diǎn)連接,異配性是度數(shù)大的節(jié)點(diǎn)傾向于和度數(shù)小的節(jié)點(diǎn)連接.相關(guān)研究表明,技術(shù)網(wǎng)絡(luò)一般是異配的,而社會網(wǎng)絡(luò)通常是同配的.因此,如果圖中度數(shù)大的節(jié)點(diǎn)大多和度數(shù)小的節(jié)點(diǎn)連接,前k個度數(shù)大的全局中心節(jié)點(diǎn)在網(wǎng)絡(luò)圖上的分布較為分散;如果圖中度數(shù)大的節(jié)點(diǎn)大多和度數(shù)大的節(jié)點(diǎn)連接,前k個度數(shù)大的全局中心節(jié)點(diǎn)在網(wǎng)絡(luò)圖上的分布較為集中;所以,異配性網(wǎng)絡(luò)的全局中心點(diǎn)在網(wǎng)絡(luò)圖上的分布較分散,同配型網(wǎng)絡(luò)的全局中心節(jié)點(diǎn)在網(wǎng)絡(luò)圖上的分布較為集中.在一些真實(shí)的復(fù)雜網(wǎng)絡(luò)圖和合成復(fù)雜網(wǎng)絡(luò)圖上研究了全局中心節(jié)點(diǎn)的分布.真實(shí)的復(fù)雜網(wǎng)絡(luò)圖包括:空手道數(shù)據(jù)集、Politicalbook數(shù)據(jù)集、dolphins數(shù)據(jù)集、Football數(shù)據(jù)集.前k個全局中心節(jié)點(diǎn)的分布見圖1.從圖1中可以看出,空手道數(shù)據(jù)集的前3個全局中心點(diǎn),有兩個是連接的,dolphins數(shù)據(jù)集中的前5個全局中心點(diǎn)(著綠色和黃色的節(jié)點(diǎn))較為集中.進(jìn)行實(shí)驗(yàn)的這些復(fù)雜網(wǎng)絡(luò)具有社區(qū)結(jié)構(gòu).復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)是指整個網(wǎng)絡(luò)是由若干個“群”構(gòu)成的,每個群內(nèi)部的節(jié)點(diǎn)之間的連接較為緊密,但是各個群之間的連接比較稀疏,如圖1所示,不同形狀的節(jié)點(diǎn)表示不同的社區(qū).從圖上的全局度中心節(jié)點(diǎn)的分布可以看出,在Politicalbook數(shù)據(jù)集、dolphins數(shù)據(jù)集上,全局中心節(jié)點(diǎn)都集中在一個社區(qū)里,另外一個社區(qū)沒有全局中心節(jié)點(diǎn),在沒有全局中心點(diǎn)的社區(qū)中的節(jié)點(diǎn)距離全局中心點(diǎn)較遠(yuǎn),它們受周圍距離較近的節(jié)點(diǎn)的影響要比受全局中心節(jié)點(diǎn)的影響大.2.2局部度中心點(diǎn)分散在復(fù)雜網(wǎng)絡(luò)圖上,節(jié)點(diǎn)的中心性度量值存在最大值,也存在一些極大值,即存在一些節(jié)點(diǎn),它們的中心性度量值大于等于它的所有鄰居節(jié)點(diǎn).這樣的節(jié)點(diǎn)比它的所有鄰居節(jié)點(diǎn)的都重要.如一個節(jié)點(diǎn)的度數(shù)比它的鄰居節(jié)點(diǎn)的度數(shù)都大,則這個節(jié)點(diǎn)的影響力比它的鄰居節(jié)點(diǎn)的影響力都大.這樣的節(jié)點(diǎn)就是具有較大局部影響力的節(jié)點(diǎn).把這種具有較大局部影響力的節(jié)點(diǎn)稱為局部中心點(diǎn).定義當(dāng)一個節(jié)點(diǎn)的中心性度量值不小于它的所有鄰居節(jié)點(diǎn)的中心性度量值時,稱該節(jié)點(diǎn)為圖的一個局部中心點(diǎn).當(dāng)用度中心度來去度量節(jié)點(diǎn)重要性時,局部中心點(diǎn)是局部度中心點(diǎn),它的度數(shù)大于等于它的所有鄰居節(jié)點(diǎn)的度數(shù).局部度中心點(diǎn)也可稱為極大度數(shù)頂點(diǎn),因?yàn)楹驮摴?jié)點(diǎn)鄰接的節(jié)點(diǎn)的度數(shù)都不大于該節(jié)點(diǎn)的度數(shù).圖2著紅色和黃色的節(jié)點(diǎn)是局部度中心點(diǎn).圖3中著紅色的節(jié)點(diǎn)是局部度中心點(diǎn).從圖2和圖3可以看出,局部度中心點(diǎn)分散分布在復(fù)雜網(wǎng)絡(luò)中.局部中心點(diǎn)具有如下兩個特性:特性1在圖G中,節(jié)點(diǎn)vi和節(jié)點(diǎn)vj是兩個局部中心點(diǎn),C(vi)是節(jié)點(diǎn)vi的中心性度量值,若C(vi)≠C(vj),則節(jié)點(diǎn)vi和節(jié)點(diǎn)vj不相鄰.證明用反證法證明.假設(shè)節(jié)點(diǎn)vj和節(jié)點(diǎn)vi相鄰.因?yàn)楣?jié)點(diǎn)vi是局部中心點(diǎn),C(vi)大于它的所有鄰居節(jié)點(diǎn)的中心性度量值,因此C(vi)≥C(vj).因?yàn)镃(vi)≠C(vj),所以C(vi)>C(vj),根據(jù)局部中心點(diǎn)定義,節(jié)點(diǎn)vj不是局部中心點(diǎn).和節(jié)點(diǎn)vj是局部中心點(diǎn)矛盾.特性2復(fù)雜網(wǎng)絡(luò)圖的局部中心點(diǎn)的數(shù)目是一確定值.由特性1,局部中心點(diǎn)分散分布在復(fù)雜網(wǎng)絡(luò)中,如果兩個局部中心點(diǎn)相鄰,則它們的度數(shù)一定相同.按照節(jié)點(diǎn)中心性度量值排序得到的全局中心節(jié)點(diǎn)是可能集中分布,互相連接的,這時這些節(jié)點(diǎn)的影響力局限在這部分區(qū)域,用這些排序靠前的節(jié)點(diǎn)作為網(wǎng)絡(luò)圖的重要節(jié)點(diǎn),實(shí)際上沒有反映出網(wǎng)絡(luò)圖的其他部分的重要節(jié)點(diǎn).局部中心點(diǎn)分散分布在復(fù)雜網(wǎng)絡(luò)中,可以反映出復(fù)雜網(wǎng)絡(luò)中各處的具有較大影響力的節(jié)點(diǎn),所以局部中心點(diǎn)也是網(wǎng)絡(luò)圖中的重要節(jié)點(diǎn).對于異配性網(wǎng)絡(luò),度數(shù)大的節(jié)點(diǎn)之間很少連接,局部中心點(diǎn)通常也可能就是全局中心點(diǎn),如空手道數(shù)據(jù)集上的兩個局部度中心點(diǎn)也是前2個全局中心點(diǎn).對于同配性網(wǎng)絡(luò),中心度值大的節(jié)點(diǎn)不一定是局部中心點(diǎn).根據(jù)節(jié)點(diǎn)中心性度量值排序,前k個全局中心點(diǎn)作為網(wǎng)絡(luò)的重要節(jié)點(diǎn),要找到分布在網(wǎng)絡(luò)各處的重要節(jié)點(diǎn),k的合適取值較難確定.局部中心點(diǎn)分散分布在網(wǎng)絡(luò)各處且數(shù)目一定,找到全部的局部中心點(diǎn),就是分散在圖中各處的重要節(jié)點(diǎn).同理,用接近中心性和中間中心性度量節(jié)點(diǎn)重要性時,就有局部接近中心點(diǎn)和局部介數(shù)中心點(diǎn).3局部中心節(jié)點(diǎn)社區(qū)數(shù)在LFR合成數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)研究局部中心點(diǎn)的分布,分析局部中心點(diǎn)的分布和社區(qū)的關(guān)系.合成數(shù)據(jù)有200個節(jié)點(diǎn),9個社區(qū).表1給出了局部中心點(diǎn)和全局中心點(diǎn)在9個社區(qū)中的分布情況,這里取和社區(qū)個數(shù)相同的全局中心點(diǎn),即k=9.實(shí)際上,真實(shí)網(wǎng)絡(luò)的社區(qū)個數(shù)通常是未知的,所以k的取值較難確定.根據(jù)對真實(shí)復(fù)雜網(wǎng)絡(luò)(如圖2所示)和合成復(fù)雜網(wǎng)絡(luò)(如圖3所示)的研究,可以看出,全局中心點(diǎn)的分布有時較為集中,如表中所示,全局中心點(diǎn)有些集中分布在一個社區(qū),而局部中心節(jié)點(diǎn)較為分散分布在各個社區(qū)中.這里選取了9個全局中心點(diǎn),實(shí)際上,很難預(yù)先知道多少個全局中心點(diǎn)就是分布在網(wǎng)絡(luò)中各處的重要節(jié)點(diǎn),如表1,選取前9個全局中心點(diǎn)時,有4個社區(qū)沒有全局度中心點(diǎn),有3個社區(qū)沒有介數(shù)中心點(diǎn),有5個社區(qū)沒有接近中心點(diǎn).局部介數(shù)中心點(diǎn)數(shù)和局部接近中心點(diǎn)數(shù)小于局部度中心點(diǎn)數(shù),局部度中心節(jié)點(diǎn)數(shù)最接近社區(qū)數(shù).深入研究局部中心節(jié)點(diǎn)和社區(qū)結(jié)構(gòu)的關(guān)系對于社區(qū)結(jié)構(gòu)發(fā)現(xiàn)將具有重要意義.4局部中心節(jié)點(diǎn).基于局部中心節(jié)點(diǎn).在復(fù)雜網(wǎng)絡(luò)圖中,不同的節(jié)點(diǎn)的作用和的重要程度不同.節(jié)點(diǎn)的中心