王曉敏，姚兵，2

(1. 西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州 730070; 2. 蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070)

無(wú)標(biāo)度網(wǎng)絡(luò)累積分布的新方法*

王曉敏1，姚兵1，2

(1. 西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 蘭州 730070; 2. 蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070)

以算法的方式給出了具有無(wú)標(biāo)度性的極大平面圖網(wǎng)絡(luò)，計(jì)算了極大平面圖網(wǎng)絡(luò)模型的頂點(diǎn)累積分布和邊累積分布，并驗(yàn)證二者的等價(jià)性。此外，按照混合方式的不同，提出了新的統(tǒng)計(jì)指標(biāo):邊點(diǎn)混合累積分布。隨后，提出猜想：采用線性混合方式的邊點(diǎn)混合累積分布與頂點(diǎn)累積分布是等價(jià)的。此猜想為全方位、多角度的探討無(wú)標(biāo)度網(wǎng)絡(luò)提供了新視角。

無(wú)標(biāo)度網(wǎng)絡(luò)；頂點(diǎn)累積分布；邊累積分布；冪律分布

自然界、生物界、工程界以及人類社會(huì)中的大量復(fù)雜系統(tǒng)成為當(dāng)今的復(fù)雜網(wǎng)絡(luò)科學(xué)的熱門研究對(duì)象，如 Internet[1]、社交網(wǎng)絡(luò)等[2]。復(fù)雜網(wǎng)絡(luò)的規(guī)模隨時(shí)間的推移不斷變化，給全方位的探討復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)及功能帶來(lái)了很大的障礙。因此，為復(fù)雜網(wǎng)絡(luò)建立合理的演化模型，對(duì)于深入考查其拓?fù)浣Y(jié)構(gòu)、網(wǎng)絡(luò)優(yōu)化、網(wǎng)絡(luò)資源的合理分配以及網(wǎng)絡(luò)信息安全等具有重要的指導(dǎo)意義。一般情況下，復(fù)雜網(wǎng)絡(luò)的規(guī)模較大，在缺少關(guān)于其節(jié)點(diǎn)間連接關(guān)系的前提下，最簡(jiǎn)單、最直接的復(fù)雜網(wǎng)絡(luò)演化模型應(yīng)該是 Erd?s 和 Rényi的隨機(jī)圖模型。在該模型中，每個(gè)節(jié)點(diǎn)獲得連接的機(jī)會(huì)均等，節(jié)點(diǎn)的度(即該節(jié)點(diǎn)連接的邊數(shù))服從 Poisson 分布。網(wǎng)絡(luò)技術(shù)、計(jì)算機(jī)技術(shù)以及數(shù)據(jù)處理技術(shù)的提高使得人們有可能獲得許多實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)間的連接關(guān)系，如萬(wàn)維網(wǎng)、神經(jīng)網(wǎng)絡(luò)以及物流網(wǎng)絡(luò)等。對(duì)這些實(shí)際網(wǎng)絡(luò)進(jìn)行實(shí)證研究，發(fā)現(xiàn)這些復(fù)雜網(wǎng)絡(luò)存在一個(gè)共同的特點(diǎn)，網(wǎng)絡(luò)的節(jié)點(diǎn)的度數(shù)存在極大的差異，節(jié)點(diǎn)的度分布服從冪律分布，而不是像隨機(jī)圖模型所預(yù)測(cè)的那樣服從 Poisson 分布，這樣的復(fù)雜網(wǎng)絡(luò)稱為無(wú)標(biāo)度網(wǎng)絡(luò)。

自1999年 Barabási和Albert發(fā)表有關(guān)復(fù)雜網(wǎng)絡(luò)的無(wú)標(biāo)度性的文章以來(lái)，在此后的十幾年里，各行各業(yè)的學(xué)者成功的運(yùn)用復(fù)雜網(wǎng)絡(luò)理論解決了一些問(wèn)題，使得復(fù)雜網(wǎng)絡(luò)已經(jīng)滲透到許多不同領(lǐng)域的學(xué)科[3-6]。從微觀的細(xì)胞網(wǎng)絡(luò)到宏觀的宇宙網(wǎng)絡(luò)，發(fā)現(xiàn)許多具有無(wú)標(biāo)度性質(zhì)的網(wǎng)絡(luò)。在驗(yàn)證冪律分布的時(shí)候，不少說(shuō)明網(wǎng)絡(luò)是無(wú)標(biāo)度網(wǎng)絡(luò)的文章均采用文獻(xiàn) [7] 中的技術(shù)手段，計(jì)算網(wǎng)絡(luò)模型的頂點(diǎn)累積分布，驗(yàn)證頂點(diǎn)累積分布服從冪律分布，依據(jù)此標(biāo)準(zhǔn)來(lái)確定具有無(wú)標(biāo)度性，文獻(xiàn)[8] 給出了一類遞歸集團(tuán)樹(shù)的無(wú)標(biāo)度性，文獻(xiàn)[9]構(gòu)造了全邊增長(zhǎng)網(wǎng)絡(luò)并給出了尋找其最多葉子生成樹(shù)的算法。文獻(xiàn)[10]探討一類增長(zhǎng)網(wǎng)絡(luò)模型的生成樹(shù)，文獻(xiàn)[11]中討論了無(wú)標(biāo)度網(wǎng)絡(luò)的平衡集。文獻(xiàn)[12]將低維的阿波羅網(wǎng)絡(luò)推廣到高維阿波羅網(wǎng)絡(luò)，并驗(yàn)證了高維阿波羅網(wǎng)絡(luò)的無(wú)標(biāo)度性。文獻(xiàn)[13] 的作者驗(yàn)證了極大平面圖的 Sierpinski 網(wǎng)絡(luò)的無(wú)標(biāo)度性。此外，文獻(xiàn)[14]的作者提出一個(gè)驗(yàn)證冪律分布的新方法，即邊累積分布服從冪律分布，進(jìn)而說(shuō)明網(wǎng)絡(luò)是無(wú)標(biāo)度網(wǎng)絡(luò)。此外，一些學(xué)者討論了對(duì)網(wǎng)絡(luò)添加簡(jiǎn)單圖所構(gòu)成的網(wǎng)絡(luò)的性質(zhì)，兩個(gè)網(wǎng)絡(luò)之間的運(yùn)算，以及尋找網(wǎng)絡(luò)的最大葉子生成樹(shù)的算法等[15-17]。

用文獻(xiàn) [13] 建立的極大平面圖網(wǎng)絡(luò)模型，本文計(jì)算該網(wǎng)絡(luò)模型的頂點(diǎn)累積分布和邊累積分布，并證明邊累積分布和頂點(diǎn)累積分布是等價(jià)的。隨后，提出了按照混合方式區(qū)分的新的統(tǒng)計(jì)指標(biāo)，即邊點(diǎn)混合累積分布，并對(duì)邊點(diǎn)混合累積分布的冪律特性進(jìn)行計(jì)算和證明。

1 主要結(jié)論

1.1 Sierpinski 網(wǎng)絡(luò)的建立

本小節(jié)先引入經(jīng)典的Sierpinski 分形墊(也稱Sierpinski三角形)。Sierpinski分形墊可以使用迭代的方法進(jìn)行構(gòu)造。用t表示迭代的次數(shù)，令S(t)表示經(jīng)過(guò)t步演化后得到的Sierpinski分形墊，則其具體的構(gòu)造過(guò)程可以用下面的Sierpinski算法給出。

Sierpinski-算法

初始化。t=0，S(0)是一個(gè)等邊三角形。

運(yùn)算。t=1，連接等邊三角形S(0)的各邊的三等分點(diǎn)，從而將原等邊三角形分成 9 個(gè)小等邊三角形，然后“舍棄”中間的3個(gè)倒立的小三角形，便得到S(1)。未舍棄的三角形稱為活動(dòng)三角形。

迭代。繼續(xù)對(duì)剩下的6個(gè)活動(dòng)小三角形按上面同樣的方法繼續(xù)分割，并“舍棄”中間倒立的3個(gè)小三角形，如此不斷地重復(fù)“分割”與“舍棄”的過(guò)程，便得到Sierpinski三角形S(t)。

Sierpinski 分型墊的具體生長(zhǎng)過(guò)程在圖1 中給出。

圖1 Sierpinski分型墊的構(gòu)造過(guò)程S(0), S(1), S(2) (左邊t=0, 中間t=1, 右邊t=2)Fig.1 The construction process of the Sierpinski gasket S(0), S(1), S(2)(left t=0, middle t=1, right t=2)

根據(jù) Sierpinski 分形墊，通過(guò)如下映射方法可構(gòu)造 Sierpinski 網(wǎng)絡(luò):將 Sierpinski 分形墊中每個(gè)被刪除的三角形映射為網(wǎng)絡(luò)節(jié)點(diǎn)，將 Sierpinski 分形墊的所有被刪除的三角形與初始等邊三角形相交映射為網(wǎng)絡(luò)的邊。為了保持一致，分形墊中初始等邊三角形的三條邊也分別對(duì)應(yīng) 3 個(gè)不同的節(jié)點(diǎn)。基于S(0)、S(1)、S(2)的生長(zhǎng)過(guò)程可以構(gòu)造出相應(yīng)的Sierpinski網(wǎng)絡(luò)在圖-2 給出解釋和說(shuō)明。這樣，便得到了一個(gè)Sierpinski網(wǎng)絡(luò)。由于該網(wǎng)絡(luò)描述了Sierpinski分形墊中被刪除三角形邊的接觸關(guān)系，所以稱之為Sierpinski網(wǎng)絡(luò)。Sierpinski網(wǎng)絡(luò)的N(0)、N(1)、N(2)如圖2所示。

圖2 Sierpinski 網(wǎng)絡(luò)N(0), N(1), N(2)(圓點(diǎn)為t=0, 正方形點(diǎn)為t=1, 五角星點(diǎn)為t=3)Fig.2 The Sierpinski network N(0), N(1), N(2)(the circle vertices denote t=0, the square vertices represent t=1, the pentagram vertices stand for t=2)

1.2Sierpinski網(wǎng)絡(luò)的參數(shù)

根據(jù)Sierpinski網(wǎng)絡(luò)模型的構(gòu)造來(lái)計(jì)算該網(wǎng)絡(luò)的階數(shù)和邊數(shù)，令Δv(t),Δe(t)和Δ(t) 分別表示在t時(shí)刻網(wǎng)絡(luò)新增加的節(jié)點(diǎn)數(shù)目以及新增的邊數(shù)目和新增的活動(dòng)三角形的數(shù)目。把按照S(t) 的構(gòu)造演化出來(lái)的Sierpinski網(wǎng)絡(luò)記為N(t)，根據(jù)N(t)的構(gòu)造，t-1時(shí)刻的每一個(gè)活動(dòng)三角形在t時(shí)刻將產(chǎn)生 6個(gè)活動(dòng)三角形。因此，可推算出Δ(t)=6Δ(t-1)，又因Δ(0)=1，所以Δ(t)=6t。此外，在t-1時(shí)刻每一個(gè)活動(dòng)三角形將產(chǎn)生3個(gè)新的節(jié)點(diǎn)和9條新邊，容易計(jì)算，

(1)

對(duì)于任意的t>0，用V(t)，E(t) 分別表示Sierpinski網(wǎng)絡(luò)N(t)的節(jié)點(diǎn)集合和邊集合，則可用nv(t),ne(t)分別表示網(wǎng)絡(luò)模型N(t) 在t時(shí)刻總的節(jié)點(diǎn)數(shù)目和總的邊數(shù)目。因此，有

(2)

當(dāng)t足夠大的時(shí)候，Sierpinski 網(wǎng)絡(luò)N(t)的平均度=2ne(t)/nv(t)→6，說(shuō)明該網(wǎng)絡(luò)是一個(gè)稀疏網(wǎng)絡(luò)，也就是說(shuō)，網(wǎng)絡(luò)中實(shí)際存在的邊數(shù)遠(yuǎn)遠(yuǎn)小于可能存在的最大邊數(shù)nv(t)×[nv(t)-1]/2，并且與現(xiàn)實(shí)生活的網(wǎng)絡(luò)現(xiàn)象相吻合。

1.3Sierpinski網(wǎng)絡(luò)的度分布

節(jié)點(diǎn)i是在ti時(shí)刻進(jìn)入網(wǎng)絡(luò)N(t) 的，此時(shí)，節(jié)點(diǎn)i的度為4。令Δ(i,t) 表示t時(shí)刻產(chǎn)生的活動(dòng)三角形的個(gè)數(shù)，這些三角形在t+1時(shí)刻將產(chǎn)生的新節(jié)點(diǎn)與節(jié)點(diǎn)i相連。在ti時(shí)刻，Δ(i,ti)=3，根據(jù)網(wǎng)絡(luò)的迭代過(guò)程，可以看出網(wǎng)絡(luò)N(ti) 新增加的一個(gè)活動(dòng)三角形將會(huì)在下一時(shí)刻形成 6個(gè)新的活動(dòng)三角形。令ki(t) 表示t時(shí)刻節(jié)點(diǎn)i的度數(shù)，因ki(t) 與Δ(i,t) 的關(guān)系滿足Δ(i,t)=ki(t)-1，又有Δ(i,t) =3Δ(i,t-1)和Δ(i,ti) =3，則在t時(shí)刻，節(jié)點(diǎn)i的度為ki(t)=3t-ti-1+1，從而得到Sierpinski網(wǎng)絡(luò)N(t)的度譜(見(jiàn)表1)。

表1 N(t) 的度譜

表1 告訴Sierpinski網(wǎng)絡(luò)N(t) 的度分布是離散的文給出一種新的累積分布

將ti=t+1-ln(k-1)/ln 3代入上式，得

將ti=t+1-ln(k-1)/ln 3 代入上式，得

同理，可證明

分析可知，在τ足夠大時(shí)，τ→，得β?1。因此，頂點(diǎn)累積分布和邊累積分布是等價(jià)的。除了頂點(diǎn)累積分布之外，還可以用邊累積分布來(lái)確定網(wǎng)絡(luò)N(t) 是無(wú)標(biāo)度網(wǎng)絡(luò)。

1.4 邊點(diǎn)混合累積分布

本小節(jié)給出新的統(tǒng)計(jì)指標(biāo)，叫做邊點(diǎn)混合累積分布，有以下 3 種形式:

(i) 邊點(diǎn)數(shù)乘累積分布

用ti=t+1-ln(k-1)/ln 3替換上式中的ti，整理可得

(ii) 邊點(diǎn)差累積分布

用ti=t+1-ln(k-1)/ln 3替換上式中的ti，整理可得

(iii) 邊點(diǎn)根式累積分布

2 討 論

本文借助于現(xiàn)有的無(wú)標(biāo)度網(wǎng)絡(luò)模型，驗(yàn)證了頂點(diǎn)累積分布和邊累積分布的等價(jià)性?；诓煌幕旌戏绞?，提出3種新的累積分布。為探索網(wǎng)絡(luò)的無(wú)標(biāo)度性提供了一個(gè)新的方法。大多數(shù)驗(yàn)證無(wú)標(biāo)度網(wǎng)絡(luò)的方式是說(shuō)明頂點(diǎn)累積分布服從冪律分布。本文發(fā)現(xiàn)雖然采用不同的方式計(jì)算累積分布，例如頂點(diǎn)累積分布和邊累積分布，仍可以得出網(wǎng)絡(luò)服從無(wú)標(biāo)度網(wǎng)絡(luò)的結(jié)論。因此，我們猜想：頂點(diǎn)累積分布服從冪律分布和邊累積分布服從冪律分布都可以作為來(lái)確定網(wǎng)絡(luò)是無(wú)標(biāo)度的依據(jù)，換句話說(shuō)，頂點(diǎn)累積分布和邊累積分布是等價(jià)的。但邊點(diǎn)混合累積分布因混合的方式不同所得到的累積分布也不盡相同，需進(jìn)行深入研究和實(shí)證。

[2] 吳泓潤(rùn)，覃俊，易云飛，等. 基于優(yōu)化理論的社區(qū)無(wú)標(biāo)度網(wǎng)絡(luò)模型[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(2)：337-348. WU H R, QIN J, YI Y F, et al. A model of community-structure and scale-free network based on optimization theory [J]. Chinese Journal of Computers, 2015, 38(2): 337-348.

[3] BANCONI G, BARABSI A L．Competition and multiscaling in evolving networks [J]．Europhysics Letters, 2001,54(4): 436-442．

[5] JUNG S, KIM S, KAHNG B. Geometric fractal growth model for scale-free networks [J]. Physica Review E 2002, 65(2): 056101.

[6] VIJAYAN A, BEULA J S. Edge-vertex dominating sets and edge-vertex domination polynomials of cycles [J]. Open Journal of Discrete Mathematics, 2015, 5(4): 74-87.

[7] NEWMAN M. The structure and function of complex networks [J]. SIAM Review, 2006, 45(2): 167-256.

[8] COMELLAS F, FERTIN G, RASPAUD A. Recursive graphs with small-world scale-free properties [J]. Physical Review E, 2004, 69(3 Pt 2): 281-285.

[9] 王曉敏, 趙喜楊, 姚兵. 全邊增長(zhǎng)網(wǎng)絡(luò)模型的生成樹(shù)[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 55(1): 48-53. WANG X M, ZHAO X Y, YAO B. Spanning trees of totally edge-growing network models [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2016, 55(1): 48-53.

[10] 張婉佳, 劉霞, 姚兵. 一類增長(zhǎng)網(wǎng)絡(luò)模型的生成樹(shù)[J]. 廈門大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 54(4): 497-501. ZHANG W J, LIU X, YAO B. Spanning trees of a class of growing network models [J]. Journal of Xiamen University (Natural Science), 2015, 54(4): 497-501.

[11] 劉霞, 姚東任, 姚兵，等. 探討無(wú)標(biāo)度網(wǎng)絡(luò)的平衡集[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 54 (1): 19-23. LIU X, YAO D R, YAO B, et al. On balanced sets in scale-free networks (graphs) [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2015, 54 (1): 19-23.

[12] ZHANG Z Z, COMELLAS F, FERTIN G, et al. High dimensional apollonian networks [J]. Journal of Physics A General Physics, 2005, 39(8): 2006.

[13] ZHANG Z Z, ZHOU S G, FANG L J, et al. Maximal planar scale-free sierpinski networks with small-world effect and power-law strength-degree correlation [J]. EPL (Europhysics Letters)， 2007, 79(3): 417-429.

[14] LIU X, YAO B, ZHANG W J, et al. Uniformly bound-growing network models and their spanning trees [C]∥ International Conference on Information and Communications Technologies, 2014: 1-5.

[15] WANG X M, YAO B, MA F, et al. Hierarchical structure and particular spanning trees of edge-bound growing network models [C]∥International Conference on Fuzzy Systems and Knowledge Discovery, 2015:444-449.

[16] WANG X M, YAO B, MA F, et al. On composition and decomposition of networks [C]∥ International Conference on Biomedical Engineering and Informatics, 2015:783-788.

[17] WANG X M, ZHAO X Y, YAO B, et al. Algorithms for maximum leaf spanning tress of edge-growing network models in information system [J]. Applied Mechanics & Materials, 2015, 775: 431-435.

New method for cumulative distribution of scale-free network

WANGXiaomin1,YAOBing1，2

(1. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China; 2. School of Electronics and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

By applying algorithm method, the maximal planar network with scale-free properties is employed. The cumulative degree distribution and edge-cumulative degree distribution are computed, and the equivalence between them is testified. Besides, the new statistical index, namely, the mix cumulative distribution between edge and vertex on the basis of different mixed method is provided. A conjecture: If the mixed mode is linear, the mix cumulative distribution is equivalent to cumulative distribution is proposed. This conjecture makes a contribution to discussing scale-free network by applying all-round and multi-angle standpoint.

scale-free network; vertex cumulative distribution; edge-cumulative distribution; power law distribution

10.13471/j.cnki.acta.snus.2017.03.007

2016-09-19 基金項(xiàng)目：國(guó)家自然科學(xué)基金(61163054, 61363060, 61662066)

王曉敏(1989年生)，女；研究方向：復(fù)雜網(wǎng)絡(luò)；E-mail: 704944897@qq.com

姚兵(1956年生)，男；研究方向：圖著色與標(biāo)號(hào)、復(fù)雜網(wǎng)絡(luò)；E-mail: yybb918@163.com

O157.5

A

0529-6579(2017)03-0041-05