賈俊波，靳　禎

(1.中北大學理學院，山西太原　030051;2.山西大學復雜系統(tǒng)研究所，山西太原　030006)

?

基于偏微分方程的增長網(wǎng)絡結(jié)構(gòu)分析

賈俊波1，靳禎2

(1.中北大學理學院，山西太原030051;2.山西大學復雜系統(tǒng)研究所，山西太原030006)

摘要：為了研究網(wǎng)絡的功能，需要首先研究增長網(wǎng)絡的拓撲結(jié)構(gòu)，包括網(wǎng)絡的度分布和節(jié)點度等。當網(wǎng)絡規(guī)模足夠大時，將網(wǎng)絡節(jié)點的度看作連續(xù)變量，根據(jù)網(wǎng)絡演化過程中所滿足的馬爾科夫性，建立網(wǎng)絡節(jié)點數(shù)量的變化方程，從而化簡變形得到基于一階雙曲方程的增長網(wǎng)絡模型。求解得到了兼具優(yōu)先和隨機2種連接機制的網(wǎng)絡度分布P(k)和節(jié)點度k(t0)(t)，同時也發(fā)現(xiàn)了節(jié)點度函數(shù)與雙曲方程特征線之間的關(guān)系。根據(jù)網(wǎng)絡的演化機制，通過對該增長網(wǎng)絡模型進行隨機模擬，驗證了度分布與節(jié)點度理論結(jié)果的正確性。將網(wǎng)絡的度分布計算轉(zhuǎn)化為偏微分方程求解問題，將節(jié)點度的變化視為偏微分方程的特征線，將偏微分方程應用于增長網(wǎng)絡的建模中，從而可以解析地對網(wǎng)絡結(jié)構(gòu)進行分析。

關(guān)鍵詞：圖論；偏微分方程；應用數(shù)學；概率分布；結(jié)構(gòu)分析

復雜網(wǎng)絡是復雜系統(tǒng)的重要研究內(nèi)容，主要研究網(wǎng)絡的生成、結(jié)構(gòu)及其功能，也就是說網(wǎng)絡是從哪里來，其結(jié)構(gòu)如何，具有什么功能[1-5]。這些問題清楚了，就可以利用這些性質(zhì)研究現(xiàn)實世界大量存在的網(wǎng)絡，如Internet網(wǎng)、萬維網(wǎng)、社交朋友網(wǎng)、交通運輸網(wǎng)等復雜網(wǎng)絡[6-9]。復雜網(wǎng)絡在理論上可以看作一個圖，可以借助于圖論及隨機理論進行研究。早在1960年，ERD?S等[10]建立了隨機圖理論，開始了隨機網(wǎng)絡模型的研究。1998年，由WATTS等[11]構(gòu)造出了小世界網(wǎng)絡模型，刻畫了現(xiàn)實網(wǎng)絡中的小世界特性，解釋了六度分割理論。1999 年，BARABSI等[12]構(gòu)建了度分布具有冪律形式的無標度網(wǎng)絡模型(也稱BA網(wǎng)絡模型)，即度分布P(k)∝k-γ。BA無標度網(wǎng)絡模型描述了現(xiàn)實世界普遍存在的“富者越富”的現(xiàn)象，它的提出具有里程碑意義。

在網(wǎng)絡的生成、拓撲結(jié)構(gòu)和功能的研究中，網(wǎng)絡的度分布是描述網(wǎng)絡最基本的特征量，也是網(wǎng)絡研究的一個重點。度分布主要從實驗統(tǒng)計和理論計算獲得，目前，度分布的理論計算方法主要有BARABSI等[13]提出的平均場方法，DOROGOVTSEV等[14]提出的主方程方法，KRAPIVSKY等[15]提出的率方程方法，以及文獻[16—18]提出的基于馬氏鏈的數(shù)值方法。在網(wǎng)絡增長機制方面，LIU等[19]提出了一種同時具有優(yōu)先和隨機2種連接機制的增長網(wǎng)絡模型，并利用平均場方法計算出了網(wǎng)絡的近似度分布。譚利等[20]利用Stolz定理嚴格證明了此模型度分布的存在性。

本文將節(jié)點的度k看作連續(xù)變量，基于一階雙曲方程，建立了優(yōu)先和隨機2種連接機制下的增長網(wǎng)絡模型，使用方程求解方法解析計算了模型的網(wǎng)絡結(jié)構(gòu)，最后進行了模擬和討論。

1網(wǎng)絡的演化機制

本文所研究的增長網(wǎng)絡模型的演化機制包括新節(jié)點的增加和新增邊的連接。演化機制如下。

1)增長：以具有m0個節(jié)點l0條邊的連通網(wǎng)絡為初始網(wǎng)絡，每個時間步長增加一個新節(jié)點(i時刻新增的節(jié)點記為節(jié)點i)，同時該新節(jié)點發(fā)出m條邊連向舊節(jié)點；

2)連接：新增節(jié)點以概率p(0≤p≤1)依節(jié)點度進行優(yōu)先連接，以概率1-p進行隨機連接。則，舊節(jié)點i得到一條邊的概率為

(1)

表1　主要符號表

2增長網(wǎng)絡偏微分方程模型的建立

2.1增長網(wǎng)絡的度分布

由網(wǎng)絡的增長機制可知，網(wǎng)絡演化具有馬爾科夫性，即，在已知t時刻網(wǎng)絡結(jié)構(gòu)的情況下，t+1時刻網(wǎng)絡的演化狀況只與t時刻的網(wǎng)絡結(jié)構(gòu)有關(guān)，而與t時刻之前的網(wǎng)絡結(jié)構(gòu)無關(guān)。假設時間t和節(jié)點度k都是連續(xù)變化，則該增長網(wǎng)絡模型就是一個時間和狀態(tài)空間都連續(xù)的馬氏過程，因此可得

(2)

(3)

其中Δt為在所考慮的時間段內(nèi)新增的節(jié)點數(shù)。

將式(2)代入式(3)，得到

(4)

(5)

(6)

方程(6)兩邊同除以Δt，并令Δt→0，從而得到關(guān)于F(k,t)的偏微分方程：

(7)

解的可行域為D={(k,t)|k≥m,t>0}。當時間足夠大時，可以忽略初始網(wǎng)絡的節(jié)點數(shù)m0和邊數(shù)l0，此時令m0=0，l0=0，得到

(8)

解的可行域變?yōu)镈={(k,t)|k≥m,t≥T?0}。由于所有節(jié)點在進入網(wǎng)絡的同時都發(fā)出了m條邊，因此節(jié)點的度k一定大于等于m，所以一階雙曲方程(8)存在邊值條件:

F(m,t)=0,?t>T。

(9)

用特征線法求解方程(8)，并代入邊值條件(9)，得到F(k,t)的解析表達式:

(10)

從而得到增長網(wǎng)絡模型的度分布為

(11)

因此，對于不同優(yōu)先連接概率p可得到如下結(jié)論：

2)當p=1時，網(wǎng)絡為優(yōu)先連接增長網(wǎng)絡，即BA模型，其度分布為P(k)=2m2k-3；

2.2節(jié)點度kt0(t)

把節(jié)點t0在t(t≥t0)時刻的度記為kt0(t)，顯然kt0(t)是關(guān)于時間t的單調(diào)增函數(shù)。下面將研究節(jié)點度kt0(t)與偏微分方程(8)的關(guān)系。

根據(jù)模型的演化機制，得到節(jié)點度kt0(t)的變化率方程:

(12)

的初始條件為

kt0(t0)=m。

(13)

可以看到方程(12)即為偏微分方程(8)的特征方程。因此，節(jié)點度函數(shù)kt0(t)即為偏微分方程(8)的特征線，其解析式為

(14)

3模擬

為了驗證度分布P(k)和節(jié)點度kt0(t)理論結(jié)果的正確性，筆者進行了多次隨機模擬。從圖1-圖3可以看到，隨機模擬的結(jié)果和理論結(jié)果吻合得很好。圖1是不同連接概率p下網(wǎng)絡模型的度分布，可以看到在雙對數(shù)坐標系上隨機連接網(wǎng)絡(p=0)的度分布是一條彎曲的曲線(見圖1 a))。隨著連接概率p逐漸趨于1，度分布圖像會由曲線逐漸變成一條斜率為-3的直線。從圖2可以看到，當新節(jié)點發(fā)出的邊數(shù)m增大時，度分布圖像會向右移動。

圖1　不同優(yōu)先連接概率p下增長網(wǎng)絡模型的度分布Fig.1　Degree distribution of the network model with different parameters p

圖2　新增邊m不同時增長網(wǎng)絡模型的度分布Fig.2　Degree distribution of the network model with different parameters m

圖3　不同節(jié)點的度隨時間的變化Fig.3　Node degree changing with time

分析得知節(jié)點度函數(shù)kt0(t)與方程(8)的特征線是同一條曲線。從圖3也可以看到，節(jié)點的度確實是沿著這條曲線在增加。

4結(jié)論

通過將節(jié)點的度k作為連續(xù)變量，建立了基于偏微分方程的增長網(wǎng)絡模型，獲得了優(yōu)先和隨機2種連接機制下網(wǎng)絡度分布的解析表達式，以及節(jié)點度變化與偏微分方程特征線之間的關(guān)系。通過對該增長網(wǎng)絡模型的隨機模擬，驗證了度分布與節(jié)點度理論結(jié)果的正確性。與傳統(tǒng)方法相比，將網(wǎng)絡的度分布計算轉(zhuǎn)化為偏微分方程求解問題，把節(jié)點度的變化視為偏微分方程的特征線，將偏微分方程應用于增長網(wǎng)絡的建模中，從而可以更加解析地對網(wǎng)絡結(jié)構(gòu)進行研究，拓寬了復雜網(wǎng)絡拓撲結(jié)構(gòu)研究的方法。

參考文獻/References:

[1]汪小帆, 李翔, 陳關(guān)榮. 網(wǎng)絡科學導論[M]. 北京: 高等教育出版社，2012.

[2]趙洋, 單娟, 宋超. 復雜網(wǎng)絡中的病毒傳播機制研究[J].河北科技大學學報，2011, 32(3):252-255.

ZHAO Yang, SHAN Juan, SONG Chao. Virus propagation mechanism of complex network[J]. Journal of Hebei University of Science and Technology，2011,32(3):252-255.

[3]許云峰, 趙寧, 郝雪君,等. 基于三元閉包和會員閉包的社區(qū)發(fā)現(xiàn)算法研究[J].河北科技大學學報，2014,35(1):103-108.

XU Yunfeng, ZHAO Ning, HAO Xuejun,et al. A community detection algorithm based on triadic closure and membership closure[J]. Journal of Hebei University of Science and Technology,2014,35(1):103-108.

[4]杜云, 田強, 杜艷,等. 簡單動態(tài)遞歸神經(jīng)網(wǎng)絡在非線性系統(tǒng)辨識中的應用[J].河北科技大學學報,2009,30(2):130-134.

DU Yun, TIAN Qiang, DU Yan, et al. Application of simple dynamic recurrent neural network in non-linear system identification[J]. Journal of Hebei University of Science and Technology,2009,30(2):130-134.

[5]PASTOR-SATORRAS R, VESPIGNANI A. Epidemic dynamics and endemic states in complex networks[J]. Physical Review E, 2001, 63(6): 066117.

[6]MORENO Y, PASTOR-SATORRAS R, VESPIGNANI A. Epidemic outbreaks in complex heterogeneous networks[J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2002, 26(4): 521-529.

[7]BOGUNA M, PASTOR-SATORRAS R. Epidemic spreading in correlated complex networks[J]. Physical Review E, 2002, 66(4): 047104.

[8]方錦清, 李永, 畢橋. 統(tǒng)一混合變速增長網(wǎng)絡模型及其特性轉(zhuǎn)變[J].復雜系統(tǒng)與復雜性科學, 2008(4):56-65.

FANG Jinqing, LI Yong, BI Qiao. Unified hybrid variable speed growth model and transition of topology property[J]. Complex Systems and Complex Science, 2008(4):56-65.

[9]史定華.從幾何增長網(wǎng)絡談起[J].復雜系統(tǒng)與復雜性科學, 2010, 7(Z1):82-89.

SHI Dinghua. Starting with geometrically growing networks[J]. Complex Systems and Complex Science, 2010, 7(Z1):82-89.

[10]ERD?S P, RéNYI A. On the evolution of random graphs[J]. Publicaton of the Mathematical Institute of the Hungarian Academy Ofences, 1960, 38(1): 17-61.

[11]WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’networks[J]. Nature, 1998, 393(6684): 440-442.

[14]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.

[15]KRAPIVSKY P L, REDNER S, LEYVRAZ F. Connectivity of growing random networks[J]. Physical Review Letters, 2000, 85(21): 4629-4632.

[16]SHI Dinghua, CHEN Qinghua, LIU Liming. Markov chain-based numerical method for degree distributions of growing networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2005, 71(3): 036140.

[17]陳慶華, 史定華. 增長網(wǎng)絡的形成機理和度分布計算[J]. 應用數(shù)學與計算數(shù)學學報, 2005, 19(1):30-38.

CHEN Qinghua, SHI Dinghua. The mechanisms and degree distributions of growing networks[J]. Communication on Applied Mathematics and Computation, 2005, 19(1):30-38.

[18]曹玉芬, 侯振挺. 一類增長網(wǎng)絡模型的度分布[J].系統(tǒng)科學與數(shù)學, 2010, 30(4):548-555.

CAO Yufen, HOU Zhenting. Degree-distribution of a growing nerwork[J]. Journal of Systems Science and Mathematical Sciences, 2010, 30(4):548-555.

[19]LIU Z, LAI Y C, YE N, et al.Connectivity distribution and attack tolerance of general networks with both preferential and random attachments[J]. Physics Letters A,2002,303(5/6): 337-344.

[20]譚利, 劉新儒. 隨機增長網(wǎng)絡模型的穩(wěn)定性分析[J].河北工業(yè)大學學報,2010,39(5): 17-19.

TAN Li, LIU Xinru.Stability analysis of a random growing network model[J].Journal of Hebei University of Technology,2010, 39(5): 17-19.

Structure analysis of growing network based on partial differential equations

JIA Junbo1, JIN Zhen2

(1.School of Science, North University of China, Taiyuan，Shanxi 030051, China;2.Complex Systems Research Center, Shanxi University, Taiyuan, Shanxi 030006, China)

Abstract:The topological structure is one of the most important contents in the complex network research. Therein the node degree and the degree distribution are the most basic characteristic quantities to describe topological structure. In order to calculate the degree distribution, first of all, the node degree is considered as a continuous variable. Then, according to the Markov Property of growing network, the cumulative distribution function's evolution equation with time can be obtained. Finally, the partial differential equation (PDE) model can be established through distortion processing. Taking the growing network with preferential and random attachment mechanism as an example, the PDE model is obtained. The analytic expression of degree distribution is obtained when this model is solved. Besides, the degree function over time is the same as the characteristic line of PDE. At last, the model is simulated. This PDE method of changing the degree distribution calculation into problem of solving PDE makes the structure analysis more accurate.

Keywords:graph theory； partial differential equation； applied mathematics； probability distribution； structure analysis

中圖分類號：O175MSC(2010)主題分類：35A23

文獻標志碼：A

通訊作者：靳禎教授。E-mail：jinzhn@263.net

作者簡介：賈俊波(1990—)，男，山西昔陽人，碩士研究生，主要從事復雜網(wǎng)絡方面的研究。

基金項目：國家自然科學基金重點項目(11331009)

收稿日期：2015-12-11；修回日期：2016-01-05；責任編輯：張軍

doi:10.7535/hbkd.2016yx02007

文章編號：1008-1542(2016)02-0154-06

賈俊波,靳禎.基于偏微分方程的增長網(wǎng)絡結(jié)構(gòu)分析[J].河北科技大學學報,2016,37(2):154-159.

JIA Junbo， JIN Zhen.Structure analysis of growing network based on partial differential equations[J].Journal of Hebei University of Science and Technology,2016,37(2):154-159.