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

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

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

關鍵詞：無標度網(wǎng)絡；BA模型；生長網(wǎng)絡；率方程

中圖分類號：N941.4文獻標識碼：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

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

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

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

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

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

1模型分析

1．1模型介紹

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

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

1．2與BA模型比較

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

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

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

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

玠玁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А＊タ杉模型中度為玨的頂點數(shù)大致服從冪 律分布，所以這個網(wǎng)絡是一個無標度網(wǎng)絡。上述模型度分布服從冪指數(shù)為-2的冪律分布，而BA模型度分布服從冪指數(shù)為-3的冪律分布，這種宏觀性質的差異主要是由于模型拓撲結構 的不同造成的。該模型可以視為BA模型的擴展模型。

1．3模型演化分析

對模型展開演化分析，設玹0=0,由于每一時刻有一新邊進入網(wǎng)絡，所以t時刻網(wǎng)絡的總度 數(shù)為t, 按照優(yōu)先連接的思想，設度為k的點得到新邊的概率與度k成線性關系設為[SX(]k[]t [SX)]，P瑃﹌,s為點s在t時刻度為k的概率?？捎芍鞣匠谭ń⒎匠?/p>

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

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

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

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

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

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

2模型的應用

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

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

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

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

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

時間/年中國海洋大學復旦大學山東師范大學青島大學煙臺 大學濰坊學院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）計算可以求出各點的數(shù)學期望

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

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

3結語

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

參考文獻：

［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］.復雜系統(tǒng)與復雜性科學，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］郭雷,許曉鳴,史定華，等.復雜網(wǎng)絡［M］.上海:上海教育出版社,2006,6 14.

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

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

(責任編輯：何學華)