孫睿， 羅萬伯

(1.成都師范學院 計算機科學系， 四川，成都 611130；2.成都大學 四川省模式識別與智能信息處理重點實驗室，四川，成都 610106；3.四川大學 計算機學院， 四川，成都 610041)

?

基于節(jié)點吸引力的可調參數(shù)復雜網絡模型

孫睿1，2， 羅萬伯3

(1.成都師范學院 計算機科學系， 四川，成都 611130；2.成都大學 四川省模式識別與智能信息處理重點實驗室，四川，成都 610106；3.四川大學 計算機學院， 四川，成都 610041)

針對真實網絡的生長演化規(guī)律，以及BA無標度網絡模型和原始的節(jié)點吸引力模型在擇優(yōu)連接以及生成網絡統(tǒng)計特征方面所存在的問題，綜合考慮復雜網絡生長演化過程中節(jié)點度和節(jié)點吸引力的擇優(yōu)連接特性，提出了一種基于節(jié)點吸引力的可調參數(shù)復雜網絡模型. 理論研究與仿真實驗分析表明，基于節(jié)點吸引力的可調參數(shù)復雜網絡模型可以有效生成結構穩(wěn)定并與實際網絡統(tǒng)計特征很接近的復雜網絡，通過調節(jié)模型參數(shù)可以靈活調整網絡的生長演化過程. 模型生成的網絡度分布仍然服從冪律分布，并且具有較高的群集系數(shù)和平均路徑長度.

復雜網絡；節(jié)點吸引力；可調參數(shù)；節(jié)點度分布

現(xiàn)實世界中的諸多復雜系統(tǒng)都以網絡的形式存在[1]，比如社會系統(tǒng)中的人際關系網、科學家合作網、世界貿易網和流行病傳播網；生態(tài)系統(tǒng)中的食物鏈網、神經元網、新陳代謝網和蛋白質相互作用網；信息系統(tǒng)中的論文引用網、因特網和萬維網；人工技術系統(tǒng)中的電話網、電力網和交通運輸網等. 經過對真實網絡的大量研究，Watts和 Stregatz以及Barabasi和Albert提出了WS小世界(small world) 網絡模型[2]和BA無標度(scale free)網絡模型[3]. 小世界效應、無標度特性以及社區(qū)結構(community structure)[4]等重要的拓撲結構屬性的發(fā)現(xiàn)與研究，使得復雜網絡的研究跨越了從20世紀60年代開始的以隨機圖理論[5]為主導的研究而進入了一個嶄新的紀元，各種宏觀性質的微觀生成機制以及網絡的演化規(guī)律等一系列問題的研究成為科研學者廣泛關注的熱點. WS模型和BA模型都具有非常簡明的生成規(guī)則，但是同時也不可避免忽略了影響實際網絡生長的因素，使得某些統(tǒng)計性質與實際網絡相比有較大的偏差[6]. 比如WS小世界網絡模型雖然具有現(xiàn)實網絡的高聚類特征，但是其網絡度分布近似于泊松分布；BA無標度網絡模型的度分布服從冪律分布，這與現(xiàn)實網絡是一致的，但其聚類效應卻并不明顯并且冪指數(shù)固定為常數(shù)3，這與實際網絡冪指數(shù)通常在[1，3]的范圍內不符.

近年來，為了克服上述的這些問題，學術界提出了許多相應的改進模型. Dorogovtsev[7]最早提出了原始節(jié)點吸引力模型(簡稱為Dorogovtsev模型)，Dorogovtsev模型規(guī)定網絡中所有節(jié)點的初始吸引力都相等，網絡的生長演化受節(jié)點吸引力的影響，此模型較好的解決了現(xiàn)實網絡中孤立節(jié)點也會被連線的問題. 陶少華等[8]提出了一種基于節(jié)點吸引力的復雜網絡模型(簡稱為NAM模型)，該模型以網絡中的節(jié)點在單位時間內所獲得的連接數(shù)作為節(jié)點的吸引力，同時假設各節(jié)點有同等的連接機會，模型的擇優(yōu)連接概率由節(jié)點吸引力和節(jié)點度共同決定. 田生文等[9]針對原始節(jié)點吸引力模型及其擴展模型普遍具有較小的群集系數(shù)這一缺陷，提出了一個具有聚類效應的節(jié)點吸引力復雜網絡模型(簡稱為CALW模型). CALW模型分析了真實網絡中擇優(yōu)連接的局域性特點，將節(jié)點的吸引力定義為隨時間變化的函數(shù)，實驗結果表明此模型具有較高的群集系數(shù)，更吻合實際網絡的拓撲結構和統(tǒng)計特性. 本文在以上研究的基礎上提出了一種基于節(jié)點吸引力的可調參數(shù)的復雜網絡模型.

1 可調參數(shù)的節(jié)點吸引力模型

1.1 節(jié)點吸引力

許多真實網絡都展現(xiàn)了擇優(yōu)連接的特征，這說明節(jié)點的連接概率與節(jié)點度是有關的，但是節(jié)點擇優(yōu)的選擇標準并非都簡單如BA模型所描述的只是選擇節(jié)點度大的節(jié)點. 例如，在社交網絡中每個人結交新朋友的速率并不完全相同，有些魅力十足的人會更容易的交友，而這樣的人有時往往并不是在網絡中非?；钴S并廣泛交流的人；在科研合作網絡中，一個新加入的人員選擇合作的對象既要是在網絡中已經有很高的成就和威望的學者，又要是在與新加入者感興趣領域近期比較活躍而有較多貢獻的人員；在輿情網絡中，一個節(jié)點如果是一個輿論觀點的發(fā)起者或者是一個鮮明觀點的支持者，那么它可能在短期內以更高的速率獲得其他人的關注與聯(lián)系. 以上的例子都說明在復雜網絡的增長演化過程中，新節(jié)點的擇優(yōu)連接是普遍存在的，但選擇的標準除了考慮節(jié)點的度還要考慮其他吸引因素.

定義吸引因子β，用來具體量化網絡中節(jié)點對新節(jié)點的吸引力的大小，則每個節(jié)點的吸引因子表示為βi. 吸引因子βi的計算公式為

(1)

表示單位時間內節(jié)點獲得連接數(shù)量的多少，其中ΔT=t-ti，ti表示節(jié)點vi在ti時刻加入網絡，ni為節(jié)點vi在ΔT時間內獲得的連接數(shù)量.

節(jié)點的度表示的是節(jié)點在網絡中的拓撲位置，是某一時刻靜態(tài)的度量，節(jié)點吸引力描述的是節(jié)點在一段時間內的連接變化，是一個對于動態(tài)過程的度量.

1.2 算法描述

對于真實復雜網絡的大量實證研究表明，擇優(yōu)連接機制是具有普適性的復雜網絡生長演化特性. BA模型是最具代表性的網絡擇優(yōu)連接的生長模型，但是BA模型只考慮了節(jié)點度的擇優(yōu)連接，而完全忽略了節(jié)點吸引力的連接因素. Dorogovtsev模型則正好相反，它只依照節(jié)點吸引力的大小擇優(yōu)連接網絡節(jié)點，而不考慮節(jié)點度的大小. CALW模型雖然具有聚類的特點，使生成的復雜網絡具有與實際網絡相似的較高的群集系數(shù)，但是CALW模型同樣僅僅只以節(jié)點吸引力作為擇優(yōu)連接的標準. NAM模型雖然同時考慮了節(jié)點度和節(jié)點吸引力的擇優(yōu)連接，但是此模型中節(jié)點的連接概率只是這兩者的簡單線性相加，明顯缺乏靈活性，這也極大地限制了模型的適用范圍. 因此，針對以上的分析，本文在同時考慮節(jié)點度和節(jié)點吸引力這兩個重要的擇優(yōu)連接因素的基礎上，進一步設置了兩個可調參數(shù)，用于根據(jù)復雜網絡生長的真實環(huán)境來調節(jié)節(jié)點度和節(jié)點吸引力這兩者在節(jié)點連接概率中所占的比重. 比如，因特網的網絡生成過程往往更看重節(jié)點的度的大小，也就是新節(jié)點在加入網絡時更偏重連接具有“明星效應”的節(jié)點，此時就可以相應增大模型中節(jié)點度的比例系數(shù)而生成更接近于真實的因特網拓撲屬性的復雜網絡；同理，在社交網絡中，人們則更偏向于與對自己有足夠吸引力的節(jié)點相連接，那么此時也可以減小節(jié)點度的參數(shù)值而增大節(jié)點吸引力的參數(shù)值，以此擇優(yōu)連接概率生成的網絡就會更符合社交網絡的真實情況.

可調參數(shù)的節(jié)點吸引力復雜網絡模型的具體算法描述如下.

初始條件：初始時，網絡是由m0個節(jié)點和e0條邊組成的無向無權網絡.

增長機制：在每個時間步，一個新節(jié)點vj加入到網絡中，這個節(jié)點與網絡中已經存在的m(m≤m0)個節(jié)點相連接.

擇優(yōu)連接：每個新節(jié)點vj與網絡中舊節(jié)點vi相連的概率服從如下的規(guī)則

(2)

(3)

1.3 節(jié)點吸引力模型的度分布

假設新加入節(jié)點vj與原有節(jié)點vi相連接，則節(jié)點vi將會依照式(2)成比例的增加其度數(shù)ki，根據(jù)平均場理論[10]，則有

(4)

?ki?t=mαki+γβi∑l(αkl+γβl)=mαki+γβi2αmt+γ∑lβl.(5)

其初始條件是節(jié)點vi在ti時刻進入網絡，其度數(shù)ki(ti)=m. 故方程(5)滿足初始條件的解為

(6)

在ki≥0的部分，可將ki(t)的概率表示為

(7)

因為時間t是服從均勻分布的，所以

(8)

代入式(7)可得

(9)

因此，節(jié)點的度分布為

(10)

當t→+∞時，

(11)

所以，當α=1，γ=0時，模型退化為BA模型，P(k)≈2m2k-3；當α=γ=1/2時，P(k)≈2(m+βi)2(k+βi)-3，這與文獻[8]所描述的情況相同，模型即為NAM模型；當α=0，γ=1時，網絡擇優(yōu)連接完全按照節(jié)點吸引力的變化而變化，此時類似于文獻[9]的模型中初始節(jié)點吸引力都相同的情況，模型退化為Dorogovtsev模型. 因此，本文提出的基于節(jié)點吸引力的可調參數(shù)復雜網絡模型是一個綜合了節(jié)點度擇優(yōu)連接以及節(jié)點吸引力連接的復雜網絡生長演化的統(tǒng)一模型.

2 仿真實驗與分析

根據(jù)本文提出的基于節(jié)點吸引力的可調參數(shù)復雜網絡模型，利用計算機仿真實驗，分別從度分布、群集系數(shù)、平均路徑長度等復雜網絡的特征參數(shù)與BA模型、NAM模型以及Dorogovtsev模型進行比較.

2.1 度分布

節(jié)點度是指網絡中節(jié)點與其他節(jié)點間的連邊數(shù). 度分布則是節(jié)點恰好有k條連邊的概率，用節(jié)點度的概率分布函數(shù)P(k)表示. 對真實復雜網絡的實證研究表明，大多數(shù)復雜網絡中節(jié)點度分布服從冪律分布，即P(k)～k-γ，其中2<γ≤3.

圖1給出了幾種模型的節(jié)點度分布情況，其中，網絡模型參數(shù)為節(jié)點總數(shù)N=3 000，初始節(jié)點數(shù)m0=5，每個新節(jié)點的連接數(shù)m=3，可調參數(shù)α=1，γ=0；α=γ=1/2；α=0，γ=1；α=1/4，γ=3/4以及α=3/4，γ=1/4. 從圖1可以看出，可調參數(shù)的節(jié)點吸引力模型與其他模型一樣，其節(jié)點度分布服從冪律分布. 由此可見，雖然可以靈活調整模型的參數(shù)值，使其生成機制發(fā)生了相應的變化，但是網絡的最終整體拓撲結構并沒有發(fā)生太大的變化. 這表明同時考慮節(jié)點度與節(jié)點吸引力的擇優(yōu)連接機制是可以有效的生成結構穩(wěn)定并與現(xiàn)實情況更接近的復雜網絡的.

2.2 群集系數(shù)

圖2是網絡規(guī)模N取不同值時，幾種模型群集系數(shù)C的比較. 從圖2可以看出，本文提出的模型與其他模型生成網絡的群集系數(shù)在變化趨勢上基本一致，即隨著網絡規(guī)模的增大，群集系數(shù)降低；在同等的網絡規(guī)模下，幾種模型的群集系數(shù)差別不大，但是通過調整模型參數(shù)可以在一定程度上改變生成網絡的群集系數(shù). 當網絡規(guī)模N=3 000時，群集系數(shù)C大致在0.012～0.017的范圍內，基本與同等規(guī)模的實際復雜網絡相吻合.

2.3 平均路徑長度

圖3是網絡規(guī)模N取不同值時，幾種模型平均路徑長度L的比較. 從圖3發(fā)現(xiàn)幾種模型的平均路徑長度的增加速率大致相同，均與網絡規(guī)模的對數(shù)成正比關系，這與現(xiàn)實世界中大多數(shù)復雜網絡的特性相符合. 在同等的網絡規(guī)模下，本文模型與BA模型、NAM模型的平均路徑長度很接近，改變模型參數(shù)取值可以適當改變其平均路徑長度，但是Dorogovtsev模型生成網絡的平均路徑長度明顯要大于其他模型，這主要是因為Dorogovtsev模型在網絡增長時只考慮節(jié)點吸引力因素而忽視了節(jié)點度的大小，模型更不易于聚集. 當網絡規(guī)模N=3 000時，本文模型的平均路徑長度L≈3.8，與同等規(guī)模的實際復雜網絡大致相同.

3 結 論

研究了真實網絡的生長演化規(guī)律，針對BA模型和原始的節(jié)點吸引力模型所存在的問題，提出了一種基于節(jié)點吸引力的可調參數(shù)復雜網絡模型. 該模型考慮了網絡演化過程中節(jié)點度與節(jié)點吸引力變化對于擇優(yōu)連接機制的影響. 理論研究與仿真實驗分析表明，通過調節(jié)模型參數(shù)可以靈活調整網絡的生長演化過程，使之更加符合真實網絡的拓撲結構和統(tǒng)計特性.

[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é)點吸引力的復雜網絡演化模型研究[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] 田生文，楊洪勇，李阿麗，等.基于聚類效應節(jié)點吸引力的復雜網絡模型[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.

(責任編輯：劉芳)

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

四川省教育廳自然科學重點資助項目(15ZA0330)；四川省教育廳創(chuàng)新團隊資助項目(15TD0038)；成都師范學院培育資助項目(CS14ZD03)；成都師范學院高層次引進人才專項科研資助項目(YJRC2015-7)；成都大學模式識別與智能信息處理四川省高校重點實驗室開放資助課題

孫睿(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