復(fù)雜網(wǎng)絡(luò)中新指標-潛數(shù)的設(shè)計與分析

1、復(fù)雜網(wǎng)絡(luò)中新指標-潛數(shù)的設(shè)計與分析摘 要：依據(jù)度信息和節(jié)點連接關(guān)系構(gòu)造出復(fù)雜網(wǎng)絡(luò)的新指標-潛數(shù)，闡述了節(jié)點的先導(dǎo)潛數(shù)和后導(dǎo)潛數(shù)對網(wǎng)絡(luò)節(jié)點影響力的刻畫作用，通過實驗分析了先導(dǎo)潛數(shù)、后導(dǎo)潛數(shù)、網(wǎng)絡(luò)潛數(shù)與網(wǎng)絡(luò)其他基本指標的關(guān)系，以及先導(dǎo)潛數(shù)的分布特征。實驗展示了基于先導(dǎo)潛數(shù)和基于度的兩種節(jié)點刪除策略對網(wǎng)絡(luò)摧毀程度的作用效果，反映了基于先導(dǎo)潛數(shù)刪除策略的優(yōu)越性。最后計算了BA網(wǎng)絡(luò)、WS網(wǎng)絡(luò)、NW網(wǎng)絡(luò)的網(wǎng)絡(luò)潛數(shù)，結(jié)果表明網(wǎng)絡(luò)潛數(shù)可作為網(wǎng)絡(luò)中特有的穩(wěn)定網(wǎng)絡(luò)特征之一。關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；影響力；指標；潛數(shù)中圖分類號：O231 文獻標志碼：ADesign and Analysis of Complex netw

2、orks New Index-LanerRen Wei-ya1(1 College of Information System and Management, National University of Defense Technology,Changsha,410073,China)Abstract: A new complex networks indexLaner is constructed based on degree information and nodes connection. The paper explained the network's node'

3、s influence which described by ex-lanner and post-lanner. Through experiments，we analyzed the relationship between ex-lanner，post-lanner，network-lanner and other networks basic index，and we analyzed the ex-lanner's distribution character as well. Experiments reflected the network been destructed

4、 effect under two node delete strategies-node degree based and node ex-lanner based, the result illuminated the superiority of ex-lanner based strategy. Finally we computed the BA network,WS network and NW network's network-lanner, and the outcomes revealed the network-lanner has been one of the

5、 own steady network character in networks. Keywords: Complex network; influence; Index; Lanner0 引 言復(fù)雜網(wǎng)絡(luò)的小世界特征Error! Reference source not found.和無標度性質(zhì)Error! Reference source not found.的發(fā)現(xiàn)，使得復(fù)雜網(wǎng)絡(luò)的的研究進入了一個新的高潮，經(jīng)歷十余年的發(fā)展，復(fù)雜網(wǎng)絡(luò)已經(jīng)逐步走向了成熟并越來越引人注目，甚至被一些學(xué)者稱為“網(wǎng)絡(luò)的新科學(xué)”Error! Reference source not found.。復(fù)雜網(wǎng)絡(luò)的一系列指標

6、逐漸幫助人們揭開它神秘的面紗。多數(shù)復(fù)雜網(wǎng)絡(luò)的指標都是基于網(wǎng)絡(luò)連接圖進行構(gòu)造，節(jié)點和節(jié)點之間可以通過不同的路徑到達，而網(wǎng)絡(luò)中一個節(jié)點也不可避免地和周圍的節(jié)點具有相互影響關(guān)系。本文基于復(fù)雜網(wǎng)絡(luò)中節(jié)點相互連接關(guān)系構(gòu)造了新的統(tǒng)計指標，實驗證明依據(jù)潛數(shù)的攻擊策略比依據(jù)度的攻擊策略對網(wǎng)絡(luò)的毀傷性更大。1 潛 數(shù)1.1 潛數(shù)定義潛數(shù)描述的是節(jié)點之間的相互關(guān)系，假定在一個復(fù)雜網(wǎng)絡(luò)中進行信息傳遞，任一個節(jié)點到達其所有鄰居節(jié)點的概率都是該節(jié)點度的倒數(shù)，于是任意兩節(jié)點之間存在一個最大到達概率，定義：1,一個節(jié)點對自身的潛數(shù)是0，記為；2,節(jié)點i到節(jié)點j的最大到達概率為節(jié)點i對節(jié)點j的潛數(shù)，記為；3,節(jié)點i對網(wǎng)絡(luò)所有

7、節(jié)點的潛數(shù)之和為節(jié)點i的先導(dǎo)潛數(shù)，記為；4,網(wǎng)絡(luò)所有節(jié)點對節(jié)點j的潛數(shù)之和為節(jié)點j的后導(dǎo)潛數(shù)，記為；5,所有節(jié)點的先（后）導(dǎo)潛數(shù)之和除以網(wǎng)絡(luò)節(jié)點數(shù)目(N)為網(wǎng)絡(luò)的網(wǎng)絡(luò)潛數(shù)，記為。節(jié)點先導(dǎo)潛數(shù)的計算過程，實際上是一個信息從自身出發(fā)向外傳遞的過程，節(jié)點的先導(dǎo)潛數(shù)反映的是一個節(jié)點對網(wǎng)絡(luò)中其他節(jié)點的影響力；節(jié)點后導(dǎo)潛數(shù)的計算過程，實際上是一個信息從外界輸入自身的過程，節(jié)點的后導(dǎo)潛數(shù)則反映了網(wǎng)絡(luò)中其他節(jié)點對某個節(jié)點所產(chǎn)生的影響力。潛數(shù)和節(jié)點之間的最短路徑并不相同，節(jié)點i到節(jié)點j的潛數(shù)為二者的最大到達概率，而到達概率和節(jié)點度又有著直接關(guān)系，所以在最大到達概率路徑上并不等于最短路徑。1.2 潛數(shù)特點通過分析

8、特殊網(wǎng)絡(luò)（星型網(wǎng)絡(luò)和環(huán)形網(wǎng)路）發(fā)現(xiàn)：在沒有孤立節(jié)點的網(wǎng)絡(luò)中，先導(dǎo)潛數(shù)和后導(dǎo)潛數(shù)的取值范圍分別為：，。由于概率的累積性，某個節(jié)點的先導(dǎo)潛數(shù)受一定局部區(qū)域內(nèi)的節(jié)點影響最大。某節(jié)點的先導(dǎo)潛數(shù)越小則說明該節(jié)點對其周圍節(jié)點的影響力越大；某節(jié)點的后導(dǎo)潛數(shù)越小，表明其周圍節(jié)點對該節(jié)點的影響力越小。例如，星型網(wǎng)絡(luò)中心節(jié)點的先導(dǎo)潛數(shù)達到了1，則說明該節(jié)點對網(wǎng)絡(luò)其余節(jié)點產(chǎn)生了所能產(chǎn)生的最大影響力；同時，中心節(jié)點的后導(dǎo)潛數(shù)正比于網(wǎng)絡(luò)規(guī)模，說明其受到的外界影響力很大，而邊緣節(jié)點的后導(dǎo)潛數(shù)為1，說明這些節(jié)點所受到的影響力已經(jīng)到達了最小。由于先（后）導(dǎo)潛數(shù)的取值范圍，易知在沒有孤立節(jié)點的網(wǎng)絡(luò)中，網(wǎng)絡(luò)的網(wǎng)絡(luò)潛數(shù)不小于1，網(wǎng)

9、絡(luò)潛數(shù)可以理解為網(wǎng)絡(luò)節(jié)點的平均影響力或者是平均受影響力。選取復(fù)雜網(wǎng)絡(luò)中幾種經(jīng)典的網(wǎng)絡(luò)進行潛數(shù)分析，即：BA網(wǎng)絡(luò)Error! Reference source not found.，WS網(wǎng)絡(luò)Error! Reference source not found.、NW網(wǎng)絡(luò)Error! Reference source not found.和ER隨機圖Error! Reference source not found.。分析發(fā)現(xiàn)：先導(dǎo)潛數(shù)與節(jié)點度的關(guān)系和網(wǎng)絡(luò)類型有關(guān)，如在BA網(wǎng)絡(luò)中是冪律關(guān)系，在WS網(wǎng)絡(luò)中是無關(guān)的，在NW網(wǎng)絡(luò)中是負線性相關(guān)關(guān)系；后導(dǎo)潛數(shù)與節(jié)點度一直呈正相關(guān)關(guān)系。實驗發(fā)現(xiàn)，網(wǎng)絡(luò)潛數(shù)與聚類

10、系數(shù)呈負相關(guān)關(guān)系，與平均路徑長度呈正相關(guān)關(guān)系，但網(wǎng)絡(luò)潛數(shù)與同配系數(shù)Error! Reference source not found.是無關(guān)的。1.2.1 先導(dǎo)潛數(shù)分布先導(dǎo)潛數(shù)的分布和網(wǎng)絡(luò)類型等因素有關(guān)，如在BA網(wǎng)絡(luò)中是Weibull分布，在NW網(wǎng)絡(luò)中是正態(tài)分布，WS網(wǎng)絡(luò)中當重連概率p較小時(如0.05)服從指數(shù)分布（的Weibull分布），當重連概率p較大時(實驗表明大于0.1)，服從正態(tài)分布。在BA網(wǎng)絡(luò)中先導(dǎo)潛數(shù)均有良好的Weibull分布趨勢。圖1為m=2，n=1000（其中n為網(wǎng)絡(luò)規(guī)模，m為網(wǎng)絡(luò)增長時新節(jié)點連接的節(jié)點個數(shù)）的BA網(wǎng)絡(luò)中先導(dǎo)潛數(shù)分布直方圖。在WS網(wǎng)絡(luò)中，重連概率p較小時有

11、良好的指數(shù)分布趨勢。圖2為p=0.05，n=1 000的WS網(wǎng)絡(luò)中先導(dǎo)潛數(shù)分布直方圖。在WS網(wǎng)絡(luò)中p較大（p>0.1）時先導(dǎo)潛數(shù)均有良好的正態(tài)分布趨勢。圖3為p=0.2，n=1000時WS網(wǎng)絡(luò)中先導(dǎo)潛數(shù)分布直方圖。在NW網(wǎng)絡(luò)中，先導(dǎo)潛數(shù)均有良好的正態(tài)分布趨勢（與p無關(guān)）。圖4為p=0.2，n=1000時NW網(wǎng)絡(luò)中先導(dǎo)潛數(shù)分布直方圖。圖1 BA網(wǎng)絡(luò)先導(dǎo)潛數(shù)密度直方圖,m=2,n=1 000圖2 WS網(wǎng)絡(luò)先導(dǎo)潛數(shù)密度直方圖,p=0.05,n=1 000圖3 WS網(wǎng)絡(luò)先導(dǎo)潛數(shù)密度直方圖,p=0.2,n=1 000圖4 NW網(wǎng)絡(luò)先導(dǎo)潛數(shù)密度直方圖，p=0.2,n=1 000以上各網(wǎng)絡(luò)密度分布的m

12、atlab檢驗曲線都接近直線，說明樣本數(shù)據(jù)較符合分布假設(shè)。1.2.2先（后）導(dǎo)潛數(shù)與節(jié)點度的相關(guān)性先導(dǎo)、后導(dǎo)潛數(shù)與節(jié)點度的相關(guān)系數(shù)(試驗平均值)如表1、2。后導(dǎo)潛數(shù)普遍與節(jié)點度有很好的線性正相關(guān)性；先導(dǎo)潛數(shù)則不然，如在WS網(wǎng)絡(luò)中，先導(dǎo)潛數(shù)和度呈現(xiàn)出很弱的相關(guān)性。表 1先導(dǎo)潛數(shù)與節(jié)點度相關(guān)系數(shù)n=200n=500n=1 000BA網(wǎng)絡(luò),m=2-0.772 2-0.616 6-0.696 8BA網(wǎng)絡(luò),m=1-0.486 9-0.465 0-0.482 8WS網(wǎng)絡(luò),p=0.3-0.331 9-0.204 9-0.206 9WS網(wǎng)絡(luò),p=0.05-0.053 3-0.162 9-0.134 5NW網(wǎng)絡(luò)

13、,p=0.2-0.986 3-0.983 0-0.985 7NW網(wǎng)絡(luò)p=0.05-0.955 6-0.966 9-0.983 5ER隨機網(wǎng)絡(luò)-0.950 2-0.953 7-0.958 7表 2后導(dǎo)潛數(shù)與節(jié)點度相關(guān)系數(shù)n=200n=500n=1 000BA網(wǎng)絡(luò),m=20.988 50.992 90.994 5BA網(wǎng)絡(luò),m=11.000 01.000 01.000 0WS網(wǎng)絡(luò),p=0.30.865 20.911 50.895 7WS網(wǎng)絡(luò),p=0.050.810 60.701 70.710 2NW網(wǎng)絡(luò),p=0.20.995 30.997 90.999 1NW網(wǎng)絡(luò)p=0.050.973 70.987

14、 30.994 8ER隨機網(wǎng)絡(luò)0.984 70.993 60.996 62 復(fù)雜網(wǎng)絡(luò)的潛數(shù)分析2.1網(wǎng)絡(luò)抗毀性分析中的節(jié)點刪除策略我們往往關(guān)心如何以最快的方式摧毀一個網(wǎng)絡(luò)，本節(jié)依據(jù)刪除策略逐個刪除網(wǎng)絡(luò)中的節(jié)點，并同步計算網(wǎng)絡(luò)所有連通子圖大小的和，和網(wǎng)絡(luò)的聚類系數(shù)。以網(wǎng)絡(luò)所有連通子圖的大小和來作為網(wǎng)絡(luò)被摧毀程度的評判標準之一，而不是采用最大連通子圖大小，是因為這樣可以更好地反映出網(wǎng)絡(luò)被摧毀的整體效果。我們采用2種節(jié)點刪除策略進行對比：方案1,基于節(jié)點度依次刪除網(wǎng)絡(luò)中的節(jié)點，即依次去除網(wǎng)絡(luò)中度最大的節(jié)點，如果度最大的節(jié)點不唯一，則隨機選取一個。方案2,基于節(jié)點先導(dǎo)潛數(shù)（節(jié)點影響力）依次刪除網(wǎng)絡(luò)中的

15、節(jié)點，即依次去除網(wǎng)絡(luò)中先導(dǎo)潛數(shù)最小的節(jié)點，如果先導(dǎo)潛數(shù)最小的節(jié)點不唯一，則隨機選取一個。根據(jù)上一小節(jié)中先導(dǎo)潛數(shù)與度的相關(guān)性，選取二者相關(guān)性很低的WS網(wǎng)絡(luò)(n=500，p=0.2)作為實驗網(wǎng)路，以反映兩種方案的優(yōu)劣。相比于依據(jù)節(jié)點度的刪除策略，依據(jù)節(jié)點影響力的刪除策略，使得網(wǎng)絡(luò)所有連通子圖大小之和下降的更快，網(wǎng)絡(luò)的聚類系數(shù)也下降的更快，這說明依據(jù)節(jié)點先導(dǎo)潛數(shù)的刪除策略使摧毀網(wǎng)絡(luò)的效果更好。即依次刪除影響力最大的節(jié)點，會使網(wǎng)絡(luò)的整體性遭到更快的破壞。網(wǎng)絡(luò)所有連通子圖大小之和與刪除步驟關(guān)系如圖5。網(wǎng)絡(luò)聚類系數(shù)與刪除步驟關(guān)系如圖6。圖 5 網(wǎng)絡(luò)所有聯(lián)通子圖大小之和與刪除步驟關(guān)系圖，橫坐標為刪除步驟，縱

16、坐標為所有連通子圖大小和；方形為度刪除策略，加形為先導(dǎo)潛數(shù)刪除策略。圖 6網(wǎng)絡(luò)聚類系數(shù)與刪除步驟關(guān)系圖，橫坐標為刪除步驟，縱坐標為聚類系數(shù)；方形為度刪除策略，加形為先導(dǎo)潛數(shù)刪除策略。2.2 BA,WS,NW網(wǎng)絡(luò)的網(wǎng)絡(luò)潛數(shù)分析實驗分析了BA網(wǎng)絡(luò)（新節(jié)點與2個老節(jié)點相連，即m=2）的網(wǎng)絡(luò)節(jié)點數(shù)目n從1取到200時網(wǎng)絡(luò)潛數(shù)PLN的變化情況，其網(wǎng)絡(luò)潛數(shù)隨著網(wǎng)絡(luò)規(guī)模的增大，呈對數(shù)形式緩慢上升，如圖7。另外當n=500時，PLN=2.45，n=1 000時，PLN=2.617。同樣分析了NW網(wǎng)絡(luò)（初始網(wǎng)絡(luò)中每個節(jié)點與最近2個節(jié)點相連，即K=4）的網(wǎng)絡(luò)節(jié)點數(shù)目n從1取到200時PLN的變化情況，PLN隨著n

17、的增大，呈 Rayleigh 分布上升后緩慢下降并趨向于1，如圖8，matlab的分布檢驗曲線趨于直線。另外當n=500時，PLN=1.010 9，n=1000時，PLN=1.005 5。在WS網(wǎng)絡(luò)（K=4）中，n從1取到200時網(wǎng)絡(luò)潛數(shù)的變化情況如圖9，PLN隨著n的增大，呈對數(shù)形式緩慢上升，另外當n =500時，PLN=1.979，n=1000時，PLN =2.037。NW網(wǎng)絡(luò)中，連接概率p增大的過程，就是從局部耦合到全局耦合的過程，這個過程對網(wǎng)絡(luò)潛數(shù)產(chǎn)生的影響如圖10，p取0.05、0.075、0.1、0.2、0.3、1時，網(wǎng)絡(luò)潛數(shù)隨著重連概率p的減少呈整體下降趨勢，p=1時網(wǎng)絡(luò)潛數(shù)達到

18、最小值，即PLN=1。在WS網(wǎng)絡(luò)中，重連概率p減小時，網(wǎng)絡(luò)潛數(shù)PLN整體呈下降趨勢，p取0、0.05、0.1、0.2、0.3，0.5時，對于潛數(shù)的影響如圖11。圖 7 BA網(wǎng)絡(luò)的網(wǎng)絡(luò)潛數(shù)走勢圖，橫坐標為網(wǎng)絡(luò)節(jié)點數(shù)目，縱坐標為網(wǎng)絡(luò)潛數(shù)。圖 8 NW網(wǎng)絡(luò)的網(wǎng)絡(luò)潛數(shù)走勢圖，連接概率p=0.2,橫坐標為網(wǎng)絡(luò)節(jié)點數(shù)目，縱坐標為網(wǎng)絡(luò)潛數(shù)。圖 9 WS網(wǎng)絡(luò)的網(wǎng)絡(luò)潛數(shù)走勢圖，重連概率p=0.2,橫坐標為網(wǎng)絡(luò)節(jié)點數(shù)目，縱坐標為網(wǎng)絡(luò)潛數(shù)。圖 10 NW網(wǎng)絡(luò)的網(wǎng)絡(luò)潛數(shù)走勢圖，連接概率與網(wǎng)絡(luò)潛數(shù)走勢圖，橫坐標為網(wǎng)絡(luò)節(jié)點數(shù)目,縱坐標為PLN。圖 11 WS網(wǎng)絡(luò)的網(wǎng)絡(luò)潛數(shù)走勢圖，重連概率與網(wǎng)絡(luò)潛數(shù)走勢圖，橫坐標為網(wǎng)絡(luò)節(jié)點

19、數(shù)目,縱坐標為PLN。網(wǎng)絡(luò)潛數(shù)與網(wǎng)絡(luò)節(jié)點數(shù)目的這種對數(shù)關(guān)系，使得網(wǎng)絡(luò)潛數(shù)成為了網(wǎng)絡(luò)的一個穩(wěn)定特征。網(wǎng)絡(luò)潛數(shù)越大，則說明網(wǎng)絡(luò)中節(jié)點的平均影響力越小，同時節(jié)點平均所受影響力越大，說明網(wǎng)絡(luò)的性能較差。BA網(wǎng)絡(luò)的網(wǎng)絡(luò)潛數(shù)較高，它雖然作為許多人類活動自組織而形成的網(wǎng)絡(luò)，但從這一點看來，該網(wǎng)絡(luò)并不容樂觀。3 結(jié)束語定義了潛數(shù)，并通過先導(dǎo)潛數(shù)來描述節(jié)點的對外影響力，分析了依據(jù)網(wǎng)絡(luò)類型的先導(dǎo)潛數(shù)分布，發(fā)現(xiàn)后導(dǎo)潛數(shù)與度具有普遍的高度相關(guān)性。依據(jù)節(jié)點影響力的節(jié)點刪除策略，使得網(wǎng)絡(luò)的整體被摧毀程度下降地更快，說明了先導(dǎo)潛數(shù)的意義。通過研究經(jīng)典BA網(wǎng)絡(luò)、WS網(wǎng)絡(luò)、NW網(wǎng)絡(luò)的網(wǎng)絡(luò)潛數(shù)曲線特點，發(fā)現(xiàn)不同網(wǎng)絡(luò)所具有的穩(wěn)定特

20、征。潛數(shù)在實際網(wǎng)絡(luò)中的應(yīng)用，網(wǎng)絡(luò)的網(wǎng)絡(luò)潛數(shù)特征研究以及潛數(shù)計算的算法優(yōu)化都將是下一步繼續(xù)研究的目標。參考文獻1 Watts D J, Strogatz S H. Collective dynamics of small-world networks. Nature, 1998, 393(6684):440442.2 Barabasi A L, Albert R. Emergency of scaling in random networks. Science, 1999, 286(5439):509512.3 Barabasi A L. Linked: The New Science of N

21、etworks. Massachusetts: Persus Publishing,2002.4 Newman M E J, Watts D J. Renormalization group analysis of the small-world network model. Phys. Lett.A,1999,263:341346.5 Newman M E J. The structure and function of complex networksJ. SIAM Review, 2003, 45(2):167256.6 Albert R., Jeong H., Baarabasi A.

22、 L. Error and attack tolerance of complex networksJ. Nature, 2000, 406(6794): 378-382.7 Newman M E J. Assortative mixing in networksJ. Physical Review Letters, 2002, 89(20):20871.8 Gallos L. K., Cohen R., Argyrakis P., Bunde A., Havlin S. Stability and topology of scale-free networks under attack an

23、d defense strategiesJ. Physical Review Letters, 2005, 94(18): 188701.9 Erdos P, Renyi A. On the evolution of random networks. Science, 1999, 286 (5439) : 509512.10 汪小帆，李翔，陳關(guān)榮編著.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用M. 北京：清華大學(xué)出版社，2006.11 Fronczak A, Fronczak P,and Holyst J A. ,Mean-field theory for clustering coefficients in Barabasi Albert networks, Phys. Rev. E, 2003, 68: 046126.12 Cohen R,Havlin,S. Scale-free networks are ultrasmall. Phys. Re