聚类系数对小世界交通网络搜索路径的影响

开篇：润墨网以专业的文秘视角，为您筛选了一篇聚类系数对小世界交通网络搜索路径的影响范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：采用复杂网络理论研究方法，研究交通网络的拓扑属性对其性能的影响。仿真发现：交通网络的最短平均路径随着聚类系数的增大而增大，当聚类系数增大到一定程度时，最短平均路径突然变大；而且，采用贪婪算法获得最优路径仅适合于聚类系数较小的交通网络。

关键词：交通网络 复杂网络 最短平均路径

中图分类号：TN915 文献标识码：A 文章编号：1007-9416（2012）09-0040-01

1、引言

交通网络可以用复杂网络来描述[1]。复杂网络有两种典型的模型：无标度网络模型和小世界模型。其中，无标度网络的度分布具有幂率分布，而小世界网络则有较短的平均路径[2]。为此，我们选择小世界网络来模拟交通网络，研究聚类系数对交通网络的平均路径的影响。

本文首先给出交通网络的复杂网络定义，然后选择小世界网络为交通网络的网络模型，研究聚类系数对小世界交通网络的最短平均路径的影响，同时，研究聚类系数贪婪算法的影响。

2、城市交通网络的复杂网络定义

城市交通网络可以用复杂网络来描述，其定义如下：城市交通网络由许多节点和边组成，节点代表道路的交叉路口，边代表道路。当城市交通网络有许许多多的边和节点组成时，边构成了城市交通复杂网络。

城市交通网络中，道路有不同的特点，为了简化问题，我们做如下假设：（1）城市交通网络中的边是双向的；（2）边的长度是相等的，城市交通网络抽象为非加权网络。

3、网络模型及搜索算法

本文选择选用WS小世界模型作为交通网络模型。其构造算法如下：

（1）从规则图开始：建立一个最近邻耦合网络，节点数为。其中每个节点都与它左右相邻的各节点相连，是偶数。

（2）随机化重连：以概率随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点，其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。

我们对Dijkstra算法进行修改，得到如下获得最短平均路径的算法：

（1）选定源节点和目标节点，并且把源节点设定为当前节点，与此同时，最短路径l=0。（2）当前节点询问其邻居节点是否为目标节点，如果是，l=l+1，搜索终止。否则，把所有没有被访问过的邻居节点设置为当前节点，并且l=l+1。（3）重复步骤（2），直到当前节点没有没被访问过的邻居节点为止。

贪婪算法是最适合小世界网络的搜索算法，随机算法是成本最低的搜索算法，我们将在小世界模型上比较聚类系数对它们的影响。假定当前节点已知邻居节点与目标节点的坐标。定义节点、之间的距离为 。源节点应用贪婪策略搜索目标节点时步骤如下：

（1）首先判断自己的邻居节点中有无目标节点；（2）如有，则终止搜索；（3）若无，则向距离目标节点距离近的邻居节点查询，查询它的邻居节点中是否有目标节点；（4）重复2、3，若所有的邻居节点都访问过一次，则认为搜索失败。随机游走策略如下与贪婪算法类似，只是（3）随机选择邻居节点作为查询节点查询其邻居节点是否有目标节点。

4、仿真及结果分析

实验中，我们建立WS小世界网络模型，其中，网络规模为：N=10000，网络的平均度=4，改变重连概率以达到改变聚类系数的目的。在该网络模型上实现最短平均路径算法、贪婪算法和随机算法。由于计算所有节点间的平均路径工作量太大，为此，我们随机选择1000节点，通过上述算法研究聚类系数对最短平均路径的影响以及对贪婪算法的影响。

图1为小世界交通网络中聚类系数对最短平均路径的影响。从图1（a）可以看出，最短平均路径长度随着聚类系数的增长而增长，并且，当聚类系数较小时（C

图2为聚类系数对搜索算法的影响。从图2（a）可以看出，当聚类系数较小时，贪婪算法的平均路径远小于随机算法的平均路径，从图（b）可以看出，聚类系数较小时，贪婪算法的成功率远高于随机算法。当聚类系数较大时，两者的平均路径接近，成功率都很低。

5、结语

通过对交通网络进行定义，建立交通网络的小世界网络模型，以研究网络统计属性对其功能的影响。仿真结果显示，小世界交通网络中，聚类系数不宜太大，否则，不利于减小网络的最短平均路径，而且，也不利于最佳路径的搜索。也就是说，小世界交通网络中，距离较近的节点间建立少量的连接有利于交通流畅，但是太多的近距离连接不利于交通的流畅。

参考文献

[1]陈菁菁.基于复杂网络的城市轨道交通网络可靠性研究[J].都市快轨交通，2010，Vol.23（2）：18～21.

[2]汪小帆，李翔等.复杂网络理论及其应用[M].清华大学出版社，2006，4.