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

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

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