一类无标度合作网络的演化模型

　2005 年 11 月 系统工程理论与实践 第 11 期 　 文章编号 :100026788 (2005) 1120055206 一类无标度合作网络的演化模型 章忠志1 ,荣莉莉1 ,周 　涛2 (11 大连理工大学系统工程研究所 ,辽宁 大连 116024 ;21 中国科学技术大学近代物理系 ,安徽 合肥 230026) 摘要 : 　提出了一类特殊的无标度合作网络的演化模型. 利用平均场方法解析计算了节点的增长动态 性 ,证明了该网络是节点度分布符合幂律分布的无标度网络 ,其幂指数位于 2 和 3 之间. 给出了节点的 集聚系数与度的关系表达式 ,并证明了网络的平均路径长度最多以网络的对数形式增长. 数值模拟结果 与理论计算值很好地吻合. 关键词 : 　复杂网络 ;合作网络 ;复杂系统 ;无标度 ;无序系统 中图分类号 : 　N94 ;O173 　　　　　　　　文献标识码 : 　A 　　　 An Evolving Model for Scale2free Collaboration Networks ZHANG Zhong2zhi1 , RONGLi2li1 , ZHOU Tao2 (11Institute of Systems Engineering , Dalian University of Technology , Dalian 116024 , China ; 21Department of Modern Physics , University of Science and Technology of China , Hefei 230026 , China) Abstract : 　The collaboration networks can be found everywhere in real world. Since the collaboration networks have some particular mechanisms leading to their special topological properties , it is significant to construct a corresponding model. In this paper , we propose an evolving model aiming at a special kind of collaboration networks , of which the act2size is fixed. We prove that the degree distribution obeys power2law form with the exponent adjustable between 2 and 3. Also , we obtain the relation expression of vertex degree and its clustering coefficient. In addition , we prove that the increasing tendency of average path length is a little slower than the logarithm of network size. Further more , the simulation results are given out , which are in agreement with the theoretic calculations. Key words : 　complex networks ; collaboration networks ; complex systems ; scale2free ; disordered systems 收稿日期 :2004211229 资助项目 :国家自然科学基金重点资助项目 (70431001) 　　作者简介 :章忠志 (1974 - ) ,男 ,管理科学与工程专业博士研究生 ,研究方向 :复杂网络 ,金融风险管理 ;荣莉莉 (1964 - ) ,女 ,副教授 ,博士生导师 , 研究方向 :软计算方法及应用 ,知识管理 ,系统分析 ;周涛 (1983 - ) ,男 ,理论物理专业硕士生 , 研究方向 :复杂网络 ,组合网络分析 ,金融物理学 ,复杂系统理论 ,随机自适应算法. 1 　引言 自然界中存在的大量现实系统都可以用复杂网络加以描述[1～3 ] . 复杂网络的研究热潮首先源起于 1998 年 Watts2Strogatz 的小世界网络模型[4 ] 和 Barabási2Albert 的无标度网络模型 (BA 模型) [5 ,6 ] . 目前 ,复杂 网络特别是无标度网络研究的新局面已在全球范围内形成[1～3 ,7 ] . 在现实世界中 ,不同的网络有着完全不 同的形成机制 ,将网络分类并且针对不同类型的网络建立相应的模型是网络建模研究的必然方向 ,也是复 杂网络研究的热点之一. 合作网络是现实世界普遍存在且目前研究较多的一种网络 ,包括电影演员合作网[4 ,8 ] 、科研合作网等 等[9～11 ] . 这类网络具有与其他类型网络截然不同的独特之处 ,即它是由许多完全图组合而成的. 这里的完 全图指任何不同两顶点之间都有边相连的简单图. 例如在电影演员合作网中 ,在同一部电影参加演出的演 员就构成了一个完全图 ;在桥牌选手合作网络中 ,同在场上比赛的四名队员之间构成一个完全图 ;在科学 家合作网中 ,在同一篇文章上署名的作者构成一个完全图 ⋯⋯根据合作网络的特殊性 ,建立演化模型是很 有意义的工作. Ramasco 等提出了一个合作网络模型 (RDP 模型) [12 ] ,该模型捕捉到了合作网络的度度相关 性 (degree2degree correlation) 及簇度相关性 (Clustering2degree correlation) ,其度分布服从幂律行为 ,模型的不 足之处是每次合作的大小分布 (act2size distribution)是外生变量 ,而不是模型的内在组成部分. 何阅等人建 立了双粒子图景下的合作网络模型 ,所得到的合作网络主要统计特性也比较接近真实[13 ] . 最近 ,周涛等建 立了合作网络的一个一般模型 ,弥补了 RDP 模型的不足 ,在该模型中 ,每次合作的大小分布为单峰指数衰 减函数 ;通过调节择优连接参数 ,可使模型的节点度在指数分布与无标度分布之间转换[14 ] . 在现实世界的众多合作网络中 ,有一类较特殊的网络 ,在这类网络中 ,完成一次合作的人数是固定的 , 如桥牌网中每次合作总是由 4 个人完成 ,每场篮球或足球比赛的主力参赛队员的人数也是固定的 ,等等. 由于这类网络在现实生活中不为少见 ,对其进行研究 ,搞清合作者之间的合作关系与合作方式 ,掌握合作 的动态变化过程 ,了解由合作关系所形成网络的最终拓扑结构 ,可以为未来更好地合作提供有益的建议. 遗憾的是目前还没有相关的研究发表. 本文考虑了该类特殊的合作网络 ,建立了相应的演化模型. 解析计 算了节点的增长动态性和节点的度分布 ,给出了节点的集聚系数与度的关系表达式 ,并解析计算了网络平 均路径长度的增长趋势. 文章还对网络演化过程进行了数值模拟 ,模拟值与解析计算结果相吻合. 2 　模型的描述 一般而言 ,一个好的复杂网络模型不但能够抓住问题的要害和主要特征 ,而且生成机制简单 ,易于分 析. 本着这一建模的宗旨 ,我们对这类网络的生成机制进行简化 ,以捕捉网络的最终拓扑结构 ,并能解析求 解网络的主要参数特性. 假设每一次合作的人数为 m + 1 ( m ≥2) ,当新节点进入系统时 ,总是从原系统中 选择有过合作行为的 m 个人进行合作. 下面给出该类合作网络的演化过程. 设网络初始状态 ( t = 0)为由 m ( m ≥2)个节点和 m ( m - 1)Π2 条边组成的完全图 ( m2完全图) ,尔后在 每一个时间步内 ,网络新增一个节点 ,该节点从网络中随机选择一个 m2完全图 ,并与此 m 个节点分别连 一条边 ,表示一次 m + 1 个人的合作. 易知每一个时间步网络增加 1 个节点 , m 条边 , m 个 m2完全图和 1 个 ( m + 1) 2完全图. 图 1 给出了每次合作人数为 3 的网络增长示意图 ,在初始时刻 ,网络为相互连接的三 个节点组成的三角形 ,然后在每个时间步 ,增加一个新节点 ,新顶点与随机选择的一个三角形的三个顶点 各连一条边. 图 1 　m = 3 时的网络增长示意图 　 本模型虽然只是一个粗糙的模型 ,却抓住了合作网络最主要的特征 ,即网络由完全图构成. 例如桥牌 网络即可看作本模型在 m = 3 时的情形. 3 　网络的统计特性 311 　节点的增长动态性与度分布 模型中任一节点 v 的度 kv 随时间的演化关系可通过平均场近似的方法求得. 由于新节点进入系统 时 ,总是与一个随机选择的 m2完全图的各顶点建立连接 ,而且 ,度越大的节点会在越多的 m2完全图中出 现. 节点度每增加 1 ,由其作为组成部分的 m2完全图的数目就增加 m ,因此 ,在每一个时间步 ,新节点与其 连接的概率也越大. 在每一时间步 ,新节点进入系统并连接到节点 v 时 , kv 将增加 1. 假设 kv 为连续实变 量 ,它满足下面的动态方程 5 kv5 t = ( m - 1) kv - m ( m - 2)mt + 1 . (1) 65 系统工程理论与实践 2005 年 11 月 　　上式中的分母表示在新节点引入之前 ,系统所具有的 m2完全图的数目 ,分子表示组成成分包含节点 v 的 m2完全图的数目 ,其初始条件为 :节点 v 在 tv 时刻进入系统 ,此时其度为 kv ( tv ) = m . 于是满足这一初 始条件的方程 (1)的解为 : kv ( t) = m ( m - 2) m - 1 + m m - 1 mt + 1 mtv + 1 β , (2) 其中β= m - 1 m . 式 (2)表示所有节点的度按同一方式演化 ,即都服从幂律. 利用式 (2) ,可写出连通度 kv ( t) 小于 k 的 概率表达式 : P[ kv ( t) < k ] = P tv > mt + 1 m m - 1 m 1Πβ k - m ( m - 2) m - 1 1Πβ - 1 m . (3) 　　由于每一个时间步都有且仅有一个节点加入到原网络中 ,因此 tv 服从均匀分布 ,其概率密度为 : Pv ( tv ) = 1 m + t . (4) 将式 (4)代入式 (3) ,得 : P tv > mt + 1 m m - 1 m 1Πβ k - m ( m - 2) m - 1 1Πβ - 1 m = 1 - P tv ≤ mt + 1 m m - 1 m 1Πβ k - m ( m - 2) m - 1 1Πβ - 1 m = 1 - P tv ≤ mt + 1 ( m + t) m m - 1 m 1Πβ k - m ( m - 2) m - 1 1Πβ - 1Πmm + t , (5) 于是节点的度分布 P ( k)可通过下式得到 P ( k) = 5 P[ kv ( t) < k ]5 k = ( mt + 1) mm - 1 2 m - 1m - 1 ( m + t) m k - m ( m - 2) m - 1 1 β+1 . (6) 当 t →∞时 ,有 : P ( k) ～ m m - 1 2 m - 1 m - 1 k - m ( m - 2) m - 1 - 1 β+1 = m m - 1 2 m - 1 m - 1 k - m ( m - 2) m - 1 - γ , (7) 其中 : γ = 1β + 1 = 2 m - 1 m - 1 . (8) 　　幂律度分布的幂指数为γ= (2 m - 1)Π( m - 1) ,当 m = 2 时 ,γ= 3 ;当 m →∞,γ→2. 通过调节 m 的值 , 可以得到介于区间 (2 ,3)的不同的γ离散值 ,而多数现实网络节点度分布的幂律指数也处于该区间. 从式 (2)知 ,节点度为时间 t 的指数函数 ,其指数β= ( m - 1)Πm ,当 m = 2 时 ,β= 1Π2 ;当 m →∞,β→1 , 因此 ,β∈ 12 ,1 . 由式 (8)知 ,β和γ满足下面的关系 : β(γ - 1) = 1 (9) 符合无标度网络的普适性关系[15 ] . 图 2 给出了网络度分布的模拟结果 ,图中横、纵两个坐标轴均为对数形式 , (a) 和 (b) 分别为 m = 2 ,3 两种情况 ,网络节点数均为 10000 ,圆圈和方块分别表示 m = 2 ,3 时的网络运行 20 次的平均值. 实线表示 式 (7)给出的理论结果 ,图 (a) 、(b)中直线的斜率分别为 - 3 和 - 215. 从图 2 可以看出 ,数值实验中的节点 度服从幂律分布 ,其幂指数与平均场理论计算的结果基本一致. 值得注意的是 ,图 2 中的数值结果出现厚 75第 11 期 一类无标度合作网络的演化模型 尾现象 ,即许多度数很大的节点出现的概率相同. 发生这一情况的主要原因是 ,数值模拟中网络节点的数 目有限 ,而预测值则是 t →∞时的统计结果. 网络规模越大 ,模拟结果与理论计算值也将越吻合. 图 2 　模型的度分布 　 312 　集聚系数( Clustering Coefficient) 节点 v 的集聚系数描述网络中与 v 直接相连的节点之间的连接关系. 根据定义 ,节点 v 的集聚系数为 与该节点直接相邻的 kv 个节点间实际存在的边数目占最大可能存在的边数 12 kv ( kv - 1) 的比例. 网络的 集聚系数为所有节点集聚系数的平均值. 对于本文这类特殊的网络 ,可以求出度为 k 的节点的集聚系数 C ( k)的精确表达式. 当一个新节点进入系统与一个 m2完全图进行连接时 ,其度等于 m ,集聚系数等于 1 , 因为其所有邻居之间是全连接的. 在以后的时间步 ,当新节点与所考虑的节点连接时 ,必定同时与该节点 的 m - 1 个邻居进行连接. 因此 ,在节点度与集聚系数之间存在一一对应的关系. 对于度为 k 的节点 ,其集 聚系数为 C ( k) = m ( m - 1) 2 + ( m - 1) ( k - m) k ( k - 1) 2 = ( m - 1) (2 k - m) k ( k - 1) . (10) 　　式 (10)表明 ,对较大的 k ,集聚系数近似满足如下关系 : C ( k) ～ k - 1 . 值得一提的是 ,现实世界中包括 合作网络在内的许多网络 (如电影演员网) 的集聚系数都符合上述度量[16 ] . 假设节点的度 k 为连续变量 , 结合式 (7)和式 (10) ,可以得到整个网络的集聚系数 C 的表达式 C = ∑ k C ( k) P ( k) = ∑ ∞ k = m ( m - 1) (2 k - m) k ( k - 1) m m - 1 2 m - 1 m - 1 k - m ( m - 2) m - 1 - γ . (11) 图 3 　模型的集聚系数 　　图 3 给出了集聚系数的模拟情况 ,图中圆圈、方块、五角星和 三角形分别表示 m = 2 ,3 ,4 ,5 时网络的集聚系数 ,所有数据均为 同一规模的网络运行 20 次的平均值. 从图 3 可以看出 , m = 2 ,3 , 4 ,5 时网络的集聚系数 C 分别为 01739 ,01813 ,01851 ,01875. 可见 这类合作网络的集聚系数 C 非常大 ,而且随着 m 增加而增大 ,当 m →∞时 , C →1. 实际上 ,一般的合作网络的集聚系数都很大 ,如 电影演员网的集聚系数为 0179[4 ] . 312 　平均路径长度( Average Path Length , APL) 平均路径长度指网络所有节点对之间的平均最短距离 ,而节 点间的距离 (Distance) 指从一节点到另一节点所要经历边的最小 数目. 利用类似于文献[17 ]中的收缩法 ,可以近似预测文中所讨论网络的平均路径长度的增长趋势. 根据节点的生成时间 ,对节点进行标号. 容易证明[17 ] ,对任意两个节点 i 和 j ,每条从 i 到 j 的最短路 径 S Pij都不经过任何节点 k ,其中 k 满足条件 k > max( i , j) . 设 d ( i , j)表示 i 到 j 的最短距离 ,σ( N)表示顶点数为 N 的网络的所有节点对的距离和 ,即 85 系统工程理论与实践 2005 年 11 月 σ( N) = ∑ 0 ≤i < j ≤N - 1 d ( i , j) . (12) 用 L ( N)表示网络的平均路径长度 ,则 L ( N) = 2σ( N)N ( N - 1) (13) 由于新增节点不影响已经存在的节点之间的距离 ,因此 ,下面的式子成立 σ( N + 1) = σ( N) + ∑ N - 1 i = 0 d ( i , N) (14) 假设节点 N 进入系统时连向 m2完全图Ω ,又设Ω由 m 个节点 w1 , w2 , ⋯, wm 组成 ,则式 (14)可以写成 σ( N + 1) = σ( N) + ∑ N - 1 i = 0 ( D ( i , w) + 1) = σ( N) + N + ∑ N - 1 i = 1 D ( i , w) . (15) 式 (15)中的 D ( i , w) = min{d ( i , w1 ) ,d ( i , w2 ) , ⋯,d ( i , wm ) } . 将Ω收缩成单个节点 w ,不妨设 w ≡w1 ,此 时有 D ( i , w) = d ( i , w) . 由于 d ( w1 , w) = d ( w2 , w) = ⋯= d ( wm , w) = 0 ,式 (15)又可写成 σ( N + 1) = σ( N) + N + ∑ i ∈Ψ d ( i , w) . (16) 式 (16)的中 Ψ = {0 ,1 ,2 , ⋯, N - 1}Π{ w1 , w2 , ⋯, wm }是势为 N - m 的节点集 ,和式 ∑ i ∈Ψ d ( i , w) 可以看作是 本模型中规模为 N - m + 1 的网络里一个特定节点 w 到所有其它节点的距离和. ∑ i ∈Ψ d ( i , w) 可以近似地 用下式替代 ∑ i ∈Ψ d ( i , w) = ( N - m) L ( N - m + 1) . (17) 　　由于 L ( N)随 N 单调增加 ,显然有 ( N - m) L ( N - m + 1) = 2σ( N - m + 1)N - m + 1 < 2σ( N) N . (18) 结合式 (15) , (16)和 (17) ,可得下面的不等式 σ( N + 1) < σ( N) + N + 2σ( N)N . (19) 根据式 (19) ,可得σ( N)关于 N 的变化方程 dσ( N) d N = N + 2σ( N) N , (20) 于是得到下面的由方程 σ( N) = N2 ln N + μ. (21) 　　其中μ为常数. 当 N →∞时 ,σ( N) ～N2 ln N ,因此有 L ( N) ～ln N . 由于式 (20) 是从不等式 (19) 推导出 来的 ,故文中所考虑网络的平均路径长度 (APL)的增长趋势为 :L ( N)最多随 N 按对数形式 ln N 增长. 可见 该网络的平均路径长度较小. 另外 ,根据上节讨论 ,该网络具有较大的集聚系数. 因此 ,这类网络具有小世 界效应 (Small2world Effect) . 图 4 　模型的平均路径长度 图 4 给出了平均路径长度 L ( N ) 与网络大小 N 的关系. 图中 圆圈和方块分别表示 m = 2 ,3 时不同网络规模的平均路径长度 ,所 有数据均为同一规模的网络运行 20 次的平均值. 从图 4 可以看 出 ,平均路径长度 L ( N ) 的增长非常慢 ,当网络大小 N 较小时 , L ( N)近似以网络大小 N 的对数形式 ln N 增长 ,当 N 很大时 , L ( N)的增长比 ln N 的增长还要慢 ,与解析结果一致. 4 　结束语 本文提出了一个特殊的合作网络模型 ,模型中新加入节点与 已经存在的节点的连接隐含着择优连接机制 ,促使网络最终自组 95第 11 期 一类无标度合作网络的演化模型 织成无标度网络. 利用平均场近似的方法 ,我们解析求得了网络节点度分布的幂律指数 v = (2 m - 1)Π( m - 1) ,调节参数 m 的值 ,可以得到介于区间 (2 ,3)的不同的幂指数值. 另外 ,我们给出了网络节点的集聚系 数与度的关系表达式 ,并证明了平均路径长度最多以网络的对数形式增长. 所得的解析结果与数值模拟很 好地吻合. 当然 ,该模型仅仅是建立合作网络演化模型的一个初步的尝试. 在现实世界的许多合作网络中 , 每次合作的人数并非固定不变 ,而且选择合作伙伴的机制也十分复杂. 因此 ,如何按照不同合作网络的动 态演化机制 ,建立具体的演化网络模型 ,识别并捕捉影响网络拓扑结构形成的主要因素 ,从而加深对网络 拓扑结构及其动态变化的认识 ,是十分有价值的. 希望本模型能够为这方面的研究提供一些借鉴. 参考文献 : [ 1 ] 　Albert R , Barabási A L. Statistical mechanics of complex networks[J ] . Reviews of Modern Physics , 2002 ,74 (1) : 47 - 97. [ 2 ] 　Newman M E J . The structure and function of complex networks[J ] . SIAM Review , 2003 , 45 (2) : 167 - 256. [ 3 ] 　周涛 ,柏文洁 ,汪秉宏 ,等. 复杂网络研究概述[J ] . 物理 ,2005 , 34 (1) : 31 - 36. Zhou T , Bai W J , Wang B H ,et al. A brief review of complex networks[J ] . Physics , 2005 , 34 (1) : 31 - 36. [ 4 ] 　Watts D J , Strogatz S H. Collective dynamics of‘small2world’networks[J ] . Nature , 1998 , 393 : 440 - 442. [ 5 ] 　Barabási A L , Albert R. Emergence of scaling in random networks[J ] . Science , 1999 , 286 : 509 - 512. [ 6 ] 　Barabási A L , Albert R , Jeong H. Mean2field theory for scale2free random networks[J ] . Physica A ,1999 , 272 :173 - 187. [ 7 ] 　章忠志 ,荣莉莉. BA 网络的一个等价演化模型[J ] . 系统工程 ,2005 , 23 (2) : 1 - 5. Zhang Z Z , Rong L L. An evolving model equivalent to BA networks[J ] . Systems Engineering , 2005 , 23 (2) :1 - 5. [ 8 ] 　Amaral L A N , Scala A , Barthélémy M ,et al. Classes of small2world networks[J ] . PNAS , 2000 ,97 (21) : 11149 - 11152. [ 9 ] 　Newman M EJ . Scientific collaboration networks. Ⅰ. Network construction and fundamental results[J ] . Physical Review E , 2001 , 64 (1) : 016131. [10 ] 　Newman M E J . Scientific collaboration networks. Ⅱ. Shortest paths , weighted networks , and centrality[J ] . Physical Review E , 2001 ,64 (1) : 016132. [11 ] 　Fan Y, Li M H , Chen J W ,et al. Network of econophysicists : a weighted network to investigate the development of econophysics [J ] . International Journal of Modern Physics B , 2004 ,18 (17 - 19) :2505 - 2511. [12 ] 　Ramasco J J , Dorogovtsev S N , Pastor2Satorras R. Self2organization of collaboration networks[J ] . Physical Review E , 2004 ,70 (3) : 036106. [13 ] 　何阅 ,张培培 ,许田 ,等. 一个科研合作网的双粒子图自适应演化模型[J ] . 物理学报 ,2004 ,53 (6) : 1710 - 1715. He Y, Zhang P P , Xu T ,et al. A self2adaptive bi2particle graph model for scientific collaboration[J ] . Acta Physica Sinica , 2004 , 53 (6) : 1710 - 1715. [14 ] 　Zhou T , Jin Y D , Wang B H ,et al. A general model for collaboration networks[ R] . arXiv : cond2matΠ0502253. [15 ] 　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. [16 ] 　Ravasz E , Barabási A2L. Hierarchical organization in complex networks[J ] . Physical Review E , 2003 ,67 : 026112. [17 ] 　Zhou T , Yan G, Wang B H. Maximal planar networks with large clustering coefficient and power2law degree distribution [J ] . Physical Review E , 2005 , 71 : 046141. 06 系统工程理论与实践 2005 年 11 月