刘艳霞，奚建清，张 芩

(1.华南理工大学软件学院，510006广州;2.华南理工大学计算机科学与工程学院，510006广州)

小世界网络在自然界和人类社会中普遍存在，如蛋白质网络、科学家协作网络、WWW网络、通信网络等，都具有明显的小世界特性.通常一个稀疏网络，如果其直径(或是网络平均距离)随着网络规模的增大呈对数或小于对数形式增长，网络有相对较高的聚集系数，则该网络称为小世界网络.

为再现真实网络中存在的小世界特性，揭示小世界网络的内在生成机理，各种小世界模型不断涌现.这些模型主要分为:1)随机性模型.通过概率分析技术和随机连边方法生成网络，如最初的 WS 模型［1］及其变体 NW 模型［2］、二维的Kleinberg 模型［3］、动态演化的 OHO 模型［4］;2)确定性模型.网络节点和连边完全由确定的规则形成.随机性模型尽管符合大多数真实网络的生成特性，但无法直观、清晰地反映网络的形成机制以及解析计算网络特性，也不适合以确定方式构造的具有固定节点度的通信网络，因此确定性的小世界模型逐渐成为研究热点，基于各种构造方法的确定性模型相继被提出.

最早的确定性小世界模型由Comellas等［5］提出，采用基于循环图扩展的方法，通过降低直径或提高聚集系数，将高直径或低聚集的循环图转变为小世界网络.树通常具有低的对数级直径和小的节点度，因此基于树结构的推广或改造也可生成小世界网络，如递归团树(recursive clique tree［6］)是2-团树至K-团树的推广，二叉树可……