摘  要： 主要討論樹形網(wǎng)絡(luò)的平均節(jié)點介數(shù)，刻畫了樹形網(wǎng)絡(luò)中具有最大和最小平均節(jié)點介數(shù)的網(wǎng)絡(luò)。
關(guān)鍵詞： 介數(shù)；無圈網(wǎng)；復(fù)雜網(wǎng)絡(luò)

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

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


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

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


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

　綜上所述，星形圖具有最小的平均節(jié)點介數(shù)，證畢。
　本文主要討論了在復(fù)雜網(wǎng)絡(luò)中樹形網(wǎng)絡(luò)的平均節(jié)點介數(shù)最大和最小的網(wǎng)絡(luò)，對于與之相關(guān)節(jié)點介數(shù)增加和減少給出了兩個引理，節(jié)點介數(shù)是通過該節(jié)點的路徑數(shù)。更多的介數(shù)應(yīng)用和算法分析可以參考文獻(xiàn)[9]~[11]。
參考文獻(xiàn)
[1] SCOT J. Social network analysis： a handbook（2nd ed）[M]. Sage Publications， 1991.
[2] 張嗣瀛.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)[EB/OL].http：//news.qdu.edu.cn/newx？newsid=1514，2006-05-05.
[3] 張曉林，袁莉，楊峰，等.基于Web的個性化信息服務(wù)機制[J]. 現(xiàn)代圖書情報技術(shù)， 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.網(wǎng)絡(luò)科學(xué)原理與應(yīng)用[M].陳向陽，巨修紅練，譯.北京：機械工業(yè)出版社， 2011.
[6] 馬杰良，邢雪，安莉莉.基于科研合作網(wǎng)絡(luò)的節(jié)點樞紐特性研究[J].東北電力大學(xué)學(xué)報，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] 唐晉韜，王挺.復(fù)雜社會網(wǎng)絡(luò)的介數(shù)性質(zhì)近似計算方法研究[J].計算機工程與科學(xué)，2008，30（12）：9-14.
[9] 王小光，王鋒，李森.基于介數(shù)影響矩陣的通信網(wǎng)絡(luò)節(jié)點重要度評價方法[J].空軍工程大學(xué)學(xué)報，2012，13（5）：80-84.
[10] 何宇，趙洪利，姚曜，等.介數(shù)中心性和平均最短路徑長度整合近似算法[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2011，8（3）：44-53.
[11] 賈煒，馮登國，連一峰.基于網(wǎng)絡(luò)中心性的計算機網(wǎng)絡(luò)脆弱性評估方法[J].中國科學(xué)院研究生學(xué)報，2012，29（4）：529-535.