杨宇骐，朱磊

　　（中国人民解放军理工大学 通信工程学院，江苏 南京 210007）

       摘要：随机图是一种简单并且可用于抽象现实社会多种实际系统的网络。与其他网络模型不同，随机图的构造方式决定其节点具有对等性，且网络中可能存在孤立节点和子图。对随机图尤其是其连通性的研究有助于更深入地了解具有随机连接特性及节点对等特性的真实网络。文章采用理论与仿真相结合的方法，重点研究随机图的连通性和随机图连通率的计算方法，揭示了随机图在演化过程中的形态变化，表明随机图中树结构的广泛存在。研究还发现，在巨大连通子图形成前，随机图的子图大小呈幂律分布。本研究结果为复杂网络相关的实证研究和性质复杂的网络相变态研究提供了理论依据。

　　关键词：随机图；连通率；子图

0引言

　　自20世纪60年代ERDS P和RNYI A提出随机图模型［1］以来，随机图理论一度成为研究复杂网络的基本理论。其研究焦点多集中于自身统计特性的描述，例如子图的平均大小、巨大连通子图的存在条件，以及构图规则的改进［2］等方面。在随机图中，任意两个节点间以一定的概率直接相连，人们期望以此作为自然界一些网络的基本抽象，例如人际关系网络、病毒传播网络、交通网络等［35］。但大规模实证研究表明自然界多数实际网络均属于无标度网络［6］(节点的度分布为幂律分布)，与随机图有较大差别。随机图简单的构造方式决定了其自身缺少更精确的模拟真实网络的结构，无法单纯地通过研究随机图来获得众多实际网络的拓扑统计特征和动力学特征。然而，从统计学的角度考虑，网络的连通情况仍可通过对随机图的研究窥见。

　　现代社会中，人们每时每刻都处于或正与各种各样的复杂系统建立联系。一个很自然的思考是一个个体与另外一个个体建立联系的概率的大小。由于受研究方法和网络拓扑复杂程度的限制，传统有关网络连通情况的研究往往关注网络的连通子图［78］, 忽略网络节点间连通情况的微观考虑。此外，对随机图子图的研究主要针对子图的平均规模，缺少子图大小分布的定量描述，尤其对巨大连通子图即将形成的相变态［910］研究较少。本文以随机图为研究对象，提出并研究了随机图的连通率，对子图中迂回路由的存在情况进行了假设和验证，并基于仿真试验提出了相变态中子图大小的分布。所得研究结论可有效地应用于现实网络系统的规划、建设与分析中。

1连通率与随机图

　　定义连通率(Interconnection Rate，IR)为网络中连通（直接连接或多跳转接）的节点对数与总节点对数之比，如图1(b)所示。给定网络拓扑，便能较容易地得到该网络的连通率。对于由分散节点组成的网络，连通率为0，对于连通网络，连通率为1。图的最小生成树以最小的边数达到全连通，是最高效的全连通网络。如图1(a)、(c)、(d)所示。

　　随机图［1］定义为一个含有N个节点的网络，其中任意两个节点有连边的概率为p，总的连边数L=N(N－1)p/2。从网络结构演化的角度又可表述为，每一时刻一个新节点加入网络，新节点以概率p与每一个已存在的节点建立连边。随机图的度分布为泊松分布［11］，节点的平均度z=2L/N=(N－1)p。若p很小，只有当节点数N很大即网络规模很大时才会有较大的z，大的节点数和大的节点度数看似矛盾，在随机图网络中却有着此般紧密的联系。从构造方式可以看出，随机图的一个重要特点是节点之间关系的平等性，节点的度集中于平均度z附近，这是许多其他复杂网络模型(如无标度网络模型)不具有的性质。对于节点关系对等的随机图，若网络规模足够大或者重复试验次数较多，网络的连通率在统计意义上等价于网络中任意两个节点之间相互连通的概率，由此能将随机图的网络层次与节点层次有效地结合。

　　在对随机图的研究中，无论p的取值和随机图规模如何变化，当网络的边数L与节点数N满足L=2N(即z≈4)时, 总有IR=0.961 3。这等同于如果每一个节点平均与其余4个节点直接相连，则该节点将以0.961 3的概率与网络中任意一个节点连通。若L/N进一步增大，则连通的概率也会相应增大。事实上，随机图的平均路径长度［12］LER≈1+ln(1/p)/ln(z)，当p=0.001，z=4时，得LER≈6，这似乎与著名的“六度分离”［13］有着相似的结论。

2随机图的连通率

　　2.1不含迂回路由的情况

　　由上述随机图中节点数和边数的二次关系知, 当节点数N较小时，边数L也相对较小，假设此时网络中尚不含迂回路由，即任意两个节点间不连通或只有一条通路，此时子图呈树结构。在网络不含迂回路由的情况下，两节点不直接相连的概率为1－p，不通过2跳相连的概率为(1－p2)A1N－2,…, 不通过i(1≤i≤N－2)跳相连的概率为(1－pi)Ai－1N－2(其中Aba表示从a个节点中选出b个的排列数)。所以无迂回路由(no alternative route)的随机图中任意两节点的连通率IRna为：

　　其中，右端的参数n不同于i，代表连通路径上的中介节点数。在p确定的情况下，式(1)右端第二项是N的函数，取对数得：

　　整理得：

　　带入式(1)得：

　　式(4)即为不含迂回路由的情况下节点间的连通率，根据前述随机图的性质，此连通率也为网络的连通率。

　　从演化角度讲，在实现连通前，随机图经历了两种形态。第一种形态是网络由许多规模较小的连通子图组成，第二种形态是网络中一个巨大连通子图和一些较小的连通子图并存［14］。本文认为在巨大连通子图形成前的第一种形态，子图普遍呈树结构，即不含迂回路由。此观点将在仿真试验部分得到验证。下面讨论第二种形态下的连通率。

　　2.2存在巨大连通子图的情况

　　在随机图中, 巨大连通子图所含节点数占网络节点总数的比例S为［9］:

　　巨大连通子图本身是一棵树的可能性非常小(小于pSN－1)，所以几乎一定存在迂回路由，而与巨大连通子图共存的小连通子图中是否存在迂回路由值得思考。考虑图2所示的场景，节点C的加入带来了两条边(虚线所示)，使节点A与B之间多了一条迂回路径。但事实是当节点C加入网络时，与巨大连通子图相连的概率为P1=1－(1－p)SN，与子图AB相连的概率为P2=1－(1－p)2，P1P2，所以根据实际推断原理，图2所示场景在实际中几乎是不会发生的。或者说，在网络中随机选择一条边，极有可能位于巨大连通子图中而非网络的其他部分。基于该结论，可以判定当巨大连通子图存在时，小连通子图不含迂回路由。

　　在巨大连通子图形成后，从网络中随机选取两个节点计算连通率，存在以下3种情况：

　　(1)两个节点均位于巨大连通子图中，可能的节点对数为节点连通；

　　(2)只有一个节点在巨大连通子图中，可能的节点对数为

　　，节点不连通；

　　(3)两个节点均不在巨大连通子图中，可能的节点对数为根据上述对不含迂回路由情况下网络连通率的讨论，其中连通的节点对数为。

　　综上，巨大连通子图形成后网络的连通率为：

　　其中，为任意实数，r为非负整数。参数IRna和S分别由式(4)、(5)给出，第二个等号在N→∞的条件下严格成立。在连接概率p确定的情况下,式(6)是IR关于N的隐函数，可以通过先确定S再确定N的方法计算。

　　2.3网络的相变态

　　前述给出了随机图的连通率在两种状态下的计算方法，计算的根据为子图中不含迂回路由即子图呈树结构的假设。然而在随机图的演化过程中还存在一种中间状态，在这种状态下，子图聚合，以一种突变的方式形成巨大连通子图，该渗流状态被称为随机图的相变态［15］，研究表明巨大连通子图形成的相变点为z=1 ［16］。对相变态的量化分析较困难，相关文献也较少。本文通过大量试验研究了随机图相变态的子图大小分布，发现在双对数坐标下，相变态的子图大小符合幂律分布，如图3所示，分布图像呈倒置的烟斗形。

　　子图大小的幂律分布表明，相变态中规模较小的子图占大多数，但仍有少量规模相对很大的子图，这种子图大小的分布是极不均匀的。本文用带指数拖尾的幂律分布y=10αxβex/γ对该状态的子图大小分布进行拟合，其中x表示子图中的节点数，y表示具有x个节点的子图数，γ表示拖尾长度。拟合结果如表1所示。

3仿真试验

　　通过前文的理论分析，得到了一些关于随机图连通率和随机图形态的重要结论。本文采用仿真试验的方式对上述结论进行验证，主要给出了p=0.005时仿真试验的结果(其余结果与之相似)，试验结果取1 000次平均。对随机图连通率的仿真如图4和5所示。其中实线部分为理论值，在相变态之前和之后的连通率分别由式(4)和式(6)计算得出。图4中，仿真结果和理论值能够较好地吻合，表明了连通率计算公式的正确性，也间接证明了前述假设的正确性，即随机图的小子图基本为树结构，不含迂回路由。特别地，在式(6)中令N=801 (此时L=2N)得IR=0.961 3，这为本文第2节中的发现提供了理论依据。

　　图5显示了相变态(这里取定范围为z∈(0.85,1.15))连通率的仿真值，显然用式(4)或式(6)来计算网络相变态的连通率会存在很大误差。结合本文关于相变态子图大小分布的结论并根据表1的参数拟合值，得到相变态的连通率理论值，如图6中虚线所示。仿真结果与理论值吻合较好，证明了本文关于相变态子图大小分布结论的正确性及拟合方法的可行性。

　　根据前述分析和试验，可以清晰地描述随机图或者具有节点对等特征的网络的演化过程，如图7所示：网络初始阶段只含少量孤立节点，随着新节点的不断加入，连接逐渐增多，子图出现；子图渐渐增多，规模也在扩大，但基本都是树形结构；子图规模继续增加，出现了数量可观的小子图和少数相对较大的子图，子图大小服从幂律分布，网络演化进入相变态；相变态的时间很短，众多子图很快互连为巨大连通子图，巨大连通子图不断扩大，小子图仍呈树结构并逐渐并入巨大连通子图中；最后，网络连通。

4结论

　　现实世界存在很多具有随机连接特性的网络或系统，在一定程度上可抽象为随机图，并且由于随机图节点的对等地位，其在对等网络研究方面具有重要意义。传统的随机图理论对网络演化过程中的连通情况尤其是节点层次的连通情况研究较少。本文通过对随机图连通率的研究, 给出了随机图连通率的计算方法；通过对小子图中不存在迂回路由的假设及验证，说明了随机图中树结构的广泛存在；此外，通过试验发现并验证了相变态的子图大小满足幂律分布，进一步清晰勾勒了随机图的演化过程，即同规模子图状态、短暂且子图大小成幂律分布的相变态、巨大连通子图存在并不断扩大的状态、连通状态。本文研究成果对真实网络尤其对于对等网络的研究、规划和建设具有重要意义。不过本文仍存在许多不足之处，如连通率定义的简单性可能带来计算中的不确定因素，从而掩盖了随机图演化过程中的其他重要性质；对随机图相变态子图大小的拟合存在一定误差。如何将连通率的计算扩展到其他网络模型，并将其有效地应用在如通信网络等实证研究方面是下一阶段研究的方向。

　　参考文献

　　［1］ ERDS P, RNYI A. On random graphs［J］. Publ Math Debrecen, 1959(6): 1-14.

　　［2］ ACHLIOPTAS D, D’SOUZA R M, SPENCER J. Explosive percolation in random networks［J］. Science, 2009, 323(5920): 1453-1455.

　　［3］ KADUSHIN C. Understanding social networks: theories, concepts, and finding［M］. Oxford University Press, USA, 2012.

　　［4］ BALTHROP J, FORREST S, NEWMAN M E J, et al. Technological networks and the spread of computer viruses［J］. Science, 2004, 304(5670): 527-529.

　　［5］ 熊炜, 李清泉. 高速公路场景中车用自组织网络的节点度［J］. 电子与信息学报, 2010, 32(9): 2033-2038.

　　［6］ KRAPIVSKY P L, REDNER S, LEYVRAZ F. Connectivity of growing random networks［J］. Phys. Rev. Lett., 2000,85(21): 4629-4632.

　　［7］ BOLLOBS B. Random graphs［M］. 2nd. Cambridge University Press, 2001.

　　［8］ 黄斌, 吴春旺, 郑丰华, 等. 复杂网络中随机图模型研究［J］. 计算机工程与科学, 2014, 36(7): 1377-1383.

　　［9］ NEWMAN M E J, STROGATZ S H, WATTS D J. Random graph with arbitrary degree distributions and their applications［J］. Phys. Rev. E, 2001, 64(22):359-382.

　　［10］ 卢友军, 许道云. 随机图G(n,p)中k团的相变性质［J］. 贵州大学学报(自然科学版), 2013, 30(6): 86-90.

　　［11］ 谭利, 侯振挺. 一类无标度随机图的度序列［J］. 应用数学学报, 2011, 34(3): 440-447.

　　［12］ 汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用［M］. 北京:清华大学出版社,2006.

　　［13］ MILGRAM S. The small world problem［J］. Psychology Today, 1967,2(1):185-195.

　　［14］ NEWMAN M E J, WATTS D J, STROGATZ S H. Random graph models of social networks［C］. Proceedings of the National Academy of the Sciences of the United States of America, 2002, 99: 2566-2572.

　　［15］ 王彬. 随机图中的两种相变［D］. 天津: 南开大学, 2011.

　　［16］ MOLLOY M, REED B, MOLLOY M. The size of the largest component of a random graph on a fixed degree sequence［J］. Combinatorica, 1998, 7(3):295-305.