原創 陳昊 集智俱樂部 收錄於話題#複雜科學前沿202053個
導語
如何利用部分網絡數據推斷網絡的宏觀屬性？能否進一步推斷出網絡中隱藏的連結模式，乃至補全中的具體節點與連邊？最近arXiv的一篇綜述文章，以統計物理和信息理論的視角，從宏觀、介觀和微觀三個尺度討論了解決網絡重構問題的思路、方法和技術，本文是對綜述整體內容的介紹。
陳昊 | 作者
劉培源 | 審校
鄧一雪 | 編輯
數據缺失是數據分析過程中遇到的普遍問題。即使在大數據時代，由於注釋錯誤、難以採集和隱私保護等問題，數據仍可能是不完整的。而在非結構化的網絡數據中，該問題顯得更加突出。在研究社會、經濟和生物等系統時，解決網絡結構的數據稀缺性的需求導致了網絡重構這一研究領域的誕生。
最近一篇掛上arXiv上的網絡重構領域綜述文章《Reconstructing networks》將網絡重構領域的研究劃分為宏觀、介觀和微觀三部分，對不同尺度的網絡重構問題及研究進展進行了詳盡的介紹。
論文題目：
Reconstructing networks
論文地址：
https://arxiv.org/abs/2012.02677
1. 宏觀尺度的網絡重構
宏觀尺度上的網絡重構側重於推斷網絡的全局特徵，例如同配性和層次結構。在研究該尺度時，通常不考慮任何特定拓撲細節，而是利用網絡的多種宏觀屬性來指導重構。
主流的宏觀尺度網絡重構模型有 2011 年提出的 Directed Weighted Configuration Model[1]和 2018 年提出的 Maximum-Entropy Capital Asset Pricing Model（MECAPM） [2]。在描述網絡性質的眾多參數中，Strengths（節點所有連邊的權重和）發揮了很重要的作用，因為它是很多實際網絡能提供的唯一信息。遺憾的是在僅提供 Strengths 信息的情況下，以上兩種方法都無法很好地重構網絡宏觀結構。2014 年提出的 Enhanced Configuration Model（ECM）[3]則可以很好地解決該問題。下圖為 ECM 在宏觀尺度網絡重構中的表現。
圖1. 已知 srengths 和度的情況下，ECM 模型的表現。每張子圖都展示了針對某些網絡實際節點特定網絡屬性的重構結果（Y軸）與理論值（X軸）左上：最近鄰居平均度（average nearest neighbors degree），右上：集聚係數(clustering coefficient) ，左下：最近鄰居平均強度（average nearest neighbors strength） ，右下：加權聚類係數（weighted clustering coefficient）[3]
為了從另一個方面分析重構方法的優缺點，該綜述還討論了系統風險的量化問題。自金融危機爆發以來，這個問題變得極為重要。金融機構之間複雜的互連模式有可能使整個系統變得極為脆弱，因為這些聯繫構成了財務危機擴散的渠道，這是金融系統風險的主要來源。下圖為 dcGM[4] 和 MECAPM[2] 兩種模型在證券持有（SHS）網絡上的表現。
圖2. 在 SHS 網絡數據集中重構網絡系統性:每個點代表一個具體部門使用dcGM（藍色）或MECAPM（綠色）推斷出的相對系統性，兩種方法的平均值均以水平實線表示。[14]
2. 介觀尺度的網絡重構
介觀尺度的網絡重構側重於發現節點分布模式，如社區結構、核心-邊緣結構和二分結構，並以此指導網絡重構。該主題引起了流行病學、生物學等領域的關注，並最終確定核心問題為發現節點間連接的模式及其衍生功能的相似性。介觀尺度模式的存在對於網絡上的各種動態過程，如信息和流行病的傳播有巨大影響。
2.1 社區結構
如圖 3 所示，滿足社區結構的網絡由多個結構相似的模塊組成。社區發現問題有多方面價值：首先，同一社群的節點具有很多相似的屬性，因而可以用於指導網絡的粗粒化從而簡化數據規模。其次，具有不同屬性的社群有助於揭示在宏觀尺度下被平均化的網絡特徵。此外社區劃分還可以指導對於模塊功能的探索等。
圖3. 網絡的社區結構舉例及其鄰接矩陣表示[5]
社區檢測問題仍然是一個未解決的問題，在過去二十年中有許多算法陸續被提出，主要可以分為兩大類：局部社區檢測和全局社區檢測。局部社區檢測基於社團內部的屬性，例如度、可及性和凝聚性等。當網絡的全局信息需要納入考慮時，則需要使用全局社區檢測方法。十分流行的模塊度方法就屬於全局社區檢測。
2.2 核心-邊緣結構
如圖 4 所示，滿足核心-邊緣結構的網絡由大量緊密連結的核心節點和稀疏連接的外圍節點組成，該類型的網絡在經濟學、社會學、神經科學等領域廣泛出現。
圖4. 核心-邊緣結構網絡示例 左圖為核心-邊緣結構網絡中的節點類型，右圖為嚴格符合核心邊緣結構的網絡的鄰接矩陣[6]
第一個不以網絡一定具有核心-邊緣結構為前提的檢測算法由 Holme 在 2005 年提出[15]，該算法主要基於網絡的緊密中心性。2013 年由 Della Rossa 等人提出的基於標準隨機遊走的算法將檢測範圍擴充到了加權網絡[16]。在最近的研究中，van Lidth de Jeude 等人受超幾何分布中的 p 值啟發提出了一種新的核心-邊緣檢測基準模型[17]。
3. 微觀尺度的網絡重構
微觀尺度的網絡重構重點在於預測網絡中缺失的具體連邊，即鏈路預測問題。該問題對於多種具體網絡都有重要價值。以生物領域為例，對於食物網、蛋白質相互作用網和代謝網絡而言，通過實驗來判斷節點間是否存在連接需要付出巨大的經濟成本。與其盲目進行實驗，不如先通過鏈路預測找到那些最有可能存在的連邊，而後有的放矢地進行試驗。
連結預測方法大致可分為兩大類：基於相似度的算法和基於模型的算法。兩種方法的關鍵基本假設均為：如果兩個節點具有更大的相似性，則它們之間更可能存在連結。
3.1 基於相似度的算法
基於相似度的算法為每個待預測的連邊生成一個分數來評價其連接節點間的相似性。該分數取決於節點間屬性的差異性。依照所用節點屬性還可以將算法具體分為基於局部、半局部和全局相似性的算法。
如圖 5(a) 所示，基於局部相似性的算法通常基於社交網絡分析中的共同鄰居觀念，即如果兩個人的共同朋友越多，他們彼此認識的可能性就更大，該原理被稱為三元閉包（Triadic Closure Principle），是網絡中長度為 2 的路徑產生的主要原因。半局部相似性則與網絡中長度為 3 的路徑更為相關，例如在蛋白質相互作用網絡中，兩個結構相似的蛋白質不會相互作用。如圖 5(c) 所示，當蛋白質D與Y被很多長度為3的路徑連接時，二者才更有可能產生一條連邊。
圖5. 社交網絡與蛋白質網絡中的鏈路預測 圖a為社交網絡中連邊產生的示意圖。圖b為在滿足三元閉包原理（Triadic Closure Principle）的網絡模型下不同狀態的節點對間產生連邊的概率。圖c為蛋白質相互作用中連邊產生的示意圖。圖d為在滿足四元閉包原理（Quadrangular Closure Principle）的網絡模型下不同狀態的節點對間產生連邊的概率。[7]
3.2 基於模型的算法
基於模型的方法構建於網絡具有特定組織結構的假設之上，如圖 6 所示，該類算法希望待預測的連邊可以儘可能好地完善網絡所具備的結構。
圖6. 在基於模型的算法上對網絡結構進行採樣 （A）分層結構網絡 （B）塊狀結構網絡 （C）無標度網絡[8-10]
以層次結構模型為例，該類算法基於現實世界中許多網絡是分層組織的，這意味著可以將節點劃分為組，隨後再細分為組的組，以此類推。利用提取出的層次結構輔助鏈路預測。2008 年由 Clauset 等人提出的 Hierarchical Random Graph Model[8] 是具有代表性的基於層次結構的模型。該模型給網絡中的每個節點定義了一個連接概率，兩個節點間是否存在連邊取決於二者共同父節點的連接概率。
4. 小結
在大數據時代，人們對於數據完整性的需求愈發提高，網絡重構技術可以在信息提取質量不高的情況下，從數據本身出發最大程度的恢復數據完整性，具有廣闊的應用場景。
這篇綜述從宏觀、介觀、微觀三個角度介紹了網絡重構領域的研究問題、常見模型及應用場景。到目前為止，網絡重構領域處於快速發展和完善的階段，有向加權圖上的鏈路預測[11]、對於連邊具有信息的網絡的重構[12]以及時序網絡重構[13]等研究方向正在快速發展。
參考資料
[1] Squartini, Tiziano and D. Garlaschelli. 「Analytical maximum-likelihood method to detect patterns in real networks.」 New Journal of Physics 13 (2011): 083001.
[2] Gangi, Domenico Di et al. 「Assessing Systemic Risk Due to Fire Sales Spillover Through Maximum Entropy Network Reconstruction.」 Regulation of Financial Institutions eJournal (2018): n. pag.
[3] Mastrandrea, R. et al. 「Enhanced reconstruction of weighted networks from strengths and degrees.」 New Journal of Physics 16 (2014): 043022.
[4] Cimini, G. et al. 「Systemic Risk Analysis on Reconstructed Economic and Financial Networks.」 Scientific Reports 5 (2015): n. pag.
[5] Faskowitz, J. et al. 「Weighted Stochastic Block Models of the Human Connectome across the Life Span.」 Scientific Reports 8 (2018): n. pag.
[6] Borgatti, S. and M. Everett. 「Models of core/periphery structures.」 Soc. Networks 21 (2000): 375-395.
[7] Kovács, István A. et al. 「Network-based prediction of protein interactions.」 Nature Communications 10 (2019): n. pag.
[8] Clauset, A. et al. 「Hierarchical structure and the prediction of missing links in networks.」 Nature 453 (2008): 98-101.
[9] Larremore, D. et al. 「A Network Approach to Analyzing Highly Recombinant Malaria Parasite Genes.」 PLoS Computational Biology 9 (2013): n. pag.
[10] Oikonomou, Panos and P. Cluzel. 「Effects of topology on network evolution.」 Nature Physics 2 (2006): 532-536.
[11] Alon, U.. 「Network motifs: theory and experimental approaches.」 Nature Reviews Genetics 8 (2007): 450-461.
[12] Leskovec, J. et al. 「Predicting positive and negative links in online social networks.」 WWW '10 (2010).
[13] Tylenda, Tomasz et al. 「Towards time-aware link prediction in evolving social networks.」 SNA-KDD '09 (2009).
[14] Squartini, Tiziano et al. 「Enhanced capital-asset pricing model for the reconstruction of bipartite financial networks.」 Physical review. E 96 3-1 (2017): 032315 .
[15] Holme, P.. 「Core-periphery organization of complex networks.」 Physical review. E, Statistical, nonlinear, and soft matter physics 72 4 Pt 2 (2005): 046111 .
[16] Rossa, F. et al. 「Profiling core-periphery network structure by random walkers.」 Scientific Reports 3 (2013): n. pag.
[17] Jeude, J. V. L. D. et al. 「Detecting Core-Periphery Structures by Surprise.」 ArXiv abs/1810.04717 (2018): n. pag.
課程推薦
複雜科學最新論文
集智斑圖頂刊論文速遞欄目上線以來，持續收錄來自Nature、Science等頂刊的最新論文，追蹤複雜系統、網絡科學、計算社會科學等領域的前沿進展。現在正式推出訂閱功能，每周通過微信服務號「集智斑圖」推送論文信息。掃描下方二維碼即可一鍵訂閱：
原標題：《網絡重構最新綜述推薦：從宏觀尺度到微觀尺度》
閱讀原文