孫睿, 羅萬伯
(1.成都師范學(xué)院 計(jì)算機(jī)科學(xué)系, 四川,成都 611130;2.成都大學(xué) 四川省模式識別與智能信息處理重點(diǎn)實(shí)驗(yàn)室,四川,成都 610106;3.四川大學(xué) 計(jì)算機(jī)學(xué)院, 四川,成都 610041)
?
基于節(jié)點(diǎn)吸引力的可調(diào)參數(shù)復(fù)雜網(wǎng)絡(luò)模型
孫睿1,2, 羅萬伯3
(1.成都師范學(xué)院 計(jì)算機(jī)科學(xué)系, 四川,成都 611130;2.成都大學(xué) 四川省模式識別與智能信息處理重點(diǎn)實(shí)驗(yàn)室,四川,成都 610106;3.四川大學(xué) 計(jì)算機(jī)學(xué)院, 四川,成都 610041)
針對真實(shí)網(wǎng)絡(luò)的生長演化規(guī)律,以及BA無標(biāo)度網(wǎng)絡(luò)模型和原始的節(jié)點(diǎn)吸引力模型在擇優(yōu)連接以及生成網(wǎng)絡(luò)統(tǒng)計(jì)特征方面所存在的問題,綜合考慮復(fù)雜網(wǎng)絡(luò)生長演化過程中節(jié)點(diǎn)度和節(jié)點(diǎn)吸引力的擇優(yōu)連接特性,提出了一種基于節(jié)點(diǎn)吸引力的可調(diào)參數(shù)復(fù)雜網(wǎng)絡(luò)模型. 理論研究與仿真實(shí)驗(yàn)分析表明,基于節(jié)點(diǎn)吸引力的可調(diào)參數(shù)復(fù)雜網(wǎng)絡(luò)模型可以有效生成結(jié)構(gòu)穩(wěn)定并與實(shí)際網(wǎng)絡(luò)統(tǒng)計(jì)特征很接近的復(fù)雜網(wǎng)絡(luò),通過調(diào)節(jié)模型參數(shù)可以靈活調(diào)整網(wǎng)絡(luò)的生長演化過程. 模型生成的網(wǎng)絡(luò)度分布仍然服從冪律分布,并且具有較高的群集系數(shù)和平均路徑長度.
復(fù)雜網(wǎng)絡(luò);節(jié)點(diǎn)吸引力;可調(diào)參數(shù);節(jié)點(diǎn)度分布
現(xiàn)實(shí)世界中的諸多復(fù)雜系統(tǒng)都以網(wǎng)絡(luò)的形式存在[1],比如社會系統(tǒng)中的人際關(guān)系網(wǎng)、科學(xué)家合作網(wǎng)、世界貿(mào)易網(wǎng)和流行病傳播網(wǎng);生態(tài)系統(tǒng)中的食物鏈網(wǎng)、神經(jīng)元網(wǎng)、新陳代謝網(wǎng)和蛋白質(zhì)相互作用網(wǎng);信息系統(tǒng)中的論文引用網(wǎng)、因特網(wǎng)和萬維網(wǎng);人工技術(shù)系統(tǒng)中的電話網(wǎng)、電力網(wǎng)和交通運(yùn)輸網(wǎng)等. 經(jīng)過對真實(shí)網(wǎng)絡(luò)的大量研究,Watts和 Stregatz以及Barabasi和Albert提出了WS小世界(small world) 網(wǎng)絡(luò)模型[2]和BA無標(biāo)度(scale free)網(wǎng)絡(luò)模型[3]. 小世界效應(yīng)、無標(biāo)度特性以及社區(qū)結(jié)構(gòu)(community structure)[4]等重要的拓?fù)浣Y(jié)構(gòu)屬性的發(fā)現(xiàn)與研究,使得復(fù)雜網(wǎng)絡(luò)的研究跨越了從20世紀(jì)60年代開始的以隨機(jī)圖理論[5]為主導(dǎo)的研究而進(jìn)入了一個(gè)嶄新的紀(jì)元,各種宏觀性質(zhì)的微觀生成機(jī)制以及網(wǎng)絡(luò)的演化規(guī)律等一系列問題的研究成為科研學(xué)者廣泛關(guān)注的熱點(diǎn). WS模型和BA模型都具有非常簡明的生成規(guī)則,但是同時(shí)也不可避免忽略了影響實(shí)際網(wǎng)絡(luò)生長的因素,使得某些統(tǒng)計(jì)性質(zhì)與實(shí)際網(wǎng)絡(luò)相比有較大的偏差[6]. 比如WS小世界網(wǎng)絡(luò)模型雖然具有現(xiàn)實(shí)網(wǎng)絡(luò)的高聚類特征,但是其網(wǎng)絡(luò)度分布近似于泊松分布;BA無標(biāo)度網(wǎng)絡(luò)模型的度分布服從冪律分布,這與現(xiàn)實(shí)網(wǎng)絡(luò)是一致的,但其聚類效應(yīng)卻并不明顯并且冪指數(shù)固定為常數(shù)3,這與實(shí)際網(wǎng)絡(luò)冪指數(shù)通常在[1,3]的范圍內(nèi)不符.
近年來,為了克服上述的這些問題,學(xué)術(shù)界提出了許多相應(yīng)的改進(jìn)模型. Dorogovtsev[7]最早提出了原始節(jié)點(diǎn)吸引力模型(簡稱為Dorogovtsev模型),Dorogovtsev模型規(guī)定網(wǎng)絡(luò)中所有節(jié)點(diǎn)的初始吸引力都相等,網(wǎng)絡(luò)的生長演化受節(jié)點(diǎn)吸引力的影響,此模型較好的解決了現(xiàn)實(shí)網(wǎng)絡(luò)中孤立節(jié)點(diǎn)也會被連線的問題. 陶少華等[8]提出了一種基于節(jié)點(diǎn)吸引力的復(fù)雜網(wǎng)絡(luò)模型(簡稱為NAM模型),該模型以網(wǎng)絡(luò)中的節(jié)點(diǎn)在單位時(shí)間內(nèi)所獲得的連接數(shù)作為節(jié)點(diǎn)的吸引力,同時(shí)假設(shè)各節(jié)點(diǎn)有同等的連接機(jī)會,模型的擇優(yōu)連接概率由節(jié)點(diǎn)吸引力和節(jié)點(diǎn)度共同決定. 田生文等[9]針對原始節(jié)點(diǎn)吸引力模型及其擴(kuò)展模型普遍具有較小的群集系數(shù)這一缺陷,提出了一個(gè)具有聚類效應(yīng)的節(jié)點(diǎn)吸引力復(fù)雜網(wǎng)絡(luò)模型(簡稱為CALW模型). CALW模型分析了真實(shí)網(wǎng)絡(luò)中擇優(yōu)連接的局域性特點(diǎn),將節(jié)點(diǎn)的吸引力定義為隨時(shí)間變化的函數(shù),實(shí)驗(yàn)結(jié)果表明此模型具有較高的群集系數(shù),更吻合實(shí)際網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和統(tǒng)計(jì)特性. 本文在以上研究的基礎(chǔ)上提出了一種基于節(jié)點(diǎn)吸引力的可調(diào)參數(shù)的復(fù)雜網(wǎng)絡(luò)模型.
1.1 節(jié)點(diǎn)吸引力
許多真實(shí)網(wǎng)絡(luò)都展現(xiàn)了擇優(yōu)連接的特征,這說明節(jié)點(diǎn)的連接概率與節(jié)點(diǎn)度是有關(guān)的,但是節(jié)點(diǎn)擇優(yōu)的選擇標(biāo)準(zhǔn)并非都簡單如BA模型所描述的只是選擇節(jié)點(diǎn)度大的節(jié)點(diǎn). 例如,在社交網(wǎng)絡(luò)中每個(gè)人結(jié)交新朋友的速率并不完全相同,有些魅力十足的人會更容易的交友,而這樣的人有時(shí)往往并不是在網(wǎng)絡(luò)中非?;钴S并廣泛交流的人;在科研合作網(wǎng)絡(luò)中,一個(gè)新加入的人員選擇合作的對象既要是在網(wǎng)絡(luò)中已經(jīng)有很高的成就和威望的學(xué)者,又要是在與新加入者感興趣領(lǐng)域近期比較活躍而有較多貢獻(xiàn)的人員;在輿情網(wǎng)絡(luò)中,一個(gè)節(jié)點(diǎn)如果是一個(gè)輿論觀點(diǎn)的發(fā)起者或者是一個(gè)鮮明觀點(diǎn)的支持者,那么它可能在短期內(nèi)以更高的速率獲得其他人的關(guān)注與聯(lián)系. 以上的例子都說明在復(fù)雜網(wǎng)絡(luò)的增長演化過程中,新節(jié)點(diǎn)的擇優(yōu)連接是普遍存在的,但選擇的標(biāo)準(zhǔn)除了考慮節(jié)點(diǎn)的度還要考慮其他吸引因素.
定義吸引因子β,用來具體量化網(wǎng)絡(luò)中節(jié)點(diǎn)對新節(jié)點(diǎn)的吸引力的大小,則每個(gè)節(jié)點(diǎn)的吸引因子表示為βi. 吸引因子βi的計(jì)算公式為
(1)
表示單位時(shí)間內(nèi)節(jié)點(diǎn)獲得連接數(shù)量的多少,其中ΔT=t-ti,ti表示節(jié)點(diǎn)vi在ti時(shí)刻加入網(wǎng)絡(luò),ni為節(jié)點(diǎn)vi在ΔT時(shí)間內(nèi)獲得的連接數(shù)量.
節(jié)點(diǎn)的度表示的是節(jié)點(diǎn)在網(wǎng)絡(luò)中的拓?fù)湮恢?,是某一時(shí)刻靜態(tài)的度量,節(jié)點(diǎn)吸引力描述的是節(jié)點(diǎn)在一段時(shí)間內(nèi)的連接變化,是一個(gè)對于動態(tài)過程的度量.
1.2 算法描述
對于真實(shí)復(fù)雜網(wǎng)絡(luò)的大量實(shí)證研究表明,擇優(yōu)連接機(jī)制是具有普適性的復(fù)雜網(wǎng)絡(luò)生長演化特性. BA模型是最具代表性的網(wǎng)絡(luò)擇優(yōu)連接的生長模型,但是BA模型只考慮了節(jié)點(diǎn)度的擇優(yōu)連接,而完全忽略了節(jié)點(diǎn)吸引力的連接因素. Dorogovtsev模型則正好相反,它只依照節(jié)點(diǎn)吸引力的大小擇優(yōu)連接網(wǎng)絡(luò)節(jié)點(diǎn),而不考慮節(jié)點(diǎn)度的大小. CALW模型雖然具有聚類的特點(diǎn),使生成的復(fù)雜網(wǎng)絡(luò)具有與實(shí)際網(wǎng)絡(luò)相似的較高的群集系數(shù),但是CALW模型同樣僅僅只以節(jié)點(diǎn)吸引力作為擇優(yōu)連接的標(biāo)準(zhǔn). NAM模型雖然同時(shí)考慮了節(jié)點(diǎn)度和節(jié)點(diǎn)吸引力的擇優(yōu)連接,但是此模型中節(jié)點(diǎn)的連接概率只是這兩者的簡單線性相加,明顯缺乏靈活性,這也極大地限制了模型的適用范圍. 因此,針對以上的分析,本文在同時(shí)考慮節(jié)點(diǎn)度和節(jié)點(diǎn)吸引力這兩個(gè)重要的擇優(yōu)連接因素的基礎(chǔ)上,進(jìn)一步設(shè)置了兩個(gè)可調(diào)參數(shù),用于根據(jù)復(fù)雜網(wǎng)絡(luò)生長的真實(shí)環(huán)境來調(diào)節(jié)節(jié)點(diǎn)度和節(jié)點(diǎn)吸引力這兩者在節(jié)點(diǎn)連接概率中所占的比重. 比如,因特網(wǎng)的網(wǎng)絡(luò)生成過程往往更看重節(jié)點(diǎn)的度的大小,也就是新節(jié)點(diǎn)在加入網(wǎng)絡(luò)時(shí)更偏重連接具有“明星效應(yīng)”的節(jié)點(diǎn),此時(shí)就可以相應(yīng)增大模型中節(jié)點(diǎn)度的比例系數(shù)而生成更接近于真實(shí)的因特網(wǎng)拓?fù)鋵傩缘膹?fù)雜網(wǎng)絡(luò);同理,在社交網(wǎng)絡(luò)中,人們則更偏向于與對自己有足夠吸引力的節(jié)點(diǎn)相連接,那么此時(shí)也可以減小節(jié)點(diǎn)度的參數(shù)值而增大節(jié)點(diǎn)吸引力的參數(shù)值,以此擇優(yōu)連接概率生成的網(wǎng)絡(luò)就會更符合社交網(wǎng)絡(luò)的真實(shí)情況.
可調(diào)參數(shù)的節(jié)點(diǎn)吸引力復(fù)雜網(wǎng)絡(luò)模型的具體算法描述如下.
初始條件:初始時(shí),網(wǎng)絡(luò)是由m0個(gè)節(jié)點(diǎn)和e0條邊組成的無向無權(quán)網(wǎng)絡(luò).
增長機(jī)制:在每個(gè)時(shí)間步,一個(gè)新節(jié)點(diǎn)vj加入到網(wǎng)絡(luò)中,這個(gè)節(jié)點(diǎn)與網(wǎng)絡(luò)中已經(jīng)存在的m(m≤m0)個(gè)節(jié)點(diǎn)相連接.
擇優(yōu)連接:每個(gè)新節(jié)點(diǎn)vj與網(wǎng)絡(luò)中舊節(jié)點(diǎn)vi相連的概率服從如下的規(guī)則
(2)
(3)
1.3 節(jié)點(diǎn)吸引力模型的度分布
假設(shè)新加入節(jié)點(diǎn)vj與原有節(jié)點(diǎn)vi相連接,則節(jié)點(diǎn)vi將會依照式(2)成比例的增加其度數(shù)ki,根據(jù)平均場理論[10],則有
(4)
?ki?t=mαki+γβi∑l(αkl+γβl)=mαki+γβi2αmt+γ∑lβl.(5)
其初始條件是節(jié)點(diǎn)vi在ti時(shí)刻進(jìn)入網(wǎng)絡(luò),其度數(shù)ki(ti)=m. 故方程(5)滿足初始條件的解為
(6)
在ki≥0的部分,可將ki(t)的概率表示為
(7)
因?yàn)闀r(shí)間t是服從均勻分布的,所以
(8)
代入式(7)可得
(9)
因此,節(jié)點(diǎn)的度分布為
(10)
當(dāng)t→+∞時(shí),
(11)
所以,當(dāng)α=1,γ=0時(shí),模型退化為BA模型,P(k)≈2m2k-3;當(dāng)α=γ=1/2時(shí),P(k)≈2(m+βi)2(k+βi)-3,這與文獻(xiàn)[8]所描述的情況相同,模型即為NAM模型;當(dāng)α=0,γ=1時(shí),網(wǎng)絡(luò)擇優(yōu)連接完全按照節(jié)點(diǎn)吸引力的變化而變化,此時(shí)類似于文獻(xiàn)[9]的模型中初始節(jié)點(diǎn)吸引力都相同的情況,模型退化為Dorogovtsev模型. 因此,本文提出的基于節(jié)點(diǎn)吸引力的可調(diào)參數(shù)復(fù)雜網(wǎng)絡(luò)模型是一個(gè)綜合了節(jié)點(diǎn)度擇優(yōu)連接以及節(jié)點(diǎn)吸引力連接的復(fù)雜網(wǎng)絡(luò)生長演化的統(tǒng)一模型.
根據(jù)本文提出的基于節(jié)點(diǎn)吸引力的可調(diào)參數(shù)復(fù)雜網(wǎng)絡(luò)模型,利用計(jì)算機(jī)仿真實(shí)驗(yàn),分別從度分布、群集系數(shù)、平均路徑長度等復(fù)雜網(wǎng)絡(luò)的特征參數(shù)與BA模型、NAM模型以及Dorogovtsev模型進(jìn)行比較.
2.1 度分布
節(jié)點(diǎn)度是指網(wǎng)絡(luò)中節(jié)點(diǎn)與其他節(jié)點(diǎn)間的連邊數(shù). 度分布則是節(jié)點(diǎn)恰好有k條連邊的概率,用節(jié)點(diǎn)度的概率分布函數(shù)P(k)表示. 對真實(shí)復(fù)雜網(wǎng)絡(luò)的實(shí)證研究表明,大多數(shù)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)度分布服從冪律分布,即P(k)~k-γ,其中2<γ≤3.
圖1給出了幾種模型的節(jié)點(diǎn)度分布情況,其中,網(wǎng)絡(luò)模型參數(shù)為節(jié)點(diǎn)總數(shù)N=3 000,初始節(jié)點(diǎn)數(shù)m0=5,每個(gè)新節(jié)點(diǎn)的連接數(shù)m=3,可調(diào)參數(shù)α=1,γ=0;α=γ=1/2;α=0,γ=1;α=1/4,γ=3/4以及α=3/4,γ=1/4. 從圖1可以看出,可調(diào)參數(shù)的節(jié)點(diǎn)吸引力模型與其他模型一樣,其節(jié)點(diǎn)度分布服從冪律分布. 由此可見,雖然可以靈活調(diào)整模型的參數(shù)值,使其生成機(jī)制發(fā)生了相應(yīng)的變化,但是網(wǎng)絡(luò)的最終整體拓?fù)浣Y(jié)構(gòu)并沒有發(fā)生太大的變化. 這表明同時(shí)考慮節(jié)點(diǎn)度與節(jié)點(diǎn)吸引力的擇優(yōu)連接機(jī)制是可以有效的生成結(jié)構(gòu)穩(wěn)定并與現(xiàn)實(shí)情況更接近的復(fù)雜網(wǎng)絡(luò)的.
2.2 群集系數(shù)
圖2是網(wǎng)絡(luò)規(guī)模N取不同值時(shí),幾種模型群集系數(shù)C的比較. 從圖2可以看出,本文提出的模型與其他模型生成網(wǎng)絡(luò)的群集系數(shù)在變化趨勢上基本一致,即隨著網(wǎng)絡(luò)規(guī)模的增大,群集系數(shù)降低;在同等的網(wǎng)絡(luò)規(guī)模下,幾種模型的群集系數(shù)差別不大,但是通過調(diào)整模型參數(shù)可以在一定程度上改變生成網(wǎng)絡(luò)的群集系數(shù). 當(dāng)網(wǎng)絡(luò)規(guī)模N=3 000時(shí),群集系數(shù)C大致在0.012~0.017的范圍內(nèi),基本與同等規(guī)模的實(shí)際復(fù)雜網(wǎng)絡(luò)相吻合.
2.3 平均路徑長度
圖3是網(wǎng)絡(luò)規(guī)模N取不同值時(shí),幾種模型平均路徑長度L的比較. 從圖3發(fā)現(xiàn)幾種模型的平均路徑長度的增加速率大致相同,均與網(wǎng)絡(luò)規(guī)模的對數(shù)成正比關(guān)系,這與現(xiàn)實(shí)世界中大多數(shù)復(fù)雜網(wǎng)絡(luò)的特性相符合. 在同等的網(wǎng)絡(luò)規(guī)模下,本文模型與BA模型、NAM模型的平均路徑長度很接近,改變模型參數(shù)取值可以適當(dāng)改變其平均路徑長度,但是Dorogovtsev模型生成網(wǎng)絡(luò)的平均路徑長度明顯要大于其他模型,這主要是因?yàn)镈orogovtsev模型在網(wǎng)絡(luò)增長時(shí)只考慮節(jié)點(diǎn)吸引力因素而忽視了節(jié)點(diǎn)度的大小,模型更不易于聚集. 當(dāng)網(wǎng)絡(luò)規(guī)模N=3 000時(shí),本文模型的平均路徑長度L≈3.8,與同等規(guī)模的實(shí)際復(fù)雜網(wǎng)絡(luò)大致相同.
研究了真實(shí)網(wǎng)絡(luò)的生長演化規(guī)律,針對BA模型和原始的節(jié)點(diǎn)吸引力模型所存在的問題,提出了一種基于節(jié)點(diǎn)吸引力的可調(diào)參數(shù)復(fù)雜網(wǎng)絡(luò)模型. 該模型考慮了網(wǎng)絡(luò)演化過程中節(jié)點(diǎn)度與節(jié)點(diǎn)吸引力變化對于擇優(yōu)連接機(jī)制的影響. 理論研究與仿真實(shí)驗(yàn)分析表明,通過調(diào)節(jié)模型參數(shù)可以靈活調(diào)整網(wǎng)絡(luò)的生長演化過程,使之更加符合真實(shí)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和統(tǒng)計(jì)特性.
[1] Sole R V. Complex networks: structure, robustness and function[M]. Cambridge: Cambridge University Press, 2012.
[2] Watts D J, Strogatz S H. Collective dynamics of small world networks[J]. Nature, 1998,393(4):440-442.
[3] Barabasi A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999,286(5439):509-512.
[4] Nadakuditi R R, Newman M E J. Graph spectra and the detectability of community structure in networks[J]. Physical Review Letters, 2012,108(18):188701.
[5] Karrer B, Newman M E J. Random graphs containing arbitrary distributions of subgraphs[J]. Physical Review E, 2010,82(6):066118.
[6] Li M, Gao L, Fan Y, et al. Emergence of global preferential attachment from local interaction[J]. New Journal of Physics, 2010,12(4):043029.
[7] Dorogovtsev S N, Mendes J F F, Samukhin A N. Structure of Growing Networks with Preferential Linking[J]. Physical Review Letters, 2000,85(21):4633-4636.
[8] 陶少華,楊春,李慧娜,等.基于節(jié)點(diǎn)吸引力的復(fù)雜網(wǎng)絡(luò)演化模型研究[J].計(jì)算機(jī)工程,2009,35(1):111-113.
Tao Shaohua, Yang Chun, Li Huina, et al. Research on complex networks evolution model based on node attraction[J]. Computer Engineering, 2009,35(1):111-113. (in Chinese)
[9] 田生文,楊洪勇,李阿麗,等.基于聚類效應(yīng)節(jié)點(diǎn)吸引力的復(fù)雜網(wǎng)絡(luò)模型[J].計(jì)算機(jī)工程,2010,36(10):58-60.
Tian Shengwen, Yang Hongyong, Li Ali, et al. Complex network model based on node attraction with clustering effect[J]. Computer Engineering, 2010,36(10):58-60. (in Chinese)
[10] Buice M A, Chow C C. Beyond mean field theory: statistical field theory for neural networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2013(3):P03003.
(責(zé)任編輯:劉芳)
Complex Network Model Based on Node Attraction with Tunable Parameters
SUN Rui1,2, LUO Wan-bo3
(1.Department of Computer Science, Chengdu Normal University, Chengdu, Sichuan 611130, China;2.Key Laboratory of Pattern Recognition and Intelligent Information Processing, Institutions of Higher Education of Sichuan Province, Chengdu University, Chengdu, Sichuan 610106, China;3.School of Computer Science, Sichuan University, Chengdu, Sichuan 610041, China)
According to the evolution rule of real-world networks and aiming at the problems existing in preferential attachment and statistical characteristics of network in BA model and initial attractive model, taking into account preferential attachment of node degree and node attraction in the evolution process of complex network, a complex network model based on node attraction with tunable parameters was proposed. Theory research and simulation analysis show the fact that the complex network model based on node attraction with tunable parameters can effectively generate networks with stable structure and actual statistical characteristics. Specifically, the degree distribution of networks still follows power-law distribution, while clustering coefficient and average path length are high.
complex network; node attraction; tunable parameters; degree distribution
2013-07-31
四川省教育廳自然科學(xué)重點(diǎn)資助項(xiàng)目(15ZA0330);四川省教育廳創(chuàng)新團(tuán)隊(duì)資助項(xiàng)目(15TD0038);成都師范學(xué)院培育資助項(xiàng)目(CS14ZD03);成都師范學(xué)院高層次引進(jìn)人才專項(xiàng)科研資助項(xiàng)目(YJRC2015-7);成都大學(xué)模式識別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室開放資助課題
孫睿(1982—),男,博士,講師,E-mail:cug123456@126.com.
TP 311; N 94
A
1001-0645(2016)01-0059-05
10.15918/j.tbit1001-0645.2016.01.011