一類特殊生長網(wǎng)絡(luò)模型的分析與應(yīng)用

沈秀?！⒒勖鳌埵缛A

（1. 青島科技大學(xué)數(shù)理學(xué)院，山東青島266061；2.青島科技大學(xué)網(wǎng)絡(luò)管理中心，山東 青島266061；3. 青島科技大學(xué)教務(wù)處，山東青島266061）

摘要： 討論了一類基于BA模型生成機(jī)理的特殊的生長網(wǎng)絡(luò)模型，采用率方程的方法計(jì)算得 其度分布，證明了該網(wǎng)絡(luò)是節(jié)點(diǎn)度分布是符合冪律分布的無標(biāo)度網(wǎng)絡(luò)，其冪指數(shù)為-2。從理 論上分析了這個(gè)模型與BA模型由于拓?fù)浣Y(jié)構(gòu)的不同而造成的宏觀性質(zhì)的差異。并將這個(gè)模型 應(yīng)用于高校人才吸引網(wǎng)絡(luò)，利用SPSS和Matlab模擬仿真證明了該模型數(shù)學(xué)期望關(guān)系式的正確 性及模型的有效性。

關(guān)鍵詞：無標(biāo)度網(wǎng)絡(luò)；BA模型；生長網(wǎng)絡(luò)；率方程

中圖分類號：N941.4文獻(xiàn)標(biāo)識碼：A[WT]文章編號：16721098(2008)02008103

Analysis and Application of A Special Growth Network Model

SHEN Xiuzhuan LIU Huiming ZHANG Shuhua

(1. School of Sciences, Qingdao University of Science and Technology, Qingdao Sh andong 266061, China; 2. Network Centre, Qingdao University of Science and Techn ology, Qingdao Shandong 266061, China; 3. Teaching Affairs Office, Qingdao Unive rsity of Science and Technology, Qingdao Shandong 266061, China) Abstract: A special growth network model based on BA model was discussed. Its de gree distribution was computed by use of rate equation method. The degree distri bution was proved to be scale free network, which obeys powerlaw with exponen t-2. The discrepancy of macroscopical property between BA and the model was analy zed in aspect of theory as result from difference of their topological structure . The model was applied to university attracting talents network. Simulations wi th SPSS and Matlab proved that the models mathematical expectation formulais correct and available.

Key words:scale free network; BA model; growth network; rateequation

自然界中存在的大量復(fù)雜系統(tǒng)都可以通過形形色色的網(wǎng)絡(luò)加以描述。例如，神經(jīng)系統(tǒng)可以看 作大量神經(jīng)細(xì)胞通過神經(jīng)纖維相互連接形成的網(wǎng)絡(luò)；計(jì)算機(jī)網(wǎng)絡(luò)可以看作是自主工作的計(jì)算 機(jī)通過通信介質(zhì)如光纜、雙絞線、同軸電纜等相互連接形成的網(wǎng)絡(luò)。類似的還有電力網(wǎng)絡(luò)、 社會(huì)關(guān)系網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等等。

復(fù)雜網(wǎng)絡(luò)的研究熱潮首先源起于1998年WattsStrogatz的小世界網(wǎng)絡(luò)模型［1］，它 揭示了復(fù)雜網(wǎng)絡(luò)的小世界效應(yīng)。近年來在復(fù)雜網(wǎng)絡(luò)研究上的另一重大發(fā)現(xiàn)就是許多復(fù)雜網(wǎng)絡(luò) ，如Internet、WWW以及新陳代謝網(wǎng)絡(luò)等的連接度分布函數(shù)具有冪律形式。由于這類網(wǎng)絡(luò)的 節(jié)點(diǎn)的連接度沒有明顯的特征長度，故稱為無標(biāo)度網(wǎng)絡(luò)［2］510。

為了解析冪律分布的產(chǎn)生機(jī)理,文獻(xiàn)［2］510提出了一個(gè)無標(biāo)度網(wǎng)絡(luò)模型，現(xiàn)被稱為B A模型。他們認(rèn)為以前的許多網(wǎng)絡(luò)模型都沒有考慮到實(shí)際網(wǎng)絡(luò)的如下兩個(gè)重要特性：

(1) 生長(growth)特性：即網(wǎng)絡(luò)的規(guī)模是不斷擴(kuò)大的；

(2) 優(yōu)先連接（preferential attachment）的特性：即新的節(jié)點(diǎn)更傾向于與那些具 有較高 連接度的“大”節(jié)點(diǎn)相連接。這種現(xiàn)象也稱為“富者更富”或者“馬太效應(yīng)”。基于B A模型的內(nèi)在生成機(jī)制，文獻(xiàn)［3］85提出了一類特殊的生長網(wǎng)絡(luò)模型，其模型簡單， 即可定性地又可定量地描述問題。

1模型分析

1．1模型介紹

（1） 生長考慮有玁個(gè)點(diǎn)構(gòu)成的網(wǎng)絡(luò)，網(wǎng)絡(luò)中各點(diǎn)互不相連但每點(diǎn)具有一定的 頂點(diǎn)度 ，每一時(shí)間步長，有一新邊進(jìn)入此網(wǎng)，與網(wǎng)中某點(diǎn)相連（見圖1）。例如，玁個(gè)生 產(chǎn)同種 產(chǎn)品的企業(yè)，企業(yè)即為頂點(diǎn)，顧客選擇這個(gè)企業(yè)的產(chǎn)品就相當(dāng)于與這個(gè)企業(yè)做了一個(gè)連接， 企業(yè)的頂點(diǎn)度為選擇這個(gè)企業(yè)的顧客數(shù)目。而企業(yè)之間并無連接，但他們之間存在制約關(guān)系 ，所以這個(gè)網(wǎng)絡(luò)也可看作是一個(gè)系統(tǒng)。

圖1模型結(jié)構(gòu)示意圖（2） 優(yōu)先連接一新邊與一個(gè)節(jié)點(diǎn)相連的概率與這一節(jié)點(diǎn)的頂點(diǎn)度成正比。如一企業(yè)顧客 數(shù)目越多，其他顧客選擇這一企業(yè)的概率越大，這在實(shí)際生活中是合理的。

1．2與BA模型比較

人們在刻畫復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的統(tǒng)計(jì)特性上提出了許多概念與方法，其中有三個(gè)基本概念：平均 路徑長度、聚類系數(shù)和度分布。 BA無標(biāo)度網(wǎng)絡(luò)的平均路徑長度、 聚類系數(shù)［2］511 和節(jié)點(diǎn)度服從冪指數(shù)為-3的冪律分布。

本文介紹的模型不同于BA模型，因?yàn)槟Ｐ蛢?nèi)各點(diǎn)互相不聯(lián)接，在生長過程只添加新邊而不加 點(diǎn)（見圖1）。這個(gè)模型不存在計(jì)算平均路徑長度和聚類系數(shù)問題。但可以計(jì)算其度分布， 采用率方程的方法進(jìn)行計(jì)算［4］。

玠玁k[]玠玹[SX)]=[SX(]1[]A[SX)]［A﹌-1N﹌-1-AkNk］+δk1(1)式中：δ﹌1為初始條件；Nk為t時(shí)刻度為k的節(jié)點(diǎn)數(shù)目；[SX (]Ak[]A[SX)]為新邊與度為k的節(jié)點(diǎn)連接的概率。

對上述模型玹時(shí)刻總度數(shù)為t，引入的新點(diǎn)與原網(wǎng)絡(luò)中的度數(shù)為k的點(diǎn)連接的概率為[SX(]k []t[SX)]。這時(shí)，相應(yīng)的率方程為

玠玁k[]玠玹[SX)]=[SX(]1[]t[SX)]［(k-1)N﹌-1-kNk］+δ﹌1

為求解率方程，按照大數(shù)定律［5］有

玁k(t)≈tnk

則nk=[SX(]1[]t[SX)]［(k-1)tn﹌-1-ktnk］+δ﹌1

化簡得nk=[SX(]k-1[]k+1[SX)]n﹌-1в捎詎n1=[SX(]1[]2[SX)]，所以 nk=[SX(]1[]k(k+1)[SX)]～k-2?。可寄Ｐ椭卸葹楂k的頂點(diǎn)數(shù)大致服從冪 律分布，所以這個(gè)網(wǎng)絡(luò)是一個(gè)無標(biāo)度網(wǎng)絡(luò)。上述模型度分布服從冪指數(shù)為-2的冪律分布，而BA模型度分布服從冪指數(shù)為-3的冪律分布，這種宏觀性質(zhì)的差異主要是由于模型拓?fù)浣Y(jié)構(gòu) 的不同造成的。該模型可以視為BA模型的擴(kuò)展模型。

1．3模型演化分析

對模型展開演化分析，設(shè)玹0=0,由于每一時(shí)刻有一新邊進(jìn)入網(wǎng)絡(luò)，所以t時(shí)刻網(wǎng)絡(luò)的總度 數(shù)為t, 按照優(yōu)先連接的思想，設(shè)度為k的點(diǎn)得到新邊的概率與度k成線性關(guān)系設(shè)為[SX(]k[]t [SX)]，P瑃﹌,s為點(diǎn)s在t時(shí)刻度為k的概率。可由主方程法建立方程

P瑃+1﹌,s=P瑃﹌-1,s([SX(]k-1[]t[SX)])+P瑃﹌,s(1-[SX( ]k[]t[SX)])(2)

式(2)右端第一項(xiàng)表示玹時(shí)s點(diǎn)的度為k-1,它以概率[SX(]k-1[]t[SX)]得到一條邊，則t+1時(shí) 其度將為k；第二項(xiàng)表示t時(shí)其度為k，其度保持不變的概率為(1-[SX(]k[]t[SX)])。則若要 求t＋1時(shí)s的度為k，只要這二者中有一項(xiàng)成立即可。

式（2）實(shí)際上是條件概率的全概率公式。第一項(xiàng)是在玃瑃﹌-1,s的條件下又得到 一條邊；第二項(xiàng)是在P瑃﹌,s的條件下得不到一條邊。在文獻(xiàn)［3］87中推演 出了網(wǎng)中任何一點(diǎn)在任何時(shí)間t時(shí)的數(shù)學(xué)期望，以計(jì)算t時(shí)此點(diǎn)可能吸引到的度數(shù)，亦即可能 聚集的量。記E瑃s—點(diǎn)s在t時(shí)的數(shù)學(xué)期望。

據(jù)式（2），有E瑃+1s=[SX(]t+1[]t[SX)]E瑃s，這樣得到了一個(gè)迭代式。 由此可得E瑃+1s=[SX(]t+1[]t0[SX)]E瑃0s不失普遍性，可寫成E瑃s=[SX(]t[]t0[SX)]E瑃0s?。染J在初始條件中，對于點(diǎn)玸，只 是P瑃0﹌,s=1，其他均為0。所對應(yīng)的度數(shù)K記做Ks，又將有

E瑃s=([SX(]Ks[]t0[SX)])t(3)

* 2004年與2006年的《中國大學(xué)評價(jià)研究報(bào)告》式(3)所描寫的是一種統(tǒng)計(jì)規(guī)律，是描寫不斷加入（吸引）新邊的演化過程。同時(shí)各點(diǎn)玸 之間存在競爭機(jī)制,表現(xiàn)在具有不同的初始優(yōu)勢（或劣勢）,競爭也是一種自組織，因而式(3 )是描寫自聚集自組織演化的整體統(tǒng)計(jì)規(guī)律。

2模型的應(yīng)用

現(xiàn)在越來越多的頂尖人才愿意選擇高校作為發(fā)展基地。影響人才選擇高校的因素很多，其中 一個(gè)非常重要因素，那就是在這所高校里有多少優(yōu)秀的人才。容易理解高校優(yōu)秀人才越多其 吸引力越大。由此，考慮將該模型應(yīng)用于高校對人才的吸引網(wǎng)絡(luò)。

作者以高校為節(jié)點(diǎn)，每點(diǎn)具有一定的初始頂點(diǎn)度，代表高校此時(shí)擁有人才的數(shù)目。人才選擇 了這所高校就意味著與這所高校建立了一個(gè)連接。人才選擇一所高校的概率與高校人才的多 少成正比。為便于取得數(shù)據(jù)，本文以高校中具有博士學(xué)位的教師作為是否人才的衡量標(biāo)準(zhǔn)。

初始條件中，玹0的意義是初始時(shí)刻高校教師中具有博士學(xué)位的數(shù)目，t表示網(wǎng)絡(luò)演化到t 時(shí)刻的高校教師中具有博士學(xué)位的數(shù)目。Ks表示節(jié)點(diǎn)s在初始時(shí)刻博士的數(shù)目；E瑃s 表示節(jié)點(diǎn)s經(jīng)過演化后在t時(shí)刻博士數(shù)目的數(shù)學(xué)期望。從E瑃s=([SX(]Ks[]t0[SX)]) t可以看出：節(jié)點(diǎn)s的博士數(shù)目與時(shí)間成正比，與高校初始的博士數(shù)目成正比*。

下面通過具體的數(shù)據(jù)對該模型來做模擬仿真。

表1六所高校具有博士學(xué)位的教師數(shù)目(人)

時(shí)間/年中國海洋大學(xué)復(fù)旦大學(xué)山東師范大學(xué)青島大學(xué)煙臺(tái) 大學(xué)濰坊學(xué)院2004[]550[]707[]280[]389[]150[]112[BHDWG1*8/9]2006[]579[]824[]354[]423[]200[]128[BG)F]由表1可以看出，玹0＝2 188，t＝2 508，用式（3）計(jì)算可以求出各點(diǎn)的數(shù)學(xué)期望

用SPSS將網(wǎng)中各點(diǎn)的數(shù)學(xué)期望與各點(diǎn)的實(shí)際度數(shù)進(jìn)行線性回歸 分析[CM)]， 其回歸方程為 珁=1.034x-14.078(y代表網(wǎng)中各點(diǎn)度數(shù)的數(shù) 學(xué)期望；x代表各點(diǎn)實(shí)際度數(shù))。利用Matlab模擬仿真得到擬合曲線（見圖2）。網(wǎng)絡(luò)中各點(diǎn)的實(shí)際度數(shù)

圖2各節(jié)點(diǎn)度與其數(shù)學(xué)期望的擬合曲線圖2說明用實(shí)際數(shù)據(jù)與式（3）計(jì)算出來各點(diǎn)數(shù)學(xué)期望可 以很好地吻合。從而，驗(yàn)證了該公式的正確性。雖然實(shí)際結(jié)果與理論結(jié)果有一定的定量上的 差別，但是在統(tǒng)計(jì)意義上仍不失正確性。

3結(jié)語

本文討論了一種簡單的、特殊的、但又廣泛應(yīng)用的生長網(wǎng)絡(luò)模型，從理論的角度利用率方程 計(jì)算分析了該模型的度分布，闡明了該模型與BA模型的區(qū)別與聯(lián)系。并將其應(yīng)用于高校對人 才的吸引網(wǎng)絡(luò)，利用SPSS和Matlab對具體數(shù)據(jù)進(jìn)行模擬仿真，仿真實(shí)例驗(yàn)證了理論的正確性 。

參考文獻(xiàn)：

［1］WATTS D J，STROGATZ S H.Collective Dynamics of SmallWorl d Networks［J］.Nature,1998,393:440442.

［2］BARABASI A L,ALBERT R.Emergence of Scaling in Random Netwo rks［J］.Science,1999,286:509512.

［3］張嗣瀛，自聚集.吸引核與聚集量［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2005,2(4) :8492.

［4］P L KRAPIVSKY,S REDNER.Rate Equation Approach for GrowingN etworks［J］.Statistical Mechanics of Complex Networks,2003，625:322.

［5］郭雷,許曉鳴,史定華，等.復(fù)雜網(wǎng)絡(luò)［M］.上海:上海教育出版社,2006,6 14.

［6］周濤,柏文潔,汪秉宏，等.復(fù)雜網(wǎng)絡(luò)研究概述［J］.物理,2005,34:3136.

［7］LI XIANG，CHEN GUANRONG.A LocalWorld Evolving Network Mod el［J］.Physica A,2003,328:274286．

(責(zé)任編輯：何學(xué)華)