基于偏微分方程的增長網絡結構分析

賈俊波，靳　禎

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

?

基于偏微分方程的增長網絡結構分析

賈俊波1，靳禎2

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

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

關鍵詞：圖論；偏微分方程；應用數學；概率分布；結構分析

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

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

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

1網絡的演化機制

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

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

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

(1)

表1　主要符號表

2增長網絡偏微分方程模型的建立

2.1增長網絡的度分布

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

(2)

(3)

其中Δt為在所考慮的時間段內新增的節點數。

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

(4)

(5)

(6)

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

(7)

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

(8)

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

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

(9)

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

(10)

從而得到增長網絡模型的度分布為

(11)

因此，對于不同優先連接概率p可得到如下結論：

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

2.2節點度kt0(t)

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

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

(12)

的初始條件為

kt0(t0)=m。

(13)

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

(14)

3模擬

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

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

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

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

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

4結論

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

參考文獻/References:

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

[2]趙洋, 單娟, 宋超. 復雜網絡中的病毒傳播機制研究[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]許云峰, 趙寧, 郝雪君,等. 基于三元閉包和會員閉包的社區發現算法研究[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]杜云, 田強, 杜艷,等. 簡單動態遞歸神經網絡在非線性系統辨識中的應用[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]方錦清, 李永, 畢橋. 統一混合變速增長網絡模型及其特性轉變[J].復雜系統與復雜性科學, 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]史定華.從幾何增長網絡談起[J].復雜系統與復雜性科學, 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]陳慶華, 史定華. 增長網絡的形成機理和度分布計算[J]. 應用數學與計算數學學報, 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]曹玉芬, 侯振挺. 一類增長網絡模型的度分布[J].系統科學與數學, 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].河北工業大學學報,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—)，男，山西昔陽人，碩士研究生，主要從事復雜網絡方面的研究。

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

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

doi:10.7535/hbkd.2016yx02007

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

賈俊波,靳禎.基于偏微分方程的增長網絡結構分析[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.