基于模体的目标区域网络拓扑划分方法

摘要

本发明公开了基于模体的目标区域网络拓扑划分方法，包括：获取目标区域网络拓扑；将目标区域网络拓扑进行汇聚整理，形成路由器级网络拓扑；对得到的路由器级网络拓扑进行数据预处理；将预处理后的路由器级网络拓扑抽象成一个无权无向的网络拓扑图，在网络拓扑图中进行模体的挖掘；选取模体作为初始种子的候选，并进行合并剪枝，确定最终的初始种子集合；基于适应度函数F对初始种子集合进行扩展形成不相互重叠的社团结构；基于社团密度对社团进行扩展，确定单一路径上节点的归属社团；分别基于地标和IP地理信息数据库投票的方法，对划分的社团进行地理位置映射构建。本发明能够将网络中的大部分实体与地理位置映射起来，且准确率较高。

权利要求

1.基于模体的目标区域网络拓扑划分方法，其特征在于，包括以下步骤：步骤1、获取目标区域网络拓扑；

步骤2、将目标区域网络拓扑进行汇聚整理，将探测得到的IP级网络拓扑经过别名解析，形成路由器级网络拓扑；

步骤3、对得到的路由器级网络拓扑进行数据预处理：统计路由器级网络拓扑中所有节点的度，将与度较大节点相连的度为1的节点全部挑选出来，用与所述度为1的节点相连的度较大的节点替代度为1的节点；

步骤4、将预处理后的路由器级网络拓扑抽象成一个无权无向的网络拓扑图，在所述网络拓扑图中进行模体的挖掘；

步骤5、选取模体作为初始种子的候选，并进行合并剪枝，确定最终的初始种子集合；

步骤6、基于适应度函数F对初始种子集合进行扩展形成1个以上社团，删除重复的社团，形成不相互重叠的社团结构；

步骤7、基于社团密度对社团进行扩展，确定单一路径上节点的归属社团；

步骤8、分别基于地标和IP地理信息数据库投票的方法，将网络实体与地理位置对应，对划分的社团进行地理位置映射构建。

2.根据权利要求1所述的基于模体的目标区域网络拓扑划分方法，其特征在于，所述步骤4包括：

步骤4.1、将预处理后的路由器级网络拓扑抽象成一个无权无向的网络拓扑图，利用子图枚举的方法，在所述网络拓扑图中进行子图搜索，统计出各种子图出现的次数；

步骤4.2、根据步骤4.1中所述网络拓扑图，构建出多个与步骤4.1中所述网络拓扑图在整体统计特性相同的随机网络拓扑图；

步骤4.3、在构建的随机网络拓扑图上进行子图搜索，统计出各种子图出现的次数；

步骤4.4、对比相同子图在步骤4.1中所述网络拓扑图与在步骤4.3中所述随机网络拓扑图中出现的频次，将Z‑score>2且P‑value<0.01的子图认定为目标区域网络的模体。

3.根据权利要求1所述的基于模体的目标区域网络拓扑划分方法，其特征在于，所述步骤5包括：

步骤5.1、选定大小为4的模体作为初始种子的候选；

步骤5.2、将共享2个公共节点的模体合并为一个初始种子，将只共享1个公共节点的模体作为两个初始种子之间的桥节点。

4.根据权利要求1所述的基于模体的目标区域网络拓扑划分方法，其特征在于，所述步骤6包括：

步骤6.1、基于适应度函数F对初始种子集合进行扩展，对于与社团S相邻的每个节点v，分别计算社团S加入节点v后的适应度，然后将加入节点v后的适应度函数值与加入之前的适应度函数值做对比，判断向社团S中添加节点v是否会增加社团S的适应度，从而决定是否将节点v加入社团S，如果会增加社团S的适应度，则将节点v加入社团S，如果不会增加社团S的适应度，则不将节点v加入社团S；

步骤6.2、重复执行步骤6.1，直到社团S的邻居节点中不存在可以增加社团S的适应度的节点，终止并返回最终的社团S；

步骤6.3、删除重复的社团，形成不相互重叠的社团结构。

5.根据权利要求4所述的基于模体的目标区域网络拓扑划分方法，其特征在于，所述步骤7包括：

所述社团密度的计算公式为：

其中M表示社团S内部的边数，N表示加入节点v后社团S内部的节点数；

按照与社团S连接的顺序，依次将与社团S相连的单一路径上的度为1的节点加入到Sv v

中，计算节点的fd值，将fd值大于阈值α的节点加入到社团S中，得到最终的拓扑划分结果。

6.根据权利要求1所述的基于模体的目标区域网络拓扑划分方法，其特征在于，所述步骤8包括：

步骤8.1、执行网络拓扑测量时，将地理位置已知的地标作为探测的目标节点；

步骤8.2、基于IP地理信息数据库的映射构建方法，采用投票机制确定社团位置：通过在已知的IP地理信息数据库中查找每个社团内部节点的位置信息，每个节点根据自身的位置信息对该社团所处位置进行投票，将社团内多数节点一致的位置作为社团的地理位置，构建社团内各节点与地理位置的映射关系。

说明书

基于模体的目标区域网络拓扑划分方法

技术领域

[0001] 本发明涉及网络拓扑技术领域，尤其涉及基于模体的目标区域网络拓扑划分方法。

背景技术

[0002] 随着以Internet为代表的计算机通信与网络技术的飞速发展，人类社会的发展面临着巨大而深刻的变革，互联网已经与现代社会紧密相连，人们的工作、生活和娱乐，乃至
国家政务的运行、经济的发展都高度依赖互联网的安全运行。网络安全关乎国家安全，由于
互联网天生具有异构型、动态性和发展的非集中性等特点，再加上不断发展导致其规模越
来越庞大，为了确保网络的安全稳定运行，人们迫切的需要更好地掌控和管理互联网，而建
立网络实体与其地理位置准确的映射关系是实施网络管理的基础。

[0003] 互联网主要由多个网络服务提供商ISP(Internet Service Provider)负责运营和维护，可以通过分析数据报文在网络中各个节点间的路由转发情况，进而得到节点间的
逻辑连接关系，构成网络拓扑。

[0004] 互联网拓扑可以看作是一种典型的复杂网络，当前针对互联网拓扑连接关系的研究，主要也是运用复杂网络的相关知识来进行。随着对网络性质的物理意义及数学特性的
研究分析不断深入，研究发现包括互联网在内的许多复杂网络都有一个共同的性质，即社
团现象或者称为群聚现象。研究网络的社团结构有助于深入理解网络的组织结构和其所代
表的系统功能，论文(袁韶谦,赵海,张昕,等. Internet拓扑的社团结构分析[J].复杂系统
与复杂性科学,2007,4(3):17‑27.)就揭示了互联网AS级网络拓扑中的社团结构与AS地理
位置分布之间的关系。虽然表面上互联网拓扑中节点的连接大多数是自由选择的，但在地
区和国家区域划分的现实环境下存在相当强的局部聚集现象，说明互联网节点间的连接不
是随机建立的，节点更倾向于和局域的节点连接(张国清.互联网拓扑结构知识发现及其应
用[J].通信学报,2010,31(10):18‑25.)。钱学森先生也指出，相近区域内部之间的网络拓
扑呈现高度集群化的特征。

[0005] Tian等人(Tian Ye,Dey R,Liu Y,et al.Topology mapping and geolocating for China's Internet[J].IEEE Transactions on Parallel and Distributed 
Systems,2013, 24(9):1908‑1917)提出一种基于网络拓扑启发式聚类的网络拓扑映射和
地理定位方法(HC‑Based)，采用基于网络结构的集群划分对网络实体进行聚类，首次将基
于数据库查询和网络测量的两类IP定位方法结合起来，最终根据集群的地理位置构建映射
关系。然而，该方法聚类得到的集群往往节点数太少，且采用简单的投票规则会导致基于投
票结果的定位错误，因此最后建立的映射关系误差较大。 Liu等人(Liu S,Liu F,Zhao F,
et al.IP city‑level geolocation based on the PoP‑level network topology 
analysis[C]//International Conference on Information Communication and 
Management.IEEE,2016:109‑114.)将网络中的PoP结构作为网络拓扑划分的依据，认为PoP
结构是包括一系列具有强连接关系并且地理位置分布接近的节点的集合，它们相互之间构
成Bi‑fan结构，通过在网络中寻找具有紧密连接特性Bi‑fan结构的节点集合，然后将具有
重合部分的Bi‑fan集合合并，从而实现对网络拓扑的划分。但是他们没有具体分析所要研
究的网络结构中是否大量存在Bi‑fan结构，以及是否还存在其它的强连接性的节点集合，
因此算法具有很大的局限性。Li等人(Li M,Luo X,Shi W,et al.City‑level  IP 
geolocation based on network topology community detection[C]//International 
Conference on Information NETWORKING.IEEE,2017:578‑583.)提出一种基于网络节点
聚类的 NNC(Network Node Clustering)网络拓扑划分方法，将网络拓扑中的集群与复杂
网络理论中的社团对应起来，利用Louvain社团发现算法对网络拓扑中的节点进行聚类，采
用模块度衡量社团结构的强度，将网络拓扑划分为不同的社团进行分析。但是他们的方法
没有考虑互联网的具体拓扑特性，如使用模块度衡量社团结构强度，要求社团结构内部节
点之间具有密集的连接而外部节点之间的连接稀疏，但是通常互联网拓扑连接关系中构成
这种严苛社团条件的节点大多集中在骨干网上。

[0006] 互联网作为世界上最大的复杂网络，其发展受政治、经济等因素的影响较大，不同区域呈现发展的不均衡性，因此不同区域的网络拓扑其结构也是不相同的。现有的方法在
网络拓扑上划分社团的时候，均没有充分考虑到网络拓扑的具体结构特性，只能实现少部
分网络实体与地理位置的映射关系构建，并且在准确率上仍有提升的空间。

[0007] 随着真实世界中复杂网络的规模越来越大，对于网络的全局信息很难把握，一类基于网络局部信息的局部社团发现方法被发现更加适用于规模比较大的复杂网络，因为该
方法通常是对复杂网络中的初始种子进行扩散，只需要根据网络的局部信息就能进行社团
发现。互联网作为世界上最大的复杂网络，网络的整体特性难以把握，因此基于网络局部信
息的社团发现算法在互联网拓扑上更加适用。

[0008] 通过对已有的复杂网络局部社团发现方法的分析，发现初始种子节点的选取对社团扩散的最终结果起到了至关重要的作用。但是目前局部社团发现方法的初始种子选取一
般分为以下3类：

[0009] (1)随机选择节点作为初始种子；

[0010] (2)利用一些度量指标来选择中心节点作为初始种子；

[0011] (3)选择极大子图作为初始种子。

[0012] 通过分析，可以发现第一类初始种子选取方法会使得算法稳定性较差，通常要经过多次社团划分才能够得到比较好的划分结果；第二类初始种子选取方法，若仅仅选择单
个节点作为初始的种子，无法保证该节点真正处于社团的中心；第三类初始种子选取方法
在寻找极大子图时的算法复杂度较高，而且可能由于网络自身的稀疏性，满足极大子图的
结构在网络中并不显著出现，因此该方法较为苛刻，并不能确保挖掘出网络中所有的社团。

发明内容

[0013] 本发明针对现有方法考虑网络拓扑具体结构特性不足及现有的局部社团划分方法中初始种子选取存在的问题，提出将网络拓扑的“模体”作为初始种子，发明一种基于模
体的目标区域网络拓扑划分方法，本发明方法能够将网络中的大部分实体与地理位置映射
起来，并且准确率较高。

[0014] 为了实现上述目的，本发明采用以下技术方案：

[0015] 基于模体的目标区域网络拓扑划分方法，包括以下步骤：

[0016] 步骤1、获取目标区域网络拓扑；

[0017] 步骤2、将目标区域网络拓扑进行汇聚整理，将探测得到的IP级网络拓扑经过别名解析，形成路由器级网络拓扑；

[0018] 步骤3、对得到的路由器级网络拓扑进行数据预处理：统计路由器级网络拓扑中所有节点的度，将与度较大节点相连的度为1的节点全部挑选出来，用与所述度为1的节点相
连的度较大的节点替代度为1的节点；

[0019] 步骤4、将预处理后的路由器级网络拓扑抽象成一个无权无向的网络拓扑图，在所述网络拓扑图中进行模体的挖掘；

[0020] 步骤5、选取模体作为初始种子的候选，并进行合并剪枝，确定最终的初始种子集合；

[0021] 步骤6、基于适应度函数F对初始种子集合进行扩展形成1个以上社团，删除重复的社团，形成不相互重叠的社团结构；

[0022] 步骤7、基于社团密度对社团进行扩展，确定单一路径上节点的归属社团；

[0023] 步骤8、分别基于地标和IP地理信息数据库投票的方法，将网络实体与地理位置对应，对划分的社团进行地理位置映射构建。

[0024] 进一步地，所述步骤4包括：

[0025] 步骤4.1、将预处理后的路由器级网络拓扑抽象成一个无权无向的网络拓扑图，利用子图枚举的方法，在所述网络拓扑图中进行子图搜索，统计出各种子图出现的次数；

[0026] 步骤4.2、根据步骤4.1中所述网络拓扑图，构建出多个与步骤4.1中所述网络拓扑图在整体统计特性相同的随机网络拓扑图；

[0027] 步骤4.3、在构建的随机网络拓扑图上进行子图搜索，统计出各种子图出现的次数；

[0028] 步骤4.4、对比相同子图在步骤4.1中所述网络拓扑图与在步骤4.3中所述随机网络拓扑图中出现的频次，将Z‑score>2且P‑value<0.01的子图认定为目标区域网络的模体。

[0029] 进一步地，所述步骤5包括：

[0030] 步骤5.1、选定大小为4的模体作为初始种子的候选；

[0031] 步骤5.2、将共享2个公共节点的模体合并为一个初始种子，将只共享1个公共节点的模体作为两个初始种子之间的桥节点。

[0032] 进一步地，所述步骤6包括：

[0033] 步骤6.1、基于适应度函数F对初始种子集合进行扩展，对于与社团S相邻的每个节点v，分别计算社团S加入节点v后的适应度，然后将加入节点v后的适应度函数值与加入之
前的适应度函数值做对比，判断向社团S中添加节点v 是否会增加社团S的适应度，从而决
定是否将节点v加入社团S，如果会增加社团S的适应度，则将节点v加入社团S，如果不会增
加社团S的适应度，则不将节点v加入社团S；

[0034] 步骤6.2、重复执行步骤6.1，直到社团S的邻居节点中不存在可以增加社团 S的适应度的节点，终止并返回最终的社团S；

[0035] 步骤6.3、删除重复的社团，形成不相互重叠的社团结构。

[0036] 进一步地，所述步骤7包括：

[0037] 所述社团密度的计算公式为：

[0038]

[0039] 其中M表示社团S内部的边数，N表示加入节点v后社团S内部的节点数；

[0040] 按照与社团S连接的顺序，依次将与社团S相连的单一路径上的度为1的节点加入v v
到S中，计算节点的fd 值，将fd值大于阈值α的节点加入到社团S 中，得到最终的拓扑划分
结果。

[0041] 进一步地，所述步骤8包括：

[0042] 步骤8.1、执行网络拓扑测量时，将地理位置已知的地标作为探测的目标节点；

[0043] 步骤8.2、基于IP地理信息数据库的映射构建方法，采用基于投票机制确定社团位置：通过在已知的IP地理信息数据库中查找每个社团内部节点的位置信息，每个节点根据
自身的位置信息对该社团所处位置进行投票，将社团内多数节点一致的位置作为社团的地
理位置，构建社团内各节点与地理位置的映射关系。

[0044] 与现有技术相比，本发明具有的有益效果：

[0045] 本发明以目标区域网络拓扑划分为研究对象，充分考虑目标区域网络拓扑的结构特性，首先在网络拓扑中挖掘模体，通过模体的合并剪枝组成初始种子集合，然后利用适应
度函数进行扩展，并且考虑网络中单一路径上节点的特性，提出基于社团密度的社团扩展，
尽可能的将更多的节点划入社团，最后分别基于社团中地标和已知IP地理信息数据库投票
的方法，将网络实体与地理位置对应起来，对划分的社团进行地理位置映射构建。通过大量
的实验得出，对于网络拓扑划分来说，本发明的方法更加合理，不仅能够将更多的节点与地
理位置映射起来，而且准确率更高。

附图说明

[0046] 图1为本发明实施例的基于模体的目标区域网络拓扑划分方法的基本流程示意图。

[0047] 图2为本发明实施例所选的实验对象，香港地区 、台湾地区路由器级网络拓扑的Gephi可视化结果图。

[0048] 图3为本发明实施例所选的实验对象，台湾地区路由器级网络拓扑中的“降落伞”现象示意图。

[0049] 图4为本发明实施例所选的实验对象，数据预处理之后去除“降落伞”结构的香港地区 与台湾地区的网络拓扑图。

[0050] 图5为本发明实施例基于适应度函数F扩展的社团S的理想化表示示意图；其中，椭圆虚线圈里的节点是初始种子模体通过Fs扩张而得到的社团S，直虚线所示的边将社团节
点与其邻居节点连接起来。

[0051] 图6为本发明实施例所选的实验对象，台湾地区路由器级网络拓扑结构中的单一路径的Gephi可视化结果图。

具体实施方式

[0052] 下面结合附图和具体的实施例对本发明做进一步的解释说明：

[0053] 实施例一：

[0054] 如图1所示，本发明的一种基于模体的目标区域网络拓扑划分方法，包括以下步骤：

[0055] 步骤S101：获取目标区域网络拓扑；

[0056] 作为一种可实施方式，获取目标区域网络拓扑使用的数据来自于2017年2 月CAIDA的ITDK ipv4数据集，ITDK ipv4数据集是由分布在42个国家和地区 的120 个探测点
基于Traceroute原理，对全球Internet进行探测得到的数据，数据可信度较高。提取ITDK 
ipv4数据集中的节点信息，得到目标区域网络拓扑。

[0057] 步骤S102：将目标区域网络拓扑进行汇聚整理，形成路由器级网络拓扑：将探测得到的IP级网络拓扑经过别名解析，形成路由器级网络拓扑；

[0058] 由于IP地址的动态性和可变性等特点，无法根据IP级网络拓扑形成相对稳定的拓扑连接映射，因此需要将研究对象聚焦在路由器级网络拓扑上，将探测得到的IP级网络拓
扑经过别名解析，初步整理形成路由器级网络拓扑。

[0059] 步骤S103：对得到的路由器级网络拓扑进行数据预处理：统计路由器级网络拓扑中所有节点的度，将与度较大节点相连的度为1的节点全部挑选出来，用与所述度为1的节
点相连的度较大的节点替代度为1的节点；

[0060] 将目标区域路由器级网络拓扑抽象为无权无向的复杂网络拓扑图，节点v 表示拓扑网络中的路由器，节点与节点之间的边e表示这两个路由器相邻(也就是相隔一跳的距
离)。分别利用Gephi软件进行可视化，在两个网络中均发现存在许多的“降落伞”现象，也就
是一个度比较大的节点连接许多度为1的叶子节点。这样的“降落伞”现象在网络拓扑中普
遍存在，继而在包括美国、日本、韩国等11个其它不同区域的路由器级网络拓扑进行可视化
时，也都发现了这样的现象。

[0061] 对于目标区域网络的社团划分来说，更关注于对那些连接复杂、难以直接确定归属于哪一地区的节点进行分析，而“降落伞”结构是一个极大的干扰，因此需要对数据进行
初步的预处理。数据预处理的过程就是将原始网络拓扑中的“降落伞”现象合理消除的过
程。

[0062] 步骤S104：将预处理后的路由器级网络拓扑抽象成一个无权无向的网络拓扑图，在该网络拓扑图中进行模体的挖掘；

[0063] 所述步骤S104包括：

[0064] 步骤S104.1：将预处理后的路由器级网络拓扑抽象成一个无权无向的网络拓扑图，利用子图枚举的方法，在该网络拓扑图中进行子图搜索，统计出各种子图出现的次数。

[0065] 步骤S104.2：根据步骤S104.1中网络拓扑图，构建出多个与步骤S104.1中网络拓扑图在整体统计特性相同的随机网络拓扑图。

[0066] 步骤S104.3：在构建的随机网络拓扑图上进行子图搜索，统计出各种子图出现的次数。

[0067] 步骤S104.4：对比相同子图在步骤S104.1中网络拓扑图与在步骤S104.3中随机网络拓扑图中出现的频次，将Z‑score>2且P‑value<0.01的子图认定为目标区域网络的模体。

[0068] 步骤S105：选取模体作为初始种子的候选，并进行合并剪枝，确定最终的初始种子集合；

[0069] 所述步骤S105包括：

[0070] 步骤S105.1：选定大小为4的模体作为初始种子的候选。

[0071] 步骤S105.2：将共享2个公共节点的模体合并为一个初始种子，将只共享1 个公共节点的模体作为两个初始种子之间的桥节点；

[0072] 由于真实网络数据中会出现一些模体共享某些节点，或者会出现一些模体是另一些模体的子集情况。因此将共享2个公共节点的模体合并为一个初始种子，大大的减少需要
扩展的初始种子的数量。只共享1个公共节点的模体，将其作为两个初始种子之间的桥节点
对待。

[0073] 步骤S106：基于适应度函数F对初始种子集合进行扩展形成1个以上社团，删除重复的社团，形成不相互重叠的社团结构，包括：

[0074] 步骤S106.1：基于适应度函数F对初始种子集合中进行扩展，对于与社团S 相邻的每个节点v，分别计算社团S加入节点v后的适应度，然后将加入节点v 后的适应度函数值与
加入之前的适应度函数值做对比，判断向社团S中添加节点 v是否会增加社团S的适应度，
从而决定是否将节点v加入社团S，如果会增加社团S的适应度，则将节点v加入社团S，如果
不会增加社团S的适应度，则不将节点v加入社团S；

[0075] 步骤S106.2：重复执行步骤S106.1，直到社团S的邻居节点中不存在可以增加社团S的适应度的节点，终止并返回最终的社团S。

[0076] 步骤S107：基于社团密度对社团进行扩展，确定单一路径上节点的归属社团；

[0077] 基于Traceroute原理探测得到的网络拓扑图，其实质是由多条探测路径构成的网络，显示在拓扑结构上，就会出现许多不交叉互连的单一路径，这种情况大多会发生在骨干
路由器以及网络边界路由器上。为了解决这类节点的划分问题，基于社团密度进行再次扩
展，在保证社团密度稳定的同时，最大可能的确定这些节点的归属社团。采用的社团密度的
公式为：

[0078]

[0079] 其中M表示社团S内部的边数，N表示加入节点v后社团S内部的节点数。

[0080] 按照与社团S连接的顺序，依次将与社团S相连的单一路径上的度为1的节点加入v v
到S中，计算节点的fd 值，将fd值大于阈值α的节点加入到社团S 中，得到最终的拓扑划分
结果。

[0081] 步骤S108：分别基于地标和IP地理信息数据库投票的方法，将网络实体与地理位置对应，对划分的社团进行地理位置映射构建。

[0082] 所述步骤S108包括：

[0083] 步骤S108.1：执行网络拓扑测量时，将地理位置已知的地标作为探测的目标节点；

[0084] 在执行网络拓扑测量的时候，就有选择的将一些地理位置已知的地标作为探测的目标节点，这样在最后划分的社团中就会有地标的存在，可以根据地标来确定社团结构的
可能位置。

[0085] 步骤S108.2：基于IP地理信息数据库的映射构建方法，采用基于投票机制确定社团位置：通过在已知的多个IP地理信息数据库中查找每个社团内部节点的位置信息，每个
节点根据自身的位置信息对该社团所处位置进行投票，将社团内多数节点一致的位置作为
社团的地理位置，构建社团节点与地理位置的映射关系。

[0086] 作为一种可实施方式，多个IP地理信息数据库为MaxMind、IP2Location、 Ipligence、HostIP、Netacuity、Geobytes、纯真IP数据库及淘宝IP地址库。

[0087] 本发明以目标区域网络拓扑划分为研究对象，充分考虑目标区域网络拓扑的结构特性，首先在网络拓扑中挖掘模体，通过模体的合并剪枝组成初始种子集合，然后利用适应
度函数进行扩展，并且考虑网络中单一路径上节点的特性，提出基于社团密度的社团扩展，
尽可能的将更多的节点划入社团，最后分别基于社团中地标和已知IP地理信息数据库投票
的方法，将网络实体与地理位置对应起来，对划分的社团进行地理位置映射构建。通过大量
的实验得出，对于网络拓扑划分来说，本发明的方法更加合理，不仅能够将更多的节点与地
理位置映射起来，而且准确率更高。

[0088] 实施例二：

[0089] 本发明的另一种基于模体的目标区域网络拓扑划分方法，包括：

[0090] 步骤S201：获取台湾地区 和香港地区的节点信息，得到目标区域网络拓扑：

[0091] 本实施例使用的数据来自于2017年2月CAIDA的ITDK ipv4数据集，ITDK ipv4数据集是由分布在42个国家和地区 的120个探测点基于Traceroute原理，对全球 Internet进
行探测得到的数据，数据可信度较高。提取ITDK ipv4数据集中明确标注位于台湾地区 和
香港地区的节点信息，得到目标区域网络拓扑。

[0092] 步骤S202：将目标区域网络拓扑进行汇聚整理，形成香港地区 和台湾地区 的路由器级网络拓扑：

[0093] 由于IP地址的动态性和可变性等特点，无法形成相对稳定的拓扑连接映射，因此以路由器级网络拓扑作为研究对象，将探测得到的IP级网络拓扑经过别名解析，初步整理
形成路由器级网络拓扑。

[0094] 具体地，本发明提取ITDK ipv4数据集中明确标注位于台湾地区 和香港地区的节点信息，经过汇聚整理得到目标区域网络拓扑的路由器级拓扑连接。

[0095] 步骤S203：对得到的香港地区 和台湾地区 的路由器级网络拓扑进行数据预处理：

[0096] 将两个地区路由器级网络拓扑抽象成两个复杂网络拓扑图，节点v表示拓扑网络中的路由器，节点与节点之间的边e表示这两个路由器相邻(也就是相隔一跳的距离)。分别
利用Gephi软件进行可视化，在两个网络中均发现存在许多的“降落伞”现象，也就是一个度
比较大的节点连接许多度为1的叶子节点。如图 2所示，两幅图中大量的黑色节点团，就是
许多度为1的节点大量聚集形成的。这样的“降落伞”现象在网络拓扑中普遍存在，我们继而
在包括美国、日本、韩国等11个其它不同区域的路由器级网络拓扑进行可视化时，也都发现
了这样的现象。

[0097] 图3为台湾地区网络拓扑中“降落伞”现象的具体展示，图中颜色较深的黑色小团就是这样的节点团。本发明首先更关注于对连接复杂、难以直接确定归属于哪一地区的节
点进行分析，“降落伞”结构是一个极大的干扰，因此需要对数据进行初步的预处理。数据预
处理的过程就是将原始网络拓扑中的“降落伞”现象合理消除的过程。

[0098] 统计拓扑网络中所有节点的度，将与度较大节点相连的度为1的节点全部挑选出来，将之折叠合并，用与它们相连的度较大的节点替代它们。采取这样的替换方法，是基于
对网络拓扑的认识决定的，大量的仅与一个节点相连的节点，其拓扑性质取决于这个相连
的节点。图4为数据预处理后的香港地区 与台湾地区的网络拓扑图，图中颜色较深的黑色
小团是连接紧密的节点，可以看出网络呈现出明显的抱团现象。

[0099] 步骤S204：在预处理后的香港地区 和台湾地区 的路由器级网络拓扑图上进行模体挖掘；

[0100] 所述步骤S204包括：

[0101] 步骤S204.1：将预处理过的香港地区 和台湾地区路由器级网络拓扑看作是无权无向的图，首先利用子图枚举的方法，在图中进行模体的挖掘，将Z‑score>2且P‑value<
0.01的子图认定为目标网络的模体；

[0102] 步骤S204.2：对基于初始种子进行扩展的局部社团发现算法来说，初始种子的选择对结果的影响很大。而针对目标区域网络进行模体挖掘，根据设定的模体大小的不同，挖
掘出来的模体也不相同，而且即使设定同样的大小，在实际网络中挖掘出来的子图结构符
合模体选择标准的也不止一个，因此选择合适大小、合理结构的模体作为初始种子的候选
就成为这个问题的关键所在。

[0103] 一个模体，如果该模体被接受为初始种子的候选，那么其需要满足一些基本的条件：

[0104] 一方面，模体大小应该足够大，以便任何更大的网络区域可以作为社团被发现出来，否则基于初始种子进行扩展时，就有可能将没有社团结构的网络区域扩展进社团，而得
到错误的结果。例如，如果模体大小选择为3节点的子图，那么三角形就可以被接受成为种
子，但是在某些网络中，不是所有的三角形都在社团里面。在这种情况下，就会将那些没有
在任何社团里面的三角形作为种子，最终出现错误。

[0105] 另一方面，模体大小也应该足够小，以便所有希望检测到的社团都至少包含一个模体。如果选择的模体大小太大，那么那些不包含模体的小的社团结构就不会被检测到，这
种情况也是不被允许的。

[0106] 值得说明的是，模体大小指的是模体包含的节点个数。

[0107] 通过分析挖掘出来的模体，结合网络实际特性，本发明将大小为4的模体作为初始种子的候选。这也与之前学者的研究成果(Lee C,Reid F,Mcdaid A,et al. Detecting 
highly overlapping community structure by greedy clique expansion[J]. 2010.)
(尚明生,陈端兵,周涛.Detecting Overlapping Communities Based on Community 
Cores in Complex Networks[J].中国物理快报:英文版,2010, 27(5):264‑267.)相匹配。

[0108] 表1为香港地区网络拓扑中的大小为4的模体，其中Frequency[Original]为模体在目标网络拓扑图中出现的频率；Mean‑Freq[Random]为模体在生成的所有随机网络拓扑
图中出现的频率；Standard‑Dev[Random]为模体在生成的所有随机网络拓扑图中出现频率
的标准差；Z‑Score和p‑Value分别为Z值和P值，均为衡量模体重要性的指标。

[0109] 表1香港地区网络拓扑中的大小为4的模体

[0110]

[0111] 表2为台湾地区网络拓扑中大小为4的模体。

[0112] 表2台湾地区网络拓扑中大小为4的模体

[0113]

[0114] 步骤S205：将模体合并剪枝，形成初始种子集合：

[0115] 真实网络数据中会出现一些模体共享某些节点，或者会出现一些模体是另一些模体的子集情况。如果不加以合并剪枝，直接将所有的模体作为初始种子结构，那么通过这些
模体最后扩展所得到的社团结构也几乎相同。本发明将共享2个公共节点的模体合并为一
个初始种子，大大的减少了需要扩展的初始种子的数量。至于只共享1个公共节点的模体，
将其作为两个初始种子之间的桥节点对待，实际网络中相当于连接两个不同区域网络拓扑
的骨干节点，在扩展时暂不作考虑。通过将共享重复节点模体进行合并剪枝，从而在不影响
实验结果的同时，显著节省内存开销并且缩减算法的计算时间。

[0116] 步骤S206：利用适应度函数F，在预处理后的网络拓扑关系图上，进行基于模体的社团发现，删除重复的社团，形成不相互重叠的社团结构：

[0117] 初始种子的结构确定以后，需要对初始种子进行相应扩展，从而得到社团结构。本发明采用Lancichinetti等人定义的适应度函数F，根据社团S的节点内部度 和外部度
来定义社团S的适应度，如下式所示。其中 等于开始和结束都在S中的边的数量的两倍
(即为S中内部节点的度之和)，而 是仅有一端在社团S中的边数量。适应度函数Fs定义
为：

[0118]

[0119] σ是一个可以调整的参数，是一个正实数，用来控制社团的规模。在香港地区取σ值为1.1，在台湾地区取σ得值为1.0，最终划分的社团结果比较理想。

[0120] 此外，为了确定一个节点v能否被加入到社团，还需定义一个节点测度 如下式所示：

[0121]

[0122] 判断节点v能否加入到社团S的标准是 当 时，表示节点v的加入能够使社团S的适应性度量增大。

[0123] 所述步骤S206具体操作步骤包括：

[0124] 步骤S206.1：对于与社团S相邻的每个节点v，即图5中椭圆虚线圈外与圈内用直虚线连接的节点，分别计算社团S加入v后的适应度；

[0125] 步骤S206.2：判断 是否成立，即向社团S中添加v是否会增加S的适应度；

[0126] 步骤S206.3：选择使适应度增量最大的节点Vmax，将其加入社团S；

[0127] 步骤S206.4：循环执行步骤S206.1至步骤S206.3，直到社团S的邻居节点中没有满足步骤S206.2的节点，终止并返回最终的社团S；

[0128] 步骤S206.5：因为步骤S206.1至步骤S206.4的初始种子扩展策略，在理论上只要社团S的邻居节点v的测度 社团S就会一直扩展下去。这样在网络中两个距离很近的
初始种子，在扩展形成社团S1和S2的过程中，就可能将对方的节点当做自己的节点划入到自
己一边，就会形成近似重复的社团。从网络拓扑分析的角度来看，这是不可取的，所以本发
明将这些近似重复的社团合并为一个社团，因为我们认为合并后其内部的连接程度也足够
紧密(都是基于Fs扩展得到的)，达到成为社团的标准。

[0129] 步骤S207：针对拓扑中存在的单一路径的现象，提出基于社团密度的社团扩展，最大可能的将单一路径上的节点划入社团。

[0130] 所述步骤S207包括：

[0131] 基于Traceroute原理探测得到的网络拓扑图，其实质是多条的探测路径构成的网络。针对同一探测目标，从不同的探测源返回的路径结果，其共同之处就是会经过探测目标
所在网络的边界路由器或者该地区网络的骨干路由器，因此显示在拓扑结构上，就会出现
许多不交叉互连的单一路径，这种情况大多会发生在骨干路由器以及网络边界路由器上，
如图6所示。

[0132] 对于此类单一路径上的节点，一部分是进行网络测量时选择的目标节点，这样的节点在预处理前的网络中其节点的度也为1，且因为直接与社团S中的节点相连，可以直接
并入社团S。但是还有部分节点则是在数据预处理过程中经过折叠合并其叶子节点后所得
到特殊节点，它们经过单一路径到达社团的路径长度大于1，在真实网络拓扑中显示的是
“降落伞”结构，往往是可以单独代表一个小范围的区域网络拓扑结构的，也就是自身就可
以代表一个社团。在研究目标网络拓扑中发现，探测所得到的路由器级网络拓扑连接中，哪
怕只相隔一跳的距离(路径长度为1)，在现实距离中也可能相隔很远，因此不能够简单的将
与S相连的所有单一路径上的节点直接与S进行合并。

[0133] 为了解决这类节点的划分问题，本发明提出基于社团密度的再次扩展方法，最大可能的确定这些节点的归属社团。采用的社团密度的公式为：

[0134]

[0135] 其中M表示社团S内部的边数，N表示加入节点v后社团S内部的节点数，fdv为加入节点v后社团S的社团密度。

[0136] 依次按照与社团S连接的顺序，将与社团S相连的带有“降落伞”结构的单一路径上v v
的节点加入到S中，计算节点的fd 值，将fd值大于阈值α的节点加入到社团S中，得到最终的
拓扑划分结果。α的值影响最终划分社团结果S的准确性，本发明计算了经过初始扩展后得
到的所有S的社团密度，取其中的最小值作为α的最终取值。基于此的考虑是，经过前面初始
种子扩展以及将与社团直接相连的路径长度(度)为1的节点并入到S中后，S已经得到了充
分的扩展，极限情况下已经没有与之相连的简单路径了，而且α选取S中的最小社团密度的
值，可以将最终所得的网络拓扑划分结果S的密度统一起来，更有利于分析对比不同区域网
络拓扑结构的差异性。

[0137] 最后将没有划入到任何S的“降落伞”结构节点分别单独归为一个社团，正如前面分析的一样，它往往可以单独代表一个小范围的区域网络拓扑结构，可以为网络实体的定
位分析以及分析其所处地域的网络拓扑状况提供相应的支撑。

[0138] 步骤S208：通过上述步骤得到最终划分的社团结果，分别利用基于地标和基于已知IP地理信息数据库的方法，对划分的社团进行地理位置投票，构建社团与地理位置的映
射关系。

[0139] 所述步骤S208包括：

[0140] 步骤S208.1：基于地标的社团与地理位置的映射关系构建比较简单，在执行网络拓扑测量的时候，有选择的将一些地理位置已知的地标作为探测的目标节点，这样在最后
划分的社团中就会有地标的存在，就可以根据地标来确定社团结构的位置。

[0141] 步骤S208.2：基于地理信息数据库的映射构建方法，采用基于投票机制的社团位置定位。通过在已知的多个IP地址信息库里面，最大可能的查找每个社团内部路由器节点
的位置信息，然后每个节点根据自身的位置信息对该社团所处位置进行投票，将社团内多
数节点一致的位置作为社团的地理位置，构建社团节点与地理位置的映射关系。

[0142] 作为一种可实施方式，多个IP地理信息数据库为MaxMind、IP2Location、 Ipligence、HostIP、Netacuity、Geobytes、纯真IP数据库及淘宝IP地址库。

[0143] 基于香港地区 和台湾地区的网络拓扑划分结果对本发明做详细介绍：

[0144] 本发明引入生物学网络中“模体”的概念，提出将从网络中挖掘出来的模体作为扩展的初始种子。是因为模体是复杂网络中显著出现的、相互作用的特征模式，较之于具有相
同全局统计特性的随机网络，模体在原始网络中更为常见，被定义为经常性和统计上显著
的子图或模式。具体而言，模体就是在网络中大量反复出现的具有相同结构的小规模子图，
这些子图从局部微观层次刻画了复杂网络内部相互连接的特定模式，揭示的是复杂网络的
基础信息结构或基本构建模块，在一定程度上可以视作为该网络所特有的基础结构，能够
体现网络的局部特性。

[0145] 而实际上已有的众多基于网络局部信息的社团发现方法，大多都是分为两个步骤：第一步进行初始种子的选取；第二步对初始种子进行扩散和设置终止扩散的条件。由于
初始种子的选取对网络最终社团划分的影响非常大，因此必须科学合理的选择初始种子，
所以本发明引入生物学网络中“模体”的概念，提出将从网络中挖掘出来的模体作为扩展的
初始种子。

[0146] 本发明研究的内容是目标区域网络拓扑划分方法。之所以局限于目标区域网络拓扑，主要有两点考虑：

[0147] 考虑1：获得准确、全面的拓扑连接关系是进行网络拓扑分析的基础，当前虽然有许多个人和组织长期致力于互联网拓扑的测量与分析，但是由于技术以及资金投入的限
制，他们所得到的网络拓扑是不完整的，即想要全面获取整个全球的互联网拓扑，这是不现
实的事情。

[0148] 考虑2：互联网天生具有异构性以及区域发展的不均衡性等特点，各个地区由于经济、政治等种种原因，其网络的构建方式是不同的，发展规模和水平也不在一个层次，整个
网络的整体特性不能完全代表局部区域网络的特性，因此笼统的混在一起研究是不可取
的。

[0149] 因此本发明着力于研究特定目标区域的网络拓扑，不仅具有现实可行性，而且更加的具有针对性，但不代表本发明不能适用于其它类型复杂网络。

[0150] 为了评估本发明的先进性，分别从划分的社团数量、划入社团的节点数量、社团映射准确率和节点映射准确率4个方面，将本发明与已有的经典HC‑Based (基于网络拓扑启
发式聚类的IP定位算法)方法以及NNC(Network Node Clustering)方法进行比较分析。

[0151] 划分的社团数量指最终在目标区域网络拓扑上发现的社团个数，划入社团的节点数量指最终所有社团中包含的节点的数目。这两个指标结合起来分析，可以有效地衡量网
络拓扑社团划分的粒度。因为网络拓扑限定在目标区域范围内，在很大程度上就已经缩小
了其内部社团结构的数量，毕竟目标区域内人口聚集的邻近区域是可数的，理想情况下就
是划分社团的数量与目标区域内人口聚集的区域数量相当。如果算法划分的社团数量太
多，那么相应每个社团内部的节点数量就会很少，就会将临近区域内的网络拓扑更细粒度
的划分，从而产生大量位于同一区域的社团，导致重复性的工作；如果社团划分数量太少，
就会将属于不同区域内的网络拓扑节点误认为在同一个区域，导致错误的结果。在划分的
社团数量以及划入社团的节点数量方面，三种方法的结果如表3所示。

[0152] 表3三种方法对社团划分数量以及划分的节点数的比较

[0153]

[0154] 由表3可以看出，本发明的方法无论是在社团划分数量还是划入社团的节点数量方面，都具有优势。

[0155] 社团映射准确率方面，主要是在最后构建社团结构与地理位置映射关系的结果上进行对比分析。分别采用基于地标的映射构建和基于公开IP地址信息库的映射构建两种方
法，对三种方法划分的社团结构进行地理位置映射构建。若两种映射构建方法确定的社团
结构地理位置相同，则认为映射关系构建准确；若两种方法确定的社团结构地理位置不同，
则认为映射关系构建错误；对于两种方法都不能确定位置的社团结构，则将其视为未确定
映射关系的社团，也认定为映射关系构建错误。最后将准确率设定为映射关系构建正确的
社团数量与总的社团数量的比值，因此准确率越高，表明方法的效果越好。三种方法的结果
如表4所示。

[0156] 表4三种方法的社团映射准确率对比

[0157]

[0158] 由表4可以看出，本发明的方法在两个地区网络拓扑的实验中，均能够取得较高的准确率，尤其是在未确定区域位置的社团数量上面，本发明的方法明显比其它两种方法要
少很多，在映射关系构建错误的社团数量上面，本发明的方法也有明显的优势。

[0159] 节点映射准确率方面，还进一步统计了映射构建正确的社团里面节点的总数量，可以用来说明哪种方法能够准确地将更多的网络实体与地理位置对应起来，结果如表5所
示。

[0160] 表5三种方法的节点映射准确率对比

[0161]

[0162] 表5的结果表明，本发明的方法能够将更多的网络实体与地理位置映射起来。

[0163] 本发明以目标区域网络拓扑划分为研究对象，充分考虑目标区域网络拓扑的结构特性，首先在网络拓扑中挖掘模体，通过模体的合并剪枝组成初始种子集合，然后利用适应
度函数进行扩展，并且考虑网络中单一路径上节点的特性，提出基于社团密度的社团扩展，
尽可能的将更多的节点划入社团，最后分别基于社团中地标和已知IP地理信息数据库投票
的方法，将网络实体与地理位置对应起来，对划分的社团进行地理位置映射构建。通过大量
的实验得出，对于网络拓扑划分来说，本发明的方法更加合理，不仅能够将更多的节点与地
理位置映射起来，而且准确率更高。

[0164] 以上所示仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应
视为本发明的保护范围。