本发明属于网络安全技术领域，公开的一种复杂网络拓扑中心节点的搜索算法，其步骤如下：网络拓扑结构获取；节点无向图获取；节点遍历度求解；网络遍历度求解；网络拓扑中心节点求解。本发明采用的网络拓扑中心节点是从网络信息扩散速度以及时间效率上对节点的重要性进行度量，既可以为复杂网络防御提供理论基石，也可以为复杂网络信息系统的精确授时提供解决方案。因此本发明尤其适用于复杂网络防御的关键节点及网络信息系统精确授时解决方案。
1.一种复杂网络拓扑中心节点的搜索算法，其特征是：其步骤如下：
1)、网络拓扑结构获取，扫描目标网络，发现活动主机，获取网络拓扑结构；
2)、节点无向图获取，将步骤1得到的目标网络拓扑结构的各节点及连通性用简单无向连通网络结构G＝(V,E)表示，其中V和E分别为节点和边的集合；
3)、节点遍历度求解，对步骤2得到的简单无向连通网络结构G＝(V,E)中求解节点v∈V到其它节点的最短路径，选取最短路径的最大值为节点遍历度；设节点v1,v2∈V在图G的最短路径长度为PL(v1,v2)，则节点v在网络结构G的节点遍历度为：Nd(v)＝maxu∈V(PL(u,v))；
4)、网络遍历度求解，依据步骤3，求解简单无向连通网络结构G＝(V,E)中每个节点v的节点遍历度，选取节点遍历度的最小值为网络遍历度；网络结构G的网络遍历度为：Nd＝minv∈V(Nd(v))；
5)、网络拓扑中心节点求解，依据步骤4，若节点v∈V的节点遍历度等于网络遍历度，即Nd(v)＝Nd，则判定节点v为网络拓扑中心节点；
其中所述网络拓扑存在中心节点，根据定义1、2和3，网络必定存在网络中心节点，构造仅包含两个节点的网络结构G，则网络结构G中存在两个网络中心节点，即网络结构G的中心节点不唯一；定义1节点遍历度：网络中，节点到其它各个节点的最短路径，最少跳数的最大值；定义2网络遍历度：网络中所有节点遍历度的最小值；定义3网络拓扑中心节点：节点遍历度等于网络遍历度的节点称为网络拓扑中心节点；
其中以网络拓扑中心节点为起点，遍历整个网络的遍历深度最小，遍历深度是指遍历树中节点与网络中心节点的最大距离；依据广度优先遍历原则，以网络中心节点v∈V为起点的遍历路径，对应于网络结构G中以v为根节点的生成树T；采用归纳法证明：对于任意节点u∈V，若在网络结构G中PL(u,v)＝k，则节点u在且仅在以v为起点的根节点的第k次遍历时加入生成树T，且第k次遍历获得生成子树 中节点与节点v的最大距离为k；
当k＝1时，以v为起点的第1次遍历，将与v相邻的所有节点均加入生成树T，即若PL(u,v)＝1则节点u在且仅在以v为起点的第1次遍历时加入生成树T，且第1次遍历获得生成子树中节点与节点v的最大距离为1成立；
设L＝v,v1,v2,…,u1,u为节点v,u之间的任意一条最短路径；易知L1＝v,v1,v2,…,u1为节点v,u1之间的最短路径，且PL(u1,v)＝l；根据假设条件，节点u1在且仅在以v为起点的第l次遍历时加入生成树T，且第l次遍历获得生成子树 中节点与节点v的最大距离为l；
(1)若节点u在前l次遍历时已加入生成树T：因为前l次遍历获得生成子树 中节点与节点v的最大距离不大于l，所以节点v,u之间的最短距离不大于l，与PL(u,v)＝l+1矛盾，即节点u在前l次遍历时已加入生成树T不成立；
设集合U＝{u1|u1与u相邻，且u1在v与u之间的最短路径上}，并设前l次遍历获得生成子树为 ， 易知 因为边集{(u1,u)|u1∈U}均包含于网络结构G且节点u不包含于T′，所以节点u在且仅在以v为起点的根节点的第l+1次遍历时加入生成树T，且第l+1次遍历获得生成子树中节点与节点v的最大距离为l+1；
因此，若在网络结构G中PL(u,v)＝k，则节点u在且仅在以v为起点的根节点的第k次遍历时加入生成树T，且第k次遍历获得生成子树 中节点与节点v的最大距离为k；
易知若网络结构G中节点与节点v的最大距离为k，则以v为起点的根节点的遍历深度为k；设节点v为网络结构G的网络中心节点，即节点v的节点遍历度最小，因此，以v为起点，遍历整个网络的遍历深度最小。
2.根据权利要求1所述的一种复杂网络拓扑中心节点的搜索算法，其特征是：所述网络遍历度不小于最大的节点遍历度的一半；设L＝v1,v2,…,vn为网络结构G的直径，即L为节点v1,vn之间的最短路径，且L为网络结构G中的最长最短路径；则网络遍历度不小于最大节点遍历度的一半；
易知，最大节点遍历度为n；设v为网络结构G中的任意节点，设Nd(v)为v的节点遍历度，并设L1＝v,u1,u2,…,v1和L2＝v,u′1,u2′,…,vn分别为节点v至v1和vn的最短路径；易知L1和L2的长度均不大于Nd(v)；因L为节点v1,vn之间的最短路径，所以路径L1∪L2＝v1,…,u1,v,v,u′1,…,vn的长度不小于n；因此，2·Nd(v)不小于L1∪L2的长度，且L1∪L2的长度不小于n，即Nd(v)≥n/2；
因此，网络结构G中任意节点的节点遍历度均不小于最大节点遍历度的一半；网络中心节点是网络结构G中的节点，且网络遍历度为网络中心节点的节点遍历度，即网络遍历度不小于最大节点遍历度的一半。
一种复杂网络拓扑中心节点的搜索算法
技术领域
[0001] 本发明属于网络安全技术领域，具体涉及一种复杂网络拓扑中心节点的搜索算法。
背景技术
[0002] 复杂网络中心性的研究是网络安全领域的一个重要分支，网络节点的重要性可通过节点的中心性来衡量。度中心性、接近中心性、中介中心性和特征向量中心性等度量方法主要侧重于从网络的连通性对节点的重要性进行描述，而本发明所定义的网络中心节点则是从网络信息扩散的速度以及时间效率上对节点的重要性进行度量。
[0003] 网络拓扑中心节点搜索算法与网络病毒的传播、网络舆情的扩散和NTP服务器的分层授时原则相一致，因此网络中心节点理论既可以为复杂网络防御提供理论基石，也可以为复杂网络信息系统的精确授时提供解决方案。
[0004] 复杂网络防御的理论基石网络中心节点是整个网络的关键节点和关键路径的必经之处，应该有针对性的对网络中心节点的脆弱性和薄弱环节进行防御。
[0005] 网络信息系统精确授时解决方案在不增加网络硬件设备和不改变网络拓扑结构的情况下，在网络中心节点配置NTP(网络时间服务器)主服务器，减少了主服务器对全网分层授时的层数，从而达到对整个网络的最精确授时。
[0006] 以网络信息扩散速度和时间效率度量节点重要性的复杂网络中心节点求解问题是非常有难度、有挑战性的，当前公开发表的文献中，尚未看到相关研究成果。
发明内容
[0007] 本发明提出了以网络信息扩散速度和时间效率度量节点重要性的一种复杂网络中心节点的搜索算法，既可以为复杂网络防御提供理论基石，也可以为复杂网络信息系统的精确授时提供解决方案。
[0008] 为实现上述发明目的，本发明采用如下技术方案：
[0009] 一种复杂网络拓扑中心节点的搜索算法，具体步骤如下：
[0010] 步骤1、网络拓扑结构获取
[0011] 扫描目标网络，发现活动主机，获取网络拓扑结构；
[0012] 步骤2、节点无向图获取
[0013] 将步骤1得到的目标网络拓扑结构的各节点及连通性用简单无向连通图G＝(V,E)表示，其中V和E分别为节点和边的集合；
[0014] 步骤3、节点遍历度求解
[0015] 对步骤2得到的简单无向连通图G＝(V,E)中求解节点v∈V到其它节点的最短路径，选取最短路径的最大值为节点遍历度；设节点v1,v2∈V在图G的最短路径长度为PL(v1,v2)，则节点v在图G的节点遍历度为：Nd(v)＝maxu∈V(PL(u,v))；
[0016] 步骤4、网络遍历度求解
[0017] 依据步骤3，求解简单无向连通图G＝(V,E)中每个节点v的节点遍历度，选取节点遍历度的最小值为网络遍历度；图G的网络遍历度为：Nd＝minv∈V(Nd(v))；
[0018] 步骤5、网络拓扑中心节点求解
[0019] 依据步骤4，若节点v∈V的节点遍历度等于网络遍历度，即Nd(v)＝Nd，则判定节点v为网络中心节点。
[0020] 由于采用如上所述的技术方案，本发明具有如下优越性：
[0021] 一种复杂网络拓扑中心节点的搜索算法，采用以下步骤：网络拓扑结构获取；节点无向图获取；节点遍历度求解；网络遍历度求解；网络拓扑中心节点求解。本发明采用的网络拓扑中心节点是从网络信息扩散速度以及时间效率上对节点的重要性进行度量，既可以为复杂网络防御提供理论基石，也可以为复杂网络信息系统的精确授时提供解决方案。因此本发明尤其适用于复杂网络防御的关键节点及网络信息系统精确授时解决方案。
附图说明
[0022] 图1为本发明的实现流程图；
[0023] 图2为复杂信息系统的网络拓扑结构示意图。
具体实施方式
[0024] 图1为本发明的一种复杂网络拓扑中心节点的搜索算法，其步骤如下：
[0025] 步骤1、网络拓扑结构获取
[0026] 扫描目标网络，发现活动主机，获取网络拓扑结构；
[0027] 步骤2、节点无向图获取
[0028] 将步骤1得到的目标网络拓扑结构的各节点及连通性用简单无向连通图G＝(V,E)表示，其中V和E分别为节点和边的集合；
[0029] 步骤3、节点遍历度求解
[0030] 对步骤2得到的简单无向连通图G＝(V,E)中求解节点v∈V到其它节点的最短路径，选取最短路径的最大值为节点遍历度。设节点v1,v2∈V在图G的最短路径长度为PL(v1,v2)，则节点v在图G的节点遍历度为：Nd(v)＝maxu∈V(PL(u,v))；
[0031] 步骤4、网络遍历度求解
[0032] 依据步骤3，求解简单无向连通图G＝(V,E)中每个节点v的节点遍历度，选取节点遍历度的最小值为网络遍历度。图G的网络遍历度为：Nd＝minv∈V(Nd(v))；
[0033] 步骤5、网络拓扑中心节点求解
[0034] 依据步骤4，若节点v∈V的节点遍历度等于网络遍历度，即Nd(v)＝Nd，则判定节点v为网络拓扑中心节点。
[0035] 网络中心论的概念
[0036] 定义1节点遍历度：网络中，节点到其它各个节点的最短路径(最少跳数)的最大值。
[0037] 定义2网络遍历度：网络中所有节点遍历度的最小值。
[0038] 定义3网络拓扑中心节点：节点遍历度等于网络遍历度的节点称为网络拓扑中心节点。
[0039] 证明1网络拓扑存在中心节点，但有些网络的拓扑中心节点非唯一。
[0040] 证明：根据定义1、2和3，网络必定存在网络中心节点。构造图G为仅包含两个节点的完全图，则图G中存在两个网络中心节点，即图G的中心节点不唯一。
[0041] 证明2在遵循广度优先规则的前提下，以网络拓扑中心节点为起点，遍历整个网络的遍历深度最小，遍历深度是指遍历树中节点与网络中心节点的最大距离。
[0042] 证明：依据广度优先遍历原则，以网络中心节点v∈V为起点的遍历路径，对应于图G中以v为根节点的生成树T。下面采用归纳法证明：对于任意节点u∈V，若在图G中PL(u,v)＝k，则节点u在且仅在以v为起点(根节点)的第k次遍历时加入生成树T，且第k次遍历获得生成子树 中节点与节点v的最大距离为k。
[0043] 当k＝1时，以v为起点的第1次遍历，将与v相邻的所有节点均加入生成树T，即若PL(u,v)＝1则节点u在且仅在以v为起点的第1次遍历时加入生成树T，且第1次遍历获得生成子树 中节点与节点v的最大距离为1。成立。
[0044] 假设k≤l时成立，下面证明k＝l+1时成立：
[0045] 设L＝v,v1,v2,…,u1,u为节点v,u之间的任意一条最短路径；易知L1＝v,v1,v2,…,u1为节点v,u1之间的最短路径，且PL(u1,v)＝l。根据假设条件，节点u1在且仅在以v为起点的第l次遍历时加入生成树T，且第l次遍历获得生成子树 中节点与节点v的最大距离为l。下面分两种情况讨论：
[0046] (1)若节点u在前l次遍历时已加入生成树T：因为前l次遍历获得生成子树中节点与节点v的最大距离不大于l，所以节点v,u之间的最短距离不大于l，与PL(u,v)＝l+
1矛盾，即节点u在前l次遍历时已加入生成树T不成立。
[0047] (2)若节点u在前l次遍历时没有加入生成树T：
[0048] 设集合U＝{u1|u1与u相邻，且u1在v与u之间的最短路径上}，并设前l次遍历获得生成子树为 (易知 )。因为边集{(u1,u)|u1∈U}均包含于图G且节点u不包含于T′，所以节点u在且仅在以v为起点(根节点)的第l+1次遍历时加入生成树T，且第l+1次遍历获得生成子树中节点与节点v的最大距离为l+1。
[0049] 因此，若在图G中PL(u,v)＝k，则节点u在且仅在以v为起点(根节点)的第k次遍历时加入生成树T，且第k次遍历获得生成子树 中节点与节点v的最大距离为k。
[0050] 根据上述证明，易知若图G中节点与节点v的最大距离为k，则以v为起点(根节点)的遍历深度为k。设节点v为图G的网络中心节点，即节点v的节点遍历度最小，因此，以v为起点，遍历整个网络的遍历深度最小。
[0051] 证明3网络遍历度不小于最大的节点遍历度的一半。
[0052] 证明：设L＝v1,v2,…,vn为图G的直径，即L为节点v1,vn之间的最短路径，且L为图G中的最长最短路径；则网络遍历度不小于最大节点遍历度的一半。
[0053] 易知，最大节点遍历度为n。设v为图G中的任意节点，设Nd(v)为v的节点遍历度，并设L1＝v,u1,u2,…,v1和L2＝v,u′1,u′2,…,vn分别为节点v至v1和vn的最短路径。易知L1和L2的长度均不大于Nd(v)。因为L为节点v1,vn之间的最短路径，所以路径L1∪L2＝v1,…,u1,v,v,u′1,…,vn的长度不小于n。因此，2·Nd(v)不小于L1∪L2的长度，且L1∪L2的长度不小于n，即Nd(v)≥n/2。
[0054] 因此，图G中任意节点的节点遍历度均不小于最大节点遍历度的一半。网络中心节点是图G中的节点，且网络遍历度为网络中心节点的节点遍历度，即网络遍历度不小于最大节点遍历度的一半。
[0055] 网络中心论，任何一个网络都存在网络中心节点。节点遍历度等于网络遍历度的节点称为网络中心节点。在遵循广度优先规则的前提下，由网络中心节点遍历整个网络的遍历深度最小。
[0056] 网络拓扑中心节点的求解思想与网络病毒的传播、网络舆情的扩散和NTP服务器的分层授时原则相一致，因此网络中心论既可以为复杂网络防御提供理论基石，也可以为复杂网络信息系统的精确授时提供解决方案。
[0057] 网络拓扑中心节点搜索算法
[0058] 输入：简单无向连通图G＝(V,E)，其中||V||＝n。
[0059] 输出：网络中心节点集Vc。
[0060] Step1.采用Dijkstra算法，计算V＝{v1,v2,…,vn}中任意节点对之间的最短路径长度，并建立最短路径长度矩阵D＝(dij)n×n，其中dij表示节点vi与vj之间的最短路径长度，dii＝0(i＝1,2,…,n)。转Step2。
[0061] Step2.计算向量 其中 并计算网络遍历度转Step3。
[0062] Step3.计算网络中心节点集： 算法结束。
[0063] 网络拓扑中心节点搜索算法的应用，如图2所示的一个复杂信息系统的网络拓扑结构。在图2中，节点G1、G2、G3、G4、G5、G6、G7、G8、G9、G10、G11、G12、G13、G14和G15的节点遍历度分别为6、5、4、5、5、5、6、5、6、7、5、5、5、6和7。
[0064] 据此可知，网络遍历度为4，G3为网络拓扑中心节点。
[0065] 对于复杂信息系统的统一授时，可在网络中心节点G3处部署网络时间主服务器(NTP)，经过4层分层授时，可以达到对整个系统的最精确授时，误差只经过4次累加，而网络时间主服务器部署在其他节点，误差累加不小于4次。
[0066] 对于复杂信息系统的网络防御，可有针对性的对网络中心节点G3进行重点防护，以防范敌方的网络攻击。
