网络重要节点排序方法综述_任晓龙网络重要节点排序方法综述_任晓龙.pdf

2014 年 第 59 卷 第 13 期： 1175 ~ 1197 《中国科学》杂志社 特邀评述 SCIENCE CHINA PRESS 网络重要节点排序方法综述 * 任晓龙, 吕琳媛 杭州师范大学阿里巴巴复杂科学研究中心, 杭州310036 * 联系人, E-mail: linyuan.lv@ 2013-11-21 收稿, 2014-02-25 接受, 2014-04-04 网络版发表 国家自然科学基金、杭州师范大学科研启动基金和CCF-腾讯科研基金资助 摘要 复杂网络的重要节点是指相比网络其他节点而言, 能够在更大程度上影响网络的结构与 关键词 功能的一些特殊节点. 近年来, 节点重要性排序研究受到越来越广泛的关注, 不仅因为其重大 复杂网络 的理论研究意义, 更因为其广泛的实际应用价值. 由于应用领域极广, 且不同类型的网络中节 重要节点 点的重要性评价方法各有侧重, 学者们从不同的实际问题出发设计出各种各样的方法. 本文系 节点排序 节点中心性 统地综述了复杂网络领域具有代表性的30 余种重要节点挖掘方法, 并将其分为四大类, 详细比 传播模型 较各种方法的计算思路、应用场景和优缺点. 在此基础上, 本文分析了重要节点排序研究现存的 一些问题, 并展望了若干重要的开放性问题. 食物链中哪些物种对整个生态的影响最大? 法能够帮助我们更好地理解这些复杂系统的特征, “种子短信”发给哪些手机用户可以获得更多的 并对其进行更好地预测和控制. 如上述的大停电事 转发? 故归根到底是“ 网络相继攻击的脆弱性” 问题. 如果 全球经济体系中哪些国家或地区对于体系的健 我们能够事先对这个电力网络的结构有所了解, 并 康发展至关重要? 找到关键的地区采取预防措施, 就可能避免如此巨 当传染病来临的时候, 我们应该采取何种接种 额的经济损失. 这里最核心的问题就是如何识别这 免疫策略来避免其大规模爆发? 些重要的节点. 所谓的重要节点是指相比网络其他 高价雇佣微博大号做新产品的推广和营销真的 节点而言能够在更大程度上影响网络的结构与功能 有用吗? 如果有用, 又如何找到合适的达人? 的一些特殊节点. 这里的网络结构包括度分布、平均 为什么俄亥俄州克利夫兰市的几条烧断的高压 距离、连通性、聚类系数、度相关性等, 网络功能涉 线能够造成北美大停电事故, 导致数百亿美元的损 及网络的抗毁性、传播、同步、控制等[1]. 重要节点 失? 一般数量非常少, 但其影响却可以快速地波及到网 借助网络科学的发展, 对于这些问题, 如今我们 络中大部分节点[2]. 例如, 在对一个无标度网络的蓄 已经有了一些定量化的描述和解决办法. 实际上, 几 意攻击中, 少量最重要节点被攻击就会导致整个网 乎所有的复杂系统( 比如社会、生物、信息、技术、 络瓦解[3,4]; 微博中最有影响力的几个用户所发的微 交通运输系统)都可以自然地表示为网络. 其中, 节 博很快就能传遍整个网络[5]; 仅仅 1%的公司却控制