·592. 智能系统学报 第11卷 点间形成的连通子图的数目。Centola[2o]认为节点 5 实验分析 的传播影响力与节点的聚类系数有关，聚类系数越 大越不利于信息的广泛传播。Chen等2)]在此基础 为了验证簇度指标对节点重要性的度量效果， 上提出了一种针对有向网络的ClusterRank算法，采 分别采用簇度指标以及上文提到的6种方法对中国 用SR传播模型进行仿真实验，结果表明该算法优 航空网络进行蓄意攻击仿真实验，并用脆弱性指标 于一些基准算法。任卓明等)将节点的二阶邻居 来评价攻击效果。 度和聚类系数结合起来，提出了一种新的节点重要 经过调试得出，对于函数c(i),当a的取值 范围为[4724,4952]时，脆弱性指标取最大值 性评价方法，并分别用美国航空网络以及美国西部 0.436,即得到的攻击效果最好。 电力网验证了方法的有效性。 网络中移除节点的比例和最大连通集的规模之 由此得出结论，局部聚类系数的增大对信息的 间的关系由图6给出。从图6中可以看出，按照簇 传播是具有阻碍作用的，如果节点的邻居节点更倾 度指标排列出的节点重要性顺序对中国航空网络进 向于互相连接，那么以节点为起始点，更容易形成一 行蓄意攻击，得到的脆弱性指标数值为0.405，攻击 个局部的区域：相反，如果节点的邻居更倾向于连接 效果仅次于介数中心性。但是介数的时间复杂度为 除其邻居外的其他节点，那么信息才能够迅速在较 O(N3):而该指标的时间复杂度为O(N),比介数中 大的范围内传播。例如在图5中，节点3和节点5 心性要快很多。例如在中国航空网络中，用介数排 序需要0.03s,而用簇度指标排序只需要0.01s。 具有相同的度值k:以及相同的其邻居度之和，即 10 k=k=3f=∫3=9，但是节点5的聚类系数比节点3 0.9 更小(C,=0.33,C=0),也就意味着节点5拥有比 0.8 0.7 节点3更高的影响力。这是因为节点5的邻居节点 趣0.6 0.5 更倾向于连接其他节点而不是互相连接，这样就能 0.4 0.3 把信息传播到更广的范围内。 曼 0.2 0.1 0■ 0.10.2030.40.50.60.70.80.91.0 移除节点的比例in 注释：1.D-Cluster(v.=0.4046):2.随机攻击(v=0.0243): 3.介数中心性(v0.4787):4.度数中心性(y=0.3603) 5接近中心性(v=0.341)6.半局部中心性(v,-0.314: 7特征：向量中心性(v=0.3119) 图6移除节点比例和最大连通集规模的关系（簇度指 图5示例网络拓扑结构 标与传统方法的攻击效果对比)】 Fig.5 The topology of example network Fig.6 The relationship between the proportion of re- 可见，节点的度和聚类系数对刻画其重要性都 moved nodes and the scale of the largest con- 具有非常重要的意义。将节点的直接影响力和节点 nected component(Comparison of D-cluster in- dex and traditional methods) 邻居之间连接的紧密程度结合起来，提出一种新的 指标即簇度指标为： 6 结束语 upe(i)=k:·ac0(a>1) 本文分别用度中心性、接近中心性、介数中心 式中：k为节点v:的度，a为可调参数，C()为节点 性、特征向量中心性和半局部中心性5种方法对中 i的聚类系数。 国航空网络模型进行了分析，将网络中的节点按照 在此需要说明的是： 重要性从大到小进行排序，并列出了重要性排名前 1)Chen和任卓明等在构造节点重要性指标中 10的节点城市：然后按排列出的节点次序对中国航 用到了二阶邻居度，但是由于航空网络的特殊性，即 空网络进行蓄意攻击，用脆弱性指标考察这5种方 中转成本造成的平均路径长度较小，节点的直接影 法的攻击效果。仿真结果表明，相比于其他4种方 响力在评价节点重要性的过程中占主导地位。 法，基于介数中心性的节点重要性排序方法能够更 2)由于节点的聚类系数C(i)可能为0，故构造 准确地刻画网络中节点的重要性。进而根据介数中 减函数ac((a>1),并通过仿真实验得到α的最优 心性得到的排序结果分别单独攻击各个城市节点， 值，在后面的分析中我们将以中国航空网络为样本 观察机场失效后网络的全局效率，分析得出各个局 作出详细的描述。 部地区的重要性节点。点间形成的连通子图的数目。 Ｃｅｎｔｏｌａ ［２０］ 认为节点 的传播影响力与节点的聚类系数有关，聚类系数越 大越不利于信息的广泛传播。 Ｃｈｅｎ 等［２１］ 在此基础 上提出了一种针对有向网络的 ＣｌｕｓｔｅｒＲａｎｋ 算法，采 用 ＳＩＲ 传播模型进行仿真实验，结果表明该算法优 于一些基准算法。 任卓明等［４］ 将节点的二阶邻居 度和聚类系数结合起来，提出了一种新的节点重要 性评价方法，并分别用美国航空网络以及美国西部 电力网验证了方法的有效性。 由此得出结论，局部聚类系数的增大对信息的 传播是具有阻碍作用的，如果节点的邻居节点更倾 向于互相连接，那么以节点为起始点，更容易形成一 个局部的区域；相反，如果节点的邻居更倾向于连接 除其邻居外的其他节点，那么信息才能够迅速在较 大的范围内传播。 例如在图 ５ 中，节点 ３ 和节点 ５ 具有相同的度值 ｋｉ 以及相同的其邻居度之和，即 ｋ３ ＝ ｋ５ ＝ ３，ｆ ３ ＝ ｆ ５ ＝ ９，但是节点 ５ 的聚类系数比节点 ３ 更小（Ｃ３ ＝ ０．３３，Ｃ５ ＝ ０），也就意味着节点 ５ 拥有比 节点 ３ 更高的影响力。 这是因为节点 ５ 的邻居节点 更倾向于连接其他节点而不是互相连接，这样就能 把信息传播到更广的范围内。 图 ５ 示例网络拓扑结构 Ｆｉｇ．５ Ｔｈｅ ｔｏｐｏｌｏｇｙ ｏｆ ｅｘａｍｐｌｅ ｎｅｔｗｏｒｋ 可见，节点的度和聚类系数对刻画其重要性都 具有非常重要的意义。 将节点的直接影响力和节点 邻居之间连接的紧密程度结合起来，提出一种新的 指标即簇度指标为： μＤＣＬ（ｉ） ＝ ｋｉ·α －Ｃ（ｉ） （α ＞ １） 式中：ｋｉ 为节点 ｖｉ 的度，α 为可调参数，Ｃ（ｉ）为节点 ｉ 的聚类系数。 在此需要说明的是： １）Ｃｈｅｎ 和任卓明等在构造节点重要性指标中 用到了二阶邻居度，但是由于航空网络的特殊性，即 中转成本造成的平均路径长度较小，节点的直接影 响力在评价节点重要性的过程中占主导地位。 ２）由于节点的聚类系数 Ｃ（ｉ）可能为 ０，故构造 减函数 α －Ｃ（ｉ） （α＞１），并通过仿真实验得到 α 的最优 值，在后面的分析中我们将以中国航空网络为样本 作出详细的描述。 ５ 实验分析 为了验证簇度指标对节点重要性的度量效果， 分别采用簇度指标以及上文提到的 ６ 种方法对中国 航空网络进行蓄意攻击仿真实验，并用脆弱性指标 来评价攻击效果。 经过调试得出，对于函数 μＤＣＬ（ｉ），当 α 的取值 范围为 ［ ４ ７２４， ４ ９５２］ 时， 脆弱性指标取最大值 ０．４３６，即得到的攻击效果最好。 网络中移除节点的比例和最大连通集的规模之 间的关系由图 ６ 给出。 从图 ６ 中可以看出，按照簇 度指标排列出的节点重要性顺序对中国航空网络进 行蓄意攻击，得到的脆弱性指标数值为 ０．４０５，攻击 效果仅次于介数中心性。 但是介数的时间复杂度为 Ｏ（Ｎ ３ ）；而该指标的时间复杂度为 Ｏ（Ｎ），比介数中 心性要快很多。 例如在中国航空网络中，用介数排 序需要 ０．０３ ｓ，而用簇度指标排序只需要 ０．０１ ｓ。 图 ６ 移除节点比例和最大连通集规模的关系（簇度指 标与传统方法的攻击效果对比） Ｆｉｇ．６ Ｔｈｅ ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｔｈｅ ｐｒｏｐｏｒｔｉｏｎ ｏｆ ｒｅ⁃ ｍｏｖｅｄ ｎｏｄｅｓ ａｎｄ ｔｈｅ ｓｃａｌｅ ｏｆ ｔｈｅ ｌａｒｇｅｓｔ ｃｏｎ⁃ ｎｅｃｔｅｄ ｃｏｍｐｏｎｅｎｔ（Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｄ⁃ｃｌｕｓｔｅｒ ｉｎ⁃ ｄｅｘ ａｎｄ ｔｒａｄｉｔｉｏｎａｌ ｍｅｔｈｏｄｓ） ６ 结束语 本文分别用度中心性、接近中心性、介数中心 性、特征向量中心性和半局部中心性 ５ 种方法对中 国航空网络模型进行了分析，将网络中的节点按照 重要性从大到小进行排序，并列出了重要性排名前 １０ 的节点城市；然后按排列出的节点次序对中国航 空网络进行蓄意攻击，用脆弱性指标考察这 ５ 种方 法的攻击效果。 仿真结果表明，相比于其他 ４ 种方 法，基于介数中心性的节点重要性排序方法能够更 准确地刻画网络中节点的重要性。 进而根据介数中 心性得到的排序结果分别单独攻击各个城市节点， 观察机场失效后网络的全局效率，分析得出各个局 部地区的重要性节点。 ·５９２· 智 能 系 统 学 报 第 １１ 卷