·590. 智能系统学报 第11卷 络间的连接中起到了桥梁的作用。中国航空网络节 排在第七位。从空间结构上可以看出新疆地区的城市 点的介数中心性排序中，北京依然排在第1位，但是 节点大多数通过乌鲁木齐与整个航空网络连接，若移 排在第2位的乌鲁木齐在其他排序结果的前十中从 除乌鲁木齐，则新疆地区的大部分城市节点将变为孤 未出现过，排在第3位的昆明只在度中心性排序中 立节点，而昆明也同样起到非常重要的桥梁作用。 表1排名前10中国航空网络各中心性指标 Table 1 The Top10 centrality index of Chinese aviation network 介数中心性 特征向量 半局部中心性 次序城市 度中心性 城市接近中心性 城市 城市 城市 (×103) 中心性 (×10) 1北京 0.694 北京 0.762 北京 4.475 北京 0.220 北京 0.281 2上海 0.565 上海 0.693 乌鲁木齐 2.835 广州 0.207 广州 0.268 3广州 0.565 广州 0.693 昆明 2.353 上海 0.207 上海 0.267 4深圳 0.470 深圳 0.650 广州 2.231 深圳 0.196 深圳 0.257 5成都 0.415 成都 0.628 上海 2.223 成都 0.184 成都 0.245 6西安 0.381 西安 0.615 成都 1.565 南京 0.180 南京 0.242 7昆明 0.381 重庆 0.610 西安 1.508 杭州 0.178 杭州 0.240 8重庆 0.374 杭州 0.603 深圳 1.121 重庆 0.174 重庆 0.233 9杭州 0.354 南京 0.603 重庆 0.825 长沙 0.172 长沙 0.232 10南京 0.347 长沙 0.598 长沙 0.790 郑州 0.170 郑州 0.231 3.3用网络的鲁棒性和脆弱性评价排序算法 V=1/2-R 利用之前的节点重要性评价方法对中国航空网 可见，脆弱性指标的值越大，表明采用的攻击方 络的重要节点进行排序之后，分别按照节点的重要 法效果越好。于是，分别采用度中心性、接近中心 性从大到小的顺序，依次删除网络中的节点。则节 性、介数中心性、特征向量中心性和半局部中心性5 点移除后网络的破坏程度可以用最大连通子图的相 种方法对中国航空网络进行攻击，画出/n和 对大小，全局效率以及脆弱性指标来进行评价。 σ(i/n)在二维坐标上的曲线，并用脆弱性指标考察 最大连通子图概念的提出，是为了描述网络中 这5种方法的攻击效果，同时与随机攻击网络的方 的节点或连边由于一些内部或外部的原因所发生的 法得到的效果进行比较。 变化。简单来说，最大连通子图就是一个网络的众 图4为对中国航空网络模型分别进行随机攻击 多连通子图中包含节点最多的那个子图。 和蓄意攻击后，网络中移除节点的比例和最大连通 网络中，节点：和：之间的效率为两点之间最 集的规模之间的关系。在此需要说明的是，采用的 短距离的倒数，即1/d。于是网络的全局效率16就 攻击方式是同时移除i/n比例的节点，计算剩余网 定义为所有节点对效率的平均值，即 络中最大连通集所占的比例。 EG=2-m多 1 1.0 0.9 如果用i/n表示移除的节点比例，用c(i/n)表 0.8 0.7 示移除i/n比例的节点后最大连通子图的相对大 0.6 0.5 小，则该节点移除方式下网络的鲁棒性(robustness) 04 可以用R-指标)来评价。具体定义为 0.3 0.2 R=(i/m) n i=1 00.10.20.30.40.50.60.70.80.91.0 显然，无论针对哪种算法都能得到如下结果 移除节点的比例n 1-1/m 注释：1.度数中心性(0.3603)：2.介数中心性(v,0.4787) R = 2 完全图 3.接近中心性(v=0.341:4.半局部中心性(y=0.314: 5.特征向量中心性(v0.3119):6.随机攻击(，0.0243) 。11 星形图 图4移除节点比例和最大连通集规模的关系（传统方 法的攻击效果】 所以在任何网络中，无论用何种算法移除节点， Fig.4 The relationship between the proportion of removed R∈(0,1/2)。因此，文献[18]定义V-指标来衡量网 nodes and the scale of the largest connected compo- 络对所实施的节点移除方法的脆弱性(vulnerability)。 nent (Effect of traditional attack methods)络间的连接中起到了桥梁的作用。 中国航空网络节 点的介数中心性排序中，北京依然排在第 １ 位，但是 排在第 ２ 位的乌鲁木齐在其他排序结果的前十中从 未出现过，排在第 ３ 位的昆明只在度中心性排序中 排在第七位。 从空间结构上可以看出新疆地区的城市 节点大多数通过乌鲁木齐与整个航空网络连接，若移 除乌鲁木齐，则新疆地区的大部分城市节点将变为孤 立节点，而昆明也同样起到非常重要的桥梁作用。 表 １ 排名前 １０ 中国航空网络各中心性指标 Ｔａｂｌｅ １ Ｔｈｅ Ｔｏｐ１０ ｃｅｎｔｒａｌｉｔｙ ｉｎｄｅｘ ｏｆ Ｃｈｉｎｅｓｅ ａｖｉａｔｉｏｎ ｎｅｔｗｏｒｋ 次序 城市 度中心性 城市 接近中心性 城市 介数中心性 （×１０ ３ ） 城市 特征向量 中心性 城市 半局部中心性 （×１０ ６ ） １ 北京 ０．６９４ 北京 ０．７６２ 北京 ４．４７５ 北京 ０．２２０ 北京 ０．２８１ ２ 上海 ０．５６５ 上海 ０．６９３ 乌鲁木齐 ２．８３５ 广州 ０．２０７ 广州 ０．２６８ ３ 广州 ０．５６５ 广州 ０．６９３ 昆明 ２．３５３ 上海 ０．２０７ 上海 ０．２６７ ４ 深圳 ０．４７０ 深圳 ０．６５０ 广州 ２．２３１ 深圳 ０．１９６ 深圳 ０．２５７ ５ 成都 ０．４１５ 成都 ０．６２８ 上海 ２．２２３ 成都 ０．１８４ 成都 ０．２４５ ６ 西安 ０．３８１ 西安 ０．６１５ 成都 １．５６５ 南京 ０．１８０ 南京 ０．２４２ ７ 昆明 ０．３８１ 重庆 ０．６１０ 西安 １．５０８ 杭州 ０．１７８ 杭州 ０．２４０ ８ 重庆 ０．３７４ 杭州 ０．６０３ 深圳 １．１２１ 重庆 ０．１７４ 重庆 ０．２３３ ９ 杭州 ０．３５４ 南京 ０．６０３ 重庆 ０．８２５ 长沙 ０．１７２ 长沙 ０．２３２ １０ 南京 ０．３４７ 长沙 ０．５９８ 长沙 ０．７９０ 郑州 ０．１７０ 郑州 ０．２３１ ３．３ 用网络的鲁棒性和脆弱性评价排序算法 利用之前的节点重要性评价方法对中国航空网 络的重要节点进行排序之后，分别按照节点的重要 性从大到小的顺序，依次删除网络中的节点。 则节 点移除后网络的破坏程度可以用最大连通子图的相 对大小，全局效率以及脆弱性指标来进行评价。 最大连通子图概念的提出，是为了描述网络中 的节点或连边由于一些内部或外部的原因所发生的 变化。 简单来说，最大连通子图就是一个网络的众 多连通子图中包含节点最多的那个子图。 网络中，节点 ｖｉ 和 ｖｊ 之间的效率为两点之间最 短距离的倒数，即 １ ／ ｄｉｊ。 于是网络的全局效率［１６］就 定义为所有节点对效率的平均值，即 Ｅ（Ｇ） ＝ ２ Ｎ（Ｎ － １）∑ｉ ＞ ｊ １ ｄｉｊ 如果用 ｉ ／ ｎ 表示移除的节点比例，用 σ（ｉ ／ ｎ）表 示移除 ｉ ／ ｎ 比例的节点后最大连通子图的相对大 小，则该节点移除方式下网络的鲁棒性（ｒｏｂｕｓｔｎｅｓｓ） 可以用 Ｒ⁃指标［１７］来评价。 具体定义为 Ｒ ＝ １ ｎ ∑ ｎ ｉ ＝ １ σ（ｉ ／ ｎ） 显然，无论针对哪种算法都能得到如下结果 Ｒｍａｘ ＝ １ － １ ／ ｎ ２ ， 完全图 Ｒｍｉｎ ＝ １ ｎ － １ ｎ ２ ， 星形图 ì î í ï ï ï ï 所以在任何网络中，无论用何种算法移除节点， Ｒ∈（０，１／ ２）。 因此，文献［１８］定义 Ｖ⁃指标来衡量网 络对所实施的节点移除方法的脆弱性（ｖｕｌｎｅｒａｂｉｌｉｔｙ）。 Ｖ ＝ １ ／ ２ － Ｒ 可见，脆弱性指标的值越大，表明采用的攻击方 法效果越好。 于是，分别采用度中心性、接近中心 性、介数中心性、特征向量中心性和半局部中心性 ５ 种方 法 对 中 国 航 空 网 络 进 行 攻 击， 画 出 ｉ ／ ｎ 和 σ（ｉ ／ ｎ）在二维坐标上的曲线，并用脆弱性指标考察 这 ５ 种方法的攻击效果，同时与随机攻击网络的方 法得到的效果进行比较。 图 ４ 为对中国航空网络模型分别进行随机攻击 和蓄意攻击后，网络中移除节点的比例和最大连通 集的规模之间的关系。 在此需要说明的是，采用的 攻击方式是同时移除 ｉ ／ ｎ 比例的节点，计算剩余网 络中最大连通集所占的比例。 图 ４ 移除节点比例和最大连通集规模的关系（传统方 法的攻击效果） Ｆｉｇ．４ Ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｔｈｅ ｐｒｏｐｏｒｔｉｏｎ ｏｆ ｒｅｍｏｖｅｄ ｎｏｄｅｓ ａｎｄ ｔｈｅ ｓｃａｌｅ ｏｆ ｔｈｅ ｌａｒｇｅｓｔ ｃｏｎｎｅｃｔｅｄ ｃｏｍｐｏ⁃ ｎｅｎｔ （Ｅｆｆｅｃｔ ｏｆ ｔｒａｄｉｔｉｏｎａｌ ａｔｔａｃｋ ｍｅｔｈｏｄｓ） ·５９０· 智 能 系 统 学 报 第 １１ 卷