小世界網(wǎng)絡(luò)的短接邊的討論

馬麗紅 王寶麗 李 策

(1.河北建筑工程學(xué)院，河北張家口075024;2.北京交通大學(xué)海濱學(xué)院黃驊061100)

1 引言

網(wǎng)絡(luò)作為一門學(xué)科應(yīng)該是從Euler開創(chuàng)圖論學(xué)算起，近年來復(fù)雜網(wǎng)絡(luò)引起人們極大的興趣.在社會(huì)系統(tǒng)中，朋友或熟人關(guān)系網(wǎng)絡(luò)是最基本的網(wǎng)絡(luò)［1，2，3］.有人曾經(jīng)做過一個(gè)實(shí)驗(yàn)，實(shí)驗(yàn)要求參與者把一封信通過熟人傳送給指定的某個(gè)人，借此找出熟人關(guān)系網(wǎng)中路徑長(zhǎng)度的分布.統(tǒng)計(jì)顯示平均依次經(jīng)過6個(gè)熟人就可傳達(dá)到，這就是著名的“六度分離”.規(guī)則網(wǎng)絡(luò)是秩序的象征，隨機(jī)網(wǎng)絡(luò)是混亂的代表，現(xiàn)實(shí)網(wǎng)絡(luò)不可能是它們中的任何一個(gè)可代表的，于是由Watts和Strogatz提出著名的小世界模型［4，5，6］.

小世界網(wǎng)絡(luò)模型的描述:

給定規(guī)則網(wǎng)絡(luò):假如網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)為N，每個(gè)節(jié)點(diǎn)與它最近鄰的個(gè)節(jié)點(diǎn)連接，要求.

改變舊連線:以概率p為規(guī)則網(wǎng)絡(luò)的每條舊連線重新連接，將該連線的一個(gè)端點(diǎn)隨機(jī)的放到一個(gè)新位置上，不包括自身的連線和重復(fù)連線.

下面我們用平均場(chǎng)理論來研究小世界網(wǎng)絡(luò)的性質(zhì):

2 平均場(chǎng)理論

2.1 模型的微小變化

在模型中選擇任意兩點(diǎn)短接，同時(shí)沒有邊從規(guī)則網(wǎng)絡(luò)中刪除.對(duì)于大尺度網(wǎng)絡(luò)連接概率為p2k－1時(shí)距離都是一樣的，當(dāng)概率為p2k或更高時(shí)l就會(huì)產(chǎn)生變化.文中將會(huì)給出具體介紹.

2.2 連續(xù)變化的模型

考慮半徑r的鄰域，鄰域是指屬于r鄰域的點(diǎn)或不屬于它的點(diǎn)，m(r)為不屬于A的r鄰域的點(diǎn)子數(shù)，為單位長(zhǎng)度的不屬于A的r鄰域的點(diǎn)子數(shù).n(r)為A的r，鄰域的空隙數(shù)單位長(zhǎng)度的A的r鄰域的空隙數(shù).如圖所示

由此可得出

公式(2)中隨著r的增加n的增長(zhǎng)率.當(dāng)r增加dr時(shí)，r的鄰邊將覆蓋短接點(diǎn)，另外一端將生長(zhǎng)出新的點(diǎn).另外一項(xiàng)是當(dāng)r變?yōu)閞+dr時(shí)，空隙點(diǎn)將減少或消失，減少的概率為個(gè)空隙的概率為，由(2)式可得(3)

L=ξ和L?ξ分別對(duì)應(yīng)著和

由式(2)和(3)消去r，可得

可解的(4)式為

如果1=L=ξ或1=ξ=L，則(6)式是小世界網(wǎng)絡(luò)的微分解.

當(dāng)L→∞ 時(shí)，考慮到th(x1+x2)=(thx1+thx2)/1+thx1thx2，可得到

距離r的平均函數(shù)A(r)可表示為

2.3 討論

考慮到r和讓

上式表明當(dāng)x=1時(shí)，短接邊比較少;當(dāng)x?1時(shí)，短接邊比較多.

3 重整化群變換［7］

考慮重整化變換情況如下:

3.1 當(dāng) k=1 時(shí)

在一對(duì)相鄰點(diǎn)中加入一個(gè)點(diǎn)生成一個(gè)一維的格子，這個(gè)格子中有許多點(diǎn).如果加入的點(diǎn)和其它的點(diǎn)連接，重整化的格子中兩個(gè)點(diǎn)連接在一起.變換下的保留的短接邊的數(shù)目為s=pLk=pL.則

重整化前后任何兩個(gè)點(diǎn)短接的概率是不一樣的，對(duì)于大的L和小的p

因?yàn)長(zhǎng)?1，p=1，將(15)、(16)式代入(14)式，發(fā)現(xiàn)

3.2 當(dāng)k ＞1時(shí)

重整化變換形式如上.

通過上面理論分析可知，小世界網(wǎng)絡(luò)在p值較小的一個(gè)范圍內(nèi)，具有較大的群集系數(shù)和短的平均路徑，這種現(xiàn)象被稱為小世界效應(yīng).許多現(xiàn)實(shí)網(wǎng)絡(luò)都具有小世界效應(yīng).

［1］D.J.Watts and S.H.Strogatz.Nature 393.440(1998)

［2］Newman M E J.The structure and function of complex networks［J］.SIAM Review，2003，45(2):167 ～256.

［3］M.E.J.Newman and D.J.Watts，Phys.Lett.A263，341(1999)

［4］S.N.Dorogovtsev and J.F.F.Mendes.cond－mat/0005050

［5］R.Albert，H.Jeong，andA－L.Barabasi，Physica A 272(1999)173 ～187

［6］R.Albert，H.Jeong，and A－L.Barabasi，Nature 401，130(1999)

［7］Wenchen He，et al.Time evolution of the degree distribution of model A of random attachment growing networks.Physica A.384(2007):663～666

［8］Reka Albert and Albert－ Laszlo Barabasi.Phys.Rev.Lett.85(2000)5234 ～5237