论文部分内容阅读
（1. 青岛科技大学数理学院，山东青岛266061；2.青岛科技大学网络管理中心，山东 青岛266061；3. 青岛科技大学教务处，山东青岛266061）
摘要： 讨论了一类基于BA模型生成机理的特殊的生长网络模型，采用率方程的方法计算得 其度分布，证明了该网络是节点度分布是符合幂律分布的无标度网络，其幂指数为-2。从理 论上分析了这个模型与BA模型由于拓扑结构的不同而造成的宏观性质的差异。并将这个模型 应用于高校人才吸引网络，利用SPSS和Matlab模拟仿真证明了该模型数学期望关系式的正确 性及模型的有效性。
关键词：无标度网络；BA模型；生长网络；率方程
中图分类号：N941.4文献标识码：A[WT]文章编号：16721098(2008)02008103
Analysis and Application of A Special Growth Network Model
SHEN Xiuzhuan LIU Huiming ZHANG Shuhua
(1. School of Sciences, Qingdao University of Science and Technology, Qingdao Sh andong 266061, China; 2. Network Centre, Qingdao University of Science and Techn ology, Qingdao Shandong 266061, China; 3. Teaching Affairs Office, Qingdao Unive rsity of Science and Technology, Qingdao Shandong 266061, China) Abstract: A special growth network model based on BA model was discussed. Its de gree distribution was computed by use of rate equation method. The degree distri bution was proved to be scale free network, which obeys powerlaw with exponen t-2. The discrepancy of macroscopical property between BA and the model was analy zed in aspect of theory as result from difference of their topological structure . The model was applied to university attracting talents network. Simulations wi th SPSS and Matlab proved that the model’s mathematical expectation formulais correct and available.
Key words:scale free network; BA model; growth network; rateequation
自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。例如，神经系统可以看 作大量神经细胞通过神经纤维相互连接形成的网络；计算机网络可以看作是自主工作的计算 机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络。类似的还有电力网络、 社会关系网络、交通网络等等。
复杂网络的研究热潮首先源起于1998年WattsStrogatz的小世界网络模型［1］，它 揭示了复杂网络的小世界效应。近年来在复杂网络研究上的另一重大发现就是许多复杂网络 ，如Internet、WWW以及新陈代谢网络等的连接度分布函数具有幂律形式。由于这类网络的 节点的连接度没有明显的特征长度，故称为无标度网络［2］510。
为了解析幂律分布的产生机理,文献［2］510提出了一个无标度网络模型，现被称为B A模型。他们认为以前的许多网络模型都没有考虑到实际网络的如下两个重要特性：
(1) 生长(growth)特性：即网络的规模是不断扩大的；
(2) 优先连接（preferential attachment）的特性：即新的节点更倾向于与那些具 有较高 连接度的“大”节点相连接。这种现象也称为“富者更富”或者“马太效应”。基于B A模型的内在生成机制，文献［3］85提出了一类特殊的生长网络模型，其模型简单， 即可定性地又可定量地描述问题。
1模型分析
1．1模型介绍
（1） 生长考虑有N个点构成的网络，网络中各点互不相连但每点具有一定的 顶点度 ，每一时间步长，有一新边进入此网，与网中某点相连（见图1）。例如，N个生 产同种 产品的企业，企业即为顶点，顾客选择这个企业的产品就相当于与这个企业做了一个连接， 企业的顶点度为选择这个企业的顾客数目。而企业之间并无连接，但他们之间存在制约关系 ，所以这个网络也可看作是一个系统。
图1模型结构示意图（2） 优先连接一新边与一个节点相连的概率与这一节点的顶点度成正比。如一企业顾客 数目越多，其他顾客选择这一企业的概率越大，这在实际生活中是合理的。
1．2与BA模型比较
人们在刻画复杂网络结构的统计特性上提出了许多概念与方法，其中有三个基本概念：平均 路径长度、聚类系数和度分布。 BA无标度网络的平均路径长度、 聚类系数［2］511 和节点度服从幂指数为-3的幂律分布。
本文介绍的模型不同于BA模型，因为模型内各点互相不联接，在生长过程只添加新边而不加 点（见图1）。这个模型不存在计算平均路径长度和聚类系数问题。但可以计算其度分布， 采用率方程的方法进行计算［4］。
dNk[]dt[SX)]=[SX(]1[]A[SX)]［Ak-1Nk-1-AkNk］+δk1(1)式中：δk1为初始条件；Nk为t时刻度为k的节点数目；[SX (]Ak[]A[SX)]为新边与度为k的节点连接的概率。
对上述模型t时刻总度数为t，引入的新点与原网络中的度数为k的点连接的概率为[SX(]k []t[SX)]。这时，相应的率方程为
dNk[]dt[SX)]=[SX(]1[]t[SX)]［(k-1)Nk-1-kNk］+δk1
为求解率方程，按照大数定律［5］有
Nk(t)≈tnk
则nk=[SX(]1[]t[SX)]［(k-1)tnk-1-ktnk］+δk1
化简得nk=[SX(]k-1[]k+1[SX)]nk-1由于n1=[SX(]1[]2[SX)]，所以 nk=[SX(]1[]k(k+1)[SX)]～k-2。可见模型中度为k的顶点数大致服从幂 律分布，所以这个网络是一个无标度网络。上述模型度分布服从幂指数为-2的幂律分布，而BA模型度分布服从幂指数为-3的幂律分布，这种宏观性质的差异主要是由于模型拓扑结构 的不同造成的。该模型可以视为BA模型的扩展模型。
1．3模型演化分析
对模型展开演化分析，设t0=0,由于每一时刻有一新边进入网络，所以t时刻网络的总度 数为t, 按照优先连接的思想，设度为k的点得到新边的概率与度k成线性关系设为[SX(]k[]t [SX)]，Ptk,s为点s在t时刻度为k的概率。可由主方程法建立方程
Pt+1k,s=Ptk-1,s([SX(]k-1[]t[SX)])+Ptk,s(1-[SX( ]k[]t[SX)])(2)
式(2)右端第一项表示t时s点的度为k-1,它以概率[SX(]k-1[]t[SX)]得到一条边，则t+1时 其度将为k；第二项表示t时其度为k，其度保持不变的概率为(1-[SX(]k[]t[SX)])。则若要 求t＋1时s的度为k，只要这二者中有一项成立即可。
式（2）实际上是条件概率的全概率公式。第一项是在Ptk-1,s的条件下又得到 一条边；第二项是在Ptk,s的条件下得不到一条边。在文献［3］87中推演 出了网中任何一点在任何时间t时的数学期望，以计算t时此点可能吸引到的度数，亦即可能 聚集的量。记Ets—点s在t时的数学期望。
据式（2），有Et+1s=[SX(]t+1[]t[SX)]Ets，这样得到了一个迭代式。 由此可得Et+1s=[SX(]t+1[]t0[SX)]Et0s不失普遍性，可写成Ets=[SX(]t[]t0[SX)]Et0s。如果在初始条件中，对于点s，只 是Pt0k,s=1，其他均为0。所对应的度数K记做Ks，又将有
Ets=([SX(]Ks[]t0[SX)])t(3)
* 2004年与2006年的《中国大学评价研究报告》式(3)所描写的是一种统计规律，是描写不断加入（吸引）新边的演化过程。同时各点s 之间存在竞争机制,表现在具有不同的初始优势（或劣势）,竞争也是一种自组织，因而式(3 )是描写自聚集自组织演化的整体统计规律。
2模型的应用
现在越来越多的顶尖人才愿意选择高校作为发展基地。影响人才选择高校的因素很多，其中 一个非常重要因素，那就是在这所高校里有多少优秀的人才。容易理解高校优秀人才越多其 吸引力越大。由此，考虑将该模型应用于高校对人才的吸引网络。
作者以高校为节点，每点具有一定的初始顶点度，代表高校此时拥有人才的数目。人才选择 了这所高校就意味着与这所高校建立了一个连接。人才选择一所高校的概率与高校人才的多 少成正比。为便于取得数据，本文以高校中具有博士学位的教师作为是否人才的衡量标准。
初始条件中，t0的意义是初始时刻高校教师中具有博士学位的数目，t表示网络演化到t 时刻的高校教师中具有博士学位的数目。Ks表示节点s在初始时刻博士的数目；Ets 表示节点s经过演化后在t时刻博士数目的数学期望。从Ets=([SX(]Ks[]t0[SX)]) t可以看出：节点s的博士数目与时间成正比，与高校初始的博士数目成正比*。
下面通过具体的数据对该模型来做模拟仿真。
表1六所高校具有博士学位的教师数目(人)
时间/年中国海洋大学复旦大学山东师范大学青岛大学烟台 大学潍坊学院2004[]550[]707[]280[]389[]150[]112[BHDWG1*8/9]2006[]579[]824[]354[]423[]200[]128[BG)F]由表1可以看出，t0＝2 188，t＝2 508，用式（3）计算可以求出各点的数学期望
用SPSS将网中各点的数学期望与各点的实际度数进行线性回归 分析[CM)]， 其回归方程为 y=1.034x-14.078(y代表网中各点度数的数 学期望；x代表各点实际度数)。利用Matlab模拟仿真得到拟合曲线（见图2）。网络中各点的实际度数
图2各节点度与其数学期望的拟合曲线图2说明用实际数据与式（3）计算出来各点数学期望可 以很好地吻合。从而，验证了该公式的正确性。虽然实际结果与理论结果有一定的定量上的 差别，但是在统计意义上仍不失正确性。
3结语
本文讨论了一种简单的、特殊的、但又广泛应用的生长网络模型，从理论的角度利用率方程 计算分析了该模型的度分布，阐明了该模型与BA模型的区别与联系。并将其应用于高校对人 才的吸引网络，利用SPSS和Matlab对具体数据进行模拟仿真，仿真实例验证了理论的正确性 。
参考文献：
［1］WATTS D J，STROGATZ S H.Collective Dynamics of SmallWorl d Networks［J］.Nature,1998,393:440442.
［2］BARABASI A L,ALBERT R.Emergence of Scaling in Random Netwo rks［J］.Science,1999,286:509512.
［3］张嗣瀛，自聚集.吸引核与聚集量［J］.复杂系统与复杂性科学，2005,2(4) :8492.
［4］P L KRAPIVSKY,S REDNER.Rate Equation Approach for GrowingN etworks［J］.Statistical Mechanics of Complex Networks,2003，625:322.
［5］郭雷,许晓鸣,史定华，等.复杂网络［M］.上海:上海教育出版社,2006,6 14.
［6］周涛,柏文洁,汪秉宏，等.复杂网络研究概述［J］.物理,2005,34:3136.
［7］LI XIANG，CHEN GUANRONG.A LocalWorld Evolving Network Mod el［J］.Physica A,2003,328:274286．
(责任编辑：何学华)
摘要： 讨论了一类基于BA模型生成机理的特殊的生长网络模型，采用率方程的方法计算得 其度分布，证明了该网络是节点度分布是符合幂律分布的无标度网络，其幂指数为-2。从理 论上分析了这个模型与BA模型由于拓扑结构的不同而造成的宏观性质的差异。并将这个模型 应用于高校人才吸引网络，利用SPSS和Matlab模拟仿真证明了该模型数学期望关系式的正确 性及模型的有效性。
关键词：无标度网络；BA模型；生长网络；率方程
中图分类号：N941.4文献标识码：A[WT]文章编号：16721098(2008)02008103
Analysis and Application of A Special Growth Network Model
SHEN Xiuzhuan LIU Huiming ZHANG Shuhua
(1. School of Sciences, Qingdao University of Science and Technology, Qingdao Sh andong 266061, China; 2. Network Centre, Qingdao University of Science and Techn ology, Qingdao Shandong 266061, China; 3. Teaching Affairs Office, Qingdao Unive rsity of Science and Technology, Qingdao Shandong 266061, China) Abstract: A special growth network model based on BA model was discussed. Its de gree distribution was computed by use of rate equation method. The degree distri bution was proved to be scale free network, which obeys powerlaw with exponen t-2. The discrepancy of macroscopical property between BA and the model was analy zed in aspect of theory as result from difference of their topological structure . The model was applied to university attracting talents network. Simulations wi th SPSS and Matlab proved that the model’s mathematical expectation formulais correct and available.
Key words:scale free network; BA model; growth network; rateequation
自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。例如，神经系统可以看 作大量神经细胞通过神经纤维相互连接形成的网络；计算机网络可以看作是自主工作的计算 机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络。类似的还有电力网络、 社会关系网络、交通网络等等。
复杂网络的研究热潮首先源起于1998年WattsStrogatz的小世界网络模型［1］，它 揭示了复杂网络的小世界效应。近年来在复杂网络研究上的另一重大发现就是许多复杂网络 ，如Internet、WWW以及新陈代谢网络等的连接度分布函数具有幂律形式。由于这类网络的 节点的连接度没有明显的特征长度，故称为无标度网络［2］510。
为了解析幂律分布的产生机理,文献［2］510提出了一个无标度网络模型，现被称为B A模型。他们认为以前的许多网络模型都没有考虑到实际网络的如下两个重要特性：
(1) 生长(growth)特性：即网络的规模是不断扩大的；
(2) 优先连接（preferential attachment）的特性：即新的节点更倾向于与那些具 有较高 连接度的“大”节点相连接。这种现象也称为“富者更富”或者“马太效应”。基于B A模型的内在生成机制，文献［3］85提出了一类特殊的生长网络模型，其模型简单， 即可定性地又可定量地描述问题。
1模型分析
1．1模型介绍
（1） 生长考虑有N个点构成的网络，网络中各点互不相连但每点具有一定的 顶点度 ，每一时间步长，有一新边进入此网，与网中某点相连（见图1）。例如，N个生 产同种 产品的企业，企业即为顶点，顾客选择这个企业的产品就相当于与这个企业做了一个连接， 企业的顶点度为选择这个企业的顾客数目。而企业之间并无连接，但他们之间存在制约关系 ，所以这个网络也可看作是一个系统。
图1模型结构示意图（2） 优先连接一新边与一个节点相连的概率与这一节点的顶点度成正比。如一企业顾客 数目越多，其他顾客选择这一企业的概率越大，这在实际生活中是合理的。
1．2与BA模型比较
人们在刻画复杂网络结构的统计特性上提出了许多概念与方法，其中有三个基本概念：平均 路径长度、聚类系数和度分布。 BA无标度网络的平均路径长度、 聚类系数［2］511 和节点度服从幂指数为-3的幂律分布。
本文介绍的模型不同于BA模型，因为模型内各点互相不联接，在生长过程只添加新边而不加 点（见图1）。这个模型不存在计算平均路径长度和聚类系数问题。但可以计算其度分布， 采用率方程的方法进行计算［4］。
dNk[]dt[SX)]=[SX(]1[]A[SX)]［Ak-1Nk-1-AkNk］+δk1(1)式中：δk1为初始条件；Nk为t时刻度为k的节点数目；[SX (]Ak[]A[SX)]为新边与度为k的节点连接的概率。
对上述模型t时刻总度数为t，引入的新点与原网络中的度数为k的点连接的概率为[SX(]k []t[SX)]。这时，相应的率方程为
dNk[]dt[SX)]=[SX(]1[]t[SX)]［(k-1)Nk-1-kNk］+δk1
为求解率方程，按照大数定律［5］有
Nk(t)≈tnk
则nk=[SX(]1[]t[SX)]［(k-1)tnk-1-ktnk］+δk1
化简得nk=[SX(]k-1[]k+1[SX)]nk-1由于n1=[SX(]1[]2[SX)]，所以 nk=[SX(]1[]k(k+1)[SX)]～k-2。可见模型中度为k的顶点数大致服从幂 律分布，所以这个网络是一个无标度网络。上述模型度分布服从幂指数为-2的幂律分布，而BA模型度分布服从幂指数为-3的幂律分布，这种宏观性质的差异主要是由于模型拓扑结构 的不同造成的。该模型可以视为BA模型的扩展模型。
1．3模型演化分析
对模型展开演化分析，设t0=0,由于每一时刻有一新边进入网络，所以t时刻网络的总度 数为t, 按照优先连接的思想，设度为k的点得到新边的概率与度k成线性关系设为[SX(]k[]t [SX)]，Ptk,s为点s在t时刻度为k的概率。可由主方程法建立方程
Pt+1k,s=Ptk-1,s([SX(]k-1[]t[SX)])+Ptk,s(1-[SX( ]k[]t[SX)])(2)
式(2)右端第一项表示t时s点的度为k-1,它以概率[SX(]k-1[]t[SX)]得到一条边，则t+1时 其度将为k；第二项表示t时其度为k，其度保持不变的概率为(1-[SX(]k[]t[SX)])。则若要 求t＋1时s的度为k，只要这二者中有一项成立即可。
式（2）实际上是条件概率的全概率公式。第一项是在Ptk-1,s的条件下又得到 一条边；第二项是在Ptk,s的条件下得不到一条边。在文献［3］87中推演 出了网中任何一点在任何时间t时的数学期望，以计算t时此点可能吸引到的度数，亦即可能 聚集的量。记Ets—点s在t时的数学期望。
据式（2），有Et+1s=[SX(]t+1[]t[SX)]Ets，这样得到了一个迭代式。 由此可得Et+1s=[SX(]t+1[]t0[SX)]Et0s不失普遍性，可写成Ets=[SX(]t[]t0[SX)]Et0s。如果在初始条件中，对于点s，只 是Pt0k,s=1，其他均为0。所对应的度数K记做Ks，又将有
Ets=([SX(]Ks[]t0[SX)])t(3)
* 2004年与2006年的《中国大学评价研究报告》式(3)所描写的是一种统计规律，是描写不断加入（吸引）新边的演化过程。同时各点s 之间存在竞争机制,表现在具有不同的初始优势（或劣势）,竞争也是一种自组织，因而式(3 )是描写自聚集自组织演化的整体统计规律。
2模型的应用
现在越来越多的顶尖人才愿意选择高校作为发展基地。影响人才选择高校的因素很多，其中 一个非常重要因素，那就是在这所高校里有多少优秀的人才。容易理解高校优秀人才越多其 吸引力越大。由此，考虑将该模型应用于高校对人才的吸引网络。
作者以高校为节点，每点具有一定的初始顶点度，代表高校此时拥有人才的数目。人才选择 了这所高校就意味着与这所高校建立了一个连接。人才选择一所高校的概率与高校人才的多 少成正比。为便于取得数据，本文以高校中具有博士学位的教师作为是否人才的衡量标准。
初始条件中，t0的意义是初始时刻高校教师中具有博士学位的数目，t表示网络演化到t 时刻的高校教师中具有博士学位的数目。Ks表示节点s在初始时刻博士的数目；Ets 表示节点s经过演化后在t时刻博士数目的数学期望。从Ets=([SX(]Ks[]t0[SX)]) t可以看出：节点s的博士数目与时间成正比，与高校初始的博士数目成正比*。
下面通过具体的数据对该模型来做模拟仿真。
表1六所高校具有博士学位的教师数目(人)
时间/年中国海洋大学复旦大学山东师范大学青岛大学烟台 大学潍坊学院2004[]550[]707[]280[]389[]150[]112[BHDWG1*8/9]2006[]579[]824[]354[]423[]200[]128[BG)F]由表1可以看出，t0＝2 188，t＝2 508，用式（3）计算可以求出各点的数学期望
用SPSS将网中各点的数学期望与各点的实际度数进行线性回归 分析[CM)]， 其回归方程为 y=1.034x-14.078(y代表网中各点度数的数 学期望；x代表各点实际度数)。利用Matlab模拟仿真得到拟合曲线（见图2）。网络中各点的实际度数
图2各节点度与其数学期望的拟合曲线图2说明用实际数据与式（3）计算出来各点数学期望可 以很好地吻合。从而，验证了该公式的正确性。虽然实际结果与理论结果有一定的定量上的 差别，但是在统计意义上仍不失正确性。
3结语
本文讨论了一种简单的、特殊的、但又广泛应用的生长网络模型，从理论的角度利用率方程 计算分析了该模型的度分布，阐明了该模型与BA模型的区别与联系。并将其应用于高校对人 才的吸引网络，利用SPSS和Matlab对具体数据进行模拟仿真，仿真实例验证了理论的正确性 。
参考文献：
［1］WATTS D J，STROGATZ S H.Collective Dynamics of SmallWorl d Networks［J］.Nature,1998,393:440442.
［2］BARABASI A L,ALBERT R.Emergence of Scaling in Random Netwo rks［J］.Science,1999,286:509512.
［3］张嗣瀛，自聚集.吸引核与聚集量［J］.复杂系统与复杂性科学，2005,2(4) :8492.
［4］P L KRAPIVSKY,S REDNER.Rate Equation Approach for GrowingN etworks［J］.Statistical Mechanics of Complex Networks,2003，625:322.
［5］郭雷,许晓鸣,史定华，等.复杂网络［M］.上海:上海教育出版社,2006,6 14.
［6］周涛,柏文洁,汪秉宏，等.复杂网络研究概述［J］.物理,2005,34:3136.
［7］LI XIANG，CHEN GUANRONG.A LocalWorld Evolving Network Mod el［J］.Physica A,2003,328:274286．
(责任编辑：何学华)