應(yīng)用TFLS算法尋找SBEGN模型具最多葉子生成樹

王曉敏，趙喜楊，姚 兵

（西北師范大學 數(shù)學與統(tǒng)計學院，甘肅 蘭州 730070）

0 引 言

現(xiàn)實世界中的自然、社會和科學系統(tǒng)均以網(wǎng)絡(luò)的形式存在，而且這些網(wǎng)絡(luò)大多數(shù)具有無標度性或小世界性，或者二者皆有［1－3］.當今的復(fù)雜網(wǎng)絡(luò)理論已成為很多學科發(fā)展的新視角和指導(dǎo)思想，如疾病傳播［4］.近年來一個活躍的研究課題是試圖運用生成樹來刻畫復(fù)雜網(wǎng)絡(luò)，從生成樹這一全新的視角出發(fā)，對復(fù)雜網(wǎng)絡(luò)的拓撲結(jié)構(gòu)、物理意義和數(shù)學特性進行深入、廣泛的研究.新方法已在金融、生理醫(yī)學、生物等自然科學或社會科學領(lǐng)域得到深入淺出的探討.

通常，復(fù)雜網(wǎng)絡(luò)中含有很多的葉子，所以在網(wǎng)絡(luò)的結(jié)構(gòu)研究中自然而然地使用了生成樹，使得生成樹能夠廣泛地用于網(wǎng)絡(luò)研究.例如，無線傳感器網(wǎng)絡(luò)的生成樹最大限度地提高了鏈路的質(zhì)量度量的總和，并提供了與所有節(jié)點對之間的最短的最弱鏈路的路徑［5］.生成樹的最典型的應(yīng)用之一是：Perlman［6］利用生成樹與網(wǎng)絡(luò)間的結(jié)構(gòu)關(guān)系發(fā)明了廣泛用于網(wǎng)橋、交換機上的生成樹協(xié)議，以及各種使用路由算法的鏈路狀態(tài)機制.應(yīng)用生成樹在復(fù)雜網(wǎng)絡(luò)中實現(xiàn)有效的搜索也是研究網(wǎng)絡(luò)的一個重要的課題.例如：生成樹被應(yīng)用于網(wǎng)絡(luò)的搜索算法［5］.復(fù)雜網(wǎng)絡(luò)搜索的早期例子：著名的“六度分離”實驗在一定程度上揭示了實際網(wǎng)絡(luò)的可搜索性.Kleinberg［7］首先在理論上研究了復(fù)雜網(wǎng)絡(luò)的搜索能力，即在網(wǎng)絡(luò)中實現(xiàn)快速搜索的性質(zhì)；之后Kleinberg、Watts、Adamic等［8］針對各自的特定模型提出了對應(yīng)的搜索算法.值得注意的是，關(guān)于無標度生成樹的研究報道很少［9］，理解或給出網(wǎng)絡(luò)模型的無標度生成樹的文章幾乎見不到.

為更好地理解和認識復(fù)雜網(wǎng)絡(luò)，學者們經(jīng)常采用建立動態(tài)網(wǎng)絡(luò)模型來逼近和模擬現(xiàn)實網(wǎng)絡(luò).本文借用相似于文獻［3］的構(gòu)造網(wǎng)絡(luò)模型的方法，采用初始網(wǎng)絡(luò)為一般的連通網(wǎng)絡(luò)，并使得新進入網(wǎng)絡(luò)的節(jié)點多于一個，從而構(gòu)造出本文的研究對象SBEGN 模型.不難觀察到，新發(fā)表的文章更傾向于引用一些被廣泛引用的重要文獻，新的個人主頁上的超文本鏈接更有可能指向著名的站點，與強者恒強、弱者恒弱的網(wǎng)絡(luò)現(xiàn)象相吻合.受這些網(wǎng)絡(luò)現(xiàn)象的啟發(fā)，本文設(shè)計時間優(yōu)先層次搜索算法來尋找具有最多葉子的生成樹，以期用算法優(yōu)化研究網(wǎng)絡(luò)的生成樹，提高網(wǎng)絡(luò)的搜索效率，減少網(wǎng)絡(luò)的運算量，為尋找實際網(wǎng)絡(luò)模型的生成樹提供理論幫助.本文所考慮的圖均為有限、無向簡單圖，沒有定義的術(shù)語和符號均源于文獻［10］.對于一個圖G，它的葉子節(jié)點的集合用記號L（G）表示，nd（G）表示圖G中度數(shù)為d的頂點的個數(shù).記號｜X｜表示集合X的元素個數(shù).

1 SBEGN模型的建立及其基本性質(zhì)

對任意給定的至少有2 個節(jié)點的連通網(wǎng)絡(luò)N（0），用d1，d2，…，da表示連通網(wǎng)絡(luò)N（0）不同的度，且 滿 足d1＞d2＞… ＞da.初 始 網(wǎng) 絡(luò) 為N（0），用記號nv（0）和ne（0）分別表示它的節(jié)點個數(shù)和邊數(shù)目，記號V（0）和E（0）分別表示初始網(wǎng)絡(luò)N（0）的節(jié)點集合和邊集合，使得nv（0）＝｜V（0）｜，ne（0）＝｜E（0）｜.對于初始網(wǎng)絡(luò)N（0）的每一條邊界邊uv∈E（0），新增加m個節(jié)點，并且將這m個節(jié)點與邊uv的端點u、v分別相連，產(chǎn)生t＝1時刻的網(wǎng)絡(luò)N（1），并將最后一個新節(jié)點w與節(jié)點u、v分別相連所得的2條邊wu和wv定義為網(wǎng)絡(luò)N（1）的邊界邊.記號X1代表給N（0）新增加的節(jié)點集合，Y1代表給N（0）新增加的邊集合，則有Y1＝｛wu，wv：uv∈E（0），w∈X1｝，以及V（1）＝V（0）∪X1，E（1）＝E（0）∪Y1，｜Y1｜＝2｜X1｜＝2mne（0）.

類似地，對于網(wǎng)絡(luò)N（1）的每條邊界邊xy∈E（1），新增加m個新節(jié)點，并且將這m個節(jié)點分別與邊xy的端點x、y相連，從而得到t＝2時刻的網(wǎng)絡(luò)N（2），并將最后一個新節(jié)點z與節(jié)點x、y分別相連所得的2 條邊zx和zy定義為網(wǎng)絡(luò)N（2）的邊界邊.顯然，N（2）的節(jié)點集合可表示為V（2）＝V（1）∪X2，它的邊集合為E（2）＝E（1）∪Y2.以此類推，按照上述構(gòu)造方法，從網(wǎng)絡(luò)N（t－1）可得到網(wǎng)絡(luò)N（t），簡稱它為SBEGN 模型.下面給出SBEGN 模型N（t）的一些基本參數(shù).記號Xk和Yk分別表示給N（k－1）新增的節(jié)點集合和邊集合.當t≥1時，SBEGN 模型N（t）的節(jié)點集合V（t）與邊集合E（t）可以分別表示為

因為

不難得到SBEGN 模型N（t）的節(jié)點數(shù)目和邊數(shù)目

此外，SBEGN 模型N（k）的新增加節(jié)點數(shù)目為

且有ne（0）2k條邊界邊，在SBEGN 模型N（t）中，最大度Δ（N（t））＝（tm＋1）·Δ（N（0）），最小度δ（N（t））＝2.則SBEGN 模型是一個稀疏網(wǎng)絡(luò)，因為它的平均度〈k〉滿足

式（3）表明SBEGN 模型N（t）具有優(yōu)先鏈接性，即新進入N（t）的節(jié)點與初始網(wǎng)絡(luò)N（0）中的節(jié)點相連的概率較大.同時，N（t）的構(gòu)造表明N（t）具有增長性，說明N（t）屬于BA 無標度模型［3－4］.

以 下 用k（u，i）表 示 于 時 刻i節(jié) 點u在SBEGN 模型N（i）中所連接的邊數(shù)目，用kt（u，i）表示節(jié)點u在N（i）中的具有最多葉子生成樹中所連接的邊數(shù)目.

為證明SBEGN 模型N（t）是層次網(wǎng)絡(luò)，下面估算N（t）的每個節(jié)點的聚集系數(shù).

（1）對初始網(wǎng)絡(luò)N（0）的節(jié)點u∈V（0），設(shè)k（u，0）＝dj，那么，這個節(jié)點u在N（t）中的鄰點的個數(shù)也就是它的度數(shù)，且k（u，t）＝（1＋tm）dj.記號Eu表示節(jié)點u的鄰點之間的邊集合，按照SBEGN 模型N（t）的構(gòu)造，可計算出Eu的元素個數(shù)為｜Eu｜＝（1＋tm）dj.按照定義，節(jié)點u的聚集系數(shù)為

（2）對在i（＜t）時刻進入網(wǎng)絡(luò)N（i）的節(jié)點v，且節(jié)點v又是N（i＋1）的一條邊界邊的端點，那么，在N（t）中，節(jié)點v的度數(shù)為k（v，t）＝2［（ti）m＋1］，它的鄰點之間的邊集合Ev有2（t－i）m＋1個元素.節(jié)點v的聚集系數(shù)為

（3）對在j（＜t）時刻進入網(wǎng)絡(luò)N（j）的節(jié)點w，且節(jié)點w又不是N（j＋1）的一條邊界邊的端點，則在N（t）中它的度數(shù)為k（w，t）＝2，它的鄰點之間的邊集合Ew僅有一個元素，所以

按照文獻［11］和［12］的定律，上述式（6）～（8）關(guān)于節(jié)點聚集系數(shù)分布的式子證明SBEGN模型是層次網(wǎng)絡(luò)，且對任何時刻t成立，即SBEGN 模型與好萊塢的演員網(wǎng)、WWW、代謝網(wǎng)絡(luò)等屬于同一類網(wǎng)絡(luò)［12］，從而為本文的時間優(yōu)先層次搜索算法提供了理論依據(jù).圖1給出SBEGN 模型的例子.

圖1 當m＝2時，SBEGN 模型的N（0）、N（1）及N（2）Fig.1 N（0），N（1）and N（2）of SBEGN models when m＝2

2 SBEGN 模型的生成樹

SBEGN 模型N（t）的生成樹是一個連通且邊數(shù)目最少的子網(wǎng)絡(luò)，本章尋找N（t）的具有最多葉子的生成樹.一般情形下，N（t）的具有最多葉子的生成樹是不唯一的.用L（TM（t））表示N（t）的具有最多葉子的生成樹TM（t）的全體葉子的集合.SBEGN 模型N（t）的生成樹TM（t）具有如下的性質(zhì)：

引理1 SBEGN 模型N（t）的任意一棵具有最多葉子的生成樹TM（t）的葉子集合完全包含新進入N（t－1）的節(jié)點集合Xt.

證明 對任意時刻t≥1，假設(shè)存在節(jié)點w∈Xt，但wL（TM（t））.根據(jù)SBEGN 模型N（t）的構(gòu)造，節(jié)點w的度數(shù)為k（w，t）＝2，且節(jié)點w與t－1時刻的SBEGN 模型N（t－1）的一條邊界邊uv的2個端點u和v分別相連.注意到，由于w不是TM（t）的葉子，則節(jié)點u和v至少有一個不是TM（t）的葉子，假設(shè)節(jié)點u不是葉子.則可以構(gòu)造SBEGN 模型N（t）的另一棵生成樹H如下：在TM（t）中刪除邊wv，連接邊uv.顯然w，v∈L（H），且生成樹H的葉子數(shù)目｜L（H）｜≥｜L（TM（t））｜＋1，這違背TM（t）是N（t）的一棵具有最多葉子的生成樹.本引理得證.□

引理2 設(shè)N（0）是給定的連通初始網(wǎng)絡(luò).對SBEGN 模型N（t），有

（Ⅰ）當t≥3 和L（TM（1））∩V（0）≠，則L（TM（t））∩V（0）＝.

（Ⅱ）當t≥2 和L（TM（1））∩V（0）＝，則L（TM（t））∩V（0）＝.

證明 為證結(jié)論（Ⅰ），假設(shè)存在葉子x∈L（TM（t））∩V（0），即L（TM（t））∩V（0）≠，設(shè)xy∈E（0），顯然，yL（TM（t））.根據(jù)SBEGN 模型N（t）的構(gòu)造和引理1，存在N（t）的一個2度節(jié)點wt，i∈Xt與節(jié)點x、wt－1，i∈Xt－1分別相連，則有wt－1，iL（TM（t）），并且wt，i∈L（TM（t））.注意到，節(jié)點wt－1，i的度數(shù)k（wt－1，i，t）≥3，也就是說，節(jié)點wt－1，i與節(jié)點x、wt，i、wt－2，i均相連.因為t－2≥3，如果wt－2，i∈L（TM（t）），導(dǎo)致wt，i、wt－1，i與其他節(jié)點不連接，這矛盾于TM（t）是樹.下面構(gòu)造N（t）的 另 一 棵 生 成 樹H＊：刪除邊wt，iwt－1，i和wt－1，iwt－2，i；如果節(jié)點x在TM（t）中與節(jié)點y連接，將節(jié)點x與節(jié)點wt，i和wt－1，i分別相連；如果節(jié)點x在TM（t）中與節(jié)點u（≠y）連接，則刪除邊xu，然后將節(jié)點x與節(jié)點y連接.此時，｜L（H＊）｜≥｜L（TM（t））｜，矛盾于TM（t）是具有最多葉子生成樹的事實.

結(jié)論（Ⅱ）的證明相同于結(jié)論（Ⅰ）的證明，故不贅述.□

定理1 當t≥3時，SBEGN 模型N（t）的每一棵具有最多葉子的生成樹TM（t）的葉子數(shù)目為

且它的直徑D（TM（t））不超過初始網(wǎng)絡(luò)N（0）的具有最多葉子生成樹TM（0）的直徑D（TM（0））加上（2t－1）.

證明 為證明此定理，先給出時間優(yōu)先層次搜索算法.

時間優(yōu)先層次搜索算法（time－first levelsearching algorithm），簡稱為TFLS算法.

輸入 一個SBEGN 模型N（t），t≥3.

輸出N（t）的全體具有最多葉子的生成樹TM（t），且每一棵TM（t）帶有一個關(guān)于節(jié)點的時間序函數(shù)p.

步驟1 當k＝1，2時，F(xiàn)M（k）←｛N（k）的全體具有最多葉子的生成樹｝.對每一棵具有最多葉子的生成樹T0∈FM（k），定義V（T0）節(jié)點的一個時間序函數(shù)p為：若在V（T0）中，節(jié)點x的位置前于節(jié)點y的位置，則p（x）＜p（y），且有1＝min｛p（x）｜x∈V（T0）｝，｜V（T0）｜＝max｛p（x）｜x∈V（T0）｝.以下記號Nei（x）為與節(jié)點x有連線的節(jié)點集合.

步驟2s←1若t為奇數(shù)，否則s←2.

步驟3 如果s＜t－2，Gs←，到步驟4.如果s＝t－2，到步驟5.

步驟4 若FM（s）＼Gs＝，s←s＋1，到步驟3.否則，取Ts∈FM（s）＼Gs，V″←V（Ts），E″←E（Ts），T″←（V″，E″），Xs←，到步驟4.1.

步驟4.1 如果V（Ts）＼Xs＝，TM（s＋1）←T″；FM（s＋1）←FM（s＋1）∪｛TM（s＋1）｝，Gs←Gs∪｛Ts｝，到步驟4.如果V（Ts）＼Xs≠，到步驟4.2.

步驟4.2 取x∈V（Ts）＼Xs，使得p（x）＝min｛p（y）｜y∈V（Ts）＼Xs｝.若Nei（x）∩（V（s＋1）＼V″）＝，Xs←Xs∪｛x｝，到步驟4.1；否則，到步驟4.3.

步驟4.3Nei（x）∩（V（s＋1）＼V″）＝｛ux，1，ux，2，…，ux，m｝（m≥1），執(zhí)行：p（ux，1）←p（u′）＋1，u′是V″的最后一個節(jié)點，然后把ux，1放進V″的最后 一 個 位 置 上；從j＝2 到m，p（ux，j）←p（ux，j－1）＋1，把ux，j放進V″的最后一個位置上.E″←E″∪｛xy｜y∈V″｝，T″←（V″，E″）；Xs←Xs∪｛x｝，到步驟4.1.

步驟5FM（t）←，F(xiàn)←.

步驟5.1 如果FM（t－2）＼F≠，取Tt－2∈FM（t－2）＼F，由上面的過程，知V（Tt－2）的節(jié)點有 一 個 時 間 序 函 數(shù)p；VH←V（Tt－2），EH←E（Tt－2），H←（VH，EH）；Xt←，到步驟5.2.如果FM（t－2）＼F＝，到步驟6.

步驟5.2 如果V（Tt－2）＼Xt≠，到步驟5.3；如果V（Tt－2）＼Xt＝，F(xiàn)←F∪｛Tt－2｝，到步驟5.1.

步驟5.3 取x∈V（Tt－2）＼Xt，使得p（x）＝min｛p（y）｜y∈V（Tt－2）＼Xt｝，若Nei（x）∩（V（t）＼V（t－2））＝，Xt←Xt∪｛x｝，到步驟5.2；否則，到步驟5.4.

步驟5.4Nei（x）∩（V（t）＼V（t－2））＝｛vx，1，vx，2，…，vx，n｝（n≥1）.執(zhí) 行：p（vx，1）←p（u′）＋1，u′是VH的最后一個節(jié)點，然后把vx，1放進VH的最后一個位置上；從j＝2到n，p（vx，j）←p（ux，j－1）＋1，把ux，j放進VH的最后一個位置上.EH←EH∪｛xy｜y∈VH｝，H←（VH，EH）.Xt←Xt∪｛x｝.FM（t）←FM（t）∪｛H｝，到步驟5.2.

步驟6 返回FM（t），且FM（t）的每一棵具有最多葉子的生成樹TM（t）帶有一個時間序函數(shù)p.

根據(jù)引理2，TFLS算法的步驟3中s＝t－2成立.因為SBEGN 模型N（k）中的Xk里有個節(jié)點成為N（k）的邊界邊的端點，則在SBEGN 模型N（k＋1）中，這些節(jié)點與新增加的節(jié)點連線，且當k≥2，它們不可能是TM（k＋1）的葉子.根據(jù)TFLS算法，有如下的遞歸公式：

根據(jù)｜L（TM（2））｜＝｜X2｜＋｜X1｜，整理得

聯(lián)立式（4），可求得｜L（TM（t））｜的精確值為

根據(jù)TFLS算法找到TM（t）的過程，是每次給TM（t－1）添加葉子得到生成樹TM（t），即給TM（t－1）的最長路徑增加了2.則當t≥3 時，D（TM（t））不超過初始網(wǎng)絡(luò)N（0）的具有最多葉子生成樹TM（0）的直徑加上（2t－1）.□

圖2給出用算法找到圖1中SBEGN 模型的3個具有最多葉子的生成樹.

圖2 當m ＝2 時，3棵生成樹TM （0）、TM（1）和TM（2）Fig.2 Three spanning trees TM（0），TM（1）and TM（2）when m ＝2

3 TFLS算法找到的生成樹的性質(zhì)

由定理1可得出下面2個極限.

上述兩個極限說明，當時間t足夠大時，比值QT幾乎等價于比值QNT，即QT～QNT.因此可以嘗試用生成樹TM（t）來解釋SBEGN 模型N（t）的一些性質(zhì).

下面討論生成樹TM（t）的度譜.前面提到初始網(wǎng)絡(luò)N（0）節(jié)點不同的度數(shù)為d1，d2，…，da，且d1＞d2＞…＞da.TFLS算法找到的生成樹TM（t）的節(jié)點數(shù)目與度數(shù)的度譜在表1中給出，其中t時刻度數(shù)為d的節(jié)點個數(shù)為nd（t），f（di）＝tm（di

表1 TFLS算法找到的生成樹TM（t）的度譜Tab.1 The spectrum of spanning tree TM（t）by applying the TFLS algorithm

由于生成樹TM（t）的度譜是離散型，可以計算它的隨機選擇恰好有k邊的節(jié)點的概率P（k）.根據(jù)文獻［3］使用的統(tǒng)計技術(shù)和式（4），可得下面的式子：

上式說明，最多葉子的生成樹TM（t）服從指數(shù)分布，TM（t）亦為指數(shù)型生成樹.

在j（＜t）時刻，最多葉子的生成樹TM（j）的頂點數(shù)目為｜V（TM（j））｜＝nv（j），則它的累積分布為

下面再給出關(guān)于SBEGN 模型的具有最多葉子的生成樹的結(jié)論.

定理2 當t≥3時，SBEGN 模型N（t）的任意2棵具有最多葉子的生成樹TMi（t）和TMj（t）擁有相同的葉子集合，即L（TMi（t））＝L（TMj（t））.

證明 令Li＝L（TMi（t））和Lj＝L（TMj（t））.注意到t≥3，由引理2，Li∩V（0）＝＝Lj∩V（0）.設(shè)有u∈Li，但uLj.由于Li∩N（0）＝，不妨設(shè)u是給N（k）的邊界邊xy添加的m個節(jié)點中的一個.它在Lj中的度數(shù)kt，j（u，t）滿足2［（t－k）m＋1］≥kt，j（u，t）≥2，它在N（t）中的度數(shù)k（u，t）＝2或k（u，t）＝2［（t－k）m＋1］.

情形1 如果u不是N（k＋1）的任何邊界邊的端點，則它在N（t）中的度數(shù)k（u，t）＝2，故kt，j（u，t）＝1.構(gòu)造N（t）的另一棵生成樹H＝Lj－uy＋xy，即在Lj中刪去邊uy，然后將x和y連接.顯然，｜L（H）｜＞｜L（TMj（t））｜，矛盾.這是由于u是H的葉子，而Lj的其他節(jié)點的屬性在H中沒有發(fā)生變化.

情形2 如果u是N（k＋1）的邊界邊的端點，那么，度數(shù)kt，j（u，t）≥3，且它在N（t）中的度數(shù)為k（u，N（t））＝2［（t－k）m＋1］.根據(jù)上面節(jié)點u∈Li的屬性，在N（t）中，節(jié)點x和u與節(jié)點x1，x2，…，xm均相連，節(jié)點y和u與節(jié)點y1，y2，…，ym均相連.根據(jù)引理1和u∈Li，得xr，yr∈Li，r＝1，2，…，m.因為t≥3，則在N（t）中，有度數(shù)k（x，t）≥2和k（y，t）≥2.根據(jù)引理2，xLi和yLj.對TMj（t）實施如下運算：刪去邊uy將x與y連接，然后對r＝1，2，…，m，將xr與x連接，將yr與y連接，得到新的生成樹H′.由于u∈L（H′），而且TMj（t）的其余節(jié)點的屬性在H′中沒有發(fā)生變化，也就是說｜L（H′）｜＞｜L（TMj（t））｜，這與TMj（t）是最多葉子生成樹的假定矛盾.

綜合上述2種情形的推證，L（TMi（t））＝L（TMj（t））.□

由于SBEGN 模型是層次網(wǎng)絡(luò)，運用以上結(jié)論不難證明：當t≥3時，SBEGN 模型N（t）的一棵具有最多葉子生成樹TM（t）包含次一級SBEGN 模型N（t－1）的一棵具有最多葉子的生成樹TM（t－1）.

4 結(jié) 語

本文構(gòu)造了SBEGN 模型N（t），并設(shè)計了時間優(yōu)先層次搜索算法，隨后找出SBEGN 模型N（t）的具有最多葉子的生成樹TM（t），確定了任何具有最多葉子的生成樹的拓撲性質(zhì).需要指出的是，本文的SBEGN 模型具有良好的性質(zhì)：當t≥3時，N（t）的任意2棵具有最多葉子的生成樹TMi（t）和TMj（t）擁有相同的葉子集合，且N（t）為層次網(wǎng)絡(luò)，它的直徑小于生成樹TM（t）的直徑，換句話說，N（t）是小世界網(wǎng)絡(luò)模型.這些良好的性質(zhì)不僅為實際網(wǎng)絡(luò)建設(shè)提供了可靠的理論依據(jù)，更重要的是為模擬實際網(wǎng)絡(luò)提供了易于理解和掌握的工具，并不斷產(chǎn)生優(yōu)化型算法.作為進一步研究的方向，將考慮模型的隨機增加連線或者隨機刪除連線，這樣的研究對實際網(wǎng)絡(luò)的模擬會更有價值.顯然，確定這種網(wǎng)絡(luò)模型的拓撲性質(zhì)以及找到它們的具有最多葉子的生成樹將是研究的關(guān)鍵，也是研究的難點.

［3］ ZHANG Zhong－zhi，RONG Li－li，GUO Chong－h(huán)ui.A deterministic small－world network created by edge iterations［J］.Physica A：Statistical Mechanics and its Applications，2006，363（2）：567－572.

［4］ Pastor－Satorras R，Vespignani A.Epidemic spreading in scale－free networks ［J］.Physical Review Letters，2001，86（14）：3200－3203.

［5］ ZHENG Geng－zhong，LIU San－yang，QI Xiaogang.Scale－free topology evolution for wireless sensor networks with reconstruction mechanism［J］.Computers and Electrical Engineering，2012，38（3）：643－651.

［6］ Perlman R.Hierarchical networks and the subnetwork partition problem ［J］.Computer Networks and ISDN Systems，1985，9（4）：297－303.

［7］ Kleinberg J.The small－world phenomenon：An algorithmic perspective［C］／／Proceedings of the 32nd Annual ACM Symposium on Theory of Computing，STOC 2000.New York：Association for Computing Machinery，2000：163－170.

［8］ Adamic L A，Adar E.How to search a social network［J］.Social Networks，2005，27（3）：187－203.

［9］ Kim Dong－h(huán)ee，Noh Jae－dong，Jeong Ha－woong.Scale－free trees：The skeletons of complex networks［J］.Physical Review E—Statistical Nonlinear，and Soft Matter Physics，2004，70（42）：046126.

［10］ Bondy J A，Murty U S R.Graph Theory with Applications ［M］.Amsterdam：North Holland，1976.

［11］ Dorogovtsev S N，Goltsev A V，Mendes J F F.Pseudofractal scale－free web ［J］.Physical Review E—Statistical Nonlinear，and Soft Matter Physics，2002，65（6）：066122.