局部拓?fù)湫畔Ⅰ詈洗龠M(jìn)網(wǎng)絡(luò)演化

劉樹新季新生②劉彩霞湯紅波鞏小銳

?

局部拓?fù)湫畔Ⅰ詈洗龠M(jìn)網(wǎng)絡(luò)演化

劉樹新*①季新生①②劉彩霞①湯紅波①鞏小銳①

①(國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002)②(移動(dòng)互聯(lián)網(wǎng)安全技術(shù)國(guó)家工程實(shí)驗(yàn)室 北京 100876)

為了研究局部拓?fù)湫畔Ⅰ詈蠈?duì)網(wǎng)絡(luò)演化的促進(jìn)作用，該文提出一種局部拓?fù)浼訖?quán)方法，用于表征節(jié)點(diǎn)間聯(lián)系的緊密性及拓?fù)湫畔⒌鸟詈铣潭?，并從演化模型的宏觀統(tǒng)計(jì)和實(shí)際網(wǎng)絡(luò)數(shù)據(jù)測(cè)試兩方面驗(yàn)證了局部拓?fù)湫畔Ⅰ詈洗龠M(jìn)網(wǎng)絡(luò)演化的有效性。首先將該加權(quán)方法應(yīng)用于BA模型，提出TwBA模型及局域世界模型TwLW。仿真實(shí)驗(yàn)表明，TwBA的度分布隨連邊數(shù)目的增多，迅速從指數(shù)分布轉(zhuǎn)變?yōu)閮缏煞植?，?yàn)證了現(xiàn)實(shí)網(wǎng)絡(luò)加速增長(zhǎng)產(chǎn)生冪律分布的現(xiàn)象，并基于此提出一種加速演化的TwBA模型，其在不同的加速率下呈現(xiàn)出冪律分布；而TwLW則展現(xiàn)了從廣延指數(shù)分布到冪律分布變化的形式。然后將加權(quán)方法拓展到鏈路預(yù)測(cè)方法，提出3個(gè)加權(quán)相似性指標(biāo)。實(shí)際網(wǎng)絡(luò)數(shù)據(jù)測(cè)試表明，該方法能夠大幅度地提高基本算法的預(yù)測(cè)精度，部分甚至高于全局性指標(biāo)。

復(fù)雜網(wǎng)絡(luò)；局部拓?fù)洌谎莼Ｐ?；鏈路預(yù)測(cè)；信息耦合

1 引言

近年來，復(fù)雜網(wǎng)絡(luò)領(lǐng)域的研究蓬勃發(fā)展，越來越多的現(xiàn)實(shí)網(wǎng)絡(luò)已經(jīng)成為復(fù)雜網(wǎng)絡(luò)的研究對(duì)象，包括社交媒體網(wǎng)絡(luò)[1]、互聯(lián)網(wǎng)[2]、電力網(wǎng)絡(luò)[3]、蛋白質(zhì)網(wǎng)絡(luò)[4]、交通運(yùn)輸網(wǎng)絡(luò)[5]等多種復(fù)雜性系統(tǒng)。網(wǎng)絡(luò)演化機(jī)制作為網(wǎng)絡(luò)科學(xué)的根本性問題，一直是統(tǒng)計(jì)領(lǐng)域的研究熱點(diǎn)。尤其是在小世界[6]、無標(biāo)度[7]等特性的發(fā)現(xiàn)之后，極大地豐富了人們對(duì)于現(xiàn)實(shí)網(wǎng)絡(luò)的認(rèn)識(shí)，也刺激了各領(lǐng)域研究復(fù)雜網(wǎng)絡(luò)演化機(jī)制的熱忱[8]。

經(jīng)典的BA模型揭示了網(wǎng)絡(luò)的無標(biāo)度特性，認(rèn)為網(wǎng)絡(luò)增長(zhǎng)和偏好連接是網(wǎng)絡(luò)演化的根本動(dòng)力[7]。在BA模型的基礎(chǔ)上，許多學(xué)者在連接概率和內(nèi)部連邊等上做了改進(jìn)[9,10]?？紤]到現(xiàn)實(shí)網(wǎng)絡(luò)中個(gè)體選擇的局限性，文獻(xiàn)[11]提出了局域世界演化模型(LW)，模型通過在隨機(jī)選擇的局域世界中進(jìn)行度優(yōu)先選擇，并呈現(xiàn)出指數(shù)分布和冪律分布之間的度分布形式。由于許多真實(shí)網(wǎng)絡(luò)的連接存在權(quán)值，文獻(xiàn)[12]提出了經(jīng)典的賦權(quán)演化模型BBV模型，該模型采用強(qiáng)度優(yōu)先連接，新連接添加時(shí)會(huì)為當(dāng)前點(diǎn)強(qiáng)度增加一個(gè)，產(chǎn)生了標(biāo)準(zhǔn)的無標(biāo)度網(wǎng)絡(luò)?；贐BV模型，許多學(xué)者進(jìn)一步提出了不同的含權(quán)演化模型，但在權(quán)值的賦予上多是在無權(quán)網(wǎng)絡(luò)模型上進(jìn)行簡(jiǎn)單的增添，缺乏對(duì)局部拓?fù)湫畔⒌鸟詈?，且其取值并不能反映?dāng)前連接周圍的拓?fù)浣Y(jié)構(gòu)。

現(xiàn)階段，網(wǎng)絡(luò)演化模型的研究均基于宏觀統(tǒng)計(jì)(度分布等宏觀參數(shù))，并沒有在實(shí)際網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)驗(yàn)證。因此，相關(guān)學(xué)者認(rèn)為鏈路預(yù)測(cè)可用于衡量網(wǎng)絡(luò)演化模型[16]，驗(yàn)證物理演化機(jī)制在實(shí)際網(wǎng)絡(luò)中的有效性。并基于拓?fù)溲莼瘷C(jī)制，提出了大量的鏈路預(yù)測(cè)方法，包括共同鄰居[17](Common Neighbors, CN), Salton[18]，資源分配[19](Resource Allocation, RA), LHN-II[20]和Katz[21]等相似性指標(biāo)，一定程度上豐富了人們對(duì)真實(shí)網(wǎng)絡(luò)中網(wǎng)絡(luò)演化機(jī)制的認(rèn)識(shí)。研究表明許多實(shí)際網(wǎng)絡(luò)的度分布介于冪律分布和指數(shù)分布之間[22]，呈現(xiàn)出近冪律的分布形式如去頭的冪律分布、廣延指數(shù)分布等[23]，且增長(zhǎng)過程中表現(xiàn)出了加速增長(zhǎng)的趨勢(shì)(邊的增長(zhǎng)速度遠(yuǎn)大于點(diǎn)的增加速度)[24]。具體實(shí)際網(wǎng)絡(luò)中如：政治論壇博客網(wǎng)絡(luò)[25]為近冪律分布；線蟲神經(jīng)網(wǎng)絡(luò)[6]則存在單峰[26]，呈現(xiàn)單側(cè)冪律分布；引文網(wǎng)絡(luò)[27]則為近指數(shù)分布；而路由器級(jí)互聯(lián)網(wǎng)[28]則表現(xiàn)為接近廣延指數(shù)分布的近冪律分布。度優(yōu)先選擇被認(rèn)為是冪律分布產(chǎn)生的重要機(jī)制，但越來越多實(shí)證研究發(fā)現(xiàn)局部范圍內(nèi)的拓?fù)湫畔?duì)新連接的建立也起著重要作用[29,30]。局部拓?fù)湫畔Ⅰ詈铣潭饶軌蚝艽蟪潭壬嫌绊懢W(wǎng)絡(luò)節(jié)點(diǎn)的偏好連接，現(xiàn)實(shí)網(wǎng)絡(luò)如人際關(guān)系網(wǎng)絡(luò)中，個(gè)體之間新連接的建立往往傾向于個(gè)體及其周圍社會(huì)關(guān)系的統(tǒng)合考量，新連接則可以理解為兩個(gè)節(jié)點(diǎn)周圍社會(huì)關(guān)系的偏好選擇；同樣，在引文網(wǎng)絡(luò)中，新引用的產(chǎn)生更多是基于文獻(xiàn)相互引用構(gòu)成的影響力(局部拓?fù)潢P(guān)系構(gòu)成的綜合吸引力)。

基于上述討論，本文提出了一種局部拓?fù)湫畔⒓訖?quán)方法，量化節(jié)點(diǎn)間聯(lián)系的緊密性和拓?fù)湫畔⒌鸟詈铣潭?，進(jìn)而使節(jié)點(diǎn)可以耦合更多的局部拓?fù)湫畔ⅰ⒃摲椒☉?yīng)用于經(jīng)典BA模型，基于拓?fù)浼訖?quán)后的節(jié)點(diǎn)強(qiáng)度進(jìn)行優(yōu)先選擇，提出了基于局部拓?fù)浼訖?quán)的TwBA和局域世界模型TwLW。度分布分析表明，不同于BA模型，TwBA呈現(xiàn)出從指數(shù)分布到冪律分布變化的形式，并隨著連邊數(shù)的增長(zhǎng)，迅速轉(zhuǎn)變?yōu)閮缏煞植?，這一定程度上說明了現(xiàn)實(shí)網(wǎng)絡(luò)連邊加速增長(zhǎng)后產(chǎn)生冪律分布的現(xiàn)象；基于TwBA的度分布特點(diǎn)，進(jìn)一步提出加速網(wǎng)絡(luò)模型A-TwBA，度分布統(tǒng)計(jì)顯示模型在網(wǎng)絡(luò)加速演化后呈現(xiàn)出冪律分布，部分同時(shí)呈現(xiàn)單峰和冪律分布；而TwLW模型則呈現(xiàn)了廣延指數(shù)分布到冪律分布變化的形式。為了在實(shí)際網(wǎng)絡(luò)中進(jìn)一步驗(yàn)證局部拓?fù)浼訖?quán)促進(jìn)網(wǎng)絡(luò)演化這一機(jī)制的有效性，將拓?fù)浼訖?quán)應(yīng)用于基本的鏈路預(yù)測(cè)方法CN, Jaccard和RA。多個(gè)實(shí)際網(wǎng)絡(luò)數(shù)據(jù)測(cè)試結(jié)果表明，局部拓?fù)浼訖?quán)能夠大幅度提高相似性指標(biāo)的預(yù)測(cè)精度，部分甚至高于全局性指標(biāo)。從宏觀統(tǒng)計(jì)和實(shí)際網(wǎng)絡(luò)數(shù)據(jù)兩個(gè)方面驗(yàn)證了局部拓?fù)湫畔Ⅰ詈洗龠M(jìn)網(wǎng)絡(luò)演化這一機(jī)制的合理性。

2 局部拓?fù)湫畔⒓訖?quán)方法(TW)

現(xiàn)實(shí)網(wǎng)絡(luò)中，權(quán)重一般是根據(jù)統(tǒng)計(jì)結(jié)果進(jìn)行賦值，比如：節(jié)點(diǎn)間交互的頻率、作用強(qiáng)度[31]，但并沒有進(jìn)一步反映連接周圍的拓?fù)浣Y(jié)構(gòu)關(guān)系。越來越多實(shí)際網(wǎng)絡(luò)數(shù)據(jù)表明，網(wǎng)絡(luò)局部范圍內(nèi)的積聚程度對(duì)連邊的可能性起著重要作用[32,33]。節(jié)點(diǎn)周圍拓?fù)浼鄢潭仍礁?，?duì)其他節(jié)點(diǎn)的吸引力越大，它們之間便更傾向于建立連接。對(duì)于網(wǎng)絡(luò)中直接連接的兩個(gè)節(jié)點(diǎn)和，其間接連接可以為當(dāng)前邊提供隱含的拓?fù)湫畔⒑蜐撛趦?nèi)部聯(lián)系，增加了節(jié)點(diǎn)間的相關(guān)聯(lián)系和信息耦合，一定程度上反映了節(jié)點(diǎn)間聯(lián)系的緊密程度。圖1示意了不同情形下的拓?fù)溆绊?，可分為兩種對(duì)比情況：一種情形為兩個(gè)端點(diǎn)擁有相同的連邊數(shù)目，但間接連接數(shù)目不同如：圖1(a)和圖1(b)，由于圖1(b)中含有間接連接多于圖1(a)，所以認(rèn)為圖1(b)中節(jié)點(diǎn)和間的局部拓?fù)渚o密性更高，故連邊權(quán)重大于圖1(a)；另一種情形為間接連接數(shù)目相同，但總連邊數(shù)目不同：圖1(b)和圖1(c)，由于圖1(c)中連邊數(shù)目小于圖1(b)，雖然間接連接數(shù)目相同，局部拓?fù)渚o密性也與其占比例相關(guān)，圖1(c)中節(jié)點(diǎn)和間拓?fù)潢P(guān)聯(lián)更緊密，故權(quán)重相對(duì)更大。

圖1 不同局部拓?fù)淝樾螌?duì)比圖

基于上述分析，假定每條邊可以擁有或支配的資源為1。從間接連接對(duì)節(jié)點(diǎn)間緊密性的影響上分析，若兩節(jié)點(diǎn)所有連接的數(shù)目為，間接聯(lián)系數(shù)目為，間接聯(lián)系對(duì)當(dāng)前連接的影響，可以量化表示為，而當(dāng)前直接連邊自身在所有連接中的比重為，如圖1(c)中的量化結(jié)果分別為4/7和1/7?？傊?，對(duì)于網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)和，其局部拓?fù)湫畔⒌挠绊懣傮w加權(quán)表示為

3 基于局部拓?fù)湫畔⒓訖?quán)的網(wǎng)絡(luò)演化模型

3.1 基于局部拓?fù)湫畔⒓訖?quán)的網(wǎng)絡(luò)演化模型

基于局部拓?fù)浼訖?quán)方法(TW)，對(duì)BA模型進(jìn)行加權(quán)拓展，提出TwBA模型和局域世界模型TwLW(局部拓?fù)浼訖?quán)可以拓展到任何無權(quán)網(wǎng)絡(luò)模型，在此以經(jīng)典的BA模型為例，說明局部拓?fù)鋵?duì)拓?fù)溲莼拇龠M(jìn)作用)。TwBA演化步驟為：

(2)賦權(quán)：根據(jù)式(1)對(duì)初始網(wǎng)絡(luò)的已有邊進(jìn)行賦權(quán)；

(4)權(quán)值更新：根據(jù)式(1)對(duì)變化和新加入的邊重新賦權(quán)；

(5)返回步驟(3)，直至網(wǎng)絡(luò)達(dá)到指定大小。

TwBA模型說明了新連接的偏好連接不僅僅和其節(jié)點(diǎn)度有關(guān)，也與其周圍拓?fù)浣Y(jié)構(gòu)相關(guān)。同理，在加入局域世界后，把TwBA模型拓展為TwLW模型，其具體演化步驟則表示為：

(2)賦權(quán)：根據(jù)式(1)對(duì)初始網(wǎng)絡(luò)的已有邊進(jìn)行賦權(quán)；

(5)權(quán)值更新：根據(jù)式(1)對(duì)變化和新加入的邊重新賦權(quán)；

(6)返回步驟(3)，直至網(wǎng)絡(luò)達(dá)到指定大小。

同樣，當(dāng)TwLW中局域世界為整個(gè)網(wǎng)絡(luò)時(shí)，TwLW則轉(zhuǎn)變?yōu)門wBA模型。TwLW模型中，新節(jié)點(diǎn)難以獲取整個(gè)網(wǎng)絡(luò)的信息[34]，其建立連接是在一定的社交圈內(nèi)根據(jù)已有節(jié)點(diǎn)及其社會(huì)關(guān)系進(jìn)行優(yōu)先選擇。

3.2度分布分析

不同于BA模型的標(biāo)準(zhǔn)冪律分布，經(jīng)過局部拓?fù)浼訖?quán)后，TwBA呈現(xiàn)了從指數(shù)分布到冪律分布變化的度分布形式。圖2顯示了相同初始網(wǎng)絡(luò)下BA模型和TwBA模型的度分布對(duì)比。BA模型隨著連邊數(shù)的增加始終保持冪律分布，而對(duì)于TwBA模型，當(dāng)值較小時(shí)，呈現(xiàn)近指數(shù)分布(一些朋友關(guān)系網(wǎng)[35]、蛋白質(zhì)[36]等實(shí)際網(wǎng)絡(luò)的度分布形式)；隨著值的增大，TwBA的度分布迅速轉(zhuǎn)變?yōu)閮缏尚问?，且插圖互余累積度分布曲線中均展現(xiàn)出了指數(shù)截?cái)喱F(xiàn)象[22]。實(shí)證研究表明，大多數(shù)網(wǎng)絡(luò)的度分布為近冪律分布且存在加速增長(zhǎng)的現(xiàn)象[24]，TwBA隨著的增大，迅速趨向于冪律分布，也說明了現(xiàn)實(shí)網(wǎng)絡(luò)的加速演化、平均連接的迅速增多，也是促進(jìn)網(wǎng)絡(luò)形成冪律分布的一個(gè)內(nèi)部驅(qū)動(dòng)。TwBA利用局部拓?fù)湫畔?duì)BA模型進(jìn)行了拓展，使其更多地符合了實(shí)際網(wǎng)絡(luò)的演化過程和度分布形式，說明了局部拓?fù)湫畔Ⅰ詈蠈?duì)網(wǎng)絡(luò)演化的促進(jìn)作用。

圖2 度分布對(duì)比 (，插圖為互余累積度分布曲線)

由于大量實(shí)際網(wǎng)絡(luò)如萬維網(wǎng)、合作網(wǎng)絡(luò)、蛋白質(zhì)和引文網(wǎng)絡(luò)在演化過程中均存在連邊數(shù)目加速增長(zhǎng)的現(xiàn)象[24]。在TwBA的基礎(chǔ)上，令，提出一種加速演化模型A-TwBA，其中為初始連邊數(shù)目(),為加速演化速率()。在不同參數(shù)下，加速演化模型的度分布情形如圖3所示。多數(shù)情形下模型均為冪律分布，部分情形下，甚至同時(shí)出現(xiàn)了單峰[26]和冪律分布，這與一類實(shí)際網(wǎng)絡(luò)如線蟲神經(jīng)網(wǎng)絡(luò)(CE)等網(wǎng)絡(luò)的度分布較為契合[6]。當(dāng)初始連邊數(shù)為0,時(shí)(圖3(a))，最大連邊數(shù)，此時(shí)連邊數(shù)目變化較小(從1到3)，模型呈現(xiàn)輕微的指數(shù)分布傾向，而隨著初始的增大(圖3(c)、圖3(d))，其度分布均展現(xiàn)為冪律分布，但無論加速演化速率多小，只要網(wǎng)絡(luò)規(guī)模足夠大，模型均能演化為冪律分布的形式。圖3中所有不同初始連邊數(shù)目下均顯示了模型在演化速率越大時(shí)，其冪律指數(shù)越大，度分布越陡峭，說明了網(wǎng)絡(luò)加速增長(zhǎng)的速率越快，其度分布下降速度越快，無標(biāo)度程度越明顯。A-TwBA一定程度上反映了網(wǎng)絡(luò)在加速演化中度分布的無標(biāo)度特征。

圖3 A-TwBA模型的度分布

TwLW模型是在TwBA基礎(chǔ)上添加了局域世界。圖4顯示了不同的局域世界規(guī)模和連邊數(shù)目下的互余累積度分布情況(=10000)。圖4(a)中隨著局域世界規(guī)模的增大，LW模型的度分布由近冪律分布到廣延指數(shù)分布的變化過程。當(dāng)局域世界為整個(gè)網(wǎng)絡(luò)大小時(shí)，此時(shí)為TwBA模型，則依連邊數(shù)目從指數(shù)分布變化為冪律分布。圖4(b)中顯示了時(shí)，不同連邊數(shù)目下度分布情形，此時(shí)總體呈現(xiàn)出近冪律分布(廣延指數(shù)分布)的形式，并隨著連邊數(shù)目的增加，冪律指數(shù)逐漸增大。廣延指數(shù)分布普遍存在于一些合作網(wǎng)絡(luò)系統(tǒng)中如淮陽菜肴系統(tǒng)、旅游交通線路系統(tǒng)、以及好萊塢演員網(wǎng)[23]。從上述TwBA, A-TwBA和TwLW的度分布統(tǒng)計(jì)結(jié)果中，局部拓?fù)浼訖?quán)使模型進(jìn)一步符合了實(shí)際網(wǎng)絡(luò)情形，從宏觀數(shù)據(jù)統(tǒng)計(jì)上驗(yàn)證了實(shí)際網(wǎng)絡(luò)中局部拓?fù)漶詈夏軌虼龠M(jìn)網(wǎng)絡(luò)演化這一演化機(jī)制。

圖4 TwLW的度分布 (，插圖為互余累積度分布曲線)

4 基于局部拓?fù)湫畔⒓訖?quán)的鏈路預(yù)測(cè)方法及實(shí)證分析

4.1基于局部拓?fù)湫畔⒓訖?quán)的鏈路預(yù)測(cè)方法

通過局部拓?fù)浼訖?quán)對(duì)網(wǎng)絡(luò)所有節(jié)點(diǎn)間的聯(lián)系加權(quán)后，基于基本無權(quán)網(wǎng)絡(luò)預(yù)測(cè)指標(biāo)，分別把3個(gè)鏈路預(yù)測(cè)方法拓展為含權(quán)的預(yù)測(cè)方法[31]，包括CN, Salton和RA等相似性指標(biāo)(局部拓?fù)浼訖?quán)可以拓展到多種相似性預(yù)測(cè)指標(biāo)，在此以CN等指標(biāo)為例，說明局部拓?fù)浯龠M(jìn)演化這一機(jī)制在實(shí)際網(wǎng)絡(luò)中的有效性)，其中CN指標(biāo)可以拓展為TwCN，具體相似度表示為

(3)

4.2 衡量指標(biāo)及網(wǎng)絡(luò)數(shù)據(jù)

評(píng)價(jià)鏈路預(yù)測(cè)算法精確程度的指標(biāo)為AUC。AUC可以簡(jiǎn)單地理解為在測(cè)試集中隨機(jī)選擇一條邊的分?jǐn)?shù)值大于未連接邊的分?jǐn)?shù)值高的概率[16]。若測(cè)試集中邊大于未連接邊的分?jǐn)?shù)()，則加1分，若兩者相等()，則加0.5分，表示為

為了更好地體現(xiàn)在現(xiàn)實(shí)網(wǎng)絡(luò)中局域信息加權(quán)對(duì)相似性指標(biāo)的優(yōu)化作用，選擇了7個(gè)不同類型的實(shí)際網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行測(cè)試包括：(1)Politicalblogs (PB)[25]：美國(guó)某政治論壇的博客首頁之間通過超鏈接構(gòu)成的網(wǎng)絡(luò)；(2) Hamster[35]: 在hamsterster.com網(wǎng)頁上的用戶朋友關(guān)系網(wǎng)絡(luò)；(3)Yeast[36]：蛋白質(zhì)相互作用網(wǎng)絡(luò)，節(jié)點(diǎn)表示蛋白質(zhì)，邊為相互作用關(guān)系；(4) Caenorhabditis Elegans (CE)[6]：線蟲神經(jīng)網(wǎng)絡(luò)，節(jié)點(diǎn)代表線蟲的神經(jīng)元，邊為神經(jīng)元突觸(synapse)或間隙連接(gap junction)；(5)Power[6]：美國(guó)西部電力網(wǎng)絡(luò)，節(jié)點(diǎn)表示變電站或換流站，連邊為高壓線；(6)Kohonen[27]：有關(guān)自組織映射主題或Kohonen T的論文引用網(wǎng)絡(luò)；(7)Router[28]：路由器層次的Internet。上述網(wǎng)絡(luò)具體的特征參數(shù)如表1所示，包含節(jié)點(diǎn)數(shù)目()，邊的數(shù)目()，平均度，集聚系數(shù)()[6]和匹配系數(shù)[37]。在試驗(yàn)測(cè)試中，設(shè)置集合中邊數(shù)占比為0.9，則為0.1，測(cè)試結(jié)果均為100次結(jié)果的均值。

表1 網(wǎng)絡(luò)數(shù)據(jù)特征參數(shù)

4.3實(shí)證分析

為了在實(shí)際網(wǎng)絡(luò)中驗(yàn)證局部拓?fù)湫畔Ⅰ詈洗龠M(jìn)網(wǎng)絡(luò)演化的有效性，分別對(duì)比了局部拓?fù)浼訖?quán)和非加權(quán)的鏈路預(yù)測(cè)指標(biāo)在實(shí)際網(wǎng)絡(luò)中的預(yù)測(cè)準(zhǔn)確度，其中相似性指標(biāo)包括CN, Salton和RA。

表2的數(shù)據(jù)對(duì)比可以看出，拓?fù)浼訖?quán)后的預(yù)測(cè)精度均高于未加權(quán)的預(yù)測(cè)指標(biāo)，這一定程度上驗(yàn)證了局部拓?fù)浼訖?quán)在實(shí)際網(wǎng)絡(luò)中的有效性。在Router等稀疏網(wǎng)絡(luò)中，AUC的增大是顯著的，尤其是TwRA可以把RA指標(biāo)的AUC從0.65提高到0.96。相比全局性指標(biāo)Katz()，LHN-II()，大多數(shù)情況下TwCN等含權(quán)指標(biāo)的預(yù)測(cè)精度高于LHN-II，部分高于Katz，但從CN拓展到TwCN等并沒有在時(shí)間復(fù)雜度上有量級(jí)的變化(Tw的復(fù)雜度與CN同一個(gè)量級(jí))。由于全局性算法復(fù)雜度較高，在大規(guī)模網(wǎng)絡(luò)中使用便受到一定的限制。同時(shí)，局部指標(biāo)可以應(yīng)用于大規(guī)模實(shí)際網(wǎng)絡(luò)，但預(yù)測(cè)精度不足。通過局部拓?fù)浼訖?quán)后，既能使局部預(yù)測(cè)指標(biāo)的預(yù)測(cè)精度接近全局性指標(biāo)，又能夠使其應(yīng)用于大規(guī)模網(wǎng)絡(luò)，具有重要的實(shí)際應(yīng)用價(jià)值。實(shí)際含權(quán)網(wǎng)絡(luò)的預(yù)測(cè)中，相似性指標(biāo)預(yù)測(cè)并沒有表現(xiàn)出很好的結(jié)果，權(quán)值高的邊起的作用反而難以界定，甚至出現(xiàn)了“弱連接”(weak tie)效應(yīng)[31]，而局部拓?fù)浼訖?quán)則有效促進(jìn)了相似性指標(biāo)的預(yù)測(cè)精度。綜上所述，在不改變當(dāng)前相似性指標(biāo)時(shí)間復(fù)雜度量級(jí)的基礎(chǔ)上，局部拓?fù)浼訖?quán)能夠有效提高相似性指標(biāo)的預(yù)測(cè)精度，其中部分甚至高于全局性指標(biāo)，驗(yàn)證了實(shí)際網(wǎng)絡(luò)中局部拓?fù)湫畔Ⅰ詈洗龠M(jìn)網(wǎng)絡(luò)演化這一機(jī)制的有效性。

表2 局部拓?fù)浼訖?quán)和非加權(quán)的相似性指標(biāo)AUC結(jié)果對(duì)比

5 結(jié)論

許多網(wǎng)絡(luò)演化模型認(rèn)為度優(yōu)先選擇是冪律分布產(chǎn)生的重要機(jī)制。然而，越來越多的研究表明，新連接的選擇更多的是基于節(jié)點(diǎn)及其周圍拓?fù)潢P(guān)系的優(yōu)先選擇。基于局部拓?fù)湫畔Ⅰ詈蠈?duì)網(wǎng)絡(luò)網(wǎng)絡(luò)演化的促進(jìn)作用，本文提出了一種局部拓?fù)浼訖?quán)方法，將其應(yīng)用于拓?fù)溲莼Ｐ?，分別拓展為TwBA, A-TwBA和TwLW模型，產(chǎn)生了從指數(shù)分布到冪律分布，部分出現(xiàn)單峰和廣延指數(shù)分布形式，宏觀統(tǒng)計(jì)上實(shí)證了模型的有效性；然后，將其應(yīng)用與鏈路預(yù)測(cè)，分別拓展了CN, Salton和RA相似性指標(biāo)(加權(quán)方法可以應(yīng)用于任何相似性指標(biāo))。實(shí)際網(wǎng)絡(luò)數(shù)據(jù)測(cè)試表明，拓展后的相似性指標(biāo)的預(yù)測(cè)效果較好，這一定程度上驗(yàn)證了在實(shí)際網(wǎng)絡(luò)中局部拓?fù)浼訖?quán)確實(shí)能夠揭示實(shí)際網(wǎng)絡(luò)連邊機(jī)理。由于演化模型的研究一直基于宏觀統(tǒng)計(jì)，沒有統(tǒng)一的衡量標(biāo)準(zhǔn)，很多學(xué)者認(rèn)為鏈路預(yù)測(cè)可以對(duì)演化模型進(jìn)行評(píng)價(jià)，也普遍認(rèn)同每一種演化模型就對(duì)應(yīng)一個(gè)預(yù)測(cè)方法。本文從局部拓?fù)漶詈洗龠M(jìn)網(wǎng)絡(luò)演化這一機(jī)制出發(fā)，分別將局部拓?fù)浼訖?quán)應(yīng)用于經(jīng)典的網(wǎng)絡(luò)演化模型和鏈路預(yù)測(cè)，從宏觀統(tǒng)計(jì)和實(shí)際網(wǎng)絡(luò)數(shù)據(jù)兩個(gè)方面驗(yàn)證了演化機(jī)制的合理性，也說明了復(fù)雜網(wǎng)絡(luò)演化模型和鏈路預(yù)測(cè)在同一演化機(jī)制上的統(tǒng)一。

[1] BIAN Jiang, XIE Mengjun, TOPALOGLU U,. Social network analysis of biomedical research collaboration networks in a CTSA institution[J]., 2014, 52(1): 130-140.doi:10.1016/j.jbi. 2014.01.015.

[2] WANG Shengjun, WANG Zhen, JIN Tao,. Emergence of disassortative mixing from pruning nodes in growing scale-free networks[J]., 2014, 4(7): 7536-7541. doi:10.1038/srep07536.

[3] ZHANG Yudong, BAO Zhejing, CAO Yijia,. Long-term effect of different topology evolutions on blackouts in power grid[J].&, 2014, 62(4): 718-726.doi:10.1016/j.ijepes.2014. 04.056.

[4] TESCHENDORFF A E, BANERJI C R S, SEVERINI S,. Increased signaling entropy in cancer requires the scale-free property of protein interaction networks[J]., 2015, 5(9), article number: 9646.doi: 10.1038/srep09646.

[5] SUN Li, LIU Like, XU Zhongzhi,. Locating inefficient links in a large-scale transportation network[J].:, 2015, 419(2): 537-545.doi:10.1016/j.physa.2014.10.066.

[6] WATTS D J and STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]., 1998, 393(6684): 440-442.doi: 10.1038/30918.

[7] BARABáSI A L and ALBERT R. Emergence of scaling in random networks[J]., 1999, 286(5439): 509-512.doi: 10.1126/science.286.5439.509.

[8] 方錦清, 汪小帆, 鄭志剛, 等. 一門嶄新的交叉科學(xué):網(wǎng)絡(luò)科學(xué)(上)[J]. 物理學(xué)進(jìn)展,2007, 27(3): 239-343.

FANG Jinqing, WANG Xiaofan, ZHENG Zhigang,. New interdisciplinary science: network science (1)[J]., 2007, 27(3): 239-343.

[9] ALBERT R and BARABáSI A L. Topology of evolving networks: local events and universality[J]., 2000, 85(24): 5234-5237. doi:10.1103/PhysRevLett. 85.5234

[10] BIANCONI G and BARABáSI A L. Bose-einstein condensation in complex networks[J]., 2001, 86(24): 5632-5635. doi: 10.1103/PhysRevLett.86.5632.

[11] LI Xiang and CHEN Guanrong. A local-world evolving network model[J]., 2003, 328(1): 274-286.doi: 10.1016/S0378- 4371(03)00604-6.

[12] BARRAT A, BARTHéLEMY M, and VESPIGNANI A. Weighted evolving networks: coupling topology and weight dynamics[J].2004, 92(22): 228701-228706. doi: 10.1103/PhysRevLett.92.228701.

[13] YANG Chunxia, TANG Minxuan, TANG Haiqiang,. Local-world and cluster-growing weighted networks with controllable clustering[J]., 2014, 25(5): 1440009-1440021.doi: 10.1142/S0129183114400099.

[14] DAI Meifeng and ZHANG Danping. Weighted evolving network with aging-node-deleting and local rearrangements of weights[J]., 2014, 25(2): 1350093-1350102. doi:10.1142/S0129183 113500939.

[15] 王丹, 金小崢. 可調(diào)聚類系數(shù)加權(quán)無標(biāo)度網(wǎng)絡(luò)建模及其擁塞問題研究[J]. 物理學(xué)報(bào), 61(22): 228901-228910.

WANG Dan and JIN XiaoZheng. On weightd scale-free network model with tunable clustering and congesstion[J]., 2012, 61(22): 228901-228910.

[16] Lü Linyuan and ZHOU Tao. Link prediction in complex networks: a survey[J].:, 2011, 390(6): 1150-1170.doi:10.1016/ j.physa.2010.11.027.

[17] LORRAIN F and WHITE H C. Structural equivalence of individuals in social networks[J].1971, 1(1): 49-80.doi: 10.1080/ 0022250X.1971.9989788.

[18] SALTON G and MCGILL M J. Introduction to Modern Information Retrieval[M]. New York: McGraw-Hill, 1983: 30-31.

[19] ZHOU Tao, Lü Linyuan, and ZHANG Yicheng. Predicting missing links via local information[J].2009, 71(4): 623-630.doi:10.1140/epjb/ e2009-00335-8.

[20] LEICHT E A, HOLME P, and NEWMAN M E J. Vertex similarity in networks[J]., 2006, 73(2): 026120-0261125.doi: 10.1103/PhysRevE.73.026120.

[21] KATZ L and POWELL J H. A proposed index of the conformity of one sociometric measurement to another[J]., 1953, 18(3): 249-256. doi:10.1007/ BF02289063.

[22] 汪小帆, 李翔, 陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M]. 北京：清華大學(xué)出版社, 2006: 35-85.

WANG Xiaofan, LI Xiang, and CHEN Guanrong. Complex Networks Theory and Its Applications[M]. Beijing: Tsinghua University Press, 2006: 35-85.

[23] ROBERTS J A, IYER K K, FINNIGAN S,. Scale-free bursting in human cortex following hypoxia at birth[J]., 2014, 34(19): 6557-6572.

[24] ZHANG Zhongzhi, FANG Lujun, ZHOU Shuigeng,. Effects of accelerating growth on the evolution of weighted complex networks[J].:2009, 388(2): 225-232. doi: 10.1016/j. physa.2008.10.008.

[25] ADAMIC L A and GLANCE N. The Political blogosphere and the 2004 US election: divided they blog[C]. Proceedings of the 3rd ACM International Workshop on Link Discovery,New York, NY, USA, 2005: 36-43.doi: 10.1145/1134271. 1134277.

[26] WANG Qing and GUO Jinli. Human dynamics scaling characteristics for aerial inbound logistics operation[J].:, 2010, 389(10): 2127-2133.doi:10.1016/j.physa.2010.01.009.

[27] TAN Fei, XIA Yongxiang, and ZHU Boyao. Link prediction in complex networks: a mutual information perspective[J]., 2014, 9(9): e107056-e107061. doi: 10.1371/ journal.pone.0107056.

[28] SPRING N, MAHAJAN R, and WETHERALL D. Measuring ISP topologies with rocketfuel[J]., 2002, 32(4): 133-145. doi:10.1145/964725.633039.

[29] 崔愛香, 傅彥, 尚明生, 等. 復(fù)雜網(wǎng)絡(luò)局部結(jié)構(gòu)的涌現(xiàn): 共同鄰居驅(qū)動(dòng)網(wǎng)絡(luò)演化[J]. 物理學(xué)報(bào), 2011, 60(3): 803-808.

CUI Aixiang, FU Yan, SHANG Mingsheng,. Emergence of local structures in complex network: common neighborhood drives the network evolution[J]., 2011, 60(3): 803-808.

[30] 劉樹新, 季新生, 劉彩霞, 等. 一種信息傳播促進(jìn)網(wǎng)絡(luò)增長(zhǎng)的網(wǎng)絡(luò)演化模型[J]. 物理學(xué)報(bào), 2014, 63(15): 158902.

LIU Shuxin, JI Xinsheng, LIU Caixia,. A complex network evolution model for network growth promoted by information transmission[J].2014, 63(15): 158902.

[31] Lü Linyuan and ZHOU Tao. Link prediction in weighted networks: The role of weak ties[J]., 2010, 89(1): 18001-18006. doi:10.1209/0295-5075/89/18001.

[32] XIE Zhou, LI Xiang, and WANG Xiaofan. A new community-based evolving network model[J]., 2007, 384(2): 725-732.doi:10.1016/j.physa.2007.05.031.

[33] LI Fenhua, HE Jing, HUANG Guangyan,. A clustering-based link prediction method in social networks[J]., 2014, 29(5): 432-442.doi: 10.1016/j.procs.2014.05.039.

[34] YANF Guangyong and LIU Jianguo. A local-world evolving hypernetwork model[J]., 2014, 23(1): 018901-018909. doi:10.1088/1674-1056/23/1/018901.

[35] Lü Linyuan, PAN Liming, ZHOU Tao,. Toward link predictability of complex networks[J]., 2015, 112(8): 2325-2330.

[36] VON MERING C, KRAUSE R, SNEL B,. Comparative assessment of large-scale data sets of protein-protein interactions[J]., 2002, 417(6887): 399-403.doi: 10.1038/nature750.

[37] SENDI?A-NADAL I, LEYVA I, NAVAS A,Effects of degree correlations on the explosive synchronization of scale-free networks[J]., 2015, 91(3): 032811-032819.doi: 10.1103/PhysRevE.91.032811.

Information Coupling of Local Topology Promoting the Network Evolution

LIU Shuxin①JI Xinsheng①②LIU Caixia①TANG Hongbo①GONG Xiaorui①

①(National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China)②(National Engineering Laboratory for Mobile Network Security, Beijing 100876, China)

To study the effects of information coupling of local topology on the complex network evolution, a new weighted method is proposed based on local topology information, which can measure the closeness of connection and the coupling degree of topology information between nodes. In this paper, to demonstrate the efficiency of the information coupling of local topology, an empirical research is made on characteristic statistics of evolving model and real network data testing of link prediction respectively. Firstly, the weighted method is applied to BA model; TwBA and the local world model TwLW are proposed based on the topology weighted method. Simulation experiments show that the degree distribution of TwBA can be rapidly changed from exponential distribution to power law distribution with the increasing of the connection numbers for new added nodes, which confirmes that the phenomenon of accelerating growth appears widely in the evolution of many real scale-free networks. Then, based on TwBA model, an accelerating growth model A-TwBA is proposed, and the A-TwBA model presents power law distribution for different accelerating growth rates. The degree distribution of TwLW is changed from stretched exponential distribution to power law distribution for different sizes of local world. Finally, the proposed weighted method is applied to link prediction methods (including CN, Salton and RA index), and three weighted indices are proposed. Empirical study shows that the weighted proposed method can significantly improve the prediction accuracy of these basic indices, and some of them are higher than those of the global indices.

Complex network; Local topology; Evolving model; Link prediction; Information coupling

N94; TP3; TP391

A

1009-5896(2016)09-2180-08

10.11999/JEIT151338

2015-11-26；

2016-04-07；

2016-05-25

國(guó)家自然科學(xué)基金創(chuàng)新研究群體項(xiàng)目(61521003)，國(guó)家高技術(shù)研究發(fā)展計(jì)劃(2014AA01A701)

The Foundation for Innovative Research Groups of the National Natural Science Foundation of China (61521003), The National High Technology Research and Development Program of China (2014AA01A701)

劉樹新 liushuxin11@126.com

劉樹新： 男，1987年生，博士，研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、鏈路預(yù)測(cè)、移動(dòng)網(wǎng)絡(luò)安全.

季新生： 男，1968年生，教授，博士生導(dǎo)師，研究方向?yàn)橐苿?dòng)網(wǎng)絡(luò)安全、移動(dòng)通信技術(shù)、無線網(wǎng)絡(luò)防護(hù).

劉彩霞： 女，1974年生，副教授，碩士生導(dǎo)師，研究方向?yàn)榫W(wǎng)絡(luò)安全、社會(huì)網(wǎng)絡(luò)、下一代移動(dòng)網(wǎng)絡(luò).

湯紅波： 男，1968年生，教授，碩士生導(dǎo)師，研究方向?yàn)橐苿?dòng)網(wǎng)絡(luò)安全、下一代移動(dòng)網(wǎng)絡(luò).

鞏小銳： 男，1991年生，博士，研究方向?yàn)樾滦途W(wǎng)絡(luò)體系結(jié)構(gòu)、社會(huì)網(wǎng)絡(luò).