第10卷第6期 智能系统学报 Vol.10 No.6 2015年12月 CAAI Transactions on Intelligent Systems Dec.2015 D0L:10.11992/is.201507042 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20151110.1354.012.html 复杂网络中的在线社交网络演化模型 王景丽1，许立波2，庞超逸 (1.宁波大红鹰学院信息工程学院，浙江宁波315175：2.浙江大学宁波理工学院，浙江宁波315000：3.浙江大学 宁波理工学院，浙江宁波315000) 摘要：在线社交网络是一种广泛存在的社会网络，其节点度遵循幂率分布规律，但对于其结构演化模型方面的相 关研究还不多。基于复杂网络理论研究在线社交网络内部结构特征，提出一种结合内增长、外增长及内部边更替的 演化模型，借助平均场理论分析该模型的拓扑特性，实验和理论分析表明由该模型生成的网络，其度分布服从幂率 分布，且通过调整参数，幂率指数在1~3，能较好地反映不同类型的真实在线社交网络的度分布特征，因此具有广泛 适用性。 关键词：复杂网络：社交网络：度分布：幂率分布：演化：平均场：节点度：拓扑 中图分类号：TP393文献标志码：A文章编号：1673-4785(2015)06-0949-05 中文引用格式：王景丽，许立波，庞超逸.复杂网络中的在线社交网络演化模型[J].智能系统学报，2015,10(6)：949-953. 英文引用格式：WANG Jingli,XU Libo,PANG Chaoyi..Evolution model of online social networks based on complex networks[J]. CAAI Transactions on Intelligent Systems,2015,10(6):949-953. Evolution model of online social networks based on complex networks WANG Jingli',XU Libo2,PANG Chaoyi3 (1.Information Engineering,Ningbo Dahongying University,Ningbo 315175,China;2.Research Center on Intelligent Computing and Data Management Ningbo Institute of Technology,Zhejiang University,Ningbo 315000,China;3.Research Center on Intelligent Com- puting and Data Management Ningbo Institute of Technology,Zhejiang University,Ningbo 315000,China) Abstract:As a widespread social network,the node degree of online social networks has been proven by many re- searchers to follow the power-law distribution.However,there are few studies modeling the evolution of its struc- ture.In this paper,we propose an evolution model that combines the inside growth,outside growth,and edge re- placement based on those of complex networks.The topology properties of this model are analyzed using the mean- field theory.Experiment and theoretical analyses show that the degree of a node in a network generated by the new evolution model follows the power-law distribution and that the power-law index ranges between 1 and 3.Therefore, the proposed model can better reflect the node degree distribution characteristics of different types of real online so- cial networks and will have wide applicability. Keywords:complex network;social network;degree distribution;power-law distribution;evolution;mean field; node degree;topology 复杂网络作为刻画和研究复杂系统结构及其动 态发展的强有力工具之一，近年来迅速成为学术界 研究的热点，并与计算机科学、生物学、社会学、经济 收稿日期：2015-07-05.网络出版日期：2015-11-10. 学等学科交叉融合，广泛应用于诸如生物网络、传染 基金项目：国家自然科学基金资助项目(71271191)：宁波市自然科学基 病控制、知识网络、电力网、互联网等各种自然和社 金资助项目(2015A610138). 通信作者：王景丽.E-mailjingli.wang@nbdhyu..cd.cn 会动态网络及系统研究中.复杂网络的研究涵盖很
第 １０ 卷第 ６ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．６ ２０１５ 年 １２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｄｅｃ． ２０１５ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５０７０４２ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５１１１０．１３５４．０１２．ｈｔｍｌ 复杂网络中的在线社交网络演化模型 王景丽１ ，许立波２ ，庞超逸３ （１． 宁波大红鹰学院 信息工程学院，浙江 宁波 ３１５１７５； ２． 浙江大学 宁波理工学院， 浙江 宁波 ３１５０００； ３． 浙江大学 宁波理工学院， 浙江 宁波 ３１５０００） 摘 要：在线社交网络是一种广泛存在的社会网络，其节点度遵循幂率分布规律，但对于其结构演化模型方面的相 关研究还不多。 基于复杂网络理论研究在线社交网络内部结构特征，提出一种结合内增长、外增长及内部边更替的 演化模型，借助平均场理论分析该模型的拓扑特性，实验和理论分析表明由该模型生成的网络，其度分布服从幂率 分布，且通过调整参数，幂率指数在 １～ ３，能较好地反映不同类型的真实在线社交网络的度分布特征，因此具有广泛 适用性。 关键词：复杂网络；社交网络；度分布；幂率分布；演化；平均场；节点度；拓扑 中图分类号：ＴＰ３９３ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０６⁃０９４９⁃０５ 中文引用格式：王景丽，许立波，庞超逸． 复杂网络中的在线社交网络演化模型［Ｊ］． 智能系统学报， ２０１５， １０（６）： ９４９⁃９５３． 英文引用格式：ＷＡＮＧ Ｊｉｎｇｌｉ， ＸＵ Ｌｉｂｏ， ＰＡＮＧ Ｃｈａｏｙｉ． Ｅｖｏｌｕｔｉｏｎ ｍｏｄｅｌ ｏｆ ｏｎｌｉｎｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ｂａｓｅｄ ｏｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（６）： ９４９⁃９５３． Ｅｖｏｌｕｔｉｏｎ ｍｏｄｅｌ ｏｆ ｏｎｌｉｎｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ｂａｓｅｄ ｏｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ＷＡＮＧ Ｊｉｎｇｌｉ １ ， ＸＵ Ｌｉｂｏ ２ ， ＰＡＮＧ Ｃｈａｏｙｉ ３ （１． Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｎｉｎｇｂｏ Ｄａｈｏｎｇｙｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｎｉｎｇｂｏ ３１５１７５， Ｃｈｉｎａ； ２． Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｄａｔａ Ｍａｎａｇｅｍｅｎｔ Ｎｉｎｇｂｏ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｚｈｅｊｉａｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｎｉｎｇｂｏ ３１５０００， Ｃｈｉｎａ； ３． Ｒｅｓｅａｒｃｈ Ｃｅｎｔｅｒ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｍ⁃ ｐｕｔｉｎｇ ａｎｄ Ｄａｔａ Ｍａｎａｇｅｍｅｎｔ Ｎｉｎｇｂｏ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｚｈｅｊｉａｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｎｉｎｇｂｏ ３１５０００， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｓ ａ ｗｉｄｅｓｐｒｅａｄ ｓｏｃｉａｌ ｎｅｔｗｏｒｋ， ｔｈｅ ｎｏｄｅ ｄｅｇｒｅｅ ｏｆ ｏｎｌｉｎｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ｈａｓ ｂｅｅｎ ｐｒｏｖｅｎ ｂｙ ｍａｎｙ ｒｅ⁃ ｓｅａｒｃｈｅｒｓ ｔｏ ｆｏｌｌｏｗ ｔｈｅ ｐｏｗｅｒ⁃ｌａｗ ｄｉｓｔｒｉｂｕｔｉｏｎ． Ｈｏｗｅｖｅｒ， ｔｈｅｒｅ ａｒｅ ｆｅｗ ｓｔｕｄｉｅｓ ｍｏｄｅｌｉｎｇ ｔｈｅ ｅｖｏｌｕｔｉｏｎ ｏｆ ｉｔｓ ｓｔｒｕｃ⁃ ｔｕｒｅ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｐｒｏｐｏｓｅ ａｎ ｅｖｏｌｕｔｉｏｎ ｍｏｄｅｌ ｔｈａｔ ｃｏｍｂｉｎｅｓ ｔｈｅ ｉｎｓｉｄｅ ｇｒｏｗｔｈ， ｏｕｔｓｉｄｅ ｇｒｏｗｔｈ， ａｎｄ ｅｄｇｅ ｒｅ⁃ ｐｌａｃｅｍｅｎｔ ｂａｓｅｄ ｏｎ ｔｈｏｓｅ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ． Ｔｈｅ ｔｏｐｏｌｏｇｙ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｔｈｉｓ ｍｏｄｅｌ ａｒｅ ａｎａｌｙｚｅｄ ｕｓｉｎｇ ｔｈｅ ｍｅａｎ⁃ ｆｉｅｌｄ ｔｈｅｏｒｙ． Ｅｘｐｅｒｉｍｅｎｔ ａｎｄ ｔｈｅｏｒｅｔｉｃａｌ ａｎａｌｙｓｅｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｄｅｇｒｅｅ ｏｆ ａ ｎｏｄｅ ｉｎ ａ ｎｅｔｗｏｒｋ ｇｅｎｅｒａｔｅｄ ｂｙ ｔｈｅ ｎｅｗ ｅｖｏｌｕｔｉｏｎ ｍｏｄｅｌ ｆｏｌｌｏｗｓ ｔｈｅ ｐｏｗｅｒ⁃ｌａｗ ｄｉｓｔｒｉｂｕｔｉｏｎ ａｎｄ ｔｈａｔ ｔｈｅ ｐｏｗｅｒ⁃ｌａｗ ｉｎｄｅｘ ｒａｎｇｅｓ ｂｅｔｗｅｅｎ １ ａｎｄ ３． Ｔｈｅｒｅｆｏｒｅ， ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｏｄｅｌ ｃａｎ ｂｅｔｔｅｒ ｒｅｆｌｅｃｔ ｔｈｅ ｎｏｄｅ ｄｅｇｒｅｅ ｄｉｓｔｒｉｂｕｔｉｏｎ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ｔｙｐｅｓ ｏｆ ｒｅａｌ ｏｎｌｉｎｅ ｓｏ⁃ ｃｉａｌ ｎｅｔｗｏｒｋｓ ａｎｄ ｗｉｌｌ ｈａｖｅ ｗｉｄｅ ａｐｐｌｉｃａｂｉｌｉｔｙ． Ｋｅｙｗｏｒｄｓ： ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ； ｓｏｃｉａｌ ｎｅｔｗｏｒｋ； ｄｅｇｒｅｅ ｄｉｓｔｒｉｂｕｔｉｏｎ； ｐｏｗｅｒ⁃ｌａｗ ｄｉｓｔｒｉｂｕｔｉｏｎ； ｅｖｏｌｕｔｉｏｎ； ｍｅａｎ ｆｉｅｌｄ； ｎｏｄｅ ｄｅｇｒｅｅ； ｔｏｐｏｌｏｇｙ 收稿日期：２０１５⁃０７⁃０５． 网络出版日期：２０１５⁃１１⁃１０． 基金项目：国家自然科学基金资助项目（７１２７１１９１）；宁波市自然科学基 金资助项目（２０１５Ａ６１０１３８）． 通信作者：王景丽．Ｅ⁃ｍａｉｌｊｉｎｇｌｉ．ｗａｎｇ＠ ｎｂｄｈｙｕ．ｅｄｕ．ｃｎ 复杂网络作为刻画和研究复杂系统结构及其动 态发展的强有力工具之一，近年来迅速成为学术界 研究的热点，并与计算机科学、生物学、社会学、经济 学等学科交叉融合，广泛应用于诸如生物网络、传染 病控制、知识网络、电力网、互联网等各种自然和社 会动态网络及系统研究中．复杂网络的研究涵盖很
·950· 智能系统学报 第10卷 多方面，其中网络的演化及建模研究能够相当程度 能一定程度地模拟真实在线社交网络的度分布特征。 地揭示实际网络及系统的结构组成及变化规律，从 1 而能够对系统的未来发展做出预测并提早设置改进 在线社交网络演化模型 措施。因此演化模型一直是复杂网络研究的热点之 本文构造无向的网络演化模型，模拟了内部增 一，并提出了很多网络演化模型，以刻画现实中各种 长即网络中现有节点间添加新连接、内部调整即现 不同网络的特征及结构。 有节点间重连接及网增长即新节点和现有节点的 Watts等]提出小世界模型，具有短路径、高 连接等机制，对于有向网络亦可以参照文中分析。 聚类和强传递性特征，模拟人际关系网络的演化 具体演化步骤如下： 过程。Barabasi等[)在研究万维网时提出基于增 1)初始化：初始网络包含m,个节点，每个节点 长和优先连接的无标度BA模型，连接概率与节 与其余m。-1个节点相连； 点度成线性正比，较好地模拟出万维网中幂率度 2)随机增长：每个时间步添加一个新节点，并 分布特征和马太效应。之后，研究者们发现幂率 连接到m,个原有节点上，且满足m,<mo; 度分布特征广泛存在于各种现实网络，随着Fala- 3)优先连接：新节点与原有节点i相连接的概 tous等[3]发现互联网拓扑的幂率特性，AB模 率Ⅱ表达式为 型[]被提出应用于互联网拓扑建模，其在BA模 型基础上增加了内部连接和重配置过程：基于现 Ⅱ= (1) 实互联网连接倾向度更高的观测现象，广义线性 i 优先模型s)改进BA模型以模拟新节点连接对高 式中：k:为节点i的度； 度hub的优先选择性：动态优先模型[6)]基于不同 4)内部随机增长：每个时间步在网络内增加m2 层级A$间的关系，反映出互联网中的小世界特 条边，节点i被选为新增边的端点的概率Ⅱ，按式 性：多局域世界模型]考虑节点连接的局域特 (1)计算，且m2<mo 征，能较好反映节点层次性和聚类性。众多研究 5)内部优先连接更替：每个时间步选择m条边进 表明，合作网络[)、软件组件系统[1]、蛋白质网 行更替，更替方法为先随机选择节点i,随机移除与节 络[)、在线社交网络12]、传感器网络[1]等都呈 点i相连的某条边l:,添加以连接节点j和节点r的边 现出了度分布幂率特性，局部事件模型被用来模 l.,节点r按Ⅱ，概率择优选取，Ⅱ，按式(1)计算。 拟软件组件系统的无标度特性：顶点复制模 相比一般网络，在线社交网络中的连接度大的 型描述知识引用网络和新陈代谢网络，新节 节点可能更容易得到大量连接，因此在演化模型中， 点不完全遵循优先连接机制，而是通过模仿已有 除了新节点和内部增长具有优先连接机制外，内部 节点来构建模型。 优先连接更替也不同于一般模型中的重连机制，后 在线社交网络如微博、交友等是社会网络的一 者通常是以边l替代1，节点i的度不发生变化；而 种典型关系网络，将每个用户看作网络节点，许多研 内部优先连接更替是以l,替代。，更加强化高连接 究已经表明其节点度遵循幂率分布规律，但对于其 度节点间的连接倾向，且为防止出现孤立节点，模型 结构演化模型方面的相关研究还比较少。一方面， 设定当被选择节点度为1时，进行重新选点。 目前研究集中于通过抽样数据来进行数据分析，从 统计角度发现拓扑特征，虽然能较好还原真实网络 2演化模型的度分布属性 特性，但这种研究属于静态分析，不能模拟动态过程 根据平均场理论对模型的度分布进行近似分析， 以及添加行为过程：另一方面，研究表明在线社交网 假设节点度k随时间t连续变化，对k变化率求解： 络节点可能比一般网络更倾向于连接度大的节点， 很多传统模型不能直接适用，需要进行一定的改进。 随机增长：当新节点加入时，按概率Ⅱ连接到 本文提出一种在线社交网络演化模型，以注册用 m,个原节点上，则k变化率方程为 户作为网络节点，节点间的连边就是注册用户间的关 ak;(t) =m1Ⅱ (2) 注关系，节点和连边共同构成网络，不失一般性，本文 将此网络抽象成无向网络图。演化模型考虑随机增 内部随机增长：边的端点按概率Ⅱ，优先选择， 长、优先连接、内部增长及连接更替4种机制，采用平 边有2个端点，则k:变化率方程为 均场理论对模型度分布进行理论分析。理论分析和 ak;(t) dt =2m2Ⅱ (3) 仿真表明，演化模型网络的度呈现无尺度特征，且能 够模拟较大范围的幂率分布，具有广泛的适用性，并 内部优先连接更替：包含2个过程，首先是移除
多方面，其中网络的演化及建模研究能够相当程度 地揭示实际网络及系统的结构组成及变化规律，从 而能够对系统的未来发展做出预测并提早设置改进 措施。 因此演化模型一直是复杂网络研究的热点之 一，并提出了很多网络演化模型，以刻画现实中各种 不同网络的特征及结构。 Ｗａｔｔｓ 等［ １］ 提出小世界模型，具有短路径、高 聚类和强传递性特征，模拟人际关系网络的演化 过程。 Ｂａｒａｂáｓｉ 等［ ２］ 在研究万维网时提出基于增 长和优先连接的无标度 ＢＡ 模型，连接概率与节 点度成线性正比，较好地模拟出万维网中幂率度 分布特征和马太效应。 之后，研究者们发现幂率 度分布特征广泛存在于各种现实网络，随着 Ｆａｌａ⁃ ｔｏｕｓ 等［ ３］ 发 现 互 联 网 拓 扑 的 幂 率 特 性， ＡＢ 模 型［ ４］ 被提出应用于互联网拓扑建模，其在 ＢＡ 模 型基础上增加了内部连接和重配置过程；基于现 实互联网连接倾向度更高的观测现象，广义线性 优先模型［ ５］ 改进 ＢＡ 模型以模拟新节点连接对高 度 ｈｕｂ 的优先选择性；动态优先模型［ ６］ 基于不同 层级 ＡＳ 间的关系，反映出互联网中的小世界特 性；多局域世界模型［ ７⁃８］ 考虑节点连接的局域特 征，能较好反映节点层次性和聚类性。 众多研究 表明，合作网络［ ９］ 、软件组件系统［ １０］ 、蛋白质网 络［ １１］ 、在线社交网络［ １２］ 、传感器网络［ １３］ 等都呈 现出了度分布幂率特性，局部事件模型被用来模 拟软 件 组 件 系 统 的 无 标 度 特 性； 顶 点 复 制 模 型［ １４］ 描述知识引用网络和新陈代谢网络，新节 点不完全遵循优先连接机制，而是通过模仿已有 节点来构建模型。 在线社交网络如微博、交友等是社会网络的一 种典型关系网络，将每个用户看作网络节点，许多研 究已经表明其节点度遵循幂率分布规律，但对于其 结构演化模型方面的相关研究还比较少。 一方面， 目前研究集中于通过抽样数据来进行数据分析，从 统计角度发现拓扑特征，虽然能较好还原真实网络 特性，但这种研究属于静态分析，不能模拟动态过程 以及添加行为过程；另一方面，研究表明在线社交网 络节点可能比一般网络更倾向于连接度大的节点， 很多传统模型不能直接适用，需要进行一定的改进。 本文提出一种在线社交网络演化模型，以注册用 户作为网络节点，节点间的连边就是注册用户间的关 注关系，节点和连边共同构成网络，不失一般性，本文 将此网络抽象成无向网络图。 演化模型考虑随机增 长、优先连接、内部增长及连接更替 ４ 种机制，采用平 均场理论对模型度分布进行理论分析。 理论分析和 仿真表明，演化模型网络的度呈现无尺度特征，且能 够模拟较大范围的幂率分布，具有广泛的适用性，并 能一定程度地模拟真实在线社交网络的度分布特征。 １ 在线社交网络演化模型 本文构造无向的网络演化模型，模拟了内部增 长即网络中现有节点间添加新连接、内部调整即现 有节点间重连接及网络增长即新节点和现有节点的 连接等机制，对于有向网络亦可以参照文中分析。 具体演化步骤如下： １）初始化：初始网络包含 ｍ０个节点，每个节点 与其余 ｍ０ －１ 个节点相连； ２）随机增长：每个时间步添加一个新节点，并 连接到 ｍ１个原有节点上，且满足 ｍ１＜ ｍ０ ； ３）优先连接：新节点与原有节点 ｉ 相连接的概 率 Πｉ 表达式为 Πｉ ＝ ｋｉ ∑ ｊ ｋｊ （１） 式中：ｋｉ为节点 ｉ 的度； ４）内部随机增长：每个时间步在网络内增加 ｍ２ 条边，节点 ｉ 被选为新增边的端点的概率 Πｉ 按式 （１）计算，且 ｍ２＜ ｍ０ ； ５）内部优先连接更替：每个时间步选择 ｍ３条边进 行更替，更替方法为先随机选择节点 ｉ，随机移除与节 点 ｉ 相连的某条边 ｌ ｉｊ，添加以连接节点 ｊ 和节点 ｒ 的边 ｌ ｊｒ，节点 ｒ 按 Πｒ 概率择优选取，Πｒ 按式（１）计算。 相比一般网络，在线社交网络中的连接度大的 节点可能更容易得到大量连接，因此在演化模型中， 除了新节点和内部增长具有优先连接机制外，内部 优先连接更替也不同于一般模型中的重连机制，后 者通常是以边 ｌ ｉｒ替代 ｌ ｉｊ，节点 ｉ 的度不发生变化；而 内部优先连接更替是以 ｌ ｊｒ替代 ｌ ｉｊ，更加强化高连接 度节点间的连接倾向，且为防止出现孤立节点，模型 设定当被选择节点度为 １ 时，进行重新选点。 ２ 演化模型的度分布属性 根据平均场理论对模型的度分布进行近似分析， 假设节点度 ｋｉ随时间 ｔ 连续变化，对 ｋｉ变化率求解： 随机增长：当新节点加入时，按概率 Πｉ 连接到 ｍ１个原节点上，则 ｋｉ变化率方程为 ∂ｋｉ（ｔ） ∂ｔ ＝ ｍ１Πｉ （２） 内部随机增长：边的端点按概率 Πｉ 优先选择， 边有 ２ 个端点，则 ｋｉ变化率方程为 ∂ｋｉ（ｔ） ∂ｔ ＝ ２ｍ２Πｉ （３） 内部优先连接更替：包含 ２ 个过程，首先是移除 ·９５０· 智 能 系 统 学 报 第 １０ 卷
第6期 王景丽，等：复杂网络中的在线社交网络演化模型 .951- 2(1*2 过程，节点i被随机选中的概率为尺，N为节点总 m a m1+2m2*m3 k-a 数，被选择为移除边的另一端的概率为m3Ⅱ，；其次 假设时间t→0时，网络节点的度具有稳态分 是更替过程，被选择为更替边的两端的概率为2m3 布P(k): Ⅱ，因此整个更替过程k变化率方程为 aP(k;(t) (8) 理论表达式(9)近似给出。 k-a 10° 式中：a= 2m3(m1+m2） 模型假设节点是以相对时 m1+2m2+m3 10 y=2.5 间间隔进入网络的，因此节点i的到达时间t:具有 101 10 常数概率密度： 10 P(t:)=1/N≈1/t 故有 10 10 10 10 10 2(m1*2) mi -a m1022m3 图1演化模型度分布(m,=2,m2=1,m3=0) P(t;> t)= Lk-a Fig.1 Degree distribution of evolution model(m,=2, 2(m1*2) m2=1,m3=0) m -a m1+22*m3 1-P(t:≤ t)≈
过程，节点 ｉ 被随机选中的概率为 ｍ３ Ｎ ， Ｎ 为节点总 数，被选择为移除边的另一端的概率为 ｍ３Πｉ；其次 是更替过程，被选择为更替边的两端的概率为 ２ｍ３ Πｉ，因此整个更替过程 ｋｉ变化率方程为 ∂ｋｉ（ｔ） ∂ｔ ＝ － ｍ３ Ｎ － ｍ３Πｉ ＋ ２ｍ３Πｉ ＝ ｍ３Πｉ － ｍ３ Ｎ （４） 综合式（２） ～ （４），得到演化模型 ｋｉ变化率方程为 ∂ｋｉ（ｔ） ∂ｔ ＝ ｍ１Πｉ ＋ ２ｍ２Πｉ ＋ ｍ３Πｉ － ｍ３ Ｎ （５） 由网络节点平均度数为 ２（ｍ１ ＋ ｍ２ ），并且对于 充分大的 ｔ，ｔ 时刻节点总数 Ｎ 为 ｍ０ ＋ ｔ ≈ ｔ ，因此网 络节点总度数 ∑ ｊ ｋｊ ≈ ２（ｍ１ ＋ ｍ２ ）ｔ ，得 ∂ｋｉ（ｔ） ∂ｔ ＝ （ｍ１ ＋ ２ｍ２ ＋ ｍ３ ）Πｉ － ｍ３ Ｎ ≈ （ｍ１ ＋ ２ｍ２ ＋ ｍ３ ）ｋｉ（ｔ） ２（ｍ１ ＋ ｍ２ ）ｔ － ｍ３ ｔ （６） 用变量分离法解此一阶微分方程可得 ｋｉ（ｔ） ＝ ２ｍ３（ｍ１ ＋ ｍ２ ） ｍ１ ＋ ２ｍ２ ＋ ｍ３ ＋ Ｃｔ ｍ１ ＋２ｍ２ ＋ｍ３ ２（ｍ１ ＋ｍ２ ） （７） 设节点 ｉ 是在 ｔ ｉ时刻进入网络，则有初始条件 ｋｉ（ｔ ｉ） ＝ ｍ１ ，结合式（７）可得 ｋｉ（ｔ） ＝ ２ｍ３（ｍ１ ＋ ｍ２ ） ｍ１ ＋ ２ｍ２ ＋ ｍ３ ＋ ｍ１ － ２ｍ３（ｍ１ ＋ ｍ２ ） ｍ１ ＋ ２ｍ２ ＋ ｍ３ é ë ê ê ù û ú ú （ ｔ ｔ ｉ ） ｍ１ ＋ ２ｍ２ ＋ ｍ３ ２（ｍ１ ＋ ｍ２ ） 网络中节点 ｉ 的度 ｋｉ（ｔ）小于 ｋ 的概率为 Ｐ（ｋｉ（ｔ） ＜ ｋ） ＝ Ｐ（ ２ｍ３（ｍ１ ＋ ｍ２ ） ｍ１ ＋ ２ｍ２ ＋ ｍ３ ＋ ｍ１ － ２ｍ３（ｍ１ ＋ ｍ２ ） ｍ１ ＋ ２ｍ２ ＋ ｍ３ é ë ê ê ù û ú ú （ ｔ ｔ ｉ ） ｍ１ ＋２ｍ２ ＋ｍ３ ２（ｍ１ ＋ｍ２ ） ＝ Ｐ（ｔ ｉ ＞ ｍ１ － ａ ｋ － ａ é ë ê ê ù û ú ú ｍ１ ＋２ｍ２ ＋ｍ３ ２（ｍ１ ＋ｍ２ ） ｔ） （８） 式中： ａ ＝ ２ｍ３（ｍ１ ＋ ｍ２ ） ｍ１ ＋ ２ｍ２ ＋ ｍ３ 模型假设节点是以相对时 间间隔进入网络的，因此节点 ｉ 的到达时间 ｔ ｉ具有 常数概率密度： Ｐ（ｔ ｉ） ＝ １ ／ Ｎ ≈ １ ／ ｔ 故有 Ｐ（ｔ ｉ ＞ ｍ１ － ａ ｋ － ａ é ë ê ê ù û ú ú ２（ｍ１ ＋ｍ２ ） ｍ１ ＋２ｍ２ ＋ｍ３ ｔ） ＝ １ － Ｐ（ｔ ｉ ≤ ｍ１ － ａ ｋ － ａ é ë ê ê ù û ú ú ２（ｍ１ ＋ｍ２ ） ｍ１ ＋２ｍ２ ＋ｍ３ ｔ） ≈ １ － ｍ１ － ａ ｋ － ａ é ë ê ê ù û ú ú ２（ｍ１ ＋ｍ２ ） ｍ１ ＋２ｍ２ ＋ｍ３ 假设时间 ｔ → ∞ 时，网络节点的度具有稳态分 布 Ｐ（ｋ）： Ｐ（ｋ） ＝ ∂Ｐ（ｋｉ（ｔ） ＜ ｋ） ∂ｋ ＝ ２（ｍ１ ＋ ｍ２ ） ｍ１ ＋ ２ｍ２ ＋ ｍ３ （ｍ１ － ａ） ２（ｍ１ ＋ｍ２ ） ｍ１ ＋２ｍ２ ＋ｍ３（ ｋ － ａ） － γ（９） 则度分布指数 γ ＝ ２ － ｍ３ － ｍ１ ｍ１ ＋ ２ｍ２ ＋ ｍ３ （１０） 上述理论分析表明，由本演化模型生成的网络 具有无标度特性，且通过调整 ｍ１ 、ｍ２ 和 ｍ３ 的取值， 能 得 到 不 同 的 分 布 指 数。 由 － １ ≤ ｍ３ － ｍ１ ｍ１ ＋ ２ｍ２ ＋ ｍ３ ＜ １，可得 １ ＜ γ ≤ ３。 当 ｍ２ ＝ ｍ３ ＝ ０ 时， γ ＝ ３，无标度 ＢＡ 模型成为本演化模型的一个 特例。 现有研究表明，绝大多数无标度网络的幂指 数都在 １～３，因此本演化模型具有广泛的适用性。 ３ 仿真实验和讨论 仿真实验分为 ２ 部分：１）采用 ＭＡＴＬＡＢ 软件开 发仿真程序，通过程序运行的结果来分析演化模型的 度统计特性、相关参数的影响以及理论分析的准确 性；２）通过 ＭＡＴＬＡＢ 软件分析真实社交网络数据的 度统计特性，观察演化模型理论分析值的模拟程度。 分析度分布指数 γ 的表达式（１０），可以看到 ３ 个参数的作用各不相同，ｍ１和 ｍ３决定 γ 取值大于 ２ 或者小于 ２，ｍ２则只影响值的大小，而 ｍ１和 ｍ２又影 响网络的节点规模和平均度数。 图 １、２、３ 分别显示 了 １ ５００ 节点网络演化模型在不同参数取值下的度 分布情况，演化网络度分布呈现幂率特征，且根据参 数取值的不同在 １～３ 之间变化，图中直线由度分布 理论表达式（９）近似给出。 图 １ 演化模型度分布（ｍ１ ＝ ２，ｍ２ ＝ １，ｍ３ ＝ ０） Ｆｉｇ．１ Ｄｅｇｒｅｅ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｅｖｏｌｕｔｉｏｎ ｍｏｄｅｌ（ｍ１ ＝ ２ ， ｍ２ ＝ １ ，ｍ３ ＝ ０） 第 ６ 期 王景丽，等：复杂网络中的在线社交网络演化模型 ·９５１·
.952. 智能系统学报 第10卷 可以看到，在m,和m2值不变的条件下，m3值越大， 模型的度分布幂率在2~3，不能较好地表征博客网 无标度特性越大。图4则显示在m,和m值不变的 络的度分布特征。图中拟合直线幂率值为1.4，由本 条件下，m,值变化对度分布幂率的影响，分布幂率 文表达式(9)直接给出，其中参数取值m,=2、m2= 值随着m,值变大而增大，但逐步接近某固定值，由 0、m3=8,实际上有很多种参数取值方案，这里只给 式(10)可知，此值为2。 出其中一种仅用于说明效果。通过调整参数，演化 10° 模型能较好地模拟美国政治家博客用户网络的度分 10 布特征。 10° 10 10 2=1.9 10 是10 1010 10 a 10 10 1=1.4 10 图2演化模型度分布(m1=2,m2=1,m3=3) Fig.2 Degree distribution of evolution model(m=2, 1010 10 10 10 m2=1,m3=3) 图5政治家博客用户网络度分布幂率 10°i Fig.5 Power-law degree distribution network of Polit- 10 ical blogs 10 =1.6 图6显示维基选举社交网络[1度分布情况，该 10 网络节点为维基用户，边表示为用户间的选举行为， 10 包含7000多节点。该网络度分布幂率也在1~2之 1010 10 间，传统模型不能较准确地表征。图中拟合直线幂 10 10 率值为1.5，由表达式(9)直接给出，其中参数取值 图3演化模型度分布(m,=2,m2=1,m3=6) m1=2、m2=0、m3=6,这里同样只给出一种取值方案 Fig.3 Degree distribution of evolution model (m=2, 用于说明效果。可以看到，通过调整参数，演化模型 m2=1,m3=6)】 能较好地模拟维基选举社交网络的度分布特征。 10f 10 10 m,=0 10 m2= 10 …m= …m,=8 是10i 10 10 10 y-1.5 1 10 10 10 10 10 10 0 10 10 10 图6维基选举社交网络度分布幂率 Fig.6 Power-law degree distribution of Wiki vote 图4m,取不同值时的度分布变化(m,=2,m,=8) Fig.4 Degree distribution changes according to differ- 结束语 ent values of m,(m =2,m=8) 在线社交网络作为一种普遍存在的社会网络， 采用真实在线社交网络与本文演化模型的度分 已经引起广泛的研究并证实其具有无标度特性，但 布进行对比分析。图5显示一个美国政治家博客用 对其结构演化模型的研究相对较少。本文提出一种 户网络)的度分布情况，该网络节点为博客网页， 基于内增长、外增长及内部边更替的在线社交网络 边表示为网页间的超链接，包含1224个节点和 演化模型，其优先连接机制具有强化高连接度节点 16714条无向边。可以看到，博客网页网络的度分 间的连接倾向的特征。理论分析和实验表明，该模 布幂率在1~2，传统很多演化模型如BA及其变型 型具有无标度特性，且通过调整参数的不同取值，度
可以看到，在 ｍ１和 ｍ２值不变的条件下，ｍ３值越大， 无标度特性越大。 图 ４ 则显示在 ｍ１和 ｍ３值不变的 条件下，ｍ２值变化对度分布幂率的影响，分布幂率 值随着 ｍ２值变大而增大，但逐步接近某固定值，由 式（１０）可知，此值为 ２。 图 ２ 演化模型度分布（ｍ１ ＝ ２，ｍ２ ＝ １，ｍ３ ＝ ３） Ｆｉｇ．２ Ｄｅｇｒｅｅ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｅｖｏｌｕｔｉｏｎ ｍｏｄｅｌ（ｍ１ ＝ ２， ｍ２ ＝ １，ｍ３ ＝ ３） 图 ３ 演化模型度分布（ｍ１ ＝ ２，ｍ２ ＝ １，ｍ３ ＝ ６） Ｆｉｇ．３ Ｄｅｇｒｅｅ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｅｖｏｌｕｔｉｏｎ ｍｏｄｅｌ（ｍ１ ＝ ２， ｍ２ ＝ １，ｍ３ ＝ ６） 图 ４ ｍ２取不同值时的度分布变化（ｍ１ ＝ ２，ｍ３ ＝ ８） Ｆｉｇ．４ Ｄｅｇｒｅｅ ｄｉｓｔｒｉｂｕｔｉｏｎ ｃｈａｎｇｅｓ ａｃｃｏｒｄｉｎｇ ｔｏ ｄｉｆｆｅｒ⁃ ｅｎｔ ｖａｌｕｅｓ ｏｆ ｍ２（ｍ１ ＝ ２，ｍ３ ＝ ８） 采用真实在线社交网络与本文演化模型的度分 布进行对比分析。 图 ５ 显示一个美国政治家博客用 户网络［１５］的度分布情况，该网络节点为博客网页， 边表示为网页间的超链接，包含 １ ２２４ 个节点和 １６ ７１４条无向边。 可以看到，博客网页网络的度分 布幂率在 １～ ２，传统很多演化模型如 ＢＡ 及其变型 模型的度分布幂率在 ２ ～ ３，不能较好地表征博客网 络的度分布特征。 图中拟合直线幂率值为 １．４，由本 文表达式（９） 直接给出，其中参数取值ｍ１ ＝ ２、ｍ２ ＝ ０、ｍ３ ＝ ８，实际上有很多种参数取值方案，这里只给 出其中一种仅用于说明效果。 通过调整参数，演化 模型能较好地模拟美国政治家博客用户网络的度分 布特征。 图 ５ 政治家博客用户网络度分布幂率 Ｆｉｇ．５ Ｐｏｗｅｒ⁃ｌａｗ ｄｅｇｒｅｅ ｄｉｓｔｒｉｂｕｔｉｏｎ ｎｅｔｗｏｒｋ ｏｆ Ｐｏｌｉｔ⁃ ｉｃａｌ ｂｌｏｇｓ 图 ６ 显示维基选举社交网络［１５］度分布情况，该 网络节点为维基用户，边表示为用户间的选举行为， 包含 ７ ０００ 多节点。 该网络度分布幂率也在 １～２ 之 间，传统模型不能较准确地表征。 图中拟合直线幂 率值为 １．５，由表达式（９）直接给出，其中参数取值 ｍ１ ＝ ２、ｍ２ ＝ ０、ｍ３ ＝ ６，这里同样只给出一种取值方案 用于说明效果。 可以看到，通过调整参数，演化模型 能较好地模拟维基选举社交网络的度分布特征。 图 ６ 维基选举社交网络度分布幂率 Ｆｉｇ．６ Ｐｏｗｅｒ⁃ｌａｗ ｄｅｇｒｅｅ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ Ｗｉｋｉ ｖｏｔｅ ４ 结束语 在线社交网络作为一种普遍存在的社会网络， 已经引起广泛的研究并证实其具有无标度特性，但 对其结构演化模型的研究相对较少。 本文提出一种 基于内增长、外增长及内部边更替的在线社交网络 演化模型，其优先连接机制具有强化高连接度节点 间的连接倾向的特征。 理论分析和实验表明，该模 型具有无标度特性，且通过调整参数的不同取值，度 ·９５２· 智 能 系 统 学 报 第 １０ 卷
第6期 王景丽，等：复杂网络中的在线社交网络演化模型 ·953. 分布幂率指数在1~3，具有普遍适用性。通过和真 2001,98(2):404-409 实在线社交网络结构的模拟分析，本文提出的演化 [10]MYERS C R.Software systems as complex networks:struc- 模型能较好地反映出在线社交网络的度分布特征， ture,function,and evolvability of software collaboration 且能够刻画不同类型的社交网络，具有较强的实用 graphs J].Physical Review E,2003,68 (4Pt2): 意义。 046116. [11 ]JEONG H,MASON S P,BARABASI A L,et al.Lethality 本文演化模型是基于最基本的无向无权网络， and centrality in protein networks[J].Nature,2001,411 下一步的工作考虑扩展到复杂的多属性异构网络， (6833)：41-42. 这些属性包括有向、权值、节点能力等。借助因素空 [12]王亚奇，王静，杨海滨.基于复杂网络理论的微博用户 间理论[6]，将多属性异构网络映射成因素空间网 关系网络演化模型研究[J].物理学报，2014,63(20)： 络，网络节点映射成因素空间对象，使其更加贴近于 208902. 现实网络，通过权变、拓扑结构、动态时空等因素空 WANG Yaqi,WANG Jing,YANG Haibin.An evolution 间理论工具研究演化网络模型和实际在线社会网络 model of microblog user relationship networks based on 的生成、发展及其特征。 complex network theory J].Acta Physica Sinica,2014, 63(20):208902. 参考文献： [13]刘浩然，尹文晓，董明如，等.一种强容侵能力的无线 传感器网络无标度拓扑模型研究[J].物理学报，2014， [1]WATTS D J,STROGATZ S H.Collective dynamics of 63(9):090503. small-world'networks [J].Nature,1998,393 (6684): LIU Haoran,YIN Wenxiao,DONG Mingru,et al.Study 440-442. on the scale-free topology model with strong intrusion-toler- [2]BARABASI A L,ALBERT R.Emergence of scaling in ran- ance ability in wireless sensor networks[].Acta Physica dom networks[J].Science,1999,286(5439):509-512. Sinica,2014,63(9):090503. [3]FALOUTSOS M,FALOUTSOS P,FALOUTSOS C.On pow- [14]SOLE R V,PASTOR-SATORRAS R,SMITH E,et al.A er-law relationships of the Internet topology[J].ACM SIG- model of large-scale proteome evolution[J].Advances in COMM Computer Communication Review Homepage,1999, Complex Systems,2002,5(1):43-54. 29(4):251-262. [15]维基选举社交网络[0L/EB].[2014-12-21].http:/ [4]ALBERT R,BARABASI A L.Topology of evolving net- works:local events and universality[J].Physical Review www.linkprediction.org/index.php/link/resource/data. [16]汪培庄.因素空间与因素库[J].辽宁工程技术大学学 Letters2000,85(24):5234-5237. 报：自然科学版，2013,32(10)：1297-1304. [5]BU T,TOWSLEY D.On distinguishing between Internet WANG Peizhuang.Factor spaces and factor data-bases[J]. power law topology generators[C]//Proceedings of INFO- Journal of Liaoning Technical University:Natural Science, COM 2002.Twenty-First Annual Joint Conference of the 2013,32(10):1297-1304. IEEE Computer and Communications Societies.New York, [17]汪培庄.因素空间与数据科学[J】.辽宁工程技术大学 NY:EEE,2002,2:638-647. 学报：自然科学版，2015,34(2)：273-280. [6]PARK S T,PENNOCK D M,GILES C L.Comparing static WANG Peizhuang.Factor spaces and data science [J]. and dynamic measurements and models of the Internet's as Journal of Liaoning Technical University:Natural Science, topology[C]//Proceedings of the 23rd Annual Joint Confer- 2015,34(2):273-280. ence of the IEEE Computer and Communications Societies. 作者简介： Hong Kong:EEE,2004,3:1616-1627. 王景丽，女，1981年生，讲师。主要 [7]CHEN Guangrong,FAN Zhenping,LI Xiang.Modeling the 研究方向为复杂网络。 complex Internet topology[C]//KOCAREV L,VATTAY G. Complex Dynamics in Communication Networks.Berlin Hei- delberg:Springer,2005. [8]田思，李慧嘉，赵岳.一种新型多局域世界网络模型分 析J].计算机应用研究，2013,30(3)：869-872. 许立波，男，1976年生，讲师，博士。 TIAN Si,LI Huijia,ZHAO Yue.Analysis of novel multi-lo- 主要研究方向为复杂网络、overlay网 cal world network model[J].Application Research of Com- 络。 puters,.2013,30(3):869-872. 9 NEWMAN M E J.The structure of scientific collaboration networks[C].Proceedings of National Academy Sciences
分布幂率指数在 １ ～ ３，具有普遍适用性。 通过和真 实在线社交网络结构的模拟分析，本文提出的演化 模型能较好地反映出在线社交网络的度分布特征， 且能够刻画不同类型的社交网络，具有较强的实用 意义。 本文演化模型是基于最基本的无向无权网络， 下一步的工作考虑扩展到复杂的多属性异构网络， 这些属性包括有向、权值、节点能力等。 借助因素空 间理论［１６⁃１７］ ，将多属性异构网络映射成因素空间网 络，网络节点映射成因素空间对象，使其更加贴近于 现实网络，通过权变、拓扑结构、动态时空等因素空 间理论工具研究演化网络模型和实际在线社会网络 的生成、发展及其特征。 参考文献： ［１］ ＷＡＴＴＳ Ｄ Ｊ， ＳＴＲＯＧＡＴＺ Ｓ Ｈ． Ｃｏｌｌｅｃｔｉｖｅ ｄｙｎａｍｉｃｓ ｏｆ ＇ ｓｍａｌｌ⁃ｗｏｒｌｄ′ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｎａｔｕｒｅ， １９９８， ３９３ （ ６６８４）： ４４０⁃４４２． ［２］ＢＡＲＡＢＡＳＩ Ａ Ｌ， ＡＬＢＥＲＴ Ｒ． Ｅｍｅｒｇｅｎｃｅ ｏｆ ｓｃａｌｉｎｇ ｉｎ ｒａｎ⁃ ｄｏｍ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｓｃｉｅｎｃｅ， １９９９， ２８６（５４３９）： ５０９⁃５１２． ［ ３］ＦＡＬＯＵＴＳＯＳ Ｍ， ＦＡＬＯＵＴＳＯＳ Ｐ， ＦＡＬＯＵＴＳＯＳ Ｃ． Ｏｎ ｐｏｗ⁃ ｅｒ⁃ｌａｗ ｒｅｌａｔｉｏｎｓｈｉｐｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎｅｔ ｔｏｐｏｌｏｇｙ［ Ｊ］． ＡＣＭ ＳＩＧ⁃ ＣＯＭＭ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｒｅｖｉｅｗ Ｈｏｍｅｐａｇｅ， １９９９， ２９（４）： ２５１⁃２６２． ［４］ ＡＬＢＥＲＴ Ｒ， ＢＡＲＡＢＡＳＩ Ａ Ｌ． Ｔｏｐｏｌｏｇｙ ｏｆ ｅｖｏｌｖｉｎｇ ｎｅｔ⁃ ｗｏｒｋｓ： ｌｏｃａｌ ｅｖｅｎｔｓ ａｎｄ ｕｎｉｖｅｒｓａｌｉｔｙ ［ Ｊ］． Ｐｈｙｓｉｃａｌ Ｒｅｖｉｅｗ Ｌｅｔｔｅｒｓ ２０００， ８５（２４）： ５２３４⁃５２３７． ［５］ ＢＵ Ｔ， ＴＯＷＳＬＥＹ Ｄ． Ｏｎ ｄｉｓｔｉｎｇｕｉｓｈｉｎｇ ｂｅｔｗｅｅｎ Ｉｎｔｅｒｎｅｔ ｐｏｗｅｒ ｌａｗ ｔｏｐｏｌｏｇｙ ｇｅｎｅｒａｔｏｒｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＮＦＯ⁃ ＣＯＭ ２００２． Ｔｗｅｎｔｙ⁃Ｆｉｒｓｔ Ａｎｎｕａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｆ ｔｈｅ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｏｃｉｅｔｉｅｓ． Ｎｅｗ Ｙｏｒｋ， ＮＹ： ＩＥＥＥ， ２００２， ２： ６３８⁃６４７． ［６］ＰＡＲＫ Ｓ Ｔ， ＰＥＮＮＯＣＫ Ｄ Ｍ， ＧＩＬＥＳ Ｃ Ｌ． Ｃｏｍｐａｒｉｎｇ ｓｔａｔｉｃ ａｎｄ ｄｙｎａｍｉｃ ｍｅａｓｕｒｅｍｅｎｔｓ ａｎｄ ｍｏｄｅｌｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎｅｔ＇ｓ ａｓ ｔｏｐｏｌｏｇｙ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２３ｒｄ Ａｎｎｕａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒ⁃ ｅｎｃｅ ｏｆ ｔｈｅ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｏｃｉｅｔｉｅｓ． Ｈｏｎｇ Ｋｏｎｇ： ＩＥＥＥ， ２００４， ３： １６１６⁃１６２７． ［７］ＣＨＥＮ Ｇｕａｎｇｒｏｎｇ， ＦＡＮ Ｚｈｅｎｐｉｎｇ， ＬＩ Ｘｉａｎｇ． Ｍｏｄｅｌｉｎｇ ｔｈｅ ｃｏｍｐｌｅｘ Ｉｎｔｅｒｎｅｔ ｔｏｐｏｌｏｇｙ［Ｃ］ ／ ／ ＫＯＣＡＲＥＶ Ｌ， ＶＡＴＴＡＹ Ｇ． Ｃｏｍｐｌｅｘ Ｄｙｎａｍｉｃｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｎｅｔｗｏｒｋｓ． Ｂｅｒｌｉｎ Ｈｅｉ⁃ ｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， ２００５． ［８］田思， 李慧嘉， 赵岳． 一种新型多局域世界网络模型分 析［Ｊ］． 计算机应用研究， ２０１３， ３０（３）： ８６９⁃８７２． ＴＩＡＮ Ｓｉ， ＬＩ Ｈｕｉｊｉａ， ＺＨＡＯ Ｙｕｅ． Ａｎａｌｙｓｉｓ ｏｆ ｎｏｖｅｌ ｍｕｌｔｉ⁃ｌｏ⁃ ｃａｌ ｗｏｒｌｄ ｎｅｔｗｏｒｋ ｍｏｄｅｌ［Ｊ］． Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍ⁃ ｐｕｔｅｒｓ， ２０１３， ３０（３）： ８６９⁃８７２． ［９］ ＮＥＷＭＡＮ Ｍ Ｅ Ｊ． Ｔｈｅ ｓｔｒｕｃｔｕｒｅ ｏｆ ｓｃｉｅｎｔｉｆｉｃ ｃｏｌｌａｂｏｒａｔｉｏｎ ｎｅｔｗｏｒｋｓ［Ｃ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｎａｔｉｏｎａｌ Ａｃａｄｅｍｙ Ｓｃｉｅｎｃｅｓ， ２００１， ９８（２）： ４０４⁃４０９． ［１０］ＭＹＥＲＳ Ｃ Ｒ． Ｓｏｆｔｗａｒｅ ｓｙｓｔｅｍｓ ａｓ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ： ｓｔｒｕｃ⁃ ｔｕｒｅ， ｆｕｎｃｔｉｏｎ， ａｎｄ ｅｖｏｌｖａｂｉｌｉｔｙ ｏｆ ｓｏｆｔｗａｒｅ ｃｏｌｌａｂｏｒａｔｉｏｎ ｇｒａｐｈｓ ［ Ｊ ］． Ｐｈｙｓｉｃａｌ Ｒｅｖｉｅｗ Ｅ， ２００３， ６８ （ ４Ｐｔ２ ）： ０４６１１６． ［１１］ＪＥＯＮＧ Ｈ， ＭＡＳＯＮ Ｓ Ｐ， ＢＡＲＡＢＡＳＩ Ａ Ｌ， ｅｔ ａｌ． Ｌｅｔｈａｌｉｔｙ ａｎｄ ｃｅｎｔｒａｌｉｔｙ ｉｎ ｐｒｏｔｅｉｎ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｎａｔｕｒｅ， ２００１， ４１１ （６８３３）： ４１⁃４２． ［１２］王亚奇， 王静， 杨海滨． 基于复杂网络理论的微博用户 关系网络演化模型研究［Ｊ］． 物理学报， ２０１４， ６３（２０）： ２０８９０２． ＷＡＮＧ Ｙａｑｉ， ＷＡＮＧ Ｊｉｎｇ， ＹＡＮＧ Ｈａｉｂｉｎ． Ａｎ ｅｖｏｌｕｔｉｏｎ ｍｏｄｅｌ ｏｆ ｍｉｃｒｏｂｌｏｇ ｕｓｅｒ ｒｅｌａｔｉｏｎｓｈｉｐ ｎｅｔｗｏｒｋｓ ｂａｓｅｄ ｏｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ ｔｈｅｏｒｙ ［ Ｊ］． Ａｃｔａ Ｐｈｙｓｉｃａ Ｓｉｎｉｃａ， ２０１４， ６３（２０）： ２０８９０２． ［１３］刘浩然， 尹文晓， 董明如， 等． 一种强容侵能力的无线 传感器网络无标度拓扑模型研究［Ｊ］． 物理学报， ２０１４， ６３（９）： ０９０５０３． ＬＩＵ Ｈａｏｒａｎ， ＹＩＮ Ｗｅｎｘｉａｏ， ＤＯＮＧ Ｍｉｎｇｒｕ， ｅｔ ａｌ． Ｓｔｕｄｙ ｏｎ ｔｈｅ ｓｃａｌｅ⁃ｆｒｅｅ ｔｏｐｏｌｏｇｙ ｍｏｄｅｌ ｗｉｔｈ ｓｔｒｏｎｇ ｉｎｔｒｕｓｉｏｎ⁃ｔｏｌｅｒ⁃ ａｎｃｅ ａｂｉｌｉｔｙ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ａｃｔａ Ｐｈｙｓｉｃａ Ｓｉｎｉｃａ， ２０１４， ６３（９）： ０９０５０３． ［１４］ＳＯＬＥ Ｒ Ｖ， ＰＡＳＴＯＲ⁃ＳＡＴＯＲＲＡＳ Ｒ， ＳＭＩＴＨ Ｅ， ｅｔ ａｌ． Ａ ｍｏｄｅｌ ｏｆ ｌａｒｇｅ⁃ｓｃａｌｅ ｐｒｏｔｅｏｍｅ ｅｖｏｌｕｔｉｏｎ［ Ｊ］． Ａｄｖａｎｃｅｓ ｉｎ Ｃｏｍｐｌｅｘ Ｓｙｓｔｅｍｓ， ２００２， ５（１）： ４３⁃５４． ［１５］ 维基 选 举 社 交 网 络 ［ ＯＬ／ ＥＢ］． ［ ２０１４⁃１２⁃２１］． ｈｔｔｐ： ／ ／ ｗｗｗ．ｌｉｎｋｐｒｅｄｉｃｔｉｏｎ．ｏｒｇ ／ ｉｎｄｅｘ．ｐｈｐ ／ ｌｉｎｋ ／ ｒｅｓｏｕｒｃｅ ／ ｄａｔａ． ［１６］汪培庄． 因素空间与因素库［ Ｊ］． 辽宁工程技术大学学 报： 自然科学版， ２０１３， ３２（１０）： １２９７⁃１３０４． ＷＡＮＧ Ｐｅｉｚｈｕａｎｇ． Ｆａｃｔｏｒ ｓｐａｃｅｓ ａｎｄ ｆａｃｔｏｒ ｄａｔａ⁃ｂａｓｅｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｌｉａｏｎｉｎｇ Ｔｅｃｈｎｉｃａｌ Ｕｎｉｖｅｒｓｉｔｙ： Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ， ２０１３， ３２（１０）： １２９７⁃１３０４． ［１７］汪培庄． 因素空间与数据科学［ Ｊ］． 辽宁工程技术大学 学报： 自然科学版， ２０１５， ３４（２）： ２７３⁃２８０． ＷＡＮＧ Ｐｅｉｚｈｕａｎｇ． Ｆａｃｔｏｒ ｓｐａｃｅｓ ａｎｄ ｄａｔａ ｓｃｉｅｎｃｅ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｌｉａｏｎｉｎｇ Ｔｅｃｈｎｉｃａｌ Ｕｎｉｖｅｒｓｉｔｙ： Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ， ２０１５， ３４（２）： ２７３⁃２８０． 作者简介： 王景丽，女，１９８１ 年生，讲师。 主要 研究方向为复杂网络。 许立波，男，１９７６ 年生，讲师，博士。 主要研究方向为复杂网络、 ｏｖｅｒｌａｙ 网 络。 第 ６ 期 王景丽，等：复杂网络中的在线社交网络演化模型 ·９５３·