于詠平

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

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

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

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

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

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

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

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

1.1 斷邊重連

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

1.2 權(quán)重置亂

節(jié)點(diǎn)間連邊強(qiáng)度的異質(zhì)性也是網(wǎng)絡(luò)具有不同屬性的重要因素。在加權(quán)網(wǎng)絡(luò)中，主要表現(xiàn)的是連邊上的權(quán)重因素。Opsahl等[16]利用權(quán)重置亂等方法對(duì)社交網(wǎng)絡(luò)提出了一種通用框架來(lái)研究網(wǎng)絡(luò)中資源流向性的趨勢(shì)，發(fā)現(xiàn)大部分資源可以共享，形成了控制系統(tǒng)資源的俱樂(lè)部。Barrat等[17]采用權(quán)重置亂算法研究了航空運(yù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 時(shí)間置亂

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

1.3.1 時(shí)間置亂算法

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

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

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

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

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

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

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

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

2 時(shí)變網(wǎng)絡(luò)零模型的計(jì)算量?jī)?yōu)化

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

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

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

4 結(jié)語(yǔ)

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

[參考文獻(xiàn)]

[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]胡華全，吳玲達(dá)，楊超，等.時(shí)變網(wǎng)絡(luò)可視化研究綜述[J].系統(tǒng)仿真學(xué)報(bào)，2013（9）：1975-1980，1989.

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

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

[11]吳睿，宋玉蓉.2.25階/2.5階網(wǎng)絡(luò)零模型模擬退火優(yōu)化算法[J/OL].計(jì)算機(jī)技術(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é)報(bào)，2014（1）：7-20.

[13]崔麗艷，許小可.參照零模型的雙層網(wǎng)絡(luò)結(jié)構(gòu)相關(guān)性檢測(cè)[J].科技導(dǎo)報(bà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.