一种面向大规模网络的拓扑抽样方法

摘要

一种面向大规模网络的拓扑抽样方法，包括有向网络和无向网络。本方法首先将大规模网络拓扑以源节点字段和目标节点字段的形式存储在数据库中；然后选择初始源节点。以此节点开始，根据网络范围控制算法，扫描数据库，记录与该节点直接连接的目标节点，从中选择有效的目标节点加入队列，并根据连接控制算法记录连接，然后根据拓扑连通控制算法控制采样结果的连通性。本发明可以提供一种面向大规模网络的拓扑抽取方法，通过该方法抽样得到的网络拓扑，即不丢失大规模网络的拓扑特征，又可以作为大规模网络拓扑的代表，为用户提供一种适于细粒度算法分析、且可计算机程序实现的抽样结果，解决了大规模网络拓扑无法直接进行细粒度量化分析的问题。

主权项

一种面向大规模网络的拓扑抽样方法，其特征在于包括以下工艺步骤：（1）将大规模网络拓扑测量结果形成数据库；（2）确定拓扑初始节点，抽样的初始节点可以通过随机方式随取，也可以由用户指定；（3）从初始节点开始，扫描并记录直接连接节点,根据网络范围控制算法控制抽样拓扑覆盖的网络范围，以使抽样拓扑结果尽可能覆盖较大范围网络，并将符合要求的节点记录在拓扑抽样结果中；（4）控制拓扑中的连接，对抽样的节点，记录其所有连接，包括有向连接和无向连接；并将符合要求的连接记录在拓扑抽样结果中；（5）检查并控制抽样拓扑结果的连通性；（6）重复(2)‑(5)步骤，直到拓扑抽样结果大小达到给定规模，将其生成邻接矩阵并输出。