1.2　随机图模型

在现实世界中，不确定现象是普遍存在的。例如，漂浮在液面上的微小粒子不断地进行着杂乱无章的运动，粒子在任一时刻的位置是不确定的;又如公共汽车站等车的人数在任一时刻也是不确定的，因为随时都可能有乘客的到来和离去。这类不确定现象，表面看来无法把握，其实，在其不确定的背后，往往隐藏着某种确定的概率规律，因此，以概率和数理统计为基础的随机模型就成为解决此类问题最有效的工具之一。

如果网络的节点不是按确定的规则连线，譬如按纯粹的随机方式连线，所得到的网络就称为随机网络。1960年现代数学大师、匈牙利数学家Erds和Reni建立了随机图理论，研究复杂网络中随机拓扑模型（ER），自此ER模型一直是研究复杂网络的基本模型。

随机网络的第一个模型:给定网络节点总数N，网络中任意两个节点以概率p连线，生成的网络全体记为G（N，p），构成一个概率空间。由于网络中连线数目是一个随机变量X，取值可以从0到N（N-1）/2，有m条连线的网络数目为，其中一个具有m条连线的特定网络出现的概率为P（G_m）=p^m（1-p）^{[N（N-1）/2]-m}。因此，该模型可生成的不同网络的总数为2^N（N-1）/2，它们服从二项分布。网络中平均连线数目为pN（N-1）/2。

随机网络的第二个模型:给定网络节点总数N和连线总数m，而这些连线是从总共N（N-1）/2条可能的连线中随机选取的，生成的网络全体记为G（N，p），构成一个概率空间。这样可以生成不同网络的总数为，它们出现的概率相同，服从均匀分布。网络中两个节点连线的概率为p=2m/[N（N-1）]。