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

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

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


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

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


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

　綜上所述，星形圖具有最小的平均節(jié)點(diǎn)介數(shù)，證畢。
　本文主要討論了在復(fù)雜網(wǎng)絡(luò)中樹形網(wǎng)絡(luò)的平均節(jié)點(diǎn)介數(shù)最大和最小的網(wǎng)絡(luò)，對(duì)于與之相關(guān)節(jié)點(diǎn)介數(shù)增加和減少給出了兩個(gè)引理，節(jié)點(diǎn)介數(shù)是通過該節(jié)點(diǎn)的路徑數(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的個(gè)性化信息服務(wù)機(jī)制[J]. 現(xiàn)代圖書情報(bào)技術(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].陳向陽，巨修紅練，譯.北京：機(jī)械工業(yè)出版社， 2011.
[6] 馬杰良，邢雪，安莉莉.基于科研合作網(wǎng)絡(luò)的節(jié)點(diǎn)樞紐特性研究[J].東北電力大學(xué)學(xué)報(bào)，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ù)雜社會(huì)網(wǎng)絡(luò)的介數(shù)性質(zhì)近似計(jì)算方法研究[J].計(jì)算機(jī)工程與科學(xué)，2008，30（12）：9-14.
[9] 王小光，王鋒，李森.基于介數(shù)影響矩陣的通信網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)價(jià)方法[J].空軍工程大學(xué)學(xué)報(bào)，2012，13（5）：80-84.
[10] 何宇，趙洪利，姚曜，等.介數(shù)中心性和平均最短路徑長度整合近似算法[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2011，8（3）：44-53.
[11] 賈煒，馮登國，連一峰.基于網(wǎng)絡(luò)中心性的計(jì)算機(jī)網(wǎng)絡(luò)脆弱性評(píng)估方法[J].中國科學(xué)院研究生學(xué)報(bào)，2012，29（4）：529-535.