吳 睿，宋玉蓉

(南京郵電大學(xué) 自動化學(xué)院，江蘇 南京 210023)

1 概 述

通常，將具有與實(shí)際網(wǎng)絡(luò)給定階次度相關(guān)特性的隨機(jī)網(wǎng)絡(luò)稱為該實(shí)際網(wǎng)絡(luò)的隨機(jī)化網(wǎng)絡(luò)，這類隨機(jī)化網(wǎng)絡(luò)模型在統(tǒng)計(jì)學(xué)上稱為零模型。Mahadeven等[1]為了從粗糙到精確逐步逼近真實(shí)網(wǎng)絡(luò)的性質(zhì)，按照約束條件從少到多，將零模型的階次依次從低階到高階(0階至3階)進(jìn)行了定義。不同階數(shù)網(wǎng)絡(luò)零模型之間并不是獨(dú)立的，按照約束條件從少到多，存在一種包含關(guān)系，即任何一個(gè)d階零模型都會包含d-1階零模型的性質(zhì)。通過原始網(wǎng)絡(luò)(即實(shí)際網(wǎng)絡(luò))與不同階次的零模型的比較，就可以檢測到實(shí)際網(wǎng)絡(luò)中一些性質(zhì)的來源。

零模型生成方法有兩種：網(wǎng)絡(luò)模型方法和隨機(jī)置亂方法?；诰W(wǎng)絡(luò)模型[2-4]生成零模型是一個(gè)從無到有生成新網(wǎng)絡(luò)的過程，熟知的ER隨機(jī)圖[5]、WS小世界網(wǎng)絡(luò)[6]、BA模型[7]、配置模型[8-9]等都可以視為網(wǎng)絡(luò)模型方法。ER隨機(jī)圖可以視為階數(shù)最低的0階零模型(與原始網(wǎng)絡(luò)具有相同的平均度)，而配置模型可生成1階(與原始網(wǎng)絡(luò)具有相同的度分布)、2階(與原始網(wǎng)絡(luò)具有相同的聯(lián)合度分布)或更高階零模型。基于隨機(jī)置亂生成零模型是將實(shí)際網(wǎng)絡(luò)進(jìn)行隨機(jī)斷邊重連[10-11]，在保持原有連接的前提下隨機(jī)化某些因素。這種方法可以產(chǎn)生0至2.5階網(wǎng)絡(luò)零模型。Gjoka等[12]認(rèn)為3階網(wǎng)絡(luò)零模型要求與原始網(wǎng)絡(luò)具有相同的聯(lián)合邊度分布，其約束條件已經(jīng)很多，不具備實(shí)用性；2.25階零模型與原始網(wǎng)絡(luò)具有相同的聯(lián)合度分布和平均聚類系數(shù)；2.5階零模型與原始網(wǎng)絡(luò)具有相同的聯(lián)合度分布和聚類譜，是現(xiàn)在能夠?qū)崿F(xiàn)的最高階的實(shí)用零模型。

2.25階和2.5階零模型對研究網(wǎng)絡(luò)的聚類特性有著重要作用。聚類特性作為一個(gè)重要的拓?fù)涮匦?，對?fù)雜網(wǎng)絡(luò)上的動力學(xué)行為[13-15]影響顯著。例如，有研究表明[2,16-17]，高聚類網(wǎng)絡(luò)可抑制病毒傳播；Kim[18]等對神經(jīng)網(wǎng)絡(luò)的研究發(fā)現(xiàn)，網(wǎng)絡(luò)的計(jì)算功能更多取決于聚類系數(shù)而不是度分布，且低聚類網(wǎng)絡(luò)的性能優(yōu)于高聚類網(wǎng)絡(luò)。

網(wǎng)絡(luò)中三角形的數(shù)量對聚類系數(shù)的變化有重要影響，通常三角形數(shù)量越多，聚類系數(shù)越大。文獻(xiàn)[19]基于配置模型思想，根據(jù)固定的度序列與聚類譜，對一個(gè)只有節(jié)點(diǎn)的網(wǎng)絡(luò)進(jìn)行添邊，生成指定度分布和聚類譜的網(wǎng)絡(luò)模型。進(jìn)行添邊時(shí)主要依靠對三角形數(shù)量的控制。該算法無法控制同配系數(shù)，因此聯(lián)合度分布會不同。

Bansal等[20]結(jié)合隨機(jī)重連算法和馬爾可夫鏈生成指定度分布和聚類系數(shù)的隨機(jī)網(wǎng)絡(luò)模型，簡稱ClustRNet算法。該算法從隨機(jī)選擇的節(jié)點(diǎn)入手，從該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中隨機(jī)選擇兩條邊進(jìn)行斷邊重連，確保有三角形生成，但也可能破壞現(xiàn)有三角形。該算法復(fù)雜度為O(M2),其中M為網(wǎng)絡(luò)邊數(shù)，該算法不能保證生成指定的聯(lián)合度分布。

Gjoka等[12,22]評價(jià)文獻(xiàn)[21]中的算法生成2.5階零模型是不切實(shí)際的，雖然一開始會生成許多新三角形，但同時(shí)很可能破壞了更多已有三角形，此外因約束條件限制，導(dǎo)致該算法重復(fù)率很高，得到與原始網(wǎng)絡(luò)相等的聚類譜的概率是很小的。為此，Gjoka等[12,22]對Mahadevan等[21]構(gòu)造2.5階零模型的隨機(jī)重連算法進(jìn)行了改進(jìn)(MCMC改進(jìn)算法)：交換連邊時(shí)更傾向于選擇包含較少三角形的連邊，在此理論基礎(chǔ)上能夠更少地破壞已有三角形，生成更多新三角形。為生成更多三角形，達(dá)到目標(biāo)聚類譜，該文獻(xiàn)對節(jié)點(diǎn)采樣生成了聯(lián)合度分布和度相關(guān)的聚類系數(shù)的有效估計(jì)量并成功構(gòu)建了2階零模型網(wǎng)絡(luò)和2.5階零模型網(wǎng)絡(luò)。

在國內(nèi)學(xué)者的研究中，文獻(xiàn)[23-24]很好地總結(jié)了現(xiàn)有一些零模型構(gòu)造算法及其應(yīng)用。文獻(xiàn)[25]針對生成的0階、1階、2階網(wǎng)絡(luò)零模型,提出了基于GPU的大尺度網(wǎng)絡(luò)零模型分組生成并行算法。

為此，提出了一種生成2.25階、2.5階零模型的優(yōu)化算法：dK-目標(biāo)保持重連算法(d代表階數(shù)，K代表度相關(guān)性)。該算法改進(jìn)了Hamiltonian函數(shù)[26]，并結(jié)合了模擬退火算法[27]和Metropolis準(zhǔn)則。運(yùn)用現(xiàn)有算法如dK-隨機(jī)重連算法[21](d=0,1,2)生成所需2階零模型，在2階零模型基礎(chǔ)上應(yīng)用所提出的算法，生成與真實(shí)網(wǎng)絡(luò)具有相同的聯(lián)合度分布和聚類系數(shù)/聚類譜的2.25階/2.5階零模型。最后通過實(shí)驗(yàn)對該算法進(jìn)行驗(yàn)證。

2 零模型生成算法及模擬退火算法

2.1 dK隨機(jī)重連算法

靜態(tài)無權(quán)網(wǎng)絡(luò)中最常用的就是使用隨機(jī)重連來產(chǎn)生復(fù)雜網(wǎng)絡(luò)零模型。隨機(jī)重連的方法主要是在原始網(wǎng)絡(luò)的基礎(chǔ)上將網(wǎng)絡(luò)中原有的連邊隨機(jī)地?cái)嚅_重連，使原始網(wǎng)絡(luò)模型盡可能隨機(jī)化。由于隨機(jī)重連算法簡單、易操作，不需要理解和運(yùn)用復(fù)雜的數(shù)學(xué)公式、也不會產(chǎn)生自環(huán)和重邊現(xiàn)象，卻能精確保持真實(shí)網(wǎng)絡(luò)的一些物理屬性，因此廣泛應(yīng)用于實(shí)際各種類型的網(wǎng)絡(luò)分析中。

d=0：隨機(jī)去除原始網(wǎng)絡(luò)的一條邊(i,j)，再隨機(jī)選擇網(wǎng)絡(luò)中兩個(gè)不相連的節(jié)點(diǎn)a和b,并在它們之間添加一條連邊(a,b)。

d=1：隨機(jī)選擇原始網(wǎng)絡(luò)中的兩條邊(i,j)和(a,b)，如果這四個(gè)節(jié)點(diǎn)之間只有這兩條邊，那么就去除這兩條邊，并將節(jié)點(diǎn)a和j相連、節(jié)點(diǎn)b和i相連，從而得到兩條新邊(b,i)和(a,j)。

d=2：隨機(jī)選擇原始網(wǎng)絡(luò)中的兩條邊(i,j)和(a,b)并且ka=ki(節(jié)點(diǎn)a和i度值相同),如果這四個(gè)節(jié)點(diǎn)之間只有這兩條邊，那么就去除這兩條邊，并將節(jié)點(diǎn)a和j相連、節(jié)點(diǎn)b和i相連，從而得到兩條新邊(b,i)和(a,j)。

2.2 模擬退火算法

模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻。加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。

根據(jù)Metropolis準(zhǔn)則：假設(shè)在狀態(tài)xold時(shí)，系統(tǒng)受到某種干擾而使其狀態(tài)變?yōu)閤new。與此相對應(yīng)，系統(tǒng)的能量也從E(xold)變?yōu)镋(xnew)，系統(tǒng)由狀態(tài)xold變成xnew的接受概率p表示為:

p=

(1)

粒子在溫度T時(shí)趨于平衡的概率p為exp(-ΔE/kT)，其中E為溫度T時(shí)的能量，ΔE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將改變量ΔE模擬為目標(biāo)函數(shù)值ΔH，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解。這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。

退火過程由冷卻進(jìn)度表(Cooling Schedule)控制，包括控制參數(shù)的初值T0及其衰減因子Δt、每個(gè)t值時(shí)的迭代次數(shù)N和停止條件S。模擬退火算法是一種通用的優(yōu)化算法，理論上算法具有概率的全局優(yōu)化性能,目前已在工程中得到了廣泛應(yīng)用，諸如VLSI、生產(chǎn)調(diào)度、控制工程、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、信號處理等領(lǐng)域。

3 2.25階、2.5階零模型優(yōu)化算法

為了用更少的迭代次數(shù)得到隨機(jī)化更徹底的聚類網(wǎng)絡(luò)(d=2.25,2.5)，在使用dK-隨機(jī)重連算法(d=0,1,2)的基礎(chǔ)上結(jié)合模擬退火算法，提出了dK-目標(biāo)保持重連算法(d=2.25,2.5)。

該算法具體步驟為：

Step1：設(shè)置初始參數(shù)。首先，從隨機(jī)重連算法所述過程中得到的2階零模型作為初始網(wǎng)絡(luò)G0，并令其為目標(biāo)優(yōu)化網(wǎng)絡(luò)。

設(shè)置優(yōu)化目標(biāo)誤差值為He，系統(tǒng)初始溫度T0，用于控制降溫的快慢參數(shù)γ，同一溫度內(nèi)的網(wǎng)絡(luò)未更新次數(shù)上限α，溫度的下限Tmin。

Step2:計(jì)算G0與真實(shí)網(wǎng)絡(luò)Gv關(guān)于聚類系數(shù)和聚類譜的Hamiltonian改進(jìn)函數(shù)。

(1)關(guān)于聚類系數(shù)，即2.25階：

(2)

(2)關(guān)于聚類譜，即2.5階：

(3)

Step3：對G0網(wǎng)絡(luò)執(zhí)行隨機(jī)斷邊重連算法，即從G0中隨機(jī)選擇兩條邊(u,v)和(x,y)且有ku=kx;變換連邊，得到包含新邊(u,y)和(x,v)的新網(wǎng)絡(luò)Gn；

依據(jù)式(2)和式(3)計(jì)算Hn/Hkn。

Step4：令

ΔH=|Hn-H0|

(4)

或

ΔHk=|Hkn-Hk0|

(5)

計(jì)算網(wǎng)絡(luò)更新概率：

(6)

或

(7)

以概率p/pk更新G0網(wǎng)絡(luò)及相關(guān)參數(shù)，即令G0=Gn,H0=Hn或Hk0=Hkn。

若H0

Step5：如果連續(xù)α次網(wǎng)絡(luò)未獲得更新，重復(fù)Step3和Step4，否則轉(zhuǎn)到Step6。

Step6：降溫過程：

Tk=T0×γ

(8)

若達(dá)到終止溫度Tk

Step7：輸出G0，即為得到的2.25階或2.5階零模型網(wǎng)絡(luò)。

4 實(shí)驗(yàn)仿真

實(shí)驗(yàn)選取三個(gè)無權(quán)無向的真實(shí)網(wǎng)絡(luò)。其網(wǎng)絡(luò)名稱、數(shù)據(jù)規(guī)模、具體統(tǒng)計(jì)參數(shù)如表1所示。

表1 真實(shí)網(wǎng)絡(luò)的具體統(tǒng)計(jì)參數(shù)

4.1 模擬退火算法參數(shù)分析

本算法需設(shè)置系統(tǒng)初始溫度T0，用于控制降溫的快慢參數(shù)γ，溫度的下限Tmin，優(yōu)化目標(biāo)誤差值He,同一溫度內(nèi)的網(wǎng)絡(luò)未更新次數(shù)上限α。

系統(tǒng)初始要處于一個(gè)高溫的狀態(tài)，因此T0設(shè)為100。將He設(shè)為0.02，α設(shè)為8。

參數(shù)γ的設(shè)置很重要，若γ過大，則搜索到全局最優(yōu)解的可能會較高，但搜索的過程也就較長；若γ過小，則搜索的過程會很快，但最終可能會達(dá)到一個(gè)局部最優(yōu)值。對比分析了γ分別取0.85和0.95，終止溫度Tmin分別取0.01和0.1時(shí)，生成2.25階和2.5階零模型時(shí)所需要的迭代次數(shù)。結(jié)果如表2所示，可以看到算法在取γ=0.95，Tmin=0.1時(shí)迭代次數(shù)最少，效果最好。

表2 算法參數(shù)設(shè)置對迭代次數(shù)的影響

4.2 2.25/2.5階零模型的有效性分析

運(yùn)用dK-目標(biāo)重連算法生成了2.25階和2.5階零模型后，統(tǒng)計(jì)出表3中每個(gè)真實(shí)網(wǎng)絡(luò)生成的四個(gè)網(wǎng)絡(luò)模型的平均聚類系數(shù)和聚類系數(shù)總和，以便于對算法誤差率進(jìn)行分析。

表3 三個(gè)真實(shí)網(wǎng)絡(luò)及各階零模型(d=2,2.25,2.5)聚類系數(shù)分析

接著，通過仿真分別對三個(gè)真實(shí)網(wǎng)絡(luò)的聚類譜與2.25階和2.5階零模型網(wǎng)絡(luò)的聚類譜進(jìn)行了對比分析，以驗(yàn)證本算法生成的2.5階零模型的有效性和準(zhǔn)確性。仿真結(jié)果如圖1所示。

圖1 生成的2.25階和2.5階零模型與真實(shí)網(wǎng)絡(luò)聚類譜的比較分析

從圖1可以看出，三個(gè)真實(shí)網(wǎng)絡(luò)的聚類譜分布均和本算法生成的對應(yīng)網(wǎng)絡(luò)的2.5階零模型聚類譜分布幾乎重疊，與2.25階零模型聚類譜相差明顯。仿真結(jié)果表明，本算法生成的2.5階零模型具有較高的準(zhǔn)確率和有效性。

4.3 算法復(fù)雜度對比

將MCMC算法[21]、MCMC改進(jìn)算法[12]和ClustRNet改進(jìn)算法[20]以及文中提出的算法就算法復(fù)雜度進(jìn)行對比。這些算法在生成2.25階/2.5階模型時(shí)都是建立在MCMC算法生成的同一2階零模型的基礎(chǔ)上進(jìn)行迭代后獲得。

特別說明，由于ClustRNet算法[20]不能保證生成指定的聯(lián)合度分布，故對該算法進(jìn)行一些必要的修改，將馬爾可夫鏈中的度分布信息設(shè)置為聯(lián)合度分布，以保證生成的2.25階、2.5階模型的聯(lián)合度分布與真實(shí)網(wǎng)絡(luò)相同。該算法重新命名為ClustRNet改進(jìn)算法。

經(jīng)過多次實(shí)驗(yàn)，使MCMC改進(jìn)算法[12]和ClustRNet改進(jìn)算法[20]與文中提出的算法得到的2.25階、2.5階零模型聚類系數(shù)與真實(shí)網(wǎng)絡(luò)的目標(biāo)誤差He控制在0.02范圍內(nèi)。而MCMC算法在生成2.25階時(shí)He為0.02，2.5階時(shí)He為0.1。四種算法的迭代次數(shù)如圖2所示。

圖2 2.25/2.5階零模型算法復(fù)雜度對比

從圖中可以看出，提出的算法生成2.25階和2.5階零模型時(shí)在迭代次數(shù)上占有明顯優(yōu)勢，有效降低了算法的復(fù)雜度。

5 結(jié)束語

為快速、有效地獲得與真實(shí)網(wǎng)絡(luò)具有相同的聯(lián)合度分布和聚類系數(shù)、聚類譜的零模型，將模擬退火算法運(yùn)用于構(gòu)造2.25階、2.5階零模型，提出了一種目標(biāo)保持優(yōu)化策略。仿真結(jié)果表明，該算法生成的2.25階、2.5階零模型在具有準(zhǔn)確性和有效性的同時(shí)，有效降低了計(jì)算復(fù)雜度，且其算法復(fù)雜度優(yōu)于其他已有算法。

[1] MAHADEVAN P,HUBBLE C,KRIOUKOV D,et al.Orbis:rescaling degree correlations to generate annotated internet topologies[J].ACM SIGCOMM Computer Communication Review,2007,37(4):325-336.

[2] NEWMAN M E.Properties of highly clustered networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2003,68(2):026121.

[3] GUILLAUME J L,LATAPY M.Bipartite graphs as models of complex networks[J].Physica A Statistical Mechanics & Its Applications,2006,371(2):795-813.

[4] SALA A,CAO L,WILSON C,et al.Measurement-calibrated graph models for social network experiments[C]//Proceedings of the 19th international conference on world wide web.[s.l.]:ACM,2010:861-870.

[6] WATTS D J,STROGATZ S H.Collective dynamics of “small-world” networks[J].Nature,1998,393(6684):440-442.

[8] MOLLOY M,REED B.A critical point for random graphs with a given degree sequence[J].Random Structures & Algorithms,1995,6(2-3):161-180.

[9] NEWMAN M E,STROGATZ S H,WATTS D J. Random gr-aphs with arbitrary degree distributions and their applications[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2001,64:026118.

[10] SERGEI M,KIM S.Specificity and stability in topology of protein networks[J].Science,2002,296(5569):910-913.

[11] MASLOV S,SNEPPEN K,ZALIZNYAK A.Detection of topological patterns in complex networks:correlation profile of the internet[J].Physica A:Statistical Mechanics and Its Applications,2004,333:529-540.

[12] GJOKA M,KURANT M,MARKOPOULOU A.2.5K-Graphs:from sampling to generation[C]//Proceedings of IEEE INFOCOM.[s.l.]:IEEE,2012:1968-1976.

[13] PETERMANN T,RIOS P D L.The role of clustering and gridlike ordering in epidemic spreading[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2004,69(6):066166.

[14] SOFFER S N,VZQUEZ A.Network clustering coefficient without degree-correlation biases[J].Physical Review E,2005,71(2):057101.

[15] SERRANO M,BOGUM.Clustering in complex networks. I. General formalism[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2006,74(5):056114.

[16] NEWMAN M E J.Random graphs with clustering[J].Physical Review Letters,2009,103:058701.

[17] GLEESON J P,MELNIK S,HACKETT A.How clustering affects the bond percolation threshold in complex networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2010,81:066114.

[19] ANGELES S M,BOGUM.Tuning clustering in random networks with arbitrary degree distributions[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2005,72:036133.

[20] BANSAL S,KHANDELWAL S,MEYERS L A.Exploring biological network structure with clustered random networks[J].Bmc Bioinformatics,2009,10:405.

[21] MAHADEVAN P,KRIOUKOV D,FALL K,et al.Systematic topology analysis and generation using degree correlations[J].ACM SIGCOMM Computer Communication Review,2006,36(4):135-146.

[22] GJOKA M,TILLMAN B,MARKOPOULOU A.Construction of simple graphs with a target joint degree matrix and beyond[C]//IEEE conference on computer communications.[s.l.]:IEEE,2015.

[23] 尚可可,許小可.基于置亂算法的復(fù)雜網(wǎng)絡(luò)零模型構(gòu)造及其應(yīng)用[J].電子科技大學(xué)學(xué)報(bào),2014,43(1):7-20.

[24] 陳 泉,楊建梅,曾進(jìn)群.零模型及其在復(fù)雜網(wǎng)絡(luò)研究中的應(yīng)用[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2013,10(1):8-17.

[25] 李 歡,盧 罡,郭俊霞.基于GPU的大尺度網(wǎng)絡(luò)零模型分組生成并行算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2016,37(1):93-99.

[26] PARK J,NEWMAN M E J.Statistical mechanics of networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2004,70(2):066117.

[27] GOFFE W L,FERRIER G D,ROGERS J.Global optimization of statistical functions with simulated annealing[J].Journal of Econometrics,1994,60(1-2):65-99.