极小Cayley图的确定性小世界网络模型

刘艳霞，奚建清，张 芩

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

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

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

最早的确定性小世界模型由Comellas等［5］提出，采用基于循环图扩展的方法，通过降低直径或提高聚集系数，将高直径或低聚集的循环图转变为小世界网络.树通常具有低的对数级直径和小的节点度，因此基于树结构的推广或改造也可生成小世界网络，如递归团树(recursive clique tree［6］)是2-团树至K-团树的推广，二叉树可简单改造为小世界网络［7］.经典的数学问题或数学理论同样可用于小世界网络的构造，如Corso［8］的自然数网络、Chandra等［9］的素数网络源自于素因数分解理论和哥德巴赫猜想;Boettcher等［10］提出的Hanoi网络源自经典的Hanoi塔问题.除了采用全新的构造方法，已有的网络模型也可以成为确定性小世界模型的基础，如ZRG模型［11］是随机性OHO模型的确定性版本，LG模型［12］是确定性均匀递归树DURT的小世界版本.最近，GovorcIn等［13］将线图作为确定性小世界模型，使用图论中的线图运算也获得了小世界网络.

Cayley图是运用有限群构造高对称网络的图论模型，在互连网络设计中有重要应用，Xiao等［14］曾于2006年首次提出Cayley图可作为确定性的小世界网络模型，并通过两个应用实例予以说明.本文在此基础上进行了形式化描述和扩展，引入了Cayley图的极小性概念，通过分析极小性和聚集系数的关联，建立了形式化的Cayley图扩展模型.该模型通过增加极小Cayley图的生成集，可灵活地构造出对称性强且结构规则的常数度和非常数度的小世界网络，在通信网络、P2P覆盖网络等实际领域具有广泛应用.

1 极小Cayley图及其聚集系数

首先引入极小Cayley图的概念及其聚集性质，作为小世界网络模型的理论基础.为便于建模，只考虑无向图的情况，以下的Cayley图在不作特殊说明的情况下都为无向Cayley图.

定义1(Cayley图［15］) 设G是一个有限群，e为G的单位元，S是G的一个子集且满足以下条件:1)e∉S;2)g-1∈S当且仅当g∈S，则群G关于子集S的Cayley图Γ=Cay(G，S)定义为V(Γ)=G，E(Γ)=

定义2(极小对称生成集［15］) 设G是一个有限群，S是G的子集且不含单位元，即S⊆G{e}，若S满足 ∀s∈S，Gr(S{s，s-1})为G的真子群，则S称为G的极小对称生成集．

定义3(极小Cayley图［15］) 设 Γ 为 Cayley图Cay(G，S)，若子集S为极小对称生成集，则Γ被称为极小Cayley图.

聚集系数是小世界网络的重要度量指标．如果网络中某个节点v的度为deg(v)，则节点v的聚集系数cc(v)=其中，Mv为v的所有邻节点之间实际存在的边数，也可理解为v连接的三角形个数．由于Cayley图具有点对称性，整个网络的聚集系数CC(Γ)即为任意节点v的聚集系数CC(v)，显然，0≤CC(Γ)≤1．由此，本文给出极小Cayley图的如下性质．

定理1 如果Γ=Cay(G，S)是极小Cayley图，则CC(Γ)≠0当且仅当存在生成元a，b∈S，a与b互逆，且a3=b3=e．

证 明 首先，证明充分性．若存在生成元a，b∈S，b=a-1且a3=b3=e，则b=a2，对于任意的g∈G，有(ga)a=gb∧(gb)b=ga，即g的两个邻节点ga与gb之间存在一条连边，因此CC(Γ)≠0．

其次，证明必要性．若CC(Γ)≠0，则对于任意的节点g∈G，其邻居之间至少存在一条连边．由于Cayley图的点对称性，在此仅需考虑单位元e的聚集系数，其邻节点的集合为生成集S．假设与e形成三角形的两个邻居分别为a与b，a，b∈S∧a≠b，则必定存在h，h-1∈S，满足ah=b且bh-1=a;由于S不含单位元，则有h≠b∧h≠a-1．进一步，若h≠b-1∧a≠b-1，则S{b，b-1}仍可生成G，同样的，若h≠a∧b≠a-1，则S{a，a-1}仍可生成G的所有元素，这与Γ是极小Cayley图相矛盾的，因此必有a=b-1，即a与b互逆．接下来，考虑h的取值，若h是不同于a和b的第3个生成元，即h≠a∧h≠b，由于ah=b以及a与b互逆，则h=a-1b=b2，即h可由b生成;同样地，h-1也可由a生成;也就是说S{h，h-1}仍可生成G的所有元素，这也与Γ是极小Cayley图相矛盾的，因此必有h=a或h=b成立．又因为ah=b且a非单位元，自然有h≠b．由此，可知h=a=b-1成立，即a与b互逆且a3=b3=e，得证．

很多著名的互连网络都是Cayley图且具有极小性，如圈Cn、交错群图AGn、超立方体Qn、立方连通圈CCCn等，定理1提供一种简单的方式判断这些Cayley图是否具有较高的聚集性．而且，从定理1的证明可知，若极小Cayley图的生成集中存在一对互逆的生成元，并且其3次幂为单位元，则该对生成元之间一定具有连边，形成且仅形成一个三角形;进一步，若生成集中存在n对互逆的生成元，其3次幂都为单位元，则形成的三角形个数为n，因此容易得到如下推论．

推论1 如果Γ=Cay(G，S)是极小Cayley图，则CC(Γ)=n/C2|s|当且仅当生成集S中存在n对互逆且3次幂为e的生成元．

例1 圈Cn是极小Cayley图Γ=Cay(Zn，{-1，+1})，其中:“+”和“-”分别为模n的加减运算;Cn的度为2．很明显，仅当n=3时，满足13=(-1)3=1，圈C3为三角形，其聚集系数为1，其余情况圈Cn的聚集系数都为0．

例2 交错群图AGn=Cay(An，S)［16］是针对偶置换群An构造的一类Cayley图，设g+i=(12i)，g-i=(1i2)，则生成集S=…，n}i=3，4，…，n}．AGn是度为2(n-2)的极小Cayley图，所有生成元都是3-轮换并且两两互逆，对所有的i=3，4，…，n，(12i)与(1i2)互逆，并且满足(12i)3=(1i2)3=e．因此其聚集系数为如图1是交错群图AG3和AG4，从图1中可看出，其具有较高的聚集系数．

图1 交错群图AG3和AG4

2 极小Cayley图的小世界特性

在最早提出的 WS小世界的基础上，Cont等［17］用图论的语言描述了小世界网络模型的基本原则.

定义4(小世界网络模型［17］) 一个网络模型Ω被称为小世界的，如果其生成图Γ满足以下条件，其中，V(Γ)和E(Γ)分别为Γ的节点集和边集．

1)图 Γ是稀疏的，即 deg(Γ)∈O(log|V(Γ)|);

2)图Γ具有较小的直径，即D(Γ)∈O(log|V(Γ)|);

3)图Γ具有较高的聚集系数，即存在大于0的常数c，使得CC(Γ)≥c成立．

必须说明的是，该定义可以进行小的调整，如稀疏图中关于节点度的条件可以替换为E(Γ)的条件，即|E(Γ)|∈O(|V(Γ)|log|V(Γ)|)，较小的直径可以替换为较小的平均距离，Γ的聚集系数也可表示为CC(Γ)≈c(c＞0)，但由此可知，其本质是相同的．

针对极小Cayley图和小世界之间的关联，可得到如下结论.

定理2 非常数度的极小Cayley图必定不是小世界的.

证 明 若有非常数度的极小Cayley图Γ=Cay(G，S)，从推论1 可知，CC(Γ)=n/C2|s|其中，n为S中3次幂为e的互逆生成元的对数，易知其最大取值为|S|/2，则有CC(Γ)的最大取值为1/(|S|-1)．由于deg(Γ)=|S|不为常数，则图Γ无法满足条件3)，图Γ不是小世界的，得证．

例如图1中交错群图AGn，属于非常数度的极小Cayley图，度为2(n-2)，聚集系数为(n-2)/，尽管其聚集系数较高，但随着节点规模的增大，聚集系数越来越小，按照定理2的证明可知，其不是小世界的．

根据定义4可以发现，极小Cayley图可作为候选的、确定性的小世界网络模型.遵循互连网络设计原则，很多性质良好的极小Cayley图都是可扩展的、稀疏的并具有低直径，即符合小世界网络模型定义的条件1)和条件2)，为构造小世界网络提供了很好的模型基础.

进一步，从定理2可知，极小Cayley图若不是常数度网络，则其本身一定不是小世界的.因此若要构造小世界网络，则需要扩展生成集使其不具有极小性，并且通过恰当选择扩展的生成集，获得较高的聚集系数，将极小Cayley图转换为具有小世界特性的Cayley图.

3 极小Cayley图的扩展模型

本文详细介绍如何通过扩展极小Cayley图的生成集，构造小世界网络.为便于讨论，引入以下概念和符号.

定义5(Cayley扩展图) 设Γ为极小Cayley图Cay(G，S)，若Γ为扩展的生成集，使其增加新的生成元集H，满足H-1，则形成新的Cayley图Cay(G，S∪H)称为Γ基于H的扩展图，记为Ex(Γ，H);另外，Γ也可称为Ex(Γ，H)的Cayley基图．

很明显，Cayley扩展图在其基图上增加了节点度，使节点之间存在更多的连边，降低了网络直径并且增加了聚集性.接下来，基于Cayley扩展图的概念以及定义4中小世界网络模型3个条件，定理3和定理4分别给出常数度和非常数度的小世界网络的构造方法，其中N=|V(Γ)|．

定理3 若极小Cayley图Γ=Cay(G，S)是常数度网络且满足定义4的条件2)，若有H∩(S∪H)2≠Φ且|H|=c(c为常数)，则Ex(Γ，H)是常数度的小世界网络．

证 明

1)由于|H|为常数，deg(Ex(Γ，H))=deg(Γ)+|H|=cd(cd为常数)，则有Ex(Γ，H)满足定义4的条件1)，且Ex(Γ，H)是常数度网络;

2)由于Γ满足定义4的条件2)，即有D(Γ)∈O(lgN)，又由于Ex(Γ，H)≤D(Γ)，则Ex(Γ，H)满足条件2);

3)由于H∩(S∪H)2≠Φ，|H|为常数，即任意节点g∈G的邻节点的连边Mg为常数，由于deg(Ex(Γ，H))也为常数，则CC(Ex(Γ，H))==ch(ch为常数)．

由于Ex(Γ，H)满足定义4的条件1)、2)、3)，Ex(Γ，H)是小世界的且是常数度的网络，得证．

例3 立方连通圈CCCn(n≥3)是度为3的极小Cayley图Cay(G，S)，其中群G是Z2与Zn的圈积，表示为G=Z2⊗Zn，G上的操作为∀(x1，y1)，(x2，y2)∈ (Zn2，Zn)，(x1，y1)(x2，y2)=(x1⊗σy1(x2)，y1+y2)，σy1是循环右移y1位操作，⊗是异或操作，生成集S=若令ck≤n/2的任意正整数，定义＜i≤ck}，易知H满足定理3的条件，Cayley扩展图Ex(CCCn，H)是常数度的小世界网络，若ck=n/2，其节点度为 2ck，其聚集系数为 3(ck-1)/2(2ck-1);否则其节点度为1+2ck，其聚集系数为3(ck-1)/2(2ck+1)．

定理4 若极小Cayley图Γ=Cay(G，S)满足定义4的条件1)和条件2)，且H'⊆S使得成立，并且有O(lgN)，则Ex(Γ，H)是小世界的．

证 明

1)由于 Γ 满足条件 1)，即有 deg(Γ)∈O(lgN)，又因为)，则deg(Ex(Γ，H))=deg(Γ)+|H|=|S|+|H|∈O(lgN)，Ex(Γ，H)满足条件1);

2)由于 Γ 满足条件 2)，即有D(Γ)∈O(lgN)，又由于Ex(Γ，H)≤D(Γ)，则有Ex(Γ，H)满足条件2);

3)由于|S|+|H|∈O(lgN)，又因为存在H'⊆S，使得H∪H'∪{e}是G的子群，而且满足=|H＇|+|H|∈O(lgN)，则有CC(Ex(Γ，H))≥

当n→∞ 时，CC(Ex(Γ，H))≥(其中，c1、c2分别为常量，则有CC(Ex(Γ，H))满足条件3);

综上所述，Ex(Γ，H)是小世界的，得证．

例4 超立方体Qn为极小Cayley图Cay(G，

S)，其中:G=Zn2;S=0≤i≤n-1}．若令t=「log2n⏋，H'=，x2，…，xt中仅一个为1}，H={(x1，x2，，其中单位元e为(0，0，…，0)，易知H满足定理4的条件，Cayley扩展图Ex(Γ，H)是小世界的，其节点数N=2n，度和直径都为O(lgN)，聚集系数大于或等于1/4．

从以上示例可知，定理3和定理4提供了一种基于极小Cayley图构造小世界网络的方法，该方法非常灵活，只要选择满足条件的极小Cayley图，恰当地扩展其生成集，则可以生成一类具有小世界性质的Cayley图.

4 结论

1)极小Cayley图由于其构造简单和高对称性，已经广泛应用于互连网络拓扑结构的设计中，研究学者基于各种各样的群结构提出了很多性质良好的极小Cayley图，根据互连网络的设计原则，这些图大部分是可扩展的、稀疏的并具有低直径，因此为构造小世界网络提供了很好的模型基础.

2)深入分析了Cayley图的极小性和小世界性质的关联，建立了形式化的极小Cayley图扩展模型，通过恰当的扩展生成集，构造出对称性强且结构规则的小世界网络.

3)本文提出的构造方法可应用于通信网络、结构化P2P覆盖网络等实际互连网络的拓扑结构设计中，这些网络在设计时一方面需要遵循对称性的设计原则，因为节点对称可以简化拓扑维护及路由算法的设计，并且有利于负载均衡，而边对称性可以实现最优容错，另一方面也可以引入小世界性质改进网络性能，如具有小世界性质的通信网络可根据数据访问需求进行分组聚集，并使远程通信也具有较快的通信效率，而具有小世界性质的结构化P2P覆盖网络可提高网络的路由效率、查询和检索的命中率，并且在突发高负载时保持良好性能.

［1］WATTS D J，STROGATZ S H.Collective dynamics of‘small-world’networks［J］.Nature，1998，393(6684):440-442.

［2］NEWMAN M E J，WATTS D J.Renormalization group analysis of the small-world network model［J］.Physics Letters A，1999，263(4/6):341-346.

［3］KLEINBERG J M.Navigation in a small world［J］.Nature，2000，406(6798):845.

［4］OZIK J，HUNT B R，OTT E.Growing networks with geographical attachment preference:emergence of small worlds［J］.Physical Review E，2004，69(2):26108.

［5］COMELLAS F，OZON J，PETERS J G.Deterministic small-world communication networks［J］.Information Processing Letters，2000，76(1):83-90.

［6］COMELLAS F，FERTIN G，RASPAUD A.Recursive graphs with small-world scale-free properties［J］.Physical Review E，2004，69(3):037104.

［7］GUO Shize，LU Zheming，KANG Guangyu，et al.A tree-structured deterministic small-world network［J］.IEICE Transactions on Information and Systems，2012，95(5):1536-1538.

［8］CORSO G.Families and clustering in a natural numbers network［J］.Physical Review E，2004，69(3):36106.

［9］CHANDRA A K，DASGUPTA S.A small world network of prime numbers［J］.Physica A:Statistical Mechanics and its Applications，2005，357(3/4):436-446.

［10］BOETTCHER S，GONCALVES B，AZARET J.Geometry and dynamics for hierarchical regular networks［J］.Journal of Physics A:Mathematical and Theoretical，2008，41(33):335003.

［11］ZHANG Zhongzhi，RONG Lili，GUO Chonghui.A deterministic small-world network created by edge iterations［J］.Physica A:Statistical Mechanics and its Applications，2006，363(2):567-572.

［12］LU Zheming，GUO Shize.A small-world network derived from the deterministic uniform recursive tree［J］.Physica A:Statistical Mechanics and its Applications，2012，391(1/2):87-92.

［13］GOVORCIN J，KNOR M，SKREKOVSKI R.Line graph operation and small worlds［J］.Information Processing Letters，2013，113(5/6):196-200.

［14］XIAO Wenjun，PARHAMI B.Cayley graphs as models of deterministic small-world networks［J］.Information Processing Letters，2006，97(3):115-117.

［15］BIGGS N.Algebraic graph theory［M］.Cambridge，UK:Cambridge University Press，1993.

［16］JWO J S，LAKSHMIVARAHAN S，DHALL S K.A new class of interconnection networks based on the alternating group［J］.Networks，1993，23(4):315-326.

［17］CONTR， TANIMURA E.Small-worldgraphs:characterization and alternative constructions ［J］.Advances in Applied Probability，2008，40(4):939-965.