極小Cayley圖的確定性小世界網絡模型

劉艷霞，奚建清，張 芩

(1.華南理工大學軟件學院，510006廣州;2.華南理工大學計算機科學與工程學院，510006廣州)

小世界網絡在自然界和人類社會中普遍存在，如蛋白質網絡、科學家協(xié)作網絡、WWW網絡、通信網絡等，都具有明顯的小世界特性.通常一個稀疏網絡，如果其直徑(或是網絡平均距離)隨著網絡規(guī)模的增大呈對數或小于對數形式增長，網絡有相對較高的聚集系數，則該網絡稱為小世界網絡.

為再現(xiàn)真實網絡中存在的小世界特性，揭示小世界網絡的內在生成機理，各種小世界模型不斷涌現(xiàn).這些模型主要分為:1)隨機性模型.通過概率分析技術和隨機連邊方法生成網絡，如最初的 WS 模型［1］及其變體 NW 模型［2］、二維的Kleinberg 模型［3］、動態(tài)演化的 OHO 模型［4］;2)確定性模型.網絡節(jié)點和連邊完全由確定的規(guī)則形成.隨機性模型盡管符合大多數真實網絡的生成特性，但無法直觀、清晰地反映網絡的形成機制以及解析計算網絡特性，也不適合以確定方式構造的具有固定節(jié)點度的通信網絡，因此確定性的小世界模型逐漸成為研究熱點，基于各種構造方法的確定性模型相繼被提出.

最早的確定性小世界模型由Comellas等［5］提出，采用基于循環(huán)圖擴展的方法，通過降低直徑或提高聚集系數，將高直徑或低聚集的循環(huán)圖轉變?yōu)樾∈澜缇W絡.樹通常具有低的對數級直徑和小的節(jié)點度，因此基于樹結構的推廣或改造也可生成小世界網絡，如遞歸團樹(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圖的極小性概念，通過分析極小性和聚集系數的關聯(lián)，建立了形式化的Cayley圖擴展模型.該模型通過增加極小Cayley圖的生成集，可靈活地構造出對稱性強且結構規(guī)則的常數度和非常數度的小世界網絡，在通信網絡、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圖.

聚集系數是小世界網絡的重要度量指標．如果網絡中某個節(jié)點v的度為deg(v)，則節(jié)點v的聚集系數cc(v)=其中，Mv為v的所有鄰節(jié)點之間實際存在的邊數，也可理解為v連接的三角形個數．由于Cayley圖具有點對稱性，整個網絡的聚集系數CC(Γ)即為任意節(jié)點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的兩個鄰節(jié)點ga與gb之間存在一條連邊，因此CC(Γ)≠0．

其次，證明必要性．若CC(Γ)≠0，則對于任意的節(jié)點g∈G，其鄰居之間至少存在一條連邊．由于Cayley圖的點對稱性，在此僅需考慮單位元e的聚集系數，其鄰節(jié)點的集合為生成集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(Γ)分別為Γ的節(jié)點集和邊集．

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

2)圖Γ具有較小的直徑，即D(Γ)∈O(log|V(Γ)|);

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

必須說明的是，該定義可以進行小的調整，如稀疏圖中關于節(jié)點度的條件可以替換為E(Γ)的條件，即|E(Γ)|∈O(|V(Γ)|log|V(Γ)|)，較小的直徑可以替換為較小的平均距離，Γ的聚集系數也可表示為CC(Γ)≈c(c＞0)，但由此可知，其本質是相同的．

針對極小Cayley圖和小世界之間的關聯(lián)，可得到如下結論.

定理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)/，盡管其聚集系數較高，但隨著節(jié)點規(guī)模的增大，聚集系數越來越小，按照定理2的證明可知，其不是小世界的．

根據定義4可以發(fā)現(xiàn)，極小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)稱為?；贖的擴展圖，記為Ex(Γ，H);另外，Γ也可稱為Ex(Γ，H)的Cayley基圖．

很明顯，Cayley擴展圖在其基圖上增加了節(jié)點度，使節(jié)點之間存在更多的連邊，降低了網絡直徑并且增加了聚集性.接下來，基于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|為常數，即任意節(jié)點g∈G的鄰節(jié)點的連邊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是循環(huán)右移y1位操作，?是異或操作，生成集S=若令ck≤n/2的任意正整數，定義＜i≤ck}，易知H滿足定理3的條件，Cayley擴展圖Ex(CCCn，H)是常數度的小世界網絡，若ck=n/2，其節(jié)點度為 2ck，其聚集系數為 3(ck-1)/2(2ck-1);否則其節(jié)點度為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)是小世界的，其節(jié)點數N=2n，度和直徑都為O(lgN)，聚集系數大于或等于1/4．

從以上示例可知，定理3和定理4提供了一種基于極小Cayley圖構造小世界網絡的方法，該方法非常靈活，只要選擇滿足條件的極小Cayley圖，恰當地擴展其生成集，則可以生成一類具有小世界性質的Cayley圖.

4 結論

1)極小Cayley圖由于其構造簡單和高對稱性，已經廣泛應用于互連網絡拓撲結構的設計中，研究學者基于各種各樣的群結構提出了很多性質良好的極小Cayley圖，根據互連網絡的設計原則，這些圖大部分是可擴展的、稀疏的并具有低直徑，因此為構造小世界網絡提供了很好的模型基礎.

2)深入分析了Cayley圖的極小性和小世界性質的關聯(lián)，建立了形式化的極小Cayley圖擴展模型，通過恰當的擴展生成集，構造出對稱性強且結構規(guī)則的小世界網絡.

3)本文提出的構造方法可應用于通信網絡、結構化P2P覆蓋網絡等實際互連網絡的拓撲結構設計中，這些網絡在設計時一方面需要遵循對稱性的設計原則，因為節(jié)點對稱可以簡化拓撲維護及路由算法的設計，并且有利于負載均衡，而邊對稱性可以實現(xiàn)最優(yōu)容錯，另一方面也可以引入小世界性質改進網絡性能，如具有小世界性質的通信網絡可根據數據訪問需求進行分組聚集，并使遠程通信也具有較快的通信效率，而具有小世界性質的結構化P2P覆蓋網絡可提高網絡的路由效率、查詢和檢索的命中率，并且在突發(fā)高負載時保持良好性能.

［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，F(xiàn)ERTIN 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.