一种基于总体布局的随机网络拓扑结构生成方法

摘要

本发明提供的是一种基于总体布局的随机网络拓扑结构生成方法。该方法使用随机数生成模拟随机网络，突出模拟网络的随机性，并对所生成的随机数进行控制，保证每次产生的模型网络从顶点分布到连接方式都不尽相同。本发明克服了随机网络拓扑很难贴近真实网络的缺点，生成一种更加贴近真实网络结构特性的网络拓扑。

主权项

一种基于总体布局的随机网络拓扑结构生成方法，其特征在于：设生成随机整数N,N>1为网络结点的数目，生成随机整数M为需要网络中边的数目，满足0<M≤(N×(N‑1))/2，否则重新生成M；使用N*N维矩阵G记录网络结点连接关系的拓扑图，矩阵中元素G_ij(1<i,j≤N)的值为0或者1，0表示网络结点i和结点j不存在连接通路，1表示网络结点i和结点j之间存在连接通路，任意两个结点间只保留一条连接通路；初始化矩阵G，使得矩阵G中所有元素的值为0；生成M对随机数{A₁,B₁}…{A_i,B_i}…{A_m,B_m}，其中A_i,B_i∈{1,2,...,N}且A_i≠B_i；{A_i,B_i}表示结点A_i和结点B_i间存在一条连接通路，填充矩阵G中的元素G_AiBi＝1；这样生成了一个随机网络拓扑图G，由于随机数中可能存在两对随机数{A_i,B_i},{A_j,B_j}有A_i＝B_j，B_i＝A_j的情况，这说明在生成的拓扑图中出现了两结点存在一条以上连通链路的情况，为此，将矩阵G中满足j小于等于i的所有元素G_ij置为0，然后计算矩阵G中1的个数NUM，此时NUM是已经生成的随机网络中连接边数；如果NUM<M，则生成M‑NUM对随机数，填充矩阵G，并将矩阵G中满足j小于等于i的所有元素G_ij置为0，再次计算矩阵G中1的个数NUM，如果NUM<M则重复本步骤直至NUM的值等于M；如果矩阵G中存在一行或一列的值均为0，即存在G_ij＝0(j＝1,2…n)或者G_ij＝0(i＝1,2….n)，表明结点i或者结点j不与其它结点连通，则将该结点删除，最终用矩阵G表示优化的网络拓扑结构，这样就生成了一种基于总体布局的网络拓扑结构；具体步骤为：(1)生成随机数N，用于表示网络结点数；(2)生成随机数M，用于表示网络中连接边数；(3)如果0<M≤(N×(N‑1))/2，则执行步骤4；否则执行步骤2；(4)初始化生成N*N维矩阵G，G中元素均为0；(5)初始化NUM＝0，用于表示矩阵G中元素1的个数；(6)生成随机数{A_i,B_i}；(7)如果满足条件A_i≠B_i，则执行步骤8；否则执行步骤6；(8)如果满足条件1≤A_i≤N，则执行步骤9；否则执行步骤6；(9)如果满足条件1≤B_i≤N，则执行步骤10；否则执行步骤6；(10)填充矩阵G中元素G_AiBi＝1；(11)将矩阵G中所有j小于等于i的元素G_ij置为0；(12)计算矩阵G中1的个数并保存在NUM中，如果NUM<M执行步骤6；否则执行步骤13；(13)如果矩阵G中存在G_ij＝0，对于j＝1,2…n，则删除矩阵中第i行；(14)如果矩阵G中存在G_ij＝0，对于i＝1,2….n则删除矩阵中第j列；(15)矩阵G中保存了基于总体布局的随机网络拓扑结构信息，生成程序结束。