第11卷第5期 智能系统学报 Vol.11 No.5 2016年10月 CAAI Transactions on Intelligent Systems 0ct.2016 D0I:10.11992/is.201601024 网络出版地址：htp:/ww.cnki.net/kcms/detail/23.1538.TP.20160824.0929.014.html 基于度和聚类系数的中国航空网络重要性节点分析 闫玲玲12，陈增强123，张青3 (1.南开大学计算机与控制工程学院，天津300350：2.南开大学智能机器人技术天津市重点实验室，天津300350： 3.中国民航大学理学院，天津300300) 摘要：运用度中心性、接近中心性、介数中心性、特征向量中心性和半局部中心性5种方法，对中国航空网络进行节 点重要性排序：对重要节点分别进行蓄意攻击和随机攻击，采用脆弱性指标验证排序方法的有效性，仿真结果表明 介数中心性能够更准确地刻画中国航空网络中节点的重要性；在航空网络的背景下，将节点的直接影响力和节点邻 居之间连接的紧密程度结合起来，提出了一种基于度和聚类系数的新指标，经中国航空网络实例验证，该指标的评 价准确性仅次于介数中心性，但是其时间复杂度比介数中心性低很多。 关键词：航空网络：节点重要性：度：聚类系数：复杂网络 中图分类号：N94文献标志码：A文章编号：1673-4785(2016)05-0586-08 中文引用格式：闫玲玲，陈增强，张青.基于度和聚类系数的中国航空网络重要性节点分析[J].智能系统学报，2016,11(5)：586 593. 英文引用格式：YAN Lingling,CHEN Zengqiang,ZHANG Qing.Analysis of Key Nodes in China's Aviation Network Based on the Degree Centrality Indicator and Clustering Coefficient[J].CAAI transactions on intelligent systems,2016,11(5):586-593. Analysis of key nodes in China's aviation network based on the degree centrality indicator and clustering coefficient YAN Lingling'2,CHEN Zengqiang'2.3,ZHANG Qing (1.College of Computer and Control Engineering,Nankai University,Tianjin 300350,China;2.Key Laboratory of Intelligent Robot- ics of Tianjin,Nankai University,Tianjin 300350,China;3.College of Science,Civil Aviation University of China,Tianjin 300300, China) Abstract:This paper determines the key nodes of China's aviation network based on degree centrality,closeness centrality,'betweenness'centrality,eigenvector centrality,semi-local centrality indicators,and then ranks these nodes in descending order of importance.Using a vulnerability index and reviewing risks from deliberate and ran- dom attack the effectiveness of the sorting methods is then evaluated.It is apparent from the corresponding vulnera- bility indices that the aviation network of China is most vulnerable to targeted attacks according to the betweenness centrality indicator.Moreover,based on the aviation network,this paper proposes a new evaluation method,which takes into account not only the number of neighbors,but also the clustering coefficient.Focusing on China's avia- tion network,the experimental results demonstrate that the evaluation accuracy of the new index ranks only second to the betweenness centrality,and is more efficient compared with betweenness centrality as regards time complexity. Keywords:aviation network;key nodes;degree;clustering coefficient;complex network 自20世纪初飞机问世以来，航空运输系统飞速 效、灵活的优势，尤其是在长距离运输和国际客运方 发展。与其他运输方式相比，航空运输具有及时、高 面的重要作用日益凸显[口。航空运输系统是一个 易受环境影响的开放的复杂系统，随着系统规模的 收稿日期：2016-01-15.网络出版日期：2016-08-24. 不断扩大，它在带给人们便利的同时也带来了一系 基金项目：国家自然科学基金项目(61573199)：天津自然科学基金项目 列的问题。航班延误已经成为人们司空见惯的现 (14 JCYBJC18700). 通信作者：闫玲玲.E-mail:yanlingling(@mail.nankai.eu.cm 象，于是，在自然灾害或人为因素导致航班不能正常第 １１ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．５ ２０１６ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０１０２４ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０８２４．０９２９．０１４．ｈｔｍｌ 基于度和聚类系数的中国航空网络重要性节点分析 闫玲玲１，２ ，陈增强１，２，３ ，张青３ （１．南开大学 计算机与控制工程学院，天津 ３００３５０； ２．南开大学 智能机器人技术天津市重点实验室，天津 ３００３５０； ３．中国民航大学 理学院， 天津 ３００３００） 摘 要：运用度中心性、接近中心性、介数中心性、特征向量中心性和半局部中心性 ５ 种方法，对中国航空网络进行节 点重要性排序；对重要节点分别进行蓄意攻击和随机攻击，采用脆弱性指标验证排序方法的有效性，仿真结果表明 介数中心性能够更准确地刻画中国航空网络中节点的重要性；在航空网络的背景下，将节点的直接影响力和节点邻 居之间连接的紧密程度结合起来，提出了一种基于度和聚类系数的新指标，经中国航空网络实例验证，该指标的评 价准确性仅次于介数中心性，但是其时间复杂度比介数中心性低很多。 关键词：航空网络；节点重要性；度；聚类系数；复杂网络 中图分类号：Ｎ９４ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０５⁃０５８６⁃０８ 中文引用格式：闫玲玲，陈增强，张青．基于度和聚类系数的中国航空网络重要性节点分析［ Ｊ］． 智能系统学报， ２０１６， １１（５）： ５８６⁃ ５９３． 英文引用格式：ＹＡＮ Ｌｉｎｇｌｉｎｇ，ＣＨＥＮ Ｚｅｎｇｑｉａｎｇ，ＺＨＡＮＧ Ｑｉｎｇ．Ａｎａｌｙｓｉｓ ｏｆ Ｋｅｙ Ｎｏｄｅｓ ｉｎ Ｃｈｉｎａ􀆳ｓ Ａｖｉａｔｉｏｎ Ｎｅｔｗｏｒｋ Ｂａｓｅｄ ｏｎ ｔｈｅ Ｄｅｇｒｅｅ Ｃｅｎｔｒａｌｉｔｙ Ｉｎｄｉｃａｔｏｒ ａｎｄ Ｃｌｕｓｔｅｒｉｎｇ Ｃｏｅｆｆｉｃｉｅｎｔ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（５）： ５８６⁃５９３． Ａｎａｌｙｓｉｓ ｏｆ ｋｅｙ ｎｏｄｅｓ ｉｎ Ｃｈｉｎａ􀆳ｓ ａｖｉａｔｉｏｎ ｎｅｔｗｏｒｋ ｂａｓｅｄ ｏｎ ｔｈｅ ｄｅｇｒｅｅ ｃｅｎｔｒａｌｉｔｙ ｉｎｄｉｃａｔｏｒ ａｎｄ ｃｌｕｓｔｅｒｉｎｇ ｃｏｅｆｆｉｃｉｅｎｔ ＹＡＮ Ｌｉｎｇｌｉｎｇ １，２ ， ＣＨＥＮ Ｚｅｎｇｑｉａｎｇ １，２，３ ， ＺＨＡＮＧ Ｑｉｎｇ ３ （１． Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｎｔｒｏｌ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｎａｎｋａｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｔｉａｎｊｉｎ ３００３５０， Ｃｈｉｎａ； ２． Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｒｏｂｏｔ⁃ ｉｃｓ ｏｆ Ｔｉａｎｊｉｎ， Ｎａｎｋａｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｔｉａｎｊｉｎ ３００３５０， Ｃｈｉｎａ； ３． Ｃｏｌｌｅｇｅ ｏｆ Ｓｃｉｅｎｃｅ， Ｃｉｖｉｌ Ａｖｉａｔｉｏｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃｈｉｎａ， Ｔｉａｎｊｉｎ ３００３００， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｄｅｔｅｒｍｉｎｅｓ ｔｈｅ ｋｅｙ ｎｏｄｅｓ ｏｆ Ｃｈｉｎａ’ ｓ ａｖｉａｔｉｏｎ ｎｅｔｗｏｒｋ ｂａｓｅｄ ｏｎ ｄｅｇｒｅｅ ｃｅｎｔｒａｌｉｔｙ， ｃｌｏｓｅｎｅｓｓ ｃｅｎｔｒａｌｉｔｙ， ‘ｂｅｔｗｅｅｎｎｅｓｓ’ ｃｅｎｔｒａｌｉｔｙ， ｅｉｇｅｎｖｅｃｔｏｒ ｃｅｎｔｒａｌｉｔｙ， ｓｅｍｉ⁃ｌｏｃａｌ ｃｅｎｔｒａｌｉｔｙ ｉｎｄｉｃａｔｏｒｓ， ａｎｄ ｔｈｅｎ ｒａｎｋｓ ｔｈｅｓｅ ｎｏｄｅｓ ｉｎ ｄｅｓｃｅｎｄｉｎｇ ｏｒｄｅｒ ｏｆ ｉｍｐｏｒｔａｎｃｅ． Ｕｓｉｎｇ ａ ｖｕｌｎｅｒａｂｉｌｉｔｙ ｉｎｄｅｘ ａｎｄ ｒｅｖｉｅｗｉｎｇ ｒｉｓｋｓ ｆｒｏｍ ｄｅｌｉｂｅｒａｔｅ ａｎｄ ｒａｎ⁃ ｄｏｍ ａｔｔａｃｋ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｓｏｒｔｉｎｇ ｍｅｔｈｏｄｓ ｉｓ ｔｈｅｎ ｅｖａｌｕａｔｅｄ． Ｉｔ ｉｓ ａｐｐａｒｅｎｔ ｆｒｏｍ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｖｕｌｎｅｒａ⁃ ｂｉｌｉｔｙ ｉｎｄｉｃｅｓ ｔｈａｔ ｔｈｅ ａｖｉａｔｉｏｎ ｎｅｔｗｏｒｋ ｏｆ Ｃｈｉｎａ ｉｓ ｍｏｓｔ ｖｕｌｎｅｒａｂｌｅ ｔｏ ｔａｒｇｅｔｅｄ ａｔｔａｃｋｓ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｂｅｔｗｅｅｎｎｅｓｓ ｃｅｎｔｒａｌｉｔｙ ｉｎｄｉｃａｔｏｒ． Ｍｏｒｅｏｖｅｒ， ｂａｓｅｄ ｏｎ ｔｈｅ ａｖｉａｔｉｏｎ ｎｅｔｗｏｒｋ， ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｎｅｗ ｅｖａｌｕａｔｉｏｎ ｍｅｔｈｏｄ， ｗｈｉｃｈ ｔａｋｅｓ ｉｎｔｏ ａｃｃｏｕｎｔ ｎｏｔ ｏｎｌｙ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｎｅｉｇｈｂｏｒｓ， ｂｕｔ ａｌｓｏ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｃｏｅｆｆｉｃｉｅｎｔ． Ｆｏｃｕｓｉｎｇ ｏｎ Ｃｈｉｎａ’ｓ ａｖｉａ⁃ ｔｉｏｎ ｎｅｔｗｏｒｋ， ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈａｔ ｔｈｅ ｅｖａｌｕａｔｉｏｎ ａｃｃｕｒａｃｙ ｏｆ ｔｈｅ ｎｅｗ ｉｎｄｅｘ ｒａｎｋｓ ｏｎｌｙ ｓｅｃｏｎｄ ｔｏ ｔｈｅ ｂｅｔｗｅｅｎｎｅｓｓ ｃｅｎｔｒａｌｉｔｙ， ａｎｄ ｉｓ ｍｏｒｅ ｅｆｆｉｃｉｅｎｔ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｂｅｔｗｅｅｎｎｅｓｓ ｃｅｎｔｒａｌｉｔｙ ａｓ ｒｅｇａｒｄｓ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ． Ｋｅｙｗｏｒｄｓ：ａｖｉａｔｉｏｎ ｎｅｔｗｏｒｋ； ｋｅｙ ｎｏｄｅｓ； ｄｅｇｒｅｅ； ｃｌｕｓｔｅｒｉｎｇ ｃｏｅｆｆｉｃｉｅｎｔ； ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ 收稿日期：２０１６⁃０１⁃１５． 网络出版日期：２０１６⁃０８⁃２４． 基金项目：国家自然科学基金项目（６１５７３１９９）；天津自然科学基金项目 （１４ＪＣＹＢＪＣ１８７００）． 通信作者：闫玲玲． Ｅ⁃ｍａｉｌ：ｙａｎｌｉｎｇｌｉｎｇ＠ ｍａｉｌ．ｎａｎｋａｉ．ｅｄｕ．ｃｎ． 自 ２０ 世纪初飞机问世以来，航空运输系统飞速 发展。 与其他运输方式相比，航空运输具有及时、高 效、灵活的优势，尤其是在长距离运输和国际客运方 面的重要作用日益凸显［１］ 。 航空运输系统是一个 易受环境影响的开放的复杂系统，随着系统规模的 不断扩大，它在带给人们便利的同时也带来了一系 列的问题。 航班延误已经成为人们司空见惯的现 象，于是，在自然灾害或人为因素导致航班不能正常