團體擇優廣義合作網絡的度分布分析

張 野, 孔祥星

(1.長沙航空職業技術學院 培訓與國際交流處, 長沙 410116;2.上海國際集團公司 博士后科研工作站, 上海 200041;3.中南大學 數學與統計學院, 長沙 410075;4.復旦大學 應用經濟學博士后流動站, 上海 200433)

?

團體擇優廣義合作網絡的度分布分析

張 野1,3, 孔祥星2,4*

(1.長沙航空職業技術學院 培訓與國際交流處, 長沙 410116;2.上海國際集團公司 博士后科研工作站, 上海 200041;3.中南大學 數學與統計學院, 長沙 410075;4.復旦大學 應用經濟學博士后流動站, 上海 200433)

將團體競爭的思想引入到合作網絡的研究中, 提出了一個團體擇優廣義合作網絡模型, 其中, 新加入的節點以團體擇優概率選擇已存在的節點形成一個含有T個節點完全圖. 利用馬爾可夫鏈的方法, 證明了網絡的穩態度分布是存在的, 且得到了網絡度分布的精確解析表達式, 并說明了此廣義合作網絡是一個標度指數γ=T+1的無標度網絡.

復雜網絡; 廣義合作網絡; 馬氏鏈; 度分布; 無標度

從Watts和Strogatz[1]研究小世界網絡與Barabasi和Albert[2]研究無標度網絡開始, 復雜網絡的結構和功能便成為眾多學者廣泛關注的問題. 社會合作網絡(由節點和完全圖組成, 其中, 每一個節點表示一個合作者, 完全圖表示由節點所對應的合作者共同參與的項目)是一類很重要的復雜網絡, 如在電影演員合作網絡中, 每一名演員是一個合作者, 多名演員共同參與了一部電影的拍攝, 這里合作拍攝的電影就是一個合作項目. 科學家們對合作網絡做了大量的實證和理論研究工作, 如電影演員合作網絡[1], 科研合作網絡[3-4], 友誼網絡[5]等. 隨著對社會合作網絡研究的深入和對合作關系的推廣, 學者們提出了廣義合作網絡的概念, 使合作網絡的研究領域得到了擴大和延伸, 如生物系統網絡[6-7], 軟件合作網絡[8], 菜系網絡[9]等.

張培培等[10]構造了一個廣義合作網絡模型, 利用平均場方法分析了網絡的度分布, 并討論了網絡的同類型, 群落層次及交連度等問題. 黃相森等[11]討論了合作網絡的分類問題. 趙清貴等[12]對廣義合作網絡模型的度分布進行了分析, 嚴格證明了網絡的穩態度分布是存在的, 并得到了度分布的精確解析表達式. 雷敏[13]提出了一個項目所含合作者數為隨機變量的廣義合作網絡模型, 得到了該模型度分布的精確解析表達式, 并說明了該廣義合作網絡不是無標度網絡.

合作網絡概念和模型的提出, 為研究現實的合作關系提供了一個新的視角. 在合作網絡模型中, 每個完全圖都含有一定數目(T個)的節點, 且在每個時刻都會有新節點加入到合作網絡中, 它會以一定的方式(如隨機選擇, 擇優選擇或混合型)在網絡中選擇T-1個節點共同組成一個新的完全圖. 在現有的合作網絡模型中, 新節點在選擇其它節點組成完全圖時是逐個選取的. 在社會競爭日益激烈的情況下, 團隊合作精神和競爭力顯得更為重要,具備較強整體實力的團隊才能獲更多的發展機會. 本文將團隊整體實力競爭的思想引入到廣義合作網絡的研究中, 基于文獻[14]提出的團體擇優思想提出了一個新的廣義合作網絡模型, 其中, 新節點在網絡中選取T-1個節點時的概率是團體擇優概率(即依賴于團體的度數之和). 通過節點度在網絡演化過程中所滿足的馬爾可夫性, 用馬氏鏈的方法和技巧對網絡的度分布進行了嚴格的分析, 得到了度分布的精確解析表達式, 并說明了該網絡是一個度指數γ=T+1的無標度網絡.

1模型描述

團體擇優廣義合作網絡模型的構造如下: 初始網絡(在t=0時刻)G0是一個包含m0個節點的完全圖, 每個時間步進行如下操作:

(I) 增長: 增加一個新節點,與網絡中的T-1 (T≤m0+1)舊節點一起組成一個完全圖;

(II) 團體擇優: 新節點t(在時刻t加入網絡的節點)在圖Gt-1中選擇T-1個舊節點的概率與它們的度數(節點度定義為節點參與完全圖的數目)之和成正比, 然后把這T個節點相互連接成一個完全圖, 進而得到網絡Gt.

經過t時間步后得到網絡Gt. 節點總數為Nt=m0+t≈t, 節點度數之和為Ht=Tt.

2度分布分析

令hi(t)表示節點i在時刻t的度數, 節點的瞬時度分布P(h,i,t)定義為:

P(h,i,t)=P{hi(t)=h},

網絡的瞬時度分布P(h,t)定義為節點瞬時度分布的平均值

(1)

(2)

從而馬氏鏈{hi(t)}的狀態轉移概率為:

P{hi(t)=l|hi(t-1)=h}=

(3)

由廣義合作網絡的特征,可知網絡中節點度的最小值為1, 且每個時間步度數至多增加1. 對于團體擇優廣義合作網絡的度分布可得如下引理1.

引理1在團體擇優廣義合作網絡中, 瞬時度分布P(1,t)的極限(記為P(1))存在, 且與初始網絡無關, 可得

(4)

證明度數為1的節點為那些剛加入網絡的節點或加入網絡后沒有再參加過其它完全圖的節點. 由P(1,t)的定義(1)式及轉移概率(3)式, 得

這是一個關于P(1,t)的一階線性差分方程,其解為：

上面的引理1證明了團體擇優廣義合作網絡的度分布P(1)是存在的,并求出了它的解析表達式.下面對度分布P(h) (h>1)的存在性和表達式問題進行分析.

(5)

證明網絡中度數為h的節點, 可能由那些度數為h-1的節點參與一個新完全圖, 或由那些度數為h的節點不參與新完全圖而得到. 可得

P(h,i,t+1)=P(h,i,t)[1-ft+1(h)]+

P(h-1,i,t)ft+1(h-1).

由P(h,t+1)的定義及P(h,t+1,t+1)=0, 可得

上述方程是一個關于P(h,t)的二階線性差分方程,解此方程得

定理1團體擇優廣義合作網絡的穩態度分布存在, 其度分布有如下的表達式:

(6)

證明由引理1和引理2易知團體擇優廣義合作網絡的穩態度分布是存在的. 由(4)和(5)式可遞推得(6)式, 從而該網絡是一個標度指數γ=T+1的無標度網絡.

3總結

本文將團隊競爭的思想引入到廣義合作網絡的研究中, 提出了一個團體擇優的廣義合作網絡模型. 此處的團體擇優概率是節點度的線性函數, 保持了BA模型中擇優概率的線性原則. 由模型的演化規則,可得節點度{hi(t)}是一個馬氏鏈, 并得到了它的初始分布和一步狀態轉移概率. 依據馬氏鏈理論, 嚴格證明了該廣義合作網絡模型的穩態度分布是存在的, 并求出了節點度分布的精確解析表達式. 說明了該廣義合作網絡是一個標度指數γ=1+T的無標度網絡.

在廣義合作網絡的研究中, 節點度的相關性是另外一個非常重要的特征, 它描述了一個節點在選擇相連節點時對節點特征的偏好, 如果度數大的節點傾向于連接度數大的節點則稱此網絡為正相關或同類匹配的, 反之稱網絡為負相關或非同類匹配的. 對于節點度相關性的描述可通過條件概率P(k′|k)來描述, 表示一個度數為k的節點連接到度數為k′的節點的概率, 或通過鄰居節點的平均度等方法來描述, 將在后續的工作中研究廣義合作網絡的節點度相關性問題.

[1] Watts D J,Strogatz S H. Collective dynamics of 'small-word' networks[J]. Nature, 1998, 393: 440-442.

[2] Barabasi A L,Albert R. Emergence of scaling in random networks[J].Science, 1999, 286: 509-512.

[3] Hajra K B,Sen P. Aging in citation network[J]. Physica A:Statistical Mechanics and its Applications, 2005, 346(1-2): 44-48.

[4] Ramasco J J, Dorogovtsev S N,Pastor-Satorras R. Self-organization of collaboration networks[J]. Physical Review E, 2004, 70(3): 036106, 1-10.

[5] Parker S L, Parker G R, Mccann J A. Opinion taking within friendship networks[J]. American Journal of Political Science, 2008,52(2): 412-420.

[6] Fell D A,Wagner A. The small world of metabolism[J]. Nature Biotechnology,2000, 18: 1121-1122.

[7] Chang S, Jiao X,Gong X Q,et al. Evolving model of amino acid networks[J].Physical Review E, 2008, 77(6): 061920,1-7.

[8] Myers C R. Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs[J]. Physical Review E, 2003, 68(4): 046116, 1-15.

[9] 張培培, 侯 威, 何 閱, 等. 淮揚菜系的網絡描述[J]. 復雜系統與復雜性科學,2005, 2(2): 49-53.

[10] 張培培, 何到閱, 周 濤. 一個描述合作網絡頂點度分布的模型[J].物理學報, 2006, 55(1): 60-67.

[11] 黃相森, 張淑華. 基于合作網絡的分類討論[J]. 科技與生產, 2011,11(8): 141-144.

[12] 趙清貴, 孔祥星, 侯振挺. 簡易廣義合作網絡度分布的穩定性[J]. 物理學報,2009, 58(10): 6682-6685.

[13] 雷 敏. 隨機連接廣義合作網絡模型[J]. 數學理論與應用, 2012, 32(3): 94-98.

[14] Ye B, Hou Z Z,Kong X X. Scale-free network with variable scaling exponent[C]//2010 International Workshop on Chaos-Fractal Theory and its Applications, 2010, 400-403.

The degree distribution of generalized collaboration network wit group preferential attachment

ZHANG Ye1,3, KONG Xiangxing2,4

(1.Training and International Office, Changsha Aeronautical Vocational and Technical College, Changsha 410116；2.Postdoctoral Scientific Research Workstation, Shanghai International Group Co.Ltd. (SIG), Shanghai 200041;3.School of Mathematics and Statistics, Central South University, Changsha 410075;4.Postdoctoral Research Station for Applied Economics, Fudan University, Shanghai 200433)

Inspired by the idea of team competition, a generalized collaboration network with group preferential attachment is proposed, in which the new vertex will join a complete graph withT-1 vertices chosen from the existing network preferentially. Based on the techniques of Markov chain theory, the existence of the steady degree distribution is proved, and the expressions for the degree distribution are obtained. Theoretical results show that this generalized collaboration network is a scale free network with degree exponentγ=T+1.

complex networks; generalized collaboration network; Markov chain; degree distribution; scale free

2013-12-04.

國家自然科學基金項目(11071258,11101433).

1000-1190(2014)04-0483-04

N945

A

*通訊聯系人. E-mail: xiangxingkong@gmail.com.