Scale Free网络的偏好依附模型

Next: 结束语 Up: 解析与数值计算方法 Previous: 随机网络的几何性质

Scale Free网络的偏好依附模型

对偏好依附模型的一般处理方法包含连续性方法[18,21]，速率方程[20,23]，Master方程[19]与生成函数方法[9]，这也是统计物理学经常使用的方法。这一节，我们围绕偏好依附模型的幂率分布形式介绍连续性方法，速率方程与Master方程在复杂网络研究中的应用。

考虑Scale Free网络的偏好依附模型，从顶点的度值变化的角度，假设其度值连续，我们有如下方程，

$\displaystyle {\frac{{\partial k_{i}}}{{\partial t}}}$ = m $\displaystyle \Pi$ $\displaystyle \left(\vphantom{k_{i}}\right.$ k_i $\displaystyle \left.\vphantom{k_{i}}\right)$ = m $\displaystyle {\frac{{k_{i}}}{{\sum k_{j}}}}$

(28)

每一步我们加入m条边，即增加2m个度值，于是 $\sum$ k_j = 2mt + m₀，则

$\displaystyle {\frac{{\partial k_{i}}}{{\partial t}}}$ = $\displaystyle {\frac{{k_{i}}}{{2t}}}$

(29)

顶点k_i是在t_i时刻进入系统的，且满足初始条件 k_i $\left(\vphantom{t_{i}}\right.$ t_i $\left.\vphantom{t_{i}}\right)$ = m，于是

k_i $\displaystyle \left(\vphantom{t}\right.$ t $\displaystyle \left.\vphantom{t}\right)$ = m $\displaystyle \left(\vphantom{\frac{t}{t_{i}}}\right.$ $\displaystyle {\frac{{t}}{{t_{i}}}}$ $\displaystyle \left.\vphantom{\frac{t}{t_{i}}}\right)^{{\frac{1}{2}}}_{}$

(30)

利用上式，结合t_i的分布，就可以知道任意t时刻k_i的分布，即

P $\displaystyle \left(\vphantom{k_{i}\left(t\right)<k}\right.$ k_i $\displaystyle \left(\vphantom{t}\right.$ t $\displaystyle \left.\vphantom{t}\right)$ < k $\displaystyle \left.\vphantom{k_{i}\left(t\right)<k}\right)$ = P $\displaystyle \left(\vphantom{t_{i}>\frac{m^{2}t}{k^{2}}}\right.$ t_i > $\displaystyle {\frac{{m^{2}t}}{{k^{2}}}}$ $\displaystyle \left.\vphantom{t_{i}>\frac{m^{2}t}{k^{2}}}\right)$ .

(31)

在t时刻， t_i $\in$ $\left[\vphantom{0,t}\right.$ 0, t $\left.\vphantom{0,t}\right)$ 的分布函数为

P(t_i) = $\displaystyle {\frac{{1}}{{m_{0}+t}}}$ .

(32)

结合以上两式就可以得到k_i的分布，

P(k) = $\displaystyle {\frac{{\partial P\left(k_{i}\left(t\right)<k\right)}}{{\partial k}}}$ = $\displaystyle {\frac{{2m^2t}}{{m_{0}+t}}}$ $\displaystyle {\frac{{1}}{{k^3}}}$ $\displaystyle \sim$ 2m²k^-3(t $\displaystyle \rightarrow$ $\displaystyle \infty$ ).

(33)

方程(28)是一种平均意义上的描述，实际随机过程中所加入的边只是按照 $\Pi$ $\left(\vphantom{k_{i}}\right.$ k_i $\left.\vphantom{k_{i}}\right)$ 的分布来选择，并不能保证确实让每一个顶点的度值增加那么大，也正是因此称为连续性方法，所以对实际随机过程分布函数演化的描述需要用到其他方法。引入分布函数 p $\left(\vphantom{k;t_{i},t}\right.$ k;t_i, t $\left.\vphantom{k;t_{i},t}\right)$ ，表示t_i时刻引入系统的顶点在t时刻度值为k的几率，其初始条件为 p $\left(\vphantom{k;t_{i},t_{i}}\right.$ k;t_i, t_i $\left.\vphantom{k;t_{i},t_{i}}\right)$ = $\delta$ $\left(\vphantom{k-m}\right.$ k - m $\left.\vphantom{k-m}\right)$ ，，满足如下Master方程，

p $\displaystyle \left(\vphantom{k;t_{i},t+1}\right.$ k;t_i, t + 1 $\displaystyle \left.\vphantom{k;t_{i},t+1}\right)$ = p $\displaystyle \left(\vphantom{k;t_{i},t}\right.$ k;t_i, t $\displaystyle \left.\vphantom{k;t_{i},t}\right)$ + w^get $\displaystyle \left(\vphantom{k-1}\right.$ k - 1 $\displaystyle \left.\vphantom{k-1}\right)$ p $\displaystyle \left(\vphantom{k-1;t_{i},t}\right.$ k - 1;t_i, t $\displaystyle \left.\vphantom{k-1;t_{i},t}\right)$ - w^get $\displaystyle \left(\vphantom{k-1}\right.$ k - 1 $\displaystyle \left.\vphantom{k-1}\right)$ p $\displaystyle \left(\vphantom{k;t_{i},t}\right.$ k;t_i, t $\displaystyle \left.\vphantom{k;t_{i},t}\right)$

(34)

其中 w^get $\left(\vphantom{k}\right.$ k $\left.\vphantom{k}\right)$ = ${\frac{{k}}{{2t}}}$ 。所有顶点的度值分布定义所有不同时刻加入系统的顶点的平均行为，即

P $\displaystyle \left(\vphantom{k}\right.$ k $\displaystyle \left.\vphantom{k}\right)$ = $\displaystyle \lim_{{t\rightarrow\infty}}^{}$ $\displaystyle {\frac{{\sum_{t_{i}}p\left(k;t_{i},t\right)}}{{t}}}$ .

(35)

有以上两式可以求得度分布

P $\displaystyle \left(\vphantom{k}\right.$ k $\displaystyle \left.\vphantom{k}\right)$ = $\displaystyle {\frac{{2m\left(m+1\right)}}{{k\left(k+1\right)\left(k+2\right)}}}$ $\displaystyle \sim$ k^-3.

(36)

速率方程从另一个分布空间描述。t时刻度值为k的顶点组成一个集团，集团大小为 N_k $\left(\vphantom{t}\right.$ t $\left.\vphantom{t}\right)$ 。当新顶点进入系统时， N_k可能发生改变，其变化率满足如下方程，

$\displaystyle {\frac{{dN_{k}\left(t\right)}}{{dt}}}$ = mW^get $\displaystyle \left(\vphantom{k-1}\right.$ k - 1 $\displaystyle \left.\vphantom{k-1}\right)$ - mW^get $\displaystyle \left(\vphantom{k}\right.$ k $\displaystyle \left.\vphantom{k}\right)$ + $\displaystyle \delta_{{k,m}}^{}$ .

(37)

其中 W^get $\left(\vphantom{k}\right.$ k $\left.\vphantom{k}\right)$ 为所有度值为k的顶点获得新的联接的几率，

W^get $\displaystyle \left(\vphantom{k}\right.$ k $\displaystyle \left.\vphantom{k}\right)$ = $\displaystyle {\frac{{kN_{k}\left(t\right)}}{{\sum_{d}dN_{d}\left(t\right)}}}$ .

(38)

N_k同样满足方程 $\sum_{{k}}^{}$ kN_k $\left(\vphantom{t}\right.$ t $\left.\vphantom{t}\right)$ = 2mt + m₀，且

(39)

结合一上方程可以解得度分布 P $\left(\vphantom{k}\right.$ k $\left.\vphantom{k}\right)$ ，具体计算见文章[20,23]。

Next: 结束语 Up: 解析与数值计算方法 Previous: 随机网络的几何性质

wwwwjs 2004-01-04