基于偏微分方程的增长网络结构分析

贾俊波，靳　祯

(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.