大量真实世界中的复杂系统都可以通过抽象的节点和边构成的网络来加以描述，网络中的节点表示系统中的各个个体，而边表示系统中各个个体之间的相互关系. 许多真实复杂系统构建的网络具有规模大且结构复杂的特点，要想直接对其研究较为困难. 一般的处理方法是对它们建立相应的数学模型，通过研究相应数学模型的拓扑性质来重构真实网络的拓扑性质. 经典数学模型是Erds和Rényi两人于20世纪50年代末引入的ER随机图模型. 研究表明，ER随机图的结构均匀且节点度服从二项分布. 从20世纪末开始，计算机技术的快速发展使得人们对真实网络进行实证研究成为可能. 人们研究发现，大量真实网络的节点度并不是服从二项分布，而是服从形式为Pr [deg(v)=k]∝k^-β的幂律分布^[1-3]或服从形式为Pr [deg(v)=k]∝e^-kc的指数分布^[4]，其中，deg(v)=k表示节点v的度为k，β表示幂律指数，其范围一般在(2，3］之间，c是一个常数.

提出了一种适用性更广的带非线性优先连接规则的复杂网络生成模型G(p,m,G₀)，给出并采用概率方法严格证明了该模型的节点度分布表达式，利用节点度分布表达式分别计算了2个节点加权函数f对应网络模型的节点度分布. 实验结果表明，当节点度k的取值不是特别大时，理论结果与仿真实验结果相符；当节点度k的取值特别大时，仿真节点度分布会由于网络实例的节点数有限且较小而出现截断，从而使得理论、仿真实验结果不一致.

1 非线性优先连接规则和增长模型 1.1 非线性优先连接规则

记d_k,t=|{v∈V_t|deg_v(t)=k}|为t时刻度为k的节点数，其中，V_t为t时刻所有节点构成的集合，deg_v(t)为t时刻节点v的度. 记n_t=|V_t|为t时刻网络总的节点数，定义${{Q}_{k}}=\underset{t\to \infty }{\mathop{lim}}\,~\frac{{{d}_{k,t}}}{{{n}_{t}}}$，表示在t时刻从节点数为n_t的网络中随机选择一个节点其度恰好为k的概率. 为了获得动态增长演化网络，定义一个关于节点度的加权函数f，若1≤m≤k≤M≤∞，则f(k)>0，否则，f(k)=0. 所谓非线性优先连接规则是指在网络的演化过程中选择节点i的概率p_i与节点i的度k_i的函数f(k_i)≥0满足如下关系^[3]：

${{p}_{i}}=\frac{f\left( {{k}_{i}} \right)}{\underset{j\ge 1}{\mathop{\sum }}\,f({{k}_{j}})}$

(1)

1.2 带非线性优先连接规则的增长模型

下面给出带非线性优先连接规则复杂网络增长模型的形式化描述，该模型的初始网络是一个具有n₀≥1个节点的全耦合规则网络G₀. 在每一时间步t，执行如下2步操作之一.

1) 顶点步：在t>0时刻，向当前网络中添加一个新节点v，同时在网络G_t-1中按非线性优先连接规则(1)分别选择1≤m≤n₀个旧节点u_i与新加入的节点v连边，其中，i=1,2,…,m.

2) 边步：在t>0时刻，向已有网络G_t-1中添加1≤m≤n₀条新边，新边终点r_i和s_i按非线性优先连接规则(1)选取，其中，i=1,2,…,m.

基于以上的顶点步和边步，这里给出带非线性优先连接规则的复杂网络增长模型G(p,m,G₀)，其模型构造算法如下.

1) 在t=0时，从一个具有n₀≥1个节点的全耦合规则网络G₀开始.

2) 给定概率参数p∈(0,1］，在t>0时，按如下方式修改图G_t-1得到图G_t:

a) 生成一个随机数r∈(0,1)；

b) 若r ＜p，则以概率p走顶点步；

c) 否则，以概率1-p走边步.

2 节点度分布

本节的目标是证明$\frac{{{d}_{k,t}}}{{{n}_{t}}}$在t→∞时的极限存在且极限值恰好为Q_k，由此给出Q_k的表达式. 在此之前，先在引理1中证明当t→∞时，节点数n_t高概率集中于均值E(n_t). 一个事件高概率^[5]发生是指对任意的t>1和R>1，该事件不发生的概率为O(t^-R).

引理1 在模型G(p,m,G₀)中，设E(n_t)为t时刻节点总数n_t的期望，则对任意的R>1和t>1，有

$Pr~(|{{n}_{t}}-E({{n}_{t}})|\ge \sqrt{2Rtln~t})=O({{t}^{-R}})~$

(2)

证明 设n_t为t时刻的节点总数，由模型G(p,m,G₀)的构造算法可知，在每一时间步t，要么以概率p走顶点步，要么以概率1-p走边步，节点数n_t是一个随机变量且满足如下关系：

${{n}_{t}}={{n}_{0}}+\underset{j=1}{\overset{t}{\mathop{\sum }}}\,{{X}_{j}}~$

(3)

其中：Pr (X_j=1)=p，Pr (X_j=0)=1-p. 若对式(3)两边取期望，则有E(n_t)=n₀+pt. 又因为概率0 ＜p≤1，所以有|X_j-E(X_j)|≤1. 由文献^[6]中的定理2.20可知，对任意的t>1和R>1，取λ=$\sqrt{2Rtln~t}$，则有

$Pr~(|{{n}_{t}}-E({{n}_{t}})|\ge \sqrt{2Rtln~t})=O({{t}^{-R}})$

引理1证毕.

下面在定理1中给出模型G(p,m,G₀)的节点度分布表达式，并利用概率方法进行证明.

定理1 在模型G(p,m,G₀)中,令f(k)=f_k为满足条件f_m>0,f_m+1>0，…，f_M>0,f_M+1=0的节点加权函数，其中1≤m≤k≤M≤∞. 记Q_j为在网络中随机选择一个节点其度恰好为j的概率，定义节点加权平均值〈f〉=$\underset{j\ge m}{\mathop{\sum }}\,$f_jQ_j，若节点加权平均值〈f〉≠0，则对任意的1≤m≤k≤M+1，有

$\begin{align} & {{Q}_{m}}=\frac{p\langle f\rangle }{p\langle f\rangle +\left( 2-p \right)m{{f}_{m}}} \\ & {{Q}_{k}}=\frac{p\langle f\rangle }{p\langle f\rangle +\left( 2-p \right)m{{f}_{m}}}\underset{j=m+1}{\overset{k}{\mathop{\prod }}}\,\frac{\left( 2-p \right)m{{f}_{j-1}}}{p\langle f\rangle +\left( 2-p \right)m{{f}_{j}}}~ \\ \end{align}$

(4)

证明 由引理1可知，在t→∞时，有n_t≈E(n_t)≈pt. 由此，对式(1)可作如下处理：

$\begin{align} & {{p}_{i}}=\frac{f\left( {{k}_{i}} \right)}{\underset{j\ge 1}{\mathop{\sum }}\,f({{k}_{j}})}=\frac{~f\left( {{k}_{i}} \right)/{{n}_{t}}}{\underset{l\ge m}{\mathop{\sum }}\,f\left( l \right){{d}_{l,t}}/{{n}_{t}}} \\ & \approx ~\frac{{{f}_{k}}/pt}{\underset{l\ge m}{\mathop{\sum }}\,{{f}_{l}}{{Q}_{l}}}=\text{ }\frac{{{f}_{k}}}{pt\langle f\rangle } \\ \end{align}$

(5)

注意到，在t时刻度为k的节点数d_k,t有2种情况：一是在t-1时刻该节点的度为k，若向该节点关联一条边，则度为k的节点数d_k,t减少1，若不向该节点关联边，则度为k的节点数d_k,t保持不变；二是在t-1时刻该节点的度为k-1，若向该节点关联一条边，则度为k的节点数d_k,t增加1.

假设F_t为对应于t时刻的概率空间的σ-代数，对t>0和k=m，结合式(5)，有

$\begin{align} & {{d}_{m,t-1}}\left( 1-\frac{pmf\left( m \right)}{\underset{j\ge 1}{\mathop{\sum }}\,f({{k}_{j}})}-\frac{2\left( 1-p \right)mf\left( m \right)}{\underset{j\ge 1}{\mathop{\sum }}\,f({{k}_{j}})} \right)+p= \\ & {{d}_{m,t-1}}\left( 1-\frac{\left( 2-p \right)m{{f}_{m}}}{pt\langle f\rangle } \right)+p \\ \end{align}$

(6)

由条件期望的性质可知，若对式(6)两边取期望，则有如下的递推关系：

$E({{d}_{m,t}})=E({{d}_{m,t-1}})\left( 1-\frac{\left( 2-p \right)m{{f}_{m}}}{pt\langle f\rangle } \right)+p$

(7)

同理，对t>0和k>m，结合式(5)，有

$\begin{align} & E\left( {{d}_{k,t}}|{{F}_{t-1}} \right)={{d}_{k,t-1}}\left( 1-\frac{pm{{f}_{k}}}{pt\langle f\rangle }-\frac{2\left( 1-p \right)m{{f}_{k}}}{pt\langle f\rangle } \right)+ \\ & {{d}_{k-1,t-1}}\left( \frac{pm{{f}_{k-1}}}{pt\langle f\rangle }+\frac{2\left( 1-p \right)m{{f}_{k-1}}}{pt\langle f\rangle } \right)= \\ & {{d}_{k,t-1}}\left( 1-\frac{\left( 2-p \right)m{{f}_{k}}}{pt\langle f\rangle } \right)+{{d}_{k-1,t-1}}\frac{\left( 2-p \right)m{{f}_{k-1}}}{pt\langle f\rangle } \\ \end{align}$

(8)

若对式(8)两边取期望，则有如下的递推关系:

$\begin{align} & E\left( {{d}_{k,t}} \right)=E\left( {{d}_{k,t-1}} \right)\left( 1-\frac{\left( 2-p \right)m{{f}_{k}}}{pt\langle f\rangle } \right)+ \\ & E({{d}_{k-1,t-1}})\frac{\left( 2-p \right)m{{f}_{k-1}}}{pt\langle f\rangle } \\ \end{align}$

(9)

接下来，利用文献^[6]中的引理3.1对式(7)和式(9)中的k≥m进行归纳证明，设$\underset{t\to \infty }{\mathop{lim}}\,\frac{E({{d}_{k,t}})}{t}={{M}_{k}}$.

当k=m时，由式(7)可知

$\underset{t\to \infty }{\mathop{lim}}\,{{b}_{t}}=\underset{t\to \infty }{\mathop{lim}}\,\frac{\left( 2-p \right)m{{f}_{m}}}{p\langle f\rangle }=b~\underset{t\to \infty }{\mathop{lim}}\,{{c}_{t}}=p=c$

(10)

结合式(10)和文献^[6]中的引理3.1可知，$\underset{t\to \infty }{\mathop{lim}}\,\frac{E({{d}_{k,t}})}{t}$存在，且有

${{M}_{m}}=\underset{t\to \infty }{\mathop{lim}}\,\frac{E({{d}_{m,t}})}{t}=\frac{{{p}^{2}}\langle f\rangle }{p\langle f\rangle +\left( 2-p \right)m{{f}_{m}}}$

(11)

假定对任意的k-1≥m，$\underset{t\to \infty }{\mathop{lim}}\,\frac{E({{d}_{k-1,t}})}{t}$=M_k-1成立. 证明对任意k≥m+2，$\frac{E({{d}_{k,t}})}{t}$=M_k也成立. 由式(9)可知

$\underset{t\to \infty }{\mathop{lim}}\,{{b}_{t}}=\underset{t\to \infty }{\mathop{lim}}\,\frac{\left( 2-p \right)m{{f}_{k}}}{p\langle f\rangle }=b$

(12)

$\begin{align} & \underset{t\to \infty }{\mathop{lim}}\,{{c}_{t}}=\underset{t\to \infty }{\mathop{lim}}\,\frac{\left( 2-p \right)m{{f}_{k-1}}E\left( {{d}_{k-1,t-1}} \right)}{pt\langle f\rangle }= \\ & \frac{\left( 2-p \right)m{{f}_{k-1}}}{p\langle f\rangle }{{M}_{k-1}}=c \\ \end{align}$

(13)

由式(12)、式(13)和文献^[6]中的引理3.1可知，$\underset{t\to \infty }{\mathop{lim}}\,\frac{E({{d}_{k,t}})}{t}$存在，即

${{M}_{k}}=\underset{t\to \infty }{\mathop{lim}}\,\frac{E({{d}_{k,t}})}{t}=\frac{\left( 2-p \right)m{{f}_{k-1}}}{p\langle f\rangle +\left( 2-p \right)m{{f}_{k}}}{{M}_{k-1}}$

(14)

结合式(11)和式(14)，可得

$\begin{align} & {{M}_{k}}=\underset{t\to \infty }{\mathop{lim}}\,\frac{E({{d}_{k,t}})}{t}= \\ & \frac{{{p}^{2}}\langle f\rangle }{p\langle f\rangle +\left( 2-p \right)m{{f}_{m}}}\underset{j=m+1}{\overset{k}{\mathop{\prod }}}\,\frac{\left( 2-p \right)m{{f}_{j-1}}}{p\langle f\rangle +\left( 2-p \right)m{{f}_{j}}~} \\ \end{align}$

(15)

设F_r是时刻r对应概率空间的σ-代数，F_s是时刻s对应概率空间σ-代数，其中r≤s≤t. 设d_k,t为t时刻度为k的节点数，因为E(E(d_k,t|F_s)|F_r)=E(d_k,t|F_s)，所以Z_s=E(d_k,t|F_s)是一个鞅且有Z_t=d_k,t,Z₀=E(d_k,t). 在每一时刻t>0，极端情况是以概率1-p选择连边的2个节点其节点度都为k，则有|Z_s-Z_s-1|≤2m. 利用文献^[6]中的定理2.19，对任意的t>1和R>1，取$\lambda =2m\sqrt{\frac{2Rln~t}{t}}$，有

$Pr\left( ~\left| \frac{{{d}_{k,t}}}{t}-\frac{E({{d}_{k,t}})}{t} \right|\ge \lambda \right)\le 2{{e}^{-\frac{{{\lambda }^{2}}t}{8{{m}^{2}}}}}=O({{t}^{-R}})~$

(16)

因此，对t>0和k≥m，结合引理1、式(11)、式(15)和式(16)，有

${{Q}_{m}}=\underset{t\to \infty }{\mathop{lim}}\,\frac{{{d}_{m,t}}}{{{n}_{t}}}\simeq \underset{t\to \infty }{\mathop{lim}}\,\frac{E({{d}_{m,t}})/t}{E({{n}_{t}})/t}=\frac{p\langle f\rangle }{p\langle f\rangle +\left( 2-p \right)m{{f}_{m}}}$

(17)

${{Q}_{k}}=\frac{p\langle f\rangle }{p\langle f\rangle +\left( 2-p \right)m{{f}_{m}}}\underset{j=m+1}{\overset{k}{\mathop{\prod }}}\,\frac{\left( 2-p \right)m{{f}_{j-1}}}{p\langle f\rangle +\left( 2-p \right)m{{f}_{j}}}~$

(18)

定理1证毕.

对定理1中给出的节点度分布{Q_k:k≥m}，采用文献^[3]中给出的方法容易验证其正则化条件. 由定理1可知，若M→∞，定义

${{Q}_{\infty }}=\underset{M\to \infty }{\mathop{lim}}\,\underset{j=m}{\overset{M}{\mathop{\prod }}}\,\frac{\left( 2-p \right)m{{f}_{j}}}{p\langle f\rangle +\left( 2-p \right)m{{f}_{j}}}>0$

则有$\underset{k\ge m}{\mathop{\sum }}\,{{Q}_{k}}=1$;

若M<∞,f_M+1=0，则有

$\begin{align} & \underset{k=m}{\overset{M+1}{\mathop{\sum }}}\,{{Q}_{k}}=\underset{k=m}{\overset{M+1}{\mathop{\sum }}}\,\frac{p\langle f\rangle }{p\langle f\rangle +\left( 2-p \right)m{{f}_{m}}}\times \\ & \underset{j=m+1}{\overset{k}{\mathop{\prod }}}\,\frac{\left( 2-p \right)m{{f}_{j-1}}}{p\langle f\rangle +\left( 2-p \right)m{{f}_{j}}}=1 \\ \end{align}$

在定理1中，节点度分布表达式中的概率p为已知，只要满足条件f_m>0,f_m+1>0，…,f_M>0,f_M+1=0的节点加权函数f给定，其网络的节点权重值也就给定，此时在节点度分布表达式中只有节点加权函数f的加权平均值〈f〉未知. 接下来，在下面的定理2中给出计算定理1中节点加权平均值〈f〉的表达式.

定理2 在模型G(p,m,G₀)中,令f(k)=f_k为满足条件f_m>0,f_m+1>0，…，f_M>0,f_M+1=0的节点加权函数，其中1≤m≤k≤M≤∞. 记Q_j为在网络中随机选择一个节点其度恰好为j的概率，定义节点加权平均〈f〉=$\underset{j\ge m}{\mathop{\sum }}\,$f_jQ_j,若节点加权平均值〈f〉≠0，则对任意的1≤m≤k≤M+1，有

$\underset{k=m}{\overset{M}{\mathop{\sum }}}\,\underset{j=m}{\overset{k}{\mathop{\prod }}}\,{{\left( 1+\frac{p\langle f\rangle }{\left( 2-p \right)m{{f}_{j}}} \right)}^{-1}}=\frac{\left( 2-p \right)m}{p}$

(19)

证明 在模型G(p,m,G₀)中，已知f(k)=f_k为满足f_m>0,f_m+1>0，…,f_M>0,f_M+1=0的节点加权函数，其中M≤∞. 由定义〈f〉=$\underset{j\ge m}{\mathop{\sum }}\,$f_jQ_j和定理1可知

$\begin{align} & \underset{k=m}{\overset{M+1}{\mathop{\sum }}}\,{{f}_{k}}{{Q}_{k}}= \\ & \underset{k=m}{\overset{M}{\mathop{\sum }}}\,{{f}_{k}}\frac{p\langle f\rangle }{p\langle f\rangle +\left( 2-p \right)m{{f}_{m}}}\underset{j=m+1}{\overset{k}{\mathop{\prod }}}\,\frac{\left( 2-p \right)m{{f}_{j-1}}}{p\langle f\rangle +\left( 2-p \right)m{{f}_{j}}}+ \\ & {{f}_{M+1}}\underset{j=m}{\overset{M}{\mathop{\prod }}}\,\frac{\left( 2-p \right)m{{f}_{j}}}{p\langle f\rangle +\left( 2-p \right)m{{f}_{j}}}= \\ & \frac{p\langle f\rangle }{\left( 2-p \right)m}\underset{k=m}{\overset{M}{\mathop{\sum }}}\,\underset{j=m}{\overset{k}{\mathop{\prod }}}\,\frac{\left( 2-p \right)m{{f}_{j}}}{p\langle f\rangle +\left( 2-p \right)m{{f}_{j}}}=\langle f\rangle \\ \end{align}$

(20)

化简式(20)，可得

$\underset{k=m}{\overset{M}{\mathop{\sum }}}\,\underset{j=m}{\overset{k}{\mathop{\prod }}}\,{{\left( 1+\frac{p\langle f\rangle }{\left( 2-p \right)m{{f}_{j}}} \right)}^{-1}}=\frac{\left( 2-p \right)m}{p}$

定理2证毕.

下面在定理3和定理4中分别考虑2个不同的节点加权函数f(k)=k和f(k)=k+a对应的网络模型，借助于定理1给出其对应模型的节点度分布.

定理3 在模型G(p,m,G₀)中，若节点加权函数f(k)=k,则对任意的k≥m≥1，有：

1) 节点加权函数f的加权平均值为$\langle f\rangle =\frac{2m}{p}$；

2) 相应网络模型的节点度服从幂律指数为 β=2+$\frac{p}{2-p}$∈(2,3］的幂律分布，即

${{Q}_{m}}=\frac{2}{\left( 2-p \right)m+2}\text{ }{{Q}_{k}}\approx \frac{2\Gamma \left( \frac{2}{2-p}+m \right)}{\left( 2-p \right)\Gamma (m)}{{k}^{-\left( 2+\frac{p}{2-p} \right)}}$

(21)

证明 若节点加权函数f(k)=f_k=k，由定理2有

$\begin{align} & \underset{k=m}{\overset{\infty }{\mathop{\sum }}}\,\underset{j=m}{\overset{k}{\mathop{\prod }}}\,{{\left( 1+\frac{p\langle f\rangle }{\left( 2-p \right)m{{f}_{j}}} \right)}^{-1}}=\underset{k=m}{\overset{\infty }{\mathop{\sum }}}\,\underset{j=m}{\overset{k}{\mathop{\prod }}}\,\frac{j}{\frac{p\langle f\rangle }{\left( 2-p \right)m}+j}= \\ & \frac{\left( 2-p \right){{m}^{2}}}{\left( p-2 \right)m+p\langle f\rangle }=\frac{\left( 2-p \right)m}{p} \\ \end{align}$

(22)

解式(22)，可得节点加权函数f_k=k的加权平均值为

$\langle f\rangle =\langle k\rangle =\frac{2m}{p}$

(23)

由式(23)可知，当概率p=1时，有〈f〉=〈k〉=2m.

对t>0和k=m，由定理1、式(23)和f_m=m，有

${{Q}_{m}}=\frac{p\langle f\rangle }{p\langle f\rangle +\left( 2-p \right)m{{f}_{m}}}=\frac{2}{\left( 2-p \right)m+2}$

(24)

同理，对t>0和k>m，由定理1、式(23)和f_k=k，有

$\begin{align} & {{Q}_{k}}=\frac{p\langle f\rangle }{\left( 2-p \right)mk}\underset{j=m}{\overset{k}{\mathop{\prod }}}\,\frac{\left( 2-p \right)mj}{p\langle f\rangle +\left( 2-p \right)mj}= \\ & \frac{2}{2-p}\frac{\Gamma (k)\Gamma \left( \frac{2}{2-p}+m \right)}{\Gamma (m)\Gamma \left( k+\frac{2}{2-p}+1 \right)} \\ \end{align}$

(25)

利用文献^[7]中的引理1对式(25)作近似处理，有

${{Q}_{k}}\approx \frac{2\Gamma \left( \frac{2}{2-p}+m \right)}{\left( 2-p \right)\Gamma (m)}{{k}^{-\left( 1+\frac{2}{2-p} \right)}}$

(26)

由式(26)可知，节点加权函数f_k=k对应的网络模型的节点度服从幂律分布，其幂律指数为

$\beta =1+\frac{2}{2-p}=2+\frac{p}{2-p}$

(27)

定理3证毕.

因为概率0 ＜p≤1，所以式(27)中的幂律指数β的范围为2<β≤3. 由此可知，文献^[6]中式(3.4)给出的节点度分布表达式为定理1的特例. 当p=1时，有β=3，此时，节点加权函数f(k)=k对应的网络模型退化为Barabasi和Albert提出的经典无标度网络模型，即BA模型，文献^[1]中的节点度分布为定理1的特例.

定理4 在模型G(p,m,G₀)中，若节点加权函数f(k)=k+a，则对任意的k≥m≥1,a≥0，有：

1) 节点加权函数f(k)=k+a的加权平均值为$\langle f\rangle =\frac{2m}{p}+a$；

2) 当p(m+a)≤(2-p)m时,相应网络模型的节点度服从幂律指数β=$2+\frac{p\left( m+a \right)}{\left( 2-p \right)m}$∈(2,3］的幂律分布，即

$\begin{align} & {{Q}_{m}}=\frac{2m+pa}{\left( 2-p \right)m\left( m+a \right)+2m+pa} \\ & {{Q}_{k}}\approx \frac{2m+pa}{\left( 2-p \right)m}\frac{\Gamma \left( m+a+\frac{2m+pa}{\left( 2-p \right)m} \right)}{\Gamma \left( m+a \right)}{{k}^{-\left( 1+\frac{2m+pa}{\left( 2-p \right)m} \right)}} \\ \end{align}$

(28)

当参数a→∞时，其节点度服从指数分布，即

$\begin{align} & {{Q}_{m}}=\frac{p}{\left( 2-p \right)m+p} \\ & {{Q}_{k}}=\frac{p}{\left( 2-p \right)m+p}{{\left( \frac{\left( 2-p \right)m}{\left( 2-p \right)m+p} \right)}^{k-m}} \\ \end{align}$

(29)

证明 若节点加权函数f(k)=f_k=k+a，其中a≥0是一个常数，则由定理2，有

$\begin{align} & \underset{k=m}{\overset{\infty }{\mathop{\sum }}}\,\underset{j=m}{\overset{k}{\mathop{\prod }}}\,{{\left( 1+\frac{p\langle f\rangle }{\left( 2-p \right)m{{f}_{j}}} \right)}^{-1}}= \\ & \underset{k=m}{\overset{\infty }{\mathop{\sum }}}\,\underset{j=m}{\overset{k}{\mathop{\prod }}}\,\frac{j+a}{\frac{p\langle f\rangle }{\left( 2-p \right)m}+j+a}= \\ & \frac{\left( 2-p \right)m\left( m+a \right)}{p\langle f\rangle +m\left( p-2 \right)}=\frac{\left( 2-p \right)m}{p} \\ \end{align}$

(30)

解式(30)，可得节点加权函数f(k)=k+a的加权平均值为

$\langle f\rangle =\frac{2m}{p}+a$

(31)

对t>0和k=m，结合式(31)、f_m=m+a和定理1，有

${{Q}_{m}}=\frac{p\langle f\rangle }{p\langle f\rangle +\left( 2-p \right)m{{f}_{m}}}=\frac{2m+pa}{\left( 2-p \right)m\left( m+a \right)+2m+pa}$

(32)

同理，对t>0和k>m，结合式(31)、f(k)=k+a和定理1，有

$\begin{align} & {{Q}_{k}}=\frac{p\langle f\rangle }{\left( 2-p \right)m\left( k+a \right)}\underset{j=m}{\overset{k}{\mathop{\prod }}}\,\frac{\left( 2-p \right)m\left( j+a \right)}{p\langle f\rangle +\left( 2-p \right)m\left( j+a \right)}= \\ & \frac{2m+pa}{\left( 2-p \right)m}\frac{\Gamma \left( k+a \right)\Gamma \left( m+a+\frac{2m+pa}{\left( 2-p \right)m} \right)}{~\Gamma \left( k+a+1+\frac{2m+pa}{\left( 2-p \right)m} \right)\Gamma \left( m+a \right)} \\ \end{align}$

(33)

式(33)在统计学上被称为Yule-Simon分布^[8]，它是一种离散概率分布. 当p(m+a)≤(2-p)m时，利用文献^[7]中的引理1对式(33)作近似处理，可得

${{Q}_{k}}\approx \frac{2m+pa}{\left( 2-p \right)m}\frac{\Gamma \left( m+a+\frac{2m+pa}{\left( 2-p \right)m} \right)}{\Gamma \left( m+a \right)}{{k}^{-\left( 1+\frac{2m+pa}{\left( 2-p \right)m} \right)}}$

(34)

由式(34)可知，节点加权函数f(k)=k+a对应网络模型的节点度服从幂律分布，其幂律指数为

$\beta =2+\frac{p\left( m+a \right)}{\left( 2-p \right)m}$

(35)

因为概率0 ＜p≤1，p(m+a)≤(2-p)m，所以式(35)中的幂律指数β的范围为2<β≤3. 当概率p=1和边数m=1时，有β=3+a. 由此可知，文献^[2]中式(12)给出的节点度分布表达式为定理1的特例.

对于节点加权函数f(k)=k+a，也考虑了a→∞时的情况，当a→∞时，由式(32)可知

${{Q}_{m}}=\frac{p}{\left( 2-p \right)m+p}$

(36)

结合式(33)和定理1，当a→∞时，有

$\begin{align} & {{Q}_{k}}=\frac{p\langle f\rangle }{\left( 2-p \right)m\left( k+a \right)}\underset{j=m}{\overset{k}{\mathop{\prod }}}\,\frac{\left( 2-p \right)m\left( j+a \right)}{p\langle f\rangle +\left( 2-p \right)m\left( j+a \right)}= \\ & \frac{2m+pa}{\left( 2-p \right)m\left( k+a \right)}\underset{j=m}{\overset{k}{\mathop{\prod }}}\,\frac{\left( 2-p \right)m\left( j+a \right)}{2m+pa+\left( 2-p \right)m\left( j+a \right)}= \\ & \frac{p}{\left( 2-p \right)m+p}{{\left( \frac{\left( 2-p \right)m}{\left( 2-p \right)m+p} \right)}^{k-m}} \\ \end{align}$

(37)

定理4证毕. 由式(36)和式(37)可知,当节点加权函数f(k)=k+a中的a→∞时，对应网络模型的节点度服从指数分布.

3 数值仿真实验

这一节，对2个不同节点加权函数f(k)对应的不同网络模型进行了数值仿真实验. 仿真实验表明，初始图G₀的节点数n₀远小于t时刻的节点数n_t时，初始条件对最终的结果几乎没有影响. 所以在针对2个不同节点加权函数f(k)=k和f(k)=k+a对应网络模型的数值仿真实验中均考虑初始图G₀的节点数为n₀=10，时间t=100 000.

图 1给出了节点加权函数f(k)=k对应的网络模型在双对数坐标下的理论、仿真节点度分布对比. 图 1中的星形、圆形、菱形和四方形符号分别是f(k)=k，边数m=4，概率p=0.3，0.7,0.9,1.0时的仿真节点度分布，相应的实线是利用式(21)给出的理论节点度分布表达式计算得到的值. 从图 1可以看出，当固定边数m、变化概率p时，f(k)=k对应网络模型的节点度分布近似服从幂律分布，其幂律指数β随p的增大而增大.

图 2给出了节点加权函数f(k)=k对应的网络模型在双对数坐标下的理论、仿真节点度分布的对比图. 图 2中星形、圆形以及四方形符号分别是f(k)=k，概率p=0.5，边数m=1，4,8时的仿真节点度分布，相应的点划线、点线和虚线是利用式(21)给出的理论节点度分布表达式计算得到的值. 从图 2可以看出，当固定概率p、变化边数m时，f(k)=k对应网络模型的节点度分布仍然近似服从幂律分布且幂律指数β不变.

从图 1、图 2可知，节点加权函数f(k)=k对应网络模型的节点度分布近似服从幂律分布，其幂律指数β仅与概率p有关，而与边数m无关，且幂律指数β的变化范围在(2,3］之间.

图 3给出了节点加权函数f(k)=k+a对应的网络模型在不同参数下的仿真、理论节点度分布，其中的星形、圆形符号分别表示其网络模型在不同参数下的仿真节点度分布，相应的虚线和点线是利用式(28)、式(33)和式(29)给出的理论节点度分布表达式计算得到的值. 从实验中发现，固定概率p和边数m，当0≤a<1时，对应模型的仿真节点度近似服从幂律分布；当1$ \ll $a<80时，对应模型的仿真节点度服从Yule-Simon分布；当80≤a<∞时，对应网络模型的仿真节点度服从指数分布. 故在图 3的仿真实验中，仅考虑概率p=0.5、边数m=4，8以及参数a=0.5，60，1 000时的情形，其他情形类似. 当a=0.5时，有p(m+a)≤(2-p)m，此时f(k)=k+a对应网络模型的仿真节点度分布近似服从幂律分布，分布的图形在双对数坐标下近似为一条直线，且幂律指数β与概率p、边数m和a有关，如图 3(a)所示. 当a=60时，有p(m+a)>(2-p)m，此时f(k)=k+a对应网络模型的仿真节点度分布会远离幂律，进而服从Yule-Simon分布，分布的图形在双对数坐标下呈现出明显的向下弯曲趋势，且节点度分布与概率p、边数m和参数a有关，如图 3(b)所示. 当参数a=1 000时，看到p(m+a)$ \gg $(2-p)m，此时f(k)=k+a对应网络模型的仿真节点度既不服从幂律分布也不服从Yule-Simon分布，而是服从指数分布，分布的图形在对数-线性坐标下近似为一条直线，且节点度分布与参数a的取值无关，只与概率p和边数m有关，如图 3(c)所示. 实验结果表明，概率p和边数m的取值对该模型的节点度分布的形式影响较小，而参数a的取值对该模型的节点度分布的形式影响较大，当其他参数固定时，随着参数a的取值增大，对应网络模型的节点度分布从幂律分布到指数分布演变.

从图 1、图 2和图 3可以看出，当节点度k的取值不是很大时，节点加权函数f(k)=k和f(k)=k+a对应网络模型的仿真节点度分布与理论节点度分布拟合得很好. 然而，当节点度k的取值较大时，2个节点加权函数f对应网络模型的理论节点度分布和仿真节点度分布并不一致，原因在于由该模型生成的网络实例其节点数较小且为有限值，从而使得度的最大值也为有限值，故相应模型的节点度分布在度k较大时会出现截断.

4 结束语

提出了一种更具普适性的带非线性优先连接规则的复杂网络演化模型G(p,m,G₀)，在定理1中给出了该模型的节点度分布表达式，同时在定理2中给出了节点加权平均值〈f〉的计算表达式，利用定理1分别计算了2个不同节点加权函数f对应网络模型的节点度分布. 研究发现，节点加权函数f(k)=k对应网络模型的节点度分布服从幂律指数β在(2,3］之间的幂律分布. 节点加权函数f(k)=k+a对应网络模型的节点度分布会随参数a的取值的增大从幂律分布到指数分布演化，即当p(m+a)≤(2-p)m，概率0 ＜p≤1时，对应网络模型的节点度分布近似服从幂律指数β在(2,3］之间的幂律分布，其节点度分布与概率p、参数a和边数m有关；当p(m+a)>(2-p)m时，对应网络模型的节点度分布服从Yule-Simon分布；当a→∞时，该网络模型的节点度分布会远离幂律，进而服从指数分布，其节点度分布仅与概率p和边数m有关，而与参数a无关. 此外，针对2个节点加权函数f对应网络模型的仿真实验结果表明，当节点度k的取值不是很大时，其理论结果与仿真实验结果相符；当节点度k的取值特别大时，仿真节点度分布会由于模型生成的网络实例其节点数有限且较小而出现截断，从而使得理论、仿真结果不一致.