時變網(wǎng)絡(luò)上零模型的構(gòu)造算法及應(yīng)用

于詠平

摘 要：時變網(wǎng)絡(luò)體現(xiàn)了拓?fù)浣Y(jié)構(gòu)與動力學(xué)相結(jié)合的網(wǎng)絡(luò)特性，準(zhǔn)確測量時變網(wǎng)絡(luò)的性能在預(yù)測、控制信息傳播等方面有重要的研究價值。零模型的引入使得對于時變網(wǎng)絡(luò)具有的陣發(fā)性、周期性以及因果特性等研究更加全面。文章首先介紹了零模型在生物學(xué)等領(lǐng)域的研究背景，接著利用各類網(wǎng)絡(luò)所適用的置亂算法，構(gòu)造不同參數(shù)要求的零模型。針對不同情況對于構(gòu)造要求的不同，提出并分析了時變網(wǎng)絡(luò)零模型在構(gòu)造過程中計算量的概念，并利用計算模型和理論解析驗證對比了所提出算法與隨機變動方法在變動過程中的計算量優(yōu)勢，最后討論了在雙層耦合網(wǎng)絡(luò)中零模型的應(yīng)用。

關(guān)鍵詞：時變網(wǎng)絡(luò)；零模型；社交網(wǎng)絡(luò)；置亂算法

伴隨著互聯(lián)網(wǎng)飛速發(fā)展，如今人們更傾向于通過在線社交網(wǎng)絡(luò)獲取傳播信息。而現(xiàn)有網(wǎng)絡(luò)特性的統(tǒng)計量如度分布、平均路徑長度、聚類系數(shù)等往往不能準(zhǔn)確刻畫原網(wǎng)絡(luò)的非平凡特性。零模型是一個與實際網(wǎng)絡(luò)具有某些相同性質(zhì)的隨機網(wǎng)絡(luò)，也稱該實際網(wǎng)絡(luò)的隨機化副本。

1981年，Strong等[1]提出零模型一詞。Maslov和Sneppen[2]將零模型利用到生物學(xué)，得出蛋白傾向于異配連接。Barrat等[3]介紹了ER隨機圖模型等作為網(wǎng)絡(luò)參照模型的方法。Newman等[4]提出任意度分布的隨機圖理論。Mahadevan等[5]提出了分析網(wǎng)絡(luò)拓?fù)潢P(guān)系的方法，對比網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對于網(wǎng)絡(luò)重要特性的影響。Milo等[6]提出了基于復(fù)雜網(wǎng)絡(luò)中較小子圖的顯著性剖面（Significant Profile，SP）與隨機網(wǎng)絡(luò)比較的方法，發(fā)現(xiàn)了超級家族。由于許多配置模型僅在構(gòu)造一階零模型的層面，Newman創(chuàng)建了一個可解析的網(wǎng)絡(luò)模型，展示了將標(biāo)準(zhǔn)的隨機圖形模型一般化，保持了聚類系數(shù)不變，完善了配置模型的應(yīng)用[7]。

胡華全等[8]按照保持意象圖的手段進行技術(shù)分類， 總結(jié)時變網(wǎng)絡(luò)可視化研究的思想方法。不同階次零模型成功置亂概率存在差異，難以準(zhǔn)確判斷零模型何時能夠趨于穩(wěn)定，李歡等[9]定義了“成功置亂次數(shù)”的概念，李歡等[10]針對生成大尺度網(wǎng)絡(luò)的零模型時間效率較低的問題，利用數(shù)據(jù)分組思想，提供了一種高效的解決方案。2017年吳睿等[11]提出了dK-目標(biāo)保持重連算法，降低了計算復(fù)雜度。從零模型的提出到如今各種理論與算法的逐步完善，使零模型在研究各種網(wǎng)絡(luò)特別是社交網(wǎng)絡(luò)中起到越來越重的作用，包括多層耦合網(wǎng)絡(luò)上的應(yīng)用也日臻靈活。

1 社交網(wǎng)絡(luò)上的置亂算法

社交網(wǎng)絡(luò)也是一種時變網(wǎng)絡(luò)，在社交網(wǎng)絡(luò)上加上時間戳能更具體地描述社交行為，對社交網(wǎng)絡(luò)的分析也可以說是對時變網(wǎng)絡(luò)的分析。

在保持原始網(wǎng)絡(luò)連接的條件下，置亂算法可以隨機化某些因素，將原始網(wǎng)絡(luò)參數(shù)與新得到的網(wǎng)絡(luò)參數(shù)進行對比，進而得知網(wǎng)絡(luò)的非平凡特性。這種方法的應(yīng)用更加普遍，在對比的過程中也更加靈活。尚可可等[12]整理了各種網(wǎng)絡(luò)中基于置亂算法的零模型構(gòu)造過程和它們的實際應(yīng)用。

1.1 斷邊重連

斷邊重連算法表示了原始網(wǎng)絡(luò)度分布，不會產(chǎn)生自環(huán)或重邊現(xiàn)象，操作簡便，計算量小。Maslov等[2]利用隨機斷邊重連方法，判斷生物蛋白質(zhì)大分子更傾向于異配連接。在雙層網(wǎng)絡(luò)中也可以利用到隨機斷邊重連算法，崔麗艷和許小可[13]提出了以多種雙層網(wǎng)絡(luò)零模型作參照物，通過假設(shè)檢驗方法來量化雙層網(wǎng)絡(luò)間結(jié)構(gòu)相關(guān)性，分析了這種結(jié)構(gòu)相關(guān)性存在的內(nèi)在機理。Newman等[14]利用隨機斷邊重連方式測量網(wǎng)絡(luò)的混合模式，分析數(shù)據(jù)發(fā)現(xiàn)在分類混合網(wǎng)絡(luò)模型中網(wǎng)絡(luò)魯棒性更好。局部斷邊重連算法是斷邊重連的一種，Zhou和Mondrag[15]提出富人俱樂部系數(shù)的概念并利用局部斷邊重連算法證明Internet網(wǎng)絡(luò)也具有富人俱樂部屬性。

1.2 權(quán)重置亂

節(jié)點間連邊強度的異質(zhì)性也是網(wǎng)絡(luò)具有不同屬性的重要因素。在加權(quán)網(wǎng)絡(luò)中，主要表現(xiàn)的是連邊上的權(quán)重因素。Opsahl等[16]利用權(quán)重置亂等方法對社交網(wǎng)絡(luò)提出了一種通用框架來研究網(wǎng)絡(luò)中資源流向性的趨勢，發(fā)現(xiàn)大部分資源可以共享，形成了控制系統(tǒng)資源的俱樂部。Barrat等[17]采用權(quán)重置亂算法研究了航空運輸?shù)染W(wǎng)絡(luò)的連接權(quán)重與拓?fù)湎嚓P(guān)性。其中等權(quán)置亂算法改變了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，且不破壞連邊權(quán)重分布。

1.3 時間置亂

在社交網(wǎng)絡(luò)中，測量節(jié)點的動態(tài)變化是十分必要的，相比于傳統(tǒng)的網(wǎng)絡(luò)，時變網(wǎng)絡(luò)增添了時間維度，刻畫出網(wǎng)絡(luò)事件發(fā)生順序及事件相關(guān)性等動力學(xué)特性。在社交網(wǎng)絡(luò)中，傳染病的擴散、信息的傳播等問題是此領(lǐng)域很熱點的研究問題，Barabási[18]研究了在實際生活中，人類的動態(tài)行為在時變網(wǎng)絡(luò)中的統(tǒng)計特性。

1.3.1 時間置亂算法

通過置亂網(wǎng)絡(luò)中各連邊事件發(fā)生的時間，時間置亂算法達到了隨機化相關(guān)時間參數(shù)的目的，不會改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)與每條連邊上事件發(fā)生的次數(shù)。隨機選取一個事件發(fā)生的時間戳，與另一時間戳置換，并重復(fù)操作，直到滿足要求?；?qū)⑺袝r間戳打亂，隨機分布在各連邊上，并保持每條連邊的權(quán)重不變。Holme[19]根據(jù)實際接觸網(wǎng)絡(luò)事件發(fā)生的時間序列，對比由時間置亂算法構(gòu)造的零模型，發(fā)現(xiàn)所測得信息可達性時間取決于路徑長度與交流頻率。

1.3.2 時權(quán)置亂算法

時權(quán)置亂算法破壞了網(wǎng)絡(luò)的權(quán)重特性，保留了連邊上事件發(fā)生的時間順序，沒有破壞時間陣發(fā)性，可以研究時變網(wǎng)絡(luò)權(quán)重的影響。為了研究導(dǎo)致小世界網(wǎng)絡(luò)中信息傳播速度緩慢的因素，Karsai等[20]置亂了事件發(fā)生的序列以跟蹤信息傳播，發(fā)現(xiàn)主要是由于繁復(fù)的拓?fù)潢P(guān)系以及個體的活動模式引起的。

接觸置亂是在時權(quán)置亂算法基礎(chǔ)上，隨機化破壞網(wǎng)絡(luò)連邊上事件的陣發(fā)性。置亂過程中，保證拓?fù)浣Y(jié)構(gòu)不變，將所有事件隨機重新分布在每條連邊上。

1.3.3 時間倒轉(zhuǎn)算法

在有向時變網(wǎng)絡(luò)中，事件的發(fā)生順序可以反映事件的因果特性，時間倒轉(zhuǎn)算法，打亂了事件發(fā)生的先后次序，可以研究事件的相關(guān)性與因果性。

1.3.4 區(qū)間圖上的置亂算法

在實際的社交網(wǎng)絡(luò)中，許多事件是在一個時間段內(nèi)發(fā)生的，其發(fā)生時間長短對于結(jié)果有明顯影響。例如一個傳染病患者在接觸其他人群時，接觸時間長短會影響其他人是否被感染病毒的概率結(jié)果。由此可見，一些情況下要關(guān)注事件所持續(xù)的時間段長度，區(qū)間圖就可以很好地體現(xiàn)事件發(fā)生的持續(xù)特性。Candia等[21]利用移動電話數(shù)據(jù)，借助區(qū)間圖表示，描述了個體的某些平均行為導(dǎo)致重尾現(xiàn)象發(fā)生，時空異常。

2 時變網(wǎng)絡(luò)零模型的計算量優(yōu)化

在時變網(wǎng)絡(luò)中，前面幾種算法約束條件淺顯，試錯較少或不需試錯，而根據(jù)時間倒轉(zhuǎn)算法要求，要破壞原網(wǎng)絡(luò)事件發(fā)生的相關(guān)性與因果性。如圖1所示，在原網(wǎng)絡(luò)中信息可以從A經(jīng)由B傳至C。為了破壞傳播的因果性，就要改變原來的傳播路徑。需破壞兩條路徑，即改變時間戳來影響事件傳播，使后一步傳播的時間戳排在前一步信息傳播之前。要破壞ABC這條路徑，將后一步最后出現(xiàn)的時間戳與前一步第一次出現(xiàn)的時間戳互換，則AB邊上的時間戳為7、11，BC邊上的時間戳為2、3，這樣就保證了信息不能再從A通過B傳至C，再變化過程中有可能致使其他路徑構(gòu)成因果關(guān)系，用上述方法調(diào)整時間戳，直至圖1中不存在事件間的因果性，構(gòu)造結(jié)束。

3 雙層網(wǎng)絡(luò)上的節(jié)點置亂算法及應(yīng)用

在不同的時間段用戶與其他用戶建立或解除友好關(guān)系的情況構(gòu)成了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。在社交網(wǎng)絡(luò)中，不同的時間段內(nèi)用戶的各種社交行為，是用戶社交功能在網(wǎng)絡(luò)上的體現(xiàn)，形成了社交功能網(wǎng)絡(luò)，兩層數(shù)據(jù)的網(wǎng)絡(luò)之間存在明顯的耦合關(guān)系。比較有代表性的是有傾向性節(jié)點置亂算法，傾向性指的是有一定目的的對一層節(jié)點重排。如果要得到同配網(wǎng)絡(luò)，置換節(jié)點使得一層度值大的節(jié)點連接另一層度值大的節(jié)點即可，稱為有傾向性的構(gòu)造正匹配效應(yīng)的零模型網(wǎng)絡(luò)，負(fù)匹配效應(yīng)相反。

4 結(jié)語

時變網(wǎng)絡(luò)是社交網(wǎng)絡(luò)的一部分，保持著社交網(wǎng)絡(luò)在各方面的特點，時變網(wǎng)絡(luò)與多層網(wǎng)絡(luò)應(yīng)用更加普遍，要更深層次地挖掘網(wǎng)絡(luò)屬性或微觀結(jié)構(gòu)，需要借助類似零模型這類推斷工具來對比網(wǎng)絡(luò)中影響傳播的對象。在構(gòu)造零模型的過程中，對于不同的階數(shù)與算法要求，計算量較大，本文從計算模型和理論解析驗證了提出算法的優(yōu)化特性，并在計算相關(guān)系數(shù)方面有待進一步優(yōu)化。

[參考文獻]

[1]STRONG D R，SIMBERLOFF D，ABELE L G，et al.Ecological communities： conceptual issues and the evidence[M].New Jersey：Princeton University Press，2014.

[2]MASLOV S，SNEPPEN K.Specificity and stability in topology of protein networks[J].Science，2002（5569）：910-913.

[3]BARRAT A，BARTH?LEMY M，VESPIGNANI A.Dynamical processes on complex networks[M].England：Cambridge University Press，2008.

[4]NEWMAN M E J，STROGATZ S H H，WATTS D J J.Random graphs with arbitrary degree distributions and their applications[J]. Physical Review E，2001（2）：26118.

[5]MAHADEVAN P，KRIOUKOV D，F(xiàn)ALL K，et al.Systematic topology analysis and generation using degree correlations[J].ACM SIGCOMM Computer Communication Review，2006（4）：135-146.

[6]MILO R，ITZKOVITZ S，KASHTAN N，et al.Super families of evolved and designed networks[J].Science，2004（5663）：1538-1542.

[7]NEWMAN M E J.Random graphs with clustering[J].Physical Review Letters，2009（5）：58701.

[8]胡華全，吳玲達，楊超，等.時變網(wǎng)絡(luò)可視化研究綜述[J].系統(tǒng)仿真學(xué)報，2013（9）：1975-1980，1989.

[9]李歡，盧罡，郭俊霞，等.復(fù)雜網(wǎng)絡(luò)零模型的量化評估[J].計算機應(yīng)用，2015（6）：1560-1563.

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

[11]吳睿，宋玉蓉.2.25階/2.5階網(wǎng)絡(luò)零模型模擬退火優(yōu)化算法[J/OL].計算機技術(shù)與發(fā)展，2017（12）：1-5[2018-01-12].http：//kns.cnki.net/kcms/detail/61.1450.TP.20170927.0957.006.html.

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

[13]崔麗艷，許小可.參照零模型的雙層網(wǎng)絡(luò)結(jié)構(gòu)相關(guān)性檢測[J].科技導(dǎo)報，2017（14）：63-74.

[14]NEWMAN M E J.Assortative mixing in networks[J].Physical Review Letters，2002（20）：208701.

[15]ZHOU S，MONDRAGON R J.The rich-club phenomenon in the Internet topology[J].IEEE Communications Letters，2004（3）：180-182.

[16]OPSAHL T，COLIZZA V，PANZARASA P，et al.Prominence and control： The weighted rich-club effect[J].Physical Review Letters，2008（16）：168702.

[17]BARRAT A，BARTHELEMY M，PASTOR-SATORRAS R，et al.The architecture of complex weighted networks[J].Proceedings of the National Academy of Sciences of the United States of America，2004（11）：3747-3752.

[18]BARAB?SI A L.The origin of bursts and heavy tails in human dynamics[J].Nature，2005（7039）：207-211.

[19]HOLME P.Network reachability of real-world contact sequences[J].Physical Review E，2005（4）：046119.

[20]KARSAI M，KIVEL? M，PAN R K，et al.Small but slow world： how network topology and burstiness slow down spreading[J].Physical Review E，2011（2）：25102.

[21]CANDIA J，GONZ?LEZ M C，WANG P.Uncovering individual and collective human dynamics from mobile phone records[J].Journal of Physics A： Mathematical and Theoretical，2008（22）：224015.