時變網絡上零模型的構造算法及應用

于詠平

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

關鍵詞：時變網絡；零模型；社交網絡；置亂算法

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

1981年，Strong等[1]提出零模型一詞。Maslov和Sneppen[2]將零模型利用到生物學，得出蛋白傾向于異配連接。Barrat等[3]介紹了ER隨機圖模型等作為網絡參照模型的方法。Newman等[4]提出任意度分布的隨機圖理論。Mahadevan等[5]提出了分析網絡拓撲關系的方法，對比網絡拓撲結構對于網絡重要特性的影響。Milo等[6]提出了基于復雜網絡中較小子圖的顯著性剖面（Significant Profile，SP）與隨機網絡比較的方法，發現了超級家族。由于許多配置模型僅在構造一階零模型的層面，Newman創建了一個可解析的網絡模型，展示了將標準的隨機圖形模型一般化，保持了聚類系數不變，完善了配置模型的應用[7]。

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

1 社交網絡上的置亂算法

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

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

1.1 斷邊重連

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

1.2 權重置亂

節點間連邊強度的異質性也是網絡具有不同屬性的重要因素。在加權網絡中，主要表現的是連邊上的權重因素。Opsahl等[16]利用權重置亂等方法對社交網絡提出了一種通用框架來研究網絡中資源流向性的趨勢，發現大部分資源可以共享，形成了控制系統資源的俱樂部。Barrat等[17]采用權重置亂算法研究了航空運輸等網絡的連接權重與拓撲相關性。其中等權置亂算法改變了網絡的拓撲結構，且不破壞連邊權重分布。

1.3 時間置亂

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

1.3.1 時間置亂算法

通過置亂網絡中各連邊事件發生的時間，時間置亂算法達到了隨機化相關時間參數的目的，不會改變網絡的拓撲結構與每條連邊上事件發生的次數。隨機選取一個事件發生的時間戳，與另一時間戳置換，并重復操作，直到滿足要求。或將所有時間戳打亂，隨機分布在各連邊上，并保持每條連邊的權重不變。Holme[19]根據實際接觸網絡事件發生的時間序列，對比由時間置亂算法構造的零模型，發現所測得信息可達性時間取決于路徑長度與交流頻率。

1.3.2 時權置亂算法

時權置亂算法破壞了網絡的權重特性，保留了連邊上事件發生的時間順序，沒有破壞時間陣發性，可以研究時變網絡權重的影響。為了研究導致小世界網絡中信息傳播速度緩慢的因素，Karsai等[20]置亂了事件發生的序列以跟蹤信息傳播，發現主要是由于繁復的拓撲關系以及個體的活動模式引起的。

接觸置亂是在時權置亂算法基礎上，隨機化破壞網絡連邊上事件的陣發性。置亂過程中，保證拓撲結構不變，將所有事件隨機重新分布在每條連邊上。

1.3.3 時間倒轉算法

在有向時變網絡中，事件的發生順序可以反映事件的因果特性，時間倒轉算法，打亂了事件發生的先后次序，可以研究事件的相關性與因果性。

1.3.4 區間圖上的置亂算法

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

2 時變網絡零模型的計算量優化

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

3 雙層網絡上的節點置亂算法及應用

在不同的時間段用戶與其他用戶建立或解除友好關系的情況構成了網絡的拓撲結構。在社交網絡中，不同的時間段內用戶的各種社交行為，是用戶社交功能在網絡上的體現，形成了社交功能網絡，兩層數據的網絡之間存在明顯的耦合關系。比較有代表性的是有傾向性節點置亂算法，傾向性指的是有一定目的的對一層節點重排。如果要得到同配網絡，置換節點使得一層度值大的節點連接另一層度值大的節點即可，稱為有傾向性的構造正匹配效應的零模型網絡，負匹配效應相反。

4 結語

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

[參考文獻]

[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，FALL 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]胡華全，吳玲達，楊超，等.時變網絡可視化研究綜述[J].系統仿真學報，2013（9）：1975-1980，1989.

[9]李歡，盧罡，郭俊霞，等.復雜網絡零模型的量化評估[J].計算機應用，2015（6）：1560-1563.

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

[11]吳睿，宋玉蓉.2.25階/2.5階網絡零模型模擬退火優化算法[J/OL].計算機技術與發展，2017（12）：1-5[2018-01-12].http：//kns.cnki.net/kcms/detail/61.1450.TP.20170927.0957.006.html.

[12]尚可可，許小可.基于置亂算法的復雜網絡零模型構造及其應用[J].電子科技大學學報，2014（1）：7-20.

[13]崔麗艷，許小可.參照零模型的雙層網絡結構相關性檢測[J].科技導報，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.