复杂网络中节点重要性排序的的研究进展.pdfVIP

物理学报 Acta Phys. Sin. Vol. 62, No. 17 (2013) 178901 前沿领域综述 复杂网络中节点重要性排序的研究进展* † 刘建国 任卓明 郭强 汪秉宏 ( 上海理工大学复杂系统科学研究中心, 上海 200093 ) ( 2013 年4 月11 日收到; 2013 年5 月8 日收到修改稿) 如何用定量分析的方法识别超大规模网络中哪些节点最重要, 或者评价某个节点相对于其他一个或多个节点 的重要程度, 这是复杂网络研究中亟待解决的重要问题之一. 本文分别从网络结构和传播动力学的角度, 对现有的复 杂网络中节点重要性排序方法进行了系统的回顾, 总结了节点重要性排序方法的必威体育精装版研究进展, 并对不同的节点重 要性排序指标的优缺点以及适用环境进行了分析, 最后指出了这一领域中几个有待解决的问题及可能的发展方向. 关键词: 复杂网络, 节点重要性, 网络结构, 传播动力学 PACS: 89.75.Hc, 89.75.Fb DOI: 10.7498/aps.62.178901 状, 从基于网络拓扑结构和基于节点属性两个方面 1 引言 总结了现有评价节点重要性的模型和方法. 然而 近几年有不少学者已从新的视角研究网络节点重 伴随着信息技术的迅猛发展, 人类的社会活动 16 要性排序, 例如Kitsak 等人 于2010 年首次提出 日趋网络化. 我们的生活被各种网络包围着 1−3 , 了节点重要性依赖于其在整个网络中的位置的思 例如与他人交流的在线社交网络、通信网络、科 想, 并且利用K-核分解获得了比度、介数更为准 研合作网络; 与生活密切相关的因特网、交通网 确的节点重要性排序指标. 在短短两年半内该文的 络、电力网络; 与人自身相关的新陈代谢网络、神 Google Scholar 的引用次数已高达170 余次. 因此 经网络、基因调控网络等等. 研究者们通过收集不 有必要从不同角度总结目前的研究进展, 并对未来 同复杂系统的数据, 分析网络的统计特征, 进一步 可能的研究方向进行探讨. 认识网络的动力学行为4−6 . 然而这些网络的结构 本文简要地回顾了网络节点重要性排序的研 非常复杂, 而且网络数据规模也越来越庞大 7−9 . 究进展. 我们首先介绍了基于网络结构的节点重 例如Facebook 拥有超过 10 亿用户, 腾讯即时通讯 要性排序度量指标, 这类指标主要从网络的局部属 工具 QQ 的注册用户超过 10 亿, 活跃用户超过 性、全局属性、网络的位置和随机游走等四个方 7 亿, 因特网具有超过万亿的统一资源定位符 面展开, 同时对这些方法的优缺点及适用范围进行 (URL), 大脑神经元网络有数百亿节点. 如何用定量 了分析; 然后介绍了传播动力学与节点重要性度量 分析的方法度量大规模网络中节点重要程度是复 ; 指标的关系 最后在总结和展望部分指出了当前面 杂网络研究中亟待解决的重要问题之一10−12 . 临的问题和可能的发展方向. 随着网络科学的蓬勃发展, 节点重要性的研究