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

　　1、引言
　　交通网络可以用复杂网络来描述[1]。复杂网络有两种典型的模型：无标度网络模型和小世界模型。其中，无标度网络的度分布具有幂率分布，而小世界网络则有较短的平均路径[2]。为此，我们选择小世界网络来模拟交通网络，研究聚类系数对交通网络的平均路径的影响。
　　本文首先给出交通网络的复杂网络定义，然后选择小世界网络为交通网络的网络模型，研究聚类系数对小世界交通网络的最短平均路径的影响，同时，研究聚类系数贪婪算法的影响。
　　2、城市交通网络的复杂网络定义
　　城市交通网络可以用复杂网络来描述，其定义如下：城市交通网络由许多节点和边组成，节点代表道路的交叉路口，边代表道路。当城市交通网络有许许多多的边和节点组成时，边构成了城市交通复杂网络。
　　城市交通网络中，道路有不同的特点，为了简化问题，我们做如下假设：（1）城市交通网络中的边是双向的；（2）边的长度是相等的，城市交通网络抽象为非加权网络。
　　3、网络模型及搜索算法本文由论文联盟http://www.LWlm.COM收集整理
　　本文选择选用WS小世界模型作为交通网络模型。其构造算法如下：
　　（1）从规则图开始：建立一个最近邻耦合网络，节点数为。其中每个节点都与它左右相邻的各节点相连，是偶数。
　　（2）随机化重连：以概率随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点，其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。wWw.ybask.cOm
　　我们对Dijkstra算法进行修改，得到如下获得最短平均路径的算法：
　　（1）选定源节点和目标节点，并且把源节点设定为当前节点，与此同时，最短路径l=0。（2）当前节点询问其邻居节点是否为目标节点，如果是，l=l+1，搜索终止。否则，把所有没有被访问过的邻居节点设置为当前节点，并且l=l+1。（3）重复步骤（2），直到当前节点没有没被访问过的邻居节点为止。
　　贪婪算法是最适合小世界网络的搜索算法，随机算法是成本最低的搜索算法，我们将在小世界模型上比较聚类系数对它们的影响。假定当前节点已知邻居

[1] [2] 下一页