诱导最大小世界效应的最佳网络结构

摘 要：在文章中，一般效率是全局效率和局部效率的平均值，一般效率被用来测量一个网络的通信效率。一个小世界网络的一般效率相对于一个相应规则网络的一般效率的增长率被用来定量地测量小世界效应。我们的研究结果表明，当网络的节点数增加时，小世界效应单调增长。诱导最大小世界效应的最佳连接概率大约为0.02，并且当节点数目增加时最佳平均连接概率单调递减。因此，诱导最大小世界效应的最佳网络结构是具有大量节点数（N>500），最小连接概率（≈0.02）和最小平均连接概率（<0.1）的网络。

关键词：通信效率；网络结构；效应

1 模型

复杂网络行为的另一种定义由Vito Latora和Massimo Marchiori[1]提出，该定义是基于一个网络的效率。在全局和局部范围内，网络的特征是通过效率来有效传递信息，而不是用C和L。为了定义图G[1]的效率，Vito Latora和Massimo Marchiori假设每个节点是通过网络发送信息。一个加权网络是由一个加权值与连接边相关联。加权网络需要两个矩阵来表示：一个是连接矩阵{aij}，表明两个节点直接是否存在一个连接边（对于无权网络，如果有一条边直接连接节点i和j，其项aij为1，否则为0。）；另一个表示物理距离的矩阵{lij}。数值lij可能是两个顶点之间的空间距离或者是它们可能连接的长度：即使在图G中两个节点i和j之间没有连接，lij也是被已知的[1]。例如，在传输网络中lij可能是两个站点之间的地理距离，可能是在英特网中两个路由器之间信息包裹交换所花的时间，或者是生物系统中沿着一个直接的连接的化学反应的倒转速率。在一个无权网络的特殊情况下，lij=1，？坌i，j。两个一般顶点i和j之间的最短路径长度dij是从i到j的图G中的曲线的所有可能的路径的物理距离最小的总数和。因此，矩阵{dij}能通过矩阵{aij}和矩阵lij的信息计算出来，dij？叟lij，？坌i，j，当节点i和节点j之间有直接连接边时等号成立。他们[1]假设每个顶点通过它的边沿着整个网络不断的传递信息，在传递过程中两个节点i和j之间的传递效率？着ij是最短路径dij的倒数，即？着ij=1/dij，？坌i，j。基于这个定义，当图G中的节点i和节点j之间没有任何路径连通时，dij=+∞，然而？着ij=0。

图G的全局效率能够被定义为：

（1）

而局部效率，类似于聚类系数C，能被定义为局部子图效率的平均值：

其中Gi，如先前所定义的，是节点i邻居节点所构成的子图，子图Gi由ki个节点和最多ki（ki-1）/2条边组成。公式（2）中的数值d'lm是在图Gi中节点l和m之间被计算出来的最短距离。上述给出的两个定义有个重要的属性：全局效率和局部效率已经被规范化，即：0？燮Eglob？燮1和0？燮Eloc？燮1。

我们试图定量测量小世界效应，使用一般效率Egen去测量网络的效率，Egen是全局效率和局部效率的平均值，定义为：

Egen=（Eglob+Eloc）/2。为了定量测量小世界效应，我们需要选择基量。由于规则网络的Egen是远远大于一个相应的稀疏的随机网络，我们选择规则网络的Egen作为测量的基础，基点表示为E0。因此，我们可以使用一般效率的增加的百分比来测量小世界效应，它被定义为：

？酌sw=■ （3）

2 结果

我们首先构造一个与文献[2]中所使用的相同的无权小世界网络。构造一个有N=2000和K=60的规则网络，然后通过重连概率prewire来构造小世界网络，构造的小世界网络的Egen对应于重连概率prewire绘制的曲线如图1所示，Egen首先增加，随着prewire的增加达到最佳值后然后开始下降，这就是所谓的小世界效应。另外，从图1中我们可以发现，当重连概率prewire≈0.02时，Egen值达到最大值，而根据Egen的定义可知，如果要构造一个全局效率和局部效率均较大的小世界网络，Egen值可以作为参考，即Egen最大值的点，其实可以看作是Eglob和Eloc均较大的小世界网络。

构造一个有N=2000和K=60的规则网络，然后通过重连概率prewire来构造小世界网络。根据等式（3），我们计算小世界效应的定量测量值，？酌sw，对应于重连概率prewire，并且在图2中显示结果。从图2中，我们能够很清晰的发现小世界效应，？酌sw首先增加，随着prewire的增加达到最大值后开始下降。诱导最大小世界效应的最近重连概率prewire大约是0.02，而且相应的？酌sw达到了19.2%。

对于一个小世界网络，这儿有三个参数去测量这个网络，节点的数量N，每个节点的平均连接边数（K）和这个重连概率prewire。除了参数K，我们能够用平均连接概率pave来测量网络的连接，pave值近似等于K/N。对于一个固定节点数N，我们研究pave和prewire对？酌sw的影响。类似于图2和图3，我们也设置N=2000。对于N=2000和一个确定的pave，当重连概率prewire大约为0.02时？酌sw达到最大值。对于N=2000和prewire=0.02，？酌sw对应于pave曲线如图3所示。随着pave的增加，？酌sw开始增加，当pave在最佳值0.032时？酌sw开始下降。当pave等于0.032时，？酌sw达到最佳值而且高达20%。

根据上面的研究结果，我们试着找到最优pave和prewire去诱导对应与不同节点数N的最大值？酌sw，最优prewire的几乎是一个常量，其值大约是0.02。与节点数N相对的最佳的pave被记录在图4中。随着N的增加，最优pave单调下降。如果N=50，最优pave高达0.24，如果N增加到3000，最优pave减少到0.025。随着最优pave和prewire，与节点数N相对的最大？酌sw被绘制在图5中。如图5所示，最大？酌sw随着节点数的增加不断的增加。当N=30，最大？酌sw等于0并没有小世界效应；当N=50时，最大？酌sw只有0.01，小世界效应非常弱；对于N=100，1，000，2，000和3，000，最大？酌sw与N相对应的值分别为0.033，0.16，0.20和0.23。

3 结束语

我们的结果显示小世界效应随着节点数N的增加不断增强。当节点数是30时，没有小世界效应。当节点数是3，000时，综合效率的日益增长的比率达到0.23。诱导最大小世界效应的最佳重连效率prewire几乎一个常量0.02，而且最佳平均连接概率pave随着节点数N的增加单调下降。当节点数N=3，000时，最佳pave只有0.025。因此，为了引起小世界效应，节点数应该是大的（>500），prewire应该是小的（≈0.02），并且网络应该是稀疏的（pave<0.1）。

参考文献

[1]V. Latora， M. Marchiori.Phys. Rev. Lett[J].2001，87：198+701.

[2]S. Milgram. The small world problem[J].Psychol Today， 1967，5：60-67.