一种生成稀疏无向连通随机图的方法

摘要

一种生成稀疏无向连通随机图的方法，研究对象隶属于无向图中的，连通且稀疏的，给定顶点平均度d和顶点数量n情况下，随机图的生成问题。本发明针对该随机图生成问题，提出了一种两阶段的生成方法(Dual Stage Construction Algorithm，DSCA)，首先随机生成一个包含n个顶点的树，之后再在树的基础上随机添加一定数量的边，边的数量要满足给定的顶点平均度的要求。本发明的一种生成稀疏无向连通随机图的方法，首先随机生成支撑树，再在支撑树的基础上随机添加一定数量的边，借此得到无向连通随机图。此发明的方法解决了快速随机生成稀疏的无向连通图的问题。

说明书

技术领域

本发明涉及一种图的生成方法。特别是涉及一种生成稀疏无向连通随机图的方法。

背景技术

网络(Network)是一系列有关联的个体组成的系统，现实世界中的许多系统可以用网络 来表示，例如通信网络、社交网络，以及电力网络等等。网络可以用N＝(V,E,C,W)来表示， 其中V代表N中的顶点的集合，E代表N中的边的集合，C则代表N中边的权值，W代表N 中顶点的权值。当不考虑C与W时，G＝(V,E)称为图。以电网为例，发电机(电源点)与 变电站(负荷点)等可以看作电力网络中的顶点，电力线路则是电力网络中的边，边权为电 力线路的阻抗等，点权是负荷的功率或发电机的出力等。考虑，多数研究无法在实际电网上 进行，只能利用仿真工具进行模拟。当研究者提出某种新算法后，可能无法得到大量的电网 模型作为算例，往往只能进行“casestudy”，无法说明算法的普遍适用性。为解决这一算例不 足的问题，可以借助于随机网络，即利用与实际网络主要特征基本相同的大量随机网络来近 似替代实际网络作为算例。然而不同领域的网络的点权和边权有不同的处理方法，所以，本 文仅讨论如何快速有效生成随机图的问题。

上世纪50年代末，两位匈牙利数学家和Rényi建立了随机图理论。在随机图模型 中(ER模型)，任意两个顶点之间有一条边相连接的概率均为p，所以一个含有n个顶点的 随机图中边的总数的期望值是p[n(n-1)/2]。在此基础上，学者们在很多角度上对随机图进行 了深入的研究。平均顶点度(AverageDegree，AD)、度分布(DegreeDistribution，DD)等 是用来描述图的特征的两个常用指标。其中，AD是研究最多也是最重要的指标之一。不同 网络的特征之间存在差异，孟仲伟等人计算了中国北方高压输电网的AD为2.23；Watts的美 国西部电网的AD则为2.67。相比之下，不同领域的网络之间差异更大，Newman给出的自 治系统层Internet网络的AD为5.98。模型时需要针对不同领域网络的特性有针对性的生成随 机图。而按照传统的随机图生成算法，所得到的随机图的AD是以p(n-1)为期望的随机数， 故而无法准确控制生成图的AD。所以在建立随机网络模型时需要针对不同领域网络的特性 有针对性的生成随机图。而按照传统的随机图生成算法，所得到的随机图的AD是以p(n-1) 为期望随机数，故而无法准确控制生成图的AD。对此，刘克俭等人^[7]提出了精确平均点度 (ExactAverageDegree，EAD)的概念，该模型的AD收敛性要强于传统随机图模型，但也 无法达到精确控制生成的随机图AD的程度。

除此之外，所生成的随机图的连通性也是一大研究热点。实际网络中，相互连通的顶点 之间才可能产生直接或间接的影响，例如中国正在建立区域互联电网，所以研究连通的随机 图具有实际意义。传统的ER模型中，当要生成的随机图时稀疏图，即p较小时(小于一个 临界值lnn/n)，生成图往往是不连通的，所以就需要进行多次重复直到生成的随机图连通为 止^[1]，故而效率很低。文献NobariE，LuXS，KarrasP，andBressanS.Fastrandomgraph generation[C].ACMInternationalConferenceProceedingSeries，Uppsala，Sweden，2011， 331-342.对ER模型做出了一些改进，此模型被称为ZER模型，该方法可以通过忽略特定的 边来缩短生成随机图的时间，但是同样的此方法仍然存在ER模型的弊端，即生成稀疏的无 向连通随机图时所需要的时间太长。黄斌等人提出了一种“不去割边”的近似随机图生成算法， 以概率1-p在完全图中进行去边，但要求所选的边不是割边。该算法从理论上可以保证生成 的随机图的连通性，而且可以准确的控制随机图的AD，但是由于每一步去边过程中都需要 判断当前图中哪些边是割边，而求割边的时间复杂度为O(n³)，所以算法整体的时间复杂度为 O(n⁴)，当n较大，例如高压输电网中具有几千甚至上万个顶点时，算法无法在有限的时间内 完成计算。

发明内容

本发明所要解决的技术问题是，提供一种具有更快速度，更适合生成稀疏无向连通随机 图的一种生成稀疏无向连通随机图的方法。

本发明所采用的技术方案是：一种生成稀疏无向连通随机图的方法，包括如下步骤：

1)给出稀疏无向连通随机图的顶点数量n和平均顶点度d，随机图用顶点邻接矩阵A来 表示，元素为0或1的n×n阶矩阵，其中0表示顶点间无边，1表示顶点间存在边，初始时 将A赋值为零矩阵；

2)n个顶点的编号为从1到n的正整数，从n个顶点中随机选择出一个顶点放入集合X；

3)将剩余的n-1个顶点放入集合Y；

4)判断集合Y是否为空集，是则转到步骤8)，否则执行步骤5)；

5)从集合X和集合Y中各随机选出一个顶点，分别记为顶点x和顶点y；

6)在顶点x和顶点y之间连接边，即A(x,y)＝1，A(y,x)＝1；

7)将顶点y从集合Y中移除，并将顶点y添加至集合X，之后返回步骤4)；

8)按照下式计算还需要添加的边数S：

S＝d·n/2-(n-1)；

9)按照下式计算剩余可选择的边数R；

R＝n(n-1)/2-(n-1)；

10)用i，j分别代表两个不同顶点的编号，令i＝1，j＝2；

11)判断顶点i和顶点j之间是否存在边，是则执行步骤17)，否则执行步骤12)；

12)生成一个0～1之间的随机数θ；

13)判断随机数θ是否小于边数S与边数R的比值，是则执行步骤14)，否则执行步骤 15)；

14)在顶点i和顶点j之间连接边，即A(i,j)＝1，A(j,i)＝1，且边数S＝S-1；

15)令R＝R-1；

16)判断边数S是否为零，是则退出循环，输出矩阵A作为随机图的生成结果，否则执 行步骤17)；

17)令i＝i+1，j＝j+1；

18)判断顶点i是否等于n-1，是则退出循环，输出A矩阵作为随机图的生成结果，否 则执行步骤12)。

步骤11)所述的判断顶点i和顶点j之间是否存在边，是判断A(i,j)是否等于0，当A(i,j) 等于0，表示顶点i和顶点j之间不存在边；当A(i,j)不等于0，表示顶点i和顶点j之间存在 边。

本发明的一种生成稀疏无向连通随机图的方法，首先随机生成支撑树，再在支撑树的基 础上随机添加一定数量的边，借此得到无向连通随机图。此发明的方法解决了快速随机生成 稀疏的无向连通图的问题。

附图说明

图1是本发明一种生成稀疏无向连通随机图的方法的流程图；

图2是本发明的方法与ER方法和ZER方法生成稀疏无向连通图所需时间的比较；

图3a是本发明的方法在顶点数量为3000，顶点平均度为2时随机生成的无向连通图的 顶点度分布图；

图3b是本发明的方法在顶点数量为3000，顶点平均度为3时随机生成的无向连通图的 顶点度分布图；

图3c是本发明的方法在顶点数量为3000，顶点平均度为4时随机生成的无向连通图的 顶点度分布图；

图3d是本发明的方法在顶点数量为3000，顶点平均度为5时随机生成的无向连通图的 顶点度分布图；

图3e是本发明的方法在顶点数量为3000，顶点平均度为6时随机生成的无向连通图的 顶点度分布图；

图4a是本发明的方法与ER方法和ZER方法在顶点数量为3000，顶点平均度为7时随 机生成的无向连通图的顶点度分布的比较图；

图4b是本发明的方法与ER方法和ZER方法在顶点数量为3000，顶点平均度为8时随 机生成的无向连通图的顶点度分布的比较图；

图4c是本发明的方法与ER方法和ZER方法在顶点数量为3000，顶点平均度为9时随 机生成的无向连通图的顶点度分布的比较图；

图4d是本发明的方法与ER方法和ZER方法在顶点数量为3000，顶点平均度为10时随 机生成的无向连通图的顶点度分布的比较图。

具体实施方式

下面结合实施例和附图对本发明的一种生成稀疏无向连通随机图的方法做出详细说明。

本发明的一种生成稀疏无向连通随机图的方法，研究对象隶属于无向图中的，连通且稀 疏的，给定顶点平均度d和顶点数量n情况下，随机图的生成问题。所以本发明针对该随机 图生成问题，提出了一种两阶段的生成方法(DualStageConstructionAlgorithm，DSCA)，首 先随机生成一个包含n个顶点的树，之后再在树的基础上随机添加一定数量的边，边的数量 要满足给定的顶点平均度的要求。

如图1所示，本发明的一种生成稀疏无向连通随机图的方法，包括如下步骤：

1)给定稀疏无向连通随机图的顶点数量n和平均顶点度d，随机图用顶点邻接矩阵A来 表示，元素为0或1的n×n阶矩阵，其中0表示顶点间无边，1表示顶点间存在边，初始时 将A赋值为零矩阵；

2)n个顶点的编号为从1到n的正整数{1,2,3,…,n}，从n个顶点中随机选择出一个顶 点放入集合X；

3)将剩余的n-1个顶点放入集合Y；

4)判断集合Y是否为空集，是则转到步骤8)，否则执行步骤5)；

5)从集合X和集合Y中各随机选出一个顶点，分别记为顶点x和顶点y；

6)在顶点x和顶点y之间连接边，即A(x,y)＝1，A(y,x)＝1；

7)将顶点y从集合Y中移除，并将顶点y添加至集合X，之后返回步骤4)；

8)按照下式计算还需要添加的边数S：

S＝d·n/2-(n-1)；

9)按照下式计算剩余可选择的边数R；

R＝n(n-1)/2-(n-1)；

10)用i，j分别代表两个不同顶点的编号，令i＝1，j＝2；

11)判断顶点i和顶点j之间是否存在边，是则执行步骤17)，否则执行步骤12)；

所述的判断顶点i和顶点j之间是否存在边，是判断A(i,j)是否等于0，当A(i,j)等于0， 表示顶点i和顶点j之间不存在边；当A(i,j)不等于0，表示顶点i和顶点j之间存在边。

12)生成一个0～1之间的随机数θ；

13)判断随机数θ是否小于边数S与边数R的比值，是则执行步骤14)，否则执行步骤 15)；

14)在顶点i和顶点j之间连接边，即A(i,j)＝1，A(j,i)＝1，且边数S＝S-1；

15)令R＝R-1；

16)判断边数S是否为零，是则退出循环，输出矩阵A作为随机图的生成结果，否则执 行步骤17)；

17)令i＝i+1，j＝j+1；

18)判断顶点i是否等于n-1，是则退出循环，输出A矩阵作为随机图的生成结果，否 则执行步骤12)。

将采用本发明的方法生成稀疏无向连通随机图的结果与文献P，RényiA.Onrandom graphsI[J].PublicationesMathematiae，1959，6：290-297的ER方法和文献NobariE，LuXS， KarrasP，andBressanS.Fastrandomgraphgeneration[C].ACMInternationalConference ProceedingSeries，Uppsala，Sweden，2011，331-342的ZER方法所得结果进行比较，为方便 起见，本发明的方法简称为DSCA。

给定顶点个数n∈{1000,2000,3000,4000,5000}；由于要生成稀疏的无向连通随机图， 所以顶点平均度d的取值范围选取2到10。所以，可以对超过45个不同的无向连通图的情 况进行对比。每种情况重复100次计算取平均值。从图2中可以看出本发明的DSCA方法对 于ER方法和ZER方法具有明显的优势。本发明的DSCA方法可以在两秒以内生成5000个 顶点的稀疏无向连通随机图，而ZER方法和ER方法最佳情况下分别需要4.8秒和5.5秒。 随着平均顶点度d的下降，ER方法和ZER方法生成无向连通随机图的时间越来越慢。可以 看出ER方法和ZER方法很难在短时间内生成稀疏的无向连通随机图，而本发明可以在很短 时间内完成。

生成的随机图的实际顶点平均度与所要求的顶点平均度d之间不能有太大的误差。表1 给出了本发明的DSCA方法和ER方法、ZER方法随机生成的不同稀疏无向连通图的实际顶 点平均度的比较。每格的上方是通过本发明DSCA方法得到的无向连通随机图的实际平均顶 点度，中间和下方分别是通过ER方法和ZER方法得到的无向连通随机图的实际平均顶点度。 从表1中可以看出，通过本发明的DSCA方法随机生成的无向连通图的实际顶点平均度最接 近于要求的顶点平均度d。

表1通过三种方法随机生成的不同稀疏无向连通图的实际顶点平均度的比较

由于随机图的度分布接近于泊松分布，所以需要观察生成图的度分布情况来确定其是否 是随机图。本发明方法、ER方法和ZER方法所生成无向连通图的度分布在图3a～图3e、图 4a～图4d中给出，已知顶点数量n为3000，平均顶点度d为{2,3,4,5,6,7,8,9,10}。3a～图 3e中只给出了本发明在d为2到6时所生成图的度分布情况，这是因为ER方法和ZER方法 在顶点平均度较小，也就是相对稀疏的情况下无法在短时间内生成图。从图4a～图4d中可 以看出三种方法所生成的图的度分布均满足泊松分布，也即生成图的随机性得到了保证。