公安复杂网络节点重要度研究

纪勇+周天麒+王刚+杨梅+朱小林

摘 要： 公安信息网是警务信息化工作的技术支撑，为了达到准确合理评估公安信息网稳定运行的风险度，需要对组成网络的各节点重要度进行评估分析。总结了在复杂网络环境下网络节点重要度常规计算方法并进行了相应分析，通过确立节点重要度关联指标体系，采用以度中心性和聚集中心性为核心参数的评估算法，对某型公安网络节点进行重要度计算评估实验，实验所得节点重要度值基本上反映了网络节点在整体拓扑结构中的地位，可以为复杂网络的建设及管理运维提供相应的工程借鉴和参考意义。

关键词： 公安网络； 网络节点； 节点重要度； 拓扑结构

中图分类号： TN915.08?34； D035.31 文献标识码： A 文章编号： 1004?373X（2014）13?0075?02

Research on importance of public security complex network nodes

JI Yong， ZHOU Tian?qi， WANG Gang， YANG Mei， ZHU Xiao?lin

（Department of Science and Technology Information， Chongqing Public Security Bureau， Chongqing 401147， China）

Abstract： The public security information net is a technology support of police informatization. In order to conduct an accurate risk assessment on public security network， it is necessary to assess and analyze the important degree of each node in the network. The conventional calculating methods of the importance degree of network nodes in complex public security network environment are summarized and analyzed. The index system related to node important degree is established. The assessment me?thod of taking the importance degree and gather centrality as the key parameters was adopted to perform an assessment experiment of importance calculation for the public security network node. The important degree values got from the experiment can basically reflect the status of the network node in the whole topological structure， and meet the needs of public security network risk assessment. This research result provided an engineering reference for establishment and maintenance of complex public security network.

Keywords： public security network； network node； node importance； topological structure

0 引 言

近年来网络技术的快速发展使得警务信息化的概念已经深入人心，以公安网络为支撑基础的信息系统应用日趋广泛。公安部近年来一直大力推进建设的金盾工程，本质上就是公安通信网络与计算机信息系统建设工作，该专项工程目的即通过现代化信息通信技术，进一步提升公安机关快反协作能力，提高警务工作效率，以更好服务于新形式下社会公共安全的动态管理[1]。为了保障公安数据通信网络的安全稳定运行，需要在公安网络系统的建设和运维管理中借助风险评估手段进行分析，将复杂公安网络风险值控制在合理范围之内。而对复杂公安网络进行准确的风险评估，则需要评估公安网络各节点的重要度，从而做到准确合理的评估整个网络风险，这就使得网络节点的重要性分析显得尤为重要。

1 节点重要度综述

近年来网络技术发展迅速，较多网络呈现的复杂性特征表现出与以常规网络理论不同的一些特性，如小世界特性、无尺度特性等[2]。如何在复杂网络环境下对网络进行可靠的运维是复杂化网络技术研究的重要问题，因此复杂型网络节点重要度评估显得尤为重要。通过复杂网络的节点重要度计算评估确定较为重要的网络节点，进而对重要的网络节点进行重点分析从而保证网络的整体可靠性[3]。

对网络节点重要度计算评估的方法很多，究其根源来说是依靠图论和图论基础上的数据挖掘[4]。较为便捷的手段是以节点连接度作为衡量节点的重要度指标，节点之间连接边的数量和该节点重要度成正比[5]。部分研究人员认为介数是衡量节点重要度较好的指标，某节点所连接的最短路径数量和节点的重要度之间成正比，但是节点介数的计算过程比较复杂，首先是计算节点对互相之间最短路径的长度，其次记录包含最短路径之间的路线[6]。综合而言，网络节点的重要度计算评估方法依据方法原理及侧重点的不同，根据评估方法定义分为三种：最短路径方法、关联性方法和模拟流方法[7]。其中最短路径方法指的是节点之间传播所选择的最优路径，关联性方法表示的是个体节点的直连，模拟流方法则表示对现实的模拟。节点重要度评估方法的分类如图1所示。

图1 节点重要度评估方法分类

2 节点重要度评估的指标体系

对于网络节点的重要度评估来说，其重要度之间的差异可以通过对整体网络中的某些信息的分析得来，如对最短路径、节点的度以及边的权值等指标进行分析[8]。通过统计上述信息，相对准确的表征出网络中节点的位置特性。本文所指的评估计算网络节点的重要度指标包括：度中心性、接近中心性、聚集度中心性。

（1） 度中心性：指的是该点的度数，即与该点直接相连的点的个数。在无向图中是点的度数，在有向图中是点入度和点出度之和。度中心性用于分析节点直接影响力，即评估该节点在网络中的直接关系[9]。对于节点[k]来说，节点[k]的邻域表示为[δki=kjkj∈K，j=1，2，…，n，]则节点[k]的度中心性可表示为[cd=δki]。

（2） 接近度中心性：表示某节点和所有的图中其余节点之间捷径的距离和，此类指标常用于计算网络节点通过整个网络对其余的节点间接影响力[10]，可表示为[cc=s

（3） 聚集度中心性：该指标表示的是节点在整个网络中的不可替代性，该指标和度中心性及接近度中心性具有紧密的关系，是节点重要度的关键正向评价指标[11]，可表示为：[cj=cd（cd-1）cc。]

3 节点重要度评估算法及算例分析

3.1 节点重要度评估算法

复杂网络从本质上来说是一种非同质拓扑结构，这种特性决定了在网络中各节点的重要度是不同的。复杂网络中节点的重要度首先取决于节点的位置，例如网络中非核心节点与核心节点的重要程度明显不同；其次是节点在网络中的重要度还取决于节点的连通能力，就是经过此节点最短的路径数量越多，即此节点在整个网络中地位则越重要，从而对整个网络的影响越大。因此本文针对节点的重要度评价，将节点的度中心性和聚集中心性作为评价的主要指标，节点重要度[dj]评价公式可以描述为：[dj=cd+（1-?）cj]，其中[?]指的是重要度评价权重值，可以依据网络的具体拓扑结构通过专家库的方式来进一步确定。

3.2 某型网络算例分析

通过对节点重要度评估算法的介绍，对某复杂公安网络节点重要度评估计算，以验证上述算法的合理性和准确性，图2为某复杂公安网络的拓扑图的部分区域。

图2 某复杂公安网络拓扑图部分区域

其中A和B为市局核心节点，C，D，E为分局节点，F，G，H，I分别为分局所辖科、所、队等基层机关节点。如果不引入节点重要度评估的概念，那么常规来说A与B的重要度是同样的，同理C，D，E的重要度也一致，F，G，H，I的重要度亦一致，这对于整个网络的风险评估来说会造成评估时间的增加和计算的浪费，因此需要对上述网络节点的重要度进行定量的评估，计算结果见表1。

本文所述评估重要度算法的计算流程简单，比较适合多层次且节点较多的复杂型网络，同时风险评估计算较为稳定，上述算例的计算结果也反映了各网络节点对整个公安网络风险的影响各有偏重，这对公安网络的整体风险评估具有重要的意义。

4 结 论

公安信息网是警务信息化工作的技术支撑，为了对其进行准确合理的风险评估，需要对组成网络的各节点重要度进行相关研究和分析。文章对复杂型公安网络的节点重要度研究方法进行综合分析，在此基础上确定节点重要度的指标并进行细化分析，通过节点重要度评估算法分析公安网络节点的风险度，计算得出的重要度值基本表征出网络中的节点在整体拓扑中的地位，满足对公安网络的风险评估所需。本文研究内容可为复杂网络的建设及管理运维提供相应的工程借鉴和参考意义。

参考文献

[1] 杨雅辉，李小东.IP网络性能指标体系的研究[J].通信学报，2002，23（11） ：121?127.

[2] 杨富国.网络设备安全与防火墙[M].北京：北方交通大学出版社，2005.

[3] 龙冬阳.网络安全技术及其应用[M].广州：华南理工大学出版社，2004.

[4] 李鹏翔，任玉晴，席酉民.网络节点（集）重要性的一种度量指标[J].系统工程，2004，22（4）：21?24.

[5] 杨威.网络工程设计与系统集成[M].北京：人民邮电出版社，2005.

[6] 荣莉莉，郭天柱，王建伟.复杂网络节点中心性[J].上海理工大学学报，2008，30（3）：228?229.

[7] 谭跃进，吴俊，邓宏钟.复杂网络中节点重要度评估的节点收缩方法[J].系统工程理论与实践，2006，26（11）：138?139.

[8] DE MOURA E S， NAVARRO Gonzalo， ZIVIANI Nivio， et al. Fast and flexible word searching on compressed text [J]. ACM Transactions on Information Systems， 2000， 18（2）： 133?139.

[9] 安世虎，聂培尧，贺国光.节点赋权网络中节点重要性的综合测度法[J].管理科学学报，2006，9（12）：18?19.

[10] 郝南，李德毅，淦文燕.复杂网络中重要性节点发掘综述[J].计算机科学，2007，34（12）：128?129.

[11] 李伟男，颚跃鹏.多模式匹配算法及其硬件实现[J].软件学报，2006，9（41）：121?122.

图1 节点重要度评估方法分类

2 节点重要度评估的指标体系

对于网络节点的重要度评估来说，其重要度之间的差异可以通过对整体网络中的某些信息的分析得来，如对最短路径、节点的度以及边的权值等指标进行分析[8]。通过统计上述信息，相对准确的表征出网络中节点的位置特性。本文所指的评估计算网络节点的重要度指标包括：度中心性、接近中心性、聚集度中心性。

（1） 度中心性：指的是该点的度数，即与该点直接相连的点的个数。在无向图中是点的度数，在有向图中是点入度和点出度之和。度中心性用于分析节点直接影响力，即评估该节点在网络中的直接关系[9]。对于节点[k]来说，节点[k]的邻域表示为[δki=kjkj∈K，j=1，2，…，n，]则节点[k]的度中心性可表示为[cd=δki]。

（2） 接近度中心性：表示某节点和所有的图中其余节点之间捷径的距离和，此类指标常用于计算网络节点通过整个网络对其余的节点间接影响力[10]，可表示为[cc=s

（3） 聚集度中心性：该指标表示的是节点在整个网络中的不可替代性，该指标和度中心性及接近度中心性具有紧密的关系，是节点重要度的关键正向评价指标[11]，可表示为：[cj=cd（cd-1）cc。]

3 节点重要度评估算法及算例分析

3.1 节点重要度评估算法

复杂网络从本质上来说是一种非同质拓扑结构，这种特性决定了在网络中各节点的重要度是不同的。复杂网络中节点的重要度首先取决于节点的位置，例如网络中非核心节点与核心节点的重要程度明显不同；其次是节点在网络中的重要度还取决于节点的连通能力，就是经过此节点最短的路径数量越多，即此节点在整个网络中地位则越重要，从而对整个网络的影响越大。因此本文针对节点的重要度评价，将节点的度中心性和聚集中心性作为评价的主要指标，节点重要度[dj]评价公式可以描述为：[dj=cd+（1-?）cj]，其中[?]指的是重要度评价权重值，可以依据网络的具体拓扑结构通过专家库的方式来进一步确定。

3.2 某型网络算例分析

通过对节点重要度评估算法的介绍，对某复杂公安网络节点重要度评估计算，以验证上述算法的合理性和准确性，图2为某复杂公安网络的拓扑图的部分区域。

图2 某复杂公安网络拓扑图部分区域

其中A和B为市局核心节点，C，D，E为分局节点，F，G，H，I分别为分局所辖科、所、队等基层机关节点。如果不引入节点重要度评估的概念，那么常规来说A与B的重要度是同样的，同理C，D，E的重要度也一致，F，G，H，I的重要度亦一致，这对于整个网络的风险评估来说会造成评估时间的增加和计算的浪费，因此需要对上述网络节点的重要度进行定量的评估，计算结果见表1。

本文所述评估重要度算法的计算流程简单，比较适合多层次且节点较多的复杂型网络，同时风险评估计算较为稳定，上述算例的计算结果也反映了各网络节点对整个公安网络风险的影响各有偏重，这对公安网络的整体风险评估具有重要的意义。

4 结 论

公安信息网是警务信息化工作的技术支撑，为了对其进行准确合理的风险评估，需要对组成网络的各节点重要度进行相关研究和分析。文章对复杂型公安网络的节点重要度研究方法进行综合分析，在此基础上确定节点重要度的指标并进行细化分析，通过节点重要度评估算法分析公安网络节点的风险度，计算得出的重要度值基本表征出网络中的节点在整体拓扑中的地位，满足对公安网络的风险评估所需。本文研究内容可为复杂网络的建设及管理运维提供相应的工程借鉴和参考意义。

参考文献

[1] 杨雅辉，李小东.IP网络性能指标体系的研究[J].通信学报，2002，23（11） ：121?127.

[2] 杨富国.网络设备安全与防火墙[M].北京：北方交通大学出版社，2005.

[3] 龙冬阳.网络安全技术及其应用[M].广州：华南理工大学出版社，2004.

[4] 李鹏翔，任玉晴，席酉民.网络节点（集）重要性的一种度量指标[J].系统工程，2004，22（4）：21?24.

[5] 杨威.网络工程设计与系统集成[M].北京：人民邮电出版社，2005.

[6] 荣莉莉，郭天柱，王建伟.复杂网络节点中心性[J].上海理工大学学报，2008，30（3）：228?229.

[7] 谭跃进，吴俊，邓宏钟.复杂网络中节点重要度评估的节点收缩方法[J].系统工程理论与实践，2006，26（11）：138?139.

[8] DE MOURA E S， NAVARRO Gonzalo， ZIVIANI Nivio， et al. Fast and flexible word searching on compressed text [J]. ACM Transactions on Information Systems， 2000， 18（2）： 133?139.

[9] 安世虎，聂培尧，贺国光.节点赋权网络中节点重要性的综合测度法[J].管理科学学报，2006，9（12）：18?19.

[10] 郝南，李德毅，淦文燕.复杂网络中重要性节点发掘综述[J].计算机科学，2007，34（12）：128?129.

[11] 李伟男，颚跃鹏.多模式匹配算法及其硬件实现[J].软件学报，2006，9（41）：121?122.

图1 节点重要度评估方法分类

2 节点重要度评估的指标体系

对于网络节点的重要度评估来说，其重要度之间的差异可以通过对整体网络中的某些信息的分析得来，如对最短路径、节点的度以及边的权值等指标进行分析[8]。通过统计上述信息，相对准确的表征出网络中节点的位置特性。本文所指的评估计算网络节点的重要度指标包括：度中心性、接近中心性、聚集度中心性。

（1） 度中心性：指的是该点的度数，即与该点直接相连的点的个数。在无向图中是点的度数，在有向图中是点入度和点出度之和。度中心性用于分析节点直接影响力，即评估该节点在网络中的直接关系[9]。对于节点[k]来说，节点[k]的邻域表示为[δki=kjkj∈K，j=1，2，…，n，]则节点[k]的度中心性可表示为[cd=δki]。

（2） 接近度中心性：表示某节点和所有的图中其余节点之间捷径的距离和，此类指标常用于计算网络节点通过整个网络对其余的节点间接影响力[10]，可表示为[cc=s

（3） 聚集度中心性：该指标表示的是节点在整个网络中的不可替代性，该指标和度中心性及接近度中心性具有紧密的关系，是节点重要度的关键正向评价指标[11]，可表示为：[cj=cd（cd-1）cc。]

3 节点重要度评估算法及算例分析

3.1 节点重要度评估算法

复杂网络从本质上来说是一种非同质拓扑结构，这种特性决定了在网络中各节点的重要度是不同的。复杂网络中节点的重要度首先取决于节点的位置，例如网络中非核心节点与核心节点的重要程度明显不同；其次是节点在网络中的重要度还取决于节点的连通能力，就是经过此节点最短的路径数量越多，即此节点在整个网络中地位则越重要，从而对整个网络的影响越大。因此本文针对节点的重要度评价，将节点的度中心性和聚集中心性作为评价的主要指标，节点重要度[dj]评价公式可以描述为：[dj=cd+（1-?）cj]，其中[?]指的是重要度评价权重值，可以依据网络的具体拓扑结构通过专家库的方式来进一步确定。

3.2 某型网络算例分析

通过对节点重要度评估算法的介绍，对某复杂公安网络节点重要度评估计算，以验证上述算法的合理性和准确性，图2为某复杂公安网络的拓扑图的部分区域。

图2 某复杂公安网络拓扑图部分区域

其中A和B为市局核心节点，C，D，E为分局节点，F，G，H，I分别为分局所辖科、所、队等基层机关节点。如果不引入节点重要度评估的概念，那么常规来说A与B的重要度是同样的，同理C，D，E的重要度也一致，F，G，H，I的重要度亦一致，这对于整个网络的风险评估来说会造成评估时间的增加和计算的浪费，因此需要对上述网络节点的重要度进行定量的评估，计算结果见表1。

本文所述评估重要度算法的计算流程简单，比较适合多层次且节点较多的复杂型网络，同时风险评估计算较为稳定，上述算例的计算结果也反映了各网络节点对整个公安网络风险的影响各有偏重，这对公安网络的整体风险评估具有重要的意义。

4 结 论

公安信息网是警务信息化工作的技术支撑，为了对其进行准确合理的风险评估，需要对组成网络的各节点重要度进行相关研究和分析。文章对复杂型公安网络的节点重要度研究方法进行综合分析，在此基础上确定节点重要度的指标并进行细化分析，通过节点重要度评估算法分析公安网络节点的风险度，计算得出的重要度值基本表征出网络中的节点在整体拓扑中的地位，满足对公安网络的风险评估所需。本文研究内容可为复杂网络的建设及管理运维提供相应的工程借鉴和参考意义。

参考文献

[1] 杨雅辉，李小东.IP网络性能指标体系的研究[J].通信学报，2002，23（11） ：121?127.

[2] 杨富国.网络设备安全与防火墙[M].北京：北方交通大学出版社，2005.

[3] 龙冬阳.网络安全技术及其应用[M].广州：华南理工大学出版社，2004.

[4] 李鹏翔，任玉晴，席酉民.网络节点（集）重要性的一种度量指标[J].系统工程，2004，22（4）：21?24.

[5] 杨威.网络工程设计与系统集成[M].北京：人民邮电出版社，2005.

[6] 荣莉莉，郭天柱，王建伟.复杂网络节点中心性[J].上海理工大学学报，2008，30（3）：228?229.

[7] 谭跃进，吴俊，邓宏钟.复杂网络中节点重要度评估的节点收缩方法[J].系统工程理论与实践，2006，26（11）：138?139.

[8] DE MOURA E S， NAVARRO Gonzalo， ZIVIANI Nivio， et al. Fast and flexible word searching on compressed text [J]. ACM Transactions on Information Systems， 2000， 18（2）： 133?139.

[9] 安世虎，聂培尧，贺国光.节点赋权网络中节点重要性的综合测度法[J].管理科学学报，2006，9（12）：18?19.

[10] 郝南，李德毅，淦文燕.复杂网络中重要性节点发掘综述[J].计算机科学，2007，34（12）：128?129.

[11] 李伟男，颚跃鹏.多模式匹配算法及其硬件实现[J].软件学报，2006，9（41）：121?122.