錢大千, 張曉東

(上海交通大學(xué)數(shù)學(xué)系,上海 200240)

0 引 言

文獻(xiàn)[1]基于度優(yōu)先選取機(jī)制提出了著名的BA模型,該模型反映了現(xiàn)實生活中網(wǎng)絡(luò)的一個重要特性：度分布滿足冪律分布[2],又稱為無標(biāo)度性。萬維網(wǎng)、輸電網(wǎng)和蛋白質(zhì)網(wǎng)絡(luò)等現(xiàn)實中的網(wǎng)絡(luò)都具有這一特性[3-7]。

在此之后,文獻(xiàn)[8]提出了小世界模型,該模型具有較小的平均距離和較大的聚集系數(shù),即滿足通常所說的小世界性。這里,網(wǎng)絡(luò)G的聚集系數(shù)C定義如下：

其中,T(G)代表G中三角形的個數(shù);P2(G)代表G中長度為2的道路的條數(shù)。

本文研究表明,社會網(wǎng)絡(luò)通常具有較小的平均距離和較大的聚集系數(shù)。也就是說,任意2個人之間都可以通過很少的朋友聯(lián)系起來,同時2個認(rèn)識的人很可能會有共同的朋友?，F(xiàn)實生活中很多網(wǎng)絡(luò)同時具有無標(biāo)度性和小世界性,如科研合作網(wǎng)、特網(wǎng)和電網(wǎng)等[6,8-11]。

為了更好地研究現(xiàn)實生活中種類繁多的網(wǎng)絡(luò)結(jié)構(gòu)和特性,學(xué)者們提出了各種各樣的模型。文獻(xiàn)[12]提出了一種可以同時增加和刪除節(jié)點的增長模型;文獻(xiàn)[13]提出了一種可以同時增加和刪除邊的增長模型。這2種模型反應(yīng)了現(xiàn)實網(wǎng)絡(luò)既可以增長又可以縮減的特性,如萬維網(wǎng)中網(wǎng)頁的添加和刪除。

為了模擬社會網(wǎng)絡(luò),文獻(xiàn)[14]提出了一種基于等級優(yōu)先選取機(jī)制的增長模型,該模型在構(gòu)造過程中只需要用到局部的等級順序就可以生成一個無標(biāo)度網(wǎng)絡(luò)。上述模型都反映了現(xiàn)實中網(wǎng)絡(luò)的一些特性,遺憾的是這些模型的聚集系數(shù)都很小。文獻(xiàn)[15]提出了基于距離優(yōu)先連接的增長模型,在該模型中,新加入的節(jié)點優(yōu)先連接到距離較近的老節(jié)點,因此具有較大的聚集系數(shù),然而該模型的度分布卻不服從冪律分布。

近年來,伴隨著信息技術(shù)的高速發(fā)展,社交網(wǎng)絡(luò)被越來越多的人所熟知[16]。較著名的網(wǎng)絡(luò)公司如Myspace、Facebook、開心網(wǎng)和校內(nèi)網(wǎng)擁有數(shù)以億計的用戶。人們已經(jīng)習(xí)慣了在社交網(wǎng)絡(luò)上交朋友、玩游戲和交換信息。簡單地說,這類網(wǎng)絡(luò)的增長機(jī)制可以分為如下2步：

(1)一個新用戶vi可以通過其朋友們的介紹加入網(wǎng)絡(luò)。

(2)新用戶vi會在其朋友們的好友名單中尋找認(rèn)識的和想要認(rèn)識的人,并同他們成為朋友。

在本文中,基于該增長方式提出了一種同時滿足小世界性和無標(biāo)度性的模型,這和現(xiàn)實中的社交網(wǎng)絡(luò)具有相同的特性。

1 二步增長模型(TSGN)

網(wǎng)絡(luò)規(guī)模為n,參數(shù)為m1、m2的二步增長模型TSGN(m1,m2)增長規(guī)則定義如下：

(1)開始時(T=0),從一個節(jié)點數(shù)為m=m1+m2+1的完全圖出發(fā)。

(2)T=t時,1≤t≤n-m,在網(wǎng)絡(luò)中加入一個新的節(jié)點vm+t,并隨機(jī)選取m1個舊節(jié)點與之連接,將這m1個節(jié)點記為N1(t)(隨機(jī)連接)。

(3)記 N1(t)的鄰居為 N2(t),從 N 2(t)中隨機(jī)選取m2個節(jié)點與vm+t連接(鄰域連接)。

重復(fù)執(zhí)行規(guī)則(2)和(3),直到網(wǎng)絡(luò)中節(jié)點數(shù)達(dá)到事先給定的網(wǎng)絡(luò)規(guī)模n。不難發(fā)現(xiàn),每一次增長添加了1個節(jié)點和m1+m2條邊。因此經(jīng)過t次增長,網(wǎng)絡(luò)中共有 t+m個節(jié)點和(m-1)(m+2t)/2條邊。

2 度分布

運用平均場理論可以得到TSGN模型的度分布P(k),也就是度為k的節(jié)點所占總節(jié)點數(shù)的比例。

令P(k,i,t)代表第t步時第i個節(jié)點度為k的概率,并記(1)式為第t步時的度分布,即

可以寫出如下的主方程：

(2)式的初始條件為：

這里要指出一個巧妙的方法：根據(jù)增長規(guī)則,在第t次增長時從N 2(t)中隨機(jī)選取了m2個節(jié)點與新節(jié)點連接。不難看出,N2(t)中節(jié)點的度分布為 P′(k,t),而不是 P(k,t),即

這是因為度較大的節(jié)點有更大的概率成為某個節(jié)點的鄰居。因此,N 2(t)中任意節(jié)點度為k的概率為k/(m-1)(m+2t-2),這和度優(yōu)先選取的情況類似。

在(2)式兩端對i加和有：

化簡(4)式可得：

這里無法通過(5)式得到P(k)一般的解析表達(dá)式,然而可以給出m1/m2等于某些特定值時P(k)的解析表達(dá)式,即

從(6)～(8)式中可以看到,當(dāng)m1/m2取不同數(shù)值時(1,1/2,2),對應(yīng)模型的度分布分別是參數(shù)為5、4、7的冪律分布。

從中可以看出,冪律分布的參數(shù)隨著比率m1/m2的增大而增大。

3 數(shù)值仿真

本文運用平均場理論得到了一些特殊情形下TSGN(m1,m2)網(wǎng)絡(luò)的度分布,現(xiàn)通過數(shù)值仿真驗證這一結(jié)果。此外,還需要研究解聚集系數(shù)和平均距離是如何隨著模型參數(shù)和網(wǎng)絡(luò)規(guī)模的變化而變化的。

在雙對數(shù)坐標(biāo)軸上給出了規(guī)模為5 000的TSGN網(wǎng)絡(luò)在參數(shù)比率m1/m2取不同數(shù)值時的度分布仿真結(jié)果,如圖1所示。

從圖1可以發(fā)現(xiàn),3種參數(shù)比率下 TSGN網(wǎng)絡(luò)度分布的仿真結(jié)果與(6)～(8)式中的結(jié)論吻合,均為冪律分布且對應(yīng)的參數(shù)隨著比率m1/m2的增加而增加。

TSGN網(wǎng)絡(luò)在不同網(wǎng)絡(luò)規(guī)模n、參數(shù)m1、m2條件下的平均距離和聚集系數(shù)的仿真結(jié)果,見表1～表3所列。

圖1 根據(jù)(6)～(8)式得到的仿真結(jié)果

表1 每次增長添加3條隨機(jī)連接和3條鄰域連接的仿真結(jié)果

表1中,參數(shù)取值為m1=3,m2=3。此時網(wǎng)絡(luò)具有較大的聚集系數(shù),這與很多現(xiàn)實中的網(wǎng)絡(luò)有相同的特性[8]。實際上,還可以計算出這種情形下TSGN網(wǎng)絡(luò)聚集系數(shù)的一個理論下界。不難看出,網(wǎng)絡(luò)在每一次的增長中都至少增加了3個三角形,同時P2(G)的估計為：

此外,還可以看到網(wǎng)絡(luò)的平均距離大約以ln n的階緩慢增長,這一點也和有關(guān)萬維網(wǎng)的研究結(jié)果吻合[3]。

表2 每次增長添加2條隨機(jī)連接和4條鄰域連接的仿真結(jié)果

表2中,參數(shù)取值為m1=2,m2=4,網(wǎng)絡(luò)在每次增長中都至少增加了4個三角形,因此網(wǎng)絡(luò)具有比表1中更大的聚集系數(shù)。此時,網(wǎng)絡(luò)的平均距離也相對較大,這是由于隨機(jī)連接減少而導(dǎo)致網(wǎng)絡(luò)連通性減弱。

表3 每次增長添加4條隨機(jī)連接和2條鄰域連接的仿真結(jié)果

表3中,參數(shù)取值為m1=4,m2=2,網(wǎng)絡(luò)在每次增長中都至少增加了2個三角形,因此網(wǎng)絡(luò)的聚集系數(shù)相對較小。此時,網(wǎng)絡(luò)的平均距離也相對較小,這是由于隨機(jī)連接增加而導(dǎo)致網(wǎng)絡(luò)連通性增強(qiáng)。

4 結(jié)束語

本文根據(jù)社交網(wǎng)絡(luò)的增長機(jī)制構(gòu)造了二步式增長網(wǎng)絡(luò)模型TSGN(m1,m2)。經(jīng)驗證,此模型滿足社交網(wǎng)絡(luò)的3個重要特性：冪律度分布、小平均距離及大聚集系數(shù)。通過理論推導(dǎo)及數(shù)值仿真發(fā)現(xiàn),當(dāng)模型的規(guī)模和總邊數(shù)一定時,參數(shù)比率m1/m2對這 3種特性有直接的影響。比率m1/m2較大,意味著添加了相對較多的隨機(jī)連接,這使得冪律分布的參數(shù)增大,同時也減小了平均距離和聚集系數(shù)。

[1] Barabási A L,Albert R.Emergence of scaling in randoMnetworks[J].Science,1999,286(5439)：509-512.

[2] Barabási A L,Albert R,Jeong H.Mean-field theory for scale-free randoMnetwork s[J].Physica A,1999,272(1/2)：173-187.

[3] Albert R,Jeong H,Barabási A L.Internet：diameter of the World-Wide Web[J].Nature,1999,401(6749)：130-131.

[4] Huberman BA,Piroll PL T,Pitkow JE,et al.Strong regularities in World Wide Web surfing[J].Science,1998,280(5360)：95-97.

[5] Caldarelli G,Marchetti R,Pietronero L.The fractal properties of Internet[J].Europhys Lett,2000,52(4)：386-391.

[6] Amaral L A N,Scala A,Barthelemy M,et al.Classes of small-world networks[J].Proc Natl Acad Sci USA,2000,97(21)：11149-11152.

[7] Jeong H,Mason S P,Barabasi A L,et al.Lethality and centrality in p rotein networks[J].Nature,2001,411(6833)：41-42.

[8] Watts D J,Strogatz S H.Collective dynamics of small-world networks[J].Nature,1998,393(6684)：440-442.

[9] Newman ME J.The structure of scientific collaboration networks[J].Proc Natl Acad Sci USA,2001,98(2)：404-409.

[10] Barabási A L,Jeong H,Neda Z,et al.Evolution of the social network of scientific collaborations[J].Physica A,2002,311(3/4)：590-614.

[11] Ma Y H,Li H J,Zhang X D.Strength distribution of novel local-world networks[J].Physica A,2009,388(21)：4669-4677.

[12] Moore C,Ghoshal G,Newman M.Exact solutions for models of evolving networks with addition and deletion of nodes[J].Phy s Rev E,2006,74(3)：036121(8).

[13] Deijfen M,Lindholma M.Growing networks with preferential deletion and addition of edges[J].Physica A,2009,388(19)：4297-4303.

[14] Fortunato S,Flammini A,Menczer F.Scale-free network growth by ranking[J].Phys Rev Lett,2006,96(21)：218701(4).

[15] Ozik J,Hunt B R,Ott E.Growing network s with geographical attachment preference：emergence of small world s[J].Phys Rev E,2004,69(2)：026108(5).

[16] Boyd D,Ellison N.Social network sites：definition,history,and scholarship[J].Journal of Computer-Mediated Communication,2007,13(1)：210-230.