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

賈俊波，靳　禎

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

?

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

賈俊波1，靳禎2

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

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

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

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

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

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

1網(wǎng)絡(luò)的演化機(jī)制

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

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

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

(1)

表1　主要符號(hào)表

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

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

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

(2)

(3)

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

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

(4)

(5)

(6)

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

(7)

解的可行域?yàn)镈={(k,t)|k≥m,t>0}。當(dāng)時(shí)間足夠大時(shí)，可以忽略初始網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)m0和邊數(shù)l0，此時(shí)令m0=0，l0=0，得到

(8)

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

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

(9)

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

(10)

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

(11)

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

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

2.2節(jié)點(diǎn)度kt0(t)

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

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

(12)

的初始條件為

kt0(t0)=m。

(13)

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

(14)

3模擬

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

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

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

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

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

4結(jié)論

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

參考文獻(xiàn)/References:

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

[2]趙洋, 單娟, 宋超. 復(fù)雜網(wǎng)絡(luò)中的病毒傳播機(jī)制研究[J].河北科技大學(xué)學(xué)報(bào)，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]許云峰, 趙寧, 郝雪君,等. 基于三元閉包和會(huì)員閉包的社區(qū)發(fā)現(xiàn)算法研究[J].河北科技大學(xué)學(xué)報(bào)，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]杜云, 田強(qiáng), 杜艷,等. 簡(jiǎn)單動(dòng)態(tài)遞歸神經(jīng)網(wǎng)絡(luò)在非線性系統(tǒng)辨識(shí)中的應(yīng)用[J].河北科技大學(xué)學(xué)報(bào),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)一混合變速增長(zhǎng)網(wǎng)絡(luò)模型及其特性轉(zhuǎn)變[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 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]史定華.從幾何增長(zhǎng)網(wǎng)絡(luò)談起[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 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]陳慶華, 史定華. 增長(zhǎng)網(wǎng)絡(luò)的形成機(jī)理和度分布計(jì)算[J]. 應(yīng)用數(shù)學(xué)與計(jì)算數(shù)學(xué)學(xué)報(bào), 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]曹玉芬, 侯振挺. 一類增長(zhǎng)網(wǎng)絡(luò)模型的度分布[J].系統(tǒng)科學(xué)與數(shù)學(xué), 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]譚利, 劉新儒. 隨機(jī)增長(zhǎng)網(wǎng)絡(luò)模型的穩(wěn)定性分析[J].河北工業(yè)大學(xué)學(xué)報(bào),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

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

文獻(xiàn)標(biāo)志碼：A

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

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(11331009)

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

doi:10.7535/hbkd.2016yx02007

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

賈俊波,靳禎.基于偏微分方程的增長(zhǎng)網(wǎng)絡(luò)結(jié)構(gòu)分析[J].河北科技大學(xué)學(xué)報(bào),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.