摘  要： 主要討論樹形網絡的平均節點介數，刻畫了樹形網絡中具有最大和最小平均節點介數的網絡。
關鍵詞： 介數；無圈網；復雜網絡

　自從20世紀30年代Radcliffe Brown提出社會網絡分析概念以來，社會網絡分析已經逐步成為一種重要的社會定量研究方法[1]。近年來，隨著計算機技術和互聯網的飛速發展，如何利用文本挖掘、機器學習等技術面向互聯網進行社會網絡挖掘和分析成為了一個新的研究課題。隨著數據挖掘技術的進步以及計算機處理能力的提高，研究者們分析的社會網絡的規模也急劇增大。這些分析和其他現實網絡分析一樣，面臨網絡節點規模巨大的挑戰。
　現實生活中存在的大量復雜系統都可以通過不同的網絡加以描述，網絡科學已成為眾多學科匯聚的交叉點。復雜網絡是近幾年科學研究發現的一種介于規則網絡和隨機網絡之間的一種更接近于真實網絡的網絡模型，錢學森給出了復雜網絡的一個較嚴格的定義：具有自組織、自相似、吸引子、小世界、無標度（無尺度）中部分或全部性質的網絡稱為復雜網絡[2]。隨著復雜網絡規模的不斷擴大，對于各個節點在整個圖中所起作用的研究變得迫切，各個節點的作用可以用介數來表示。介數既能刻畫圖中節點和邊的重要性，揭示網絡層次結構，又能用來構建基于點介數或邊介數的聚類算法，發現圖中特殊群體，因此，它一直是研究網絡結構性質的一個重要量化手段。首先對于介數的概念要有一定的了解。在復雜網絡研究中，研究者不僅要非常客觀地關注系統內個體之間的相互作用，而且還要注視系統的整體相互作用，表達這種整體相互作用的概念是介數。介數是一個全局的變量，反映節點或邊的作用和影響力，可分為節點介數（Vertex Betweenness）和邊介數（Edge Betweenness）兩種。節點介數定義為在網絡的所有最短路徑中，通過節點的最短路徑條數稱之為節點i的介數[3]；邊的介數定義為在網絡的所有最短徑經過邊的介數；網絡平均節點介數定義為網絡中所有節點介數的平均值；網絡平均邊介數指網絡中所有邊介數的平均值。節點的介數在一定程度反映的是節點在網絡中的核心作用，節點的介數越大，表明節點的核心作用越強，刪除這樣的節點會使大量節點對之間的最短路徑變長，邊的介數也有同樣的性質。
　本文主要討論樹形網絡的平均節點介數，其中節點介數是經過該節點的所有路徑，網絡平均節點介數是指所有節點介數的平均值。下面舉一個具體的例子來分析節點介數和邊介數。圖1所示中各節點與邊的介數可以分別表示如下。

　表1中的平均節點介數為4.375，平均邊介數為7.25，依據Newman[4]提出的介數新的計算機方法和Brandes算法可以更快地計算出介數。更多的介紹見參考文獻[5-7]。


1 樹形網絡中最大平均節點介數圖
　隨著復雜網絡規模的不斷增加，節點數目也在不斷地增加，對于一些冗余的節點刪除變得更加必要，這就需要對于節點的作用給出一個正確的評估，需要了解哪些圖形具有最大的平均節點介數，網絡結構可以盡可能地向這樣的結構變化。本節主要介紹具有最大平均節點介數的網絡。
　引理1  如圖2所示，N1是一棵樹，N1′是經過圖2的變換得到的，則等號成立當且僅當N1是一條路。
證明 有k個節點的圖，如圖2所示，圖N1中節點A上有p個分支，有n個節點的為分支P1，有m個節點的為分支P2。圖N1把分支P1添加到分支P2之后得到圖的N1′分支P1+P2。則節點A上變成了P-1個分支。因為分支節點介數與分支結構和總節點個數有關，現在樹形圖N1和N1′的平均節點介數B（N1）和B（N1′）中，圖N1和N1′中除了節點A，分支P1、P2及分支P1+P2的節點介數有變化，其他分支對應節點介數都沒有改變。把其他分支節點的介數之和用M表示。

　路是各個節點的度不大于2的連通的無圈圖，兩端的兩個點的度為1，中間的各個節點的度均為2。n個節點的路中兩端的兩個節點為1度的葉子節點，其介數為0。假如第i個節點的介數，i的取值范圍是1~n，各個節點的介數可以表示為（n-i）（i-1），其平均介數為：


　證明 用歸納法證明如下。
　（1）當n=4時，有4個節點的圖只有兩種形式，即路和星形圖，路的節點平均介數為1，星形圖的節點平均介數為0.75，星形圖有最小平均節點介數，成立。
　（2）假設當n<k時，星形圖有最小的平均節點介數成立。當n=k時，在樹形圖中，選擇一個度最大的點作為Hub節點，各個分支上選擇與Hub節點直接相連的點作為分支的根節點，各個分支的變化情況不影響Hub節點的介數和其他分支上節點的介數，Hub節點的介數和分支個數與分支的節點數有關，各分支的節點數不改變，只要分支不增加或者減少，則Hub節點的介數不變，各個分支上的節點不受其他分支變化的影響。因為當n<k時，星形圖有最小的節點平均介數，則各個分支都變為以分支根節點為中心的星形，各個分支有最小平均節點介數，Hub節點的介數不變。最終會有圖5所示的圖形，這種圖形與原圖相比，Hub節點的介數沒有改變，各個分支節點介數變成了最小。根據引理2可知，把分支上的所有1度點添加到Hub節點上，其總的節點介數和減少，故逐漸把1度節點添加到Hub節點上，其節點介數和一直在減少，直到Hub節點上連接的都是1度點，總的節點介數和無法再減少。可知星形圖具有最小的總節點介數和，成立。

　綜上所述，星形圖具有最小的平均節點介數，證畢。
　本文主要討論了在復雜網絡中樹形網絡的平均節點介數最大和最小的網絡，對于與之相關節點介數增加和減少給出了兩個引理，節點介數是通過該節點的路徑數。更多的介數應用和算法分析可以參考文獻[9]~[11]。
參考文獻
[1] SCOT J. Social network analysis： a handbook（2nd ed）[M]. Sage Publications， 1991.
[2] 張嗣瀛.復雜系統與復雜性科學[EB/OL].http：//news.qdu.edu.cn/newx？newsid=1514，2006-05-05.
[3] 張曉林，袁莉，楊峰，等.基于Web的個性化信息服務機制[J]. 現代圖書情報技術， 2001（1）：25-29.
[4] NEWMAN M E J. Scientific collaboration networks.II. shortest paths， weighted networks， and centrality[J]. Phys.Rev.E， 2001， 64（1）.
[5] LEWIS T G.網絡科學原理與應用[M].陳向陽，巨修紅練，譯.北京：機械工業出版社， 2011.
[6] 馬杰良，邢雪，安莉莉.基于科研合作網絡的節點樞紐特性研究[J].東北電力大學學報，2008，28（2）：72-76.
[7] Zhang Z Z， Zhou S G， Y Qi， et al. Topologies and laplacian spectra of a deterministic uniform recursive tree[J].Eur， Phys， J.B， 2008（63）：507-513.
[8] 唐晉韜，王挺.復雜社會網絡的介數性質近似計算方法研究[J].計算機工程與科學，2008，30（12）：9-14.
[9] 王小光，王鋒，李森.基于介數影響矩陣的通信網絡節點重要度評價方法[J].空軍工程大學學報，2012，13（5）：80-84.
[10] 何宇，趙洪利，姚曜，等.介數中心性和平均最短路徑長度整合近似算法[J].復雜系統與復雜性科學，2011，8（3）：44-53.
[11] 賈煒，馮登國，連一峰.基于網絡中心性的計算機網絡脆弱性評估方法[J].中國科學院研究生學報，2012，29（4）：529-535.