復雜網絡圖中中心性度量的應用

復雜網絡圖中中心性度量的應用

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