基于非負矩陣分解的復雜網絡重構

陳增強，謝　征，張　青

(1.南開大學計算機與控制工程學院天津市智能機器人技術重點實驗室，天津 300071；2.中國民航大學理學院，天津 300300 )

?

基于非負矩陣分解的復雜網絡重構

陳增強1,2，謝征1，張青2

(1.南開大學計算機與控制工程學院天津市智能機器人技術重點實驗室，天津 300071；2.中國民航大學理學院，天津 300300 )

將網絡連邊的產生機制和其社團結構結合在一起，基于社團結構決定網絡連邊的假設推導出節點間的連接概率矩陣并表達為矩陣乘積的形式，然后利用非負矩陣分解得到節點間的連接概率矩陣進行網絡重建。設計實驗并在幾個真實的網絡數據上測試，相比基于相似度的網絡重構算法，該算法取得了更好的網絡重構效果。

復雜網絡；網絡重構；社團結構；連接概率矩陣；非負矩陣分解

0　引言

復雜網絡[1-2]是研究自然界各種復雜系統的有力工具。通過對復雜系統進行觀測和抽象，提取出一個由節點和連邊構成的網絡結構，進一步可以進行拓撲特性[3]、傳播行為[4-5]和網絡控制[6]等方面的分析研究。由于客觀因素的限制，觀測提取到的數據不能真實完整地反映實際網絡包含的信息，比如存在未被觀測到或者被錯誤觀測的數據，這就影響到了后續對數據的分析操作。網絡重構是解決此類問題的有效方法。網絡重構[7]是指根據觀測到的網絡節點屬性和結構信息，推斷網絡的真實結構，包括鏈路預測和虛假邊識別兩個部分。鏈路預測是預測節點之間可能會產生的連邊或觀測網絡中不存在而真實網絡中存在的連邊，虛假邊識別是識別觀測網絡中存在而真實網絡中不存在的連邊。網絡重構最早由Guimerà等[8]提出，他們采用隨機分塊模型，認為網絡是由群組組成，而節點之間連接的可能性取決于它所在的群組，基于極大似然分析得到各條連邊的可信度來進行網絡重構。Shen等[9]利用復雜網絡的稀疏性，采用壓縮感知理論來重構網絡。現有的研究多集中在鏈路預測[10]上。Kleinberg等[11]認為節點之間的相似性越大，其間存在連接的可能性越大，提出許多基于節點和基于路徑的相似性指標來進行鏈路預測。Zhou等[12]改進并設計了更高效的相似度指標。Clauset等[13]結合網絡的層次結構，提出基于極大似然估計的鏈路預測模型。Gao等[14]綜合考慮網絡的多方面信息，提出一種結合網絡拓撲、節點屬性和局部相似性的鏈路預測方法。相比較，虛假邊識別的研究較少。在鏈路預測過程中計算的節點相似性也可以用來做虛假邊識別的指標[3]。

由于網絡一般由鄰接矩陣表示，網絡的連邊進行增刪和權值改變即對應于鄰接矩陣的相應元素進行改變，因此網絡重構可看作是一個矩陣重建[15-16]問題。另一方面，網絡的連接和其社團結構[17]也緊密相關。每個節點在網絡中都有自己所扮演的“角色”，節點之間根據角色的相互作用產生連邊。而節點的角色特征體現在它所屬的社團中，社團結構的重疊性質又保證了節點可以扮演不同的角色，因此可以和更多的節點產生連邊，保證了網絡的多樣性。基于上述分析，本文將網絡的連邊產生機制和其社團結構結合在一起，認為網絡是由許多社團組成且節點之間連接的可能性取決于它所在的社團，基于此推導出節點間的連接概率矩陣，然后利用非負矩陣分解求解，并以得到的連接概率矩陣來推斷真實的網絡結構。在4個真實數據集上進行測試比較，發現該算法比基于節點相似性的算法能得到更好的重構效果。最后討論了參數選取，正則化等因素對算法效果的影響。

1　基于非負矩陣分解的網絡重構

1.1網絡重構

和隨機分塊模型類似，本文做出兩個基本假設。1)網絡由許多社團[17]組成，任意節點都屬于其中的至少一個社團。社團是網絡中一種很普遍的結構，表示節點基于某種特征形成的一種集合，例如社交網絡中的朋友圈，萬維網中的主題分類，引文網絡中的研究領域等等。不同于隨機分塊模型中的群組可以是節點的任意組合，社團結構要求社團內部聯系緊密，社團之間連接稀疏。每一個節點都會在網絡中扮演一定的角色，且由于節點角色的多樣性，其所屬社團可能會有多個。對于網絡中出現孤立節點的特殊情況，也可以將孤立節點看作一個社團。2)節點之間連接的可能性取決于其所在的社團，即節點之間是通過其所在的社團之間的聯系來產生連邊。這是由于節點所在的社團一定程度上描述了節點的身份屬性，而節點之間之所以產生連邊是因為其各自身份屬性的相互作用，故節點在社團中的成員身份決定其連接行為。由以上分析得出網絡重構的基本思路：通過節點間的網絡拓撲聯系，推斷節點的所屬社團和其內在的身份屬性，再由假設2)提出的網絡生成演化機制來重新生成網絡。

(1)

W=HSHT

(2)

矩陣W可以看作對原始鄰接矩陣A的近似表達，即

A≈W=HSHT

(3)

至此，我們將原始的網絡重構問題轉化為一個非負矩陣分解問題，即尋找合適的非負矩陣H和S，使其滿足式(3)的近似關系。

1.2非負矩陣分解

非負矩陣分解(Nonnegative Matrix Factorization，NMF)是將給定的非負矩陣近似分解為幾個非負矩陣的乘積的形式。1999年Lee等[18]在Nature上發表了NMF算法，之后各種改進的NMF算法被提出以提升其性能和擴展其應用范圍[19-20]。對于給定的非負矩陣V∈Rm×n，將其近似表達為兩個非負矩陣W∈Rm×k和H∈Rk×n的乘積，即

V≈WH

(4)

一種簡單的衡量這種近似程度的指標是誤差矩陣的Frobenius范數：

(5)

為求解上述問題，文獻[21]給出了一種乘性迭代規則

(6)

(7)

以同時滿足目標函數的非增性和矩陣元素的非負性。

對于本文的網絡重構問題，同樣采用上述指標來衡量重構網絡對原始觀測網絡的逼近程度，即

(8)

如果兩個節點直接相連接代表代表其幾何空間的鄰近性，則其社團隸屬度特征也應具有相應的鄰近性。為了保持這種數據空間的幾何特征，對原目標函數引入圖正則化[22]，得到新的目標函數：

(9)

s.t. H>0,S>0,S=ST

(10)

借鑒文獻[14]，本文給出了一種快速有效的迭代方法求解上述規劃問題：

(11)

(12)

將上述算法歸納如下：

1) 確定網絡鄰接矩陣A，矩陣S的維度k，正參數λ以及指定誤差限ε。

3)重復計算：通過式(11)和(12)計算H和S；通過式(9)計算優化目標值E；直到達到指定迭代次數或迭代滿足誤差限。

4)得到重構矩陣W及逼近誤差(λ=0時的E值),節點的社團隸屬度矩陣H和社團關系矩陣S。

本文中，將由目標式(8)計算重構矩陣的方法稱為基于社團劃分的非負矩陣分解(CNMF)，將由目標式(9)計算重構矩陣的方法稱為基于社團劃分的正則化非負矩陣分解(RCNMF)

2　實驗及分析

2.1實驗設計

為了檢驗該網絡重構算法的有效性，將驗證工作分為兩部分：鏈路預測的準確性和虛假邊識別的準確性。1)對于鏈路預測來說，首先將原始網絡數據中已知的連邊集E分為訓練集E1和測試集E2兩部分：E=E1∪E2，E1∩E2=Φ，把不屬于原始數據集E的連邊集合稱為不存在的邊集EN，并將其視為基準集EB；2)對于虛假邊識別來說，首先隨機生成一些原本不存在的邊ESN?EN，將原始數據集E與隨機生成的邊合并為訓練集E1=E∪ESN，將原始數據集E視為測試集E2=E，并將隨機生成的邊集視為基準集EB=ESN。對于這兩種情況，在迭代計算重構網絡的過程中只使用訓練集E1的數據，得到重構網絡W為節點之間連接的概率。

本文采用AUC指標衡量算法的精確度，即每次隨機地從測試集E2選取一條邊linkE2并隨機地從基準集EB選擇一條邊linkEB，比較這兩條邊在重構網絡中的概率值P(linkE2)和P(linkEB)，獨立比較n次，如果有n1次P(linkE2)>P(linkEB)，有n2次P(linkE2)=P(linkEB)，那么AUC指標值為

2.2實驗驗證與結果分析

本文在幾個真實的網絡數據集上實驗，比較了不同算法的準確度。實驗的數據集包括：空手道俱樂部[23],美國航空網絡[24]，線蟲的新陳代謝網絡[25]和線蟲的神經網絡[26]。對比算法采用了不同相似度指標，包括：Common Neighbor(CN)指標，Jaccard指標，AA指標，RA指標，PA指標，Local Paths(LP)指標和Katz指標。實驗隨機選取90%的數據作為訓練數據，剩下10%作為測試數據，將不同的算法應用在上述數據集上，計算AUC值的大小。為減小隨機因素的影響，將上述實驗進行20次，對每種算法得到的AUC取平均值，以比較不同算法的實驗效果。

在進行基于非負矩陣分解的網絡重構時，需要先對網絡數據進行預處理，將各網絡視作無權無向，將節點和連邊數據轉化為元素僅為0和1的鄰接矩陣的形式。實驗中先設定社團個數k和平衡參數λ為定值，比較基于非負矩陣分解和基于不同相似度的方法得到的重構網絡的準確度，然后分別調節參數k和λ的取值大小，討論其對網絡重構效果的影響。

2.2.1基于CNMF和基于不同相似度的網絡重構方法比較

在基于相似度的方法中，基于路徑信息的指標需要設定權重衰減因子來衡量不同長度路徑對相似度的影響。本文實驗中LP指標設定參數為0.000 1，Katz指標設定參數為0.01。在CNMF中，社團的個數k是可調參數，此處設定k=16，后文將比較不同的k值對重構效果的影響。鏈路預測結果如表1所示，虛假邊識別結果如表2所示。

表1　CNMF與基于相似度的方法在四種網絡上的鏈路預測結果比較

表2　CNMF與基于相似度的的方法在四種網絡上的虛假邊識別結果比較

在表1，2中，黑體為不同的算法在該數據上的最大AUC值。可以看出，CNMF和PA指標做鏈路預測都有很好的效果，僅僅在線蟲的新陳代謝網絡上CNMF的AUC值低于基于PA指標鏈路預測的AUC值；另一方面，CNMF做虛假邊識別的效果非常好，在4個數據集上的AUC值都比基于相似度指標的算法有很大提高，相比之下PA指標的虛假邊識別能力就較差。

2.2.2基于CNMF和RCNMF的網絡重構方法比較

由于缺乏足夠的先驗知識確定社團個數，實驗中設置社團的個數取多個值。由于網絡一般具有層次性，規模較大的社團內部可能包含有小規模的社團，設定社團的個數為2，4，8，16等以2的指數冪增加。考慮到社團本身包含的節點個數的特征，設定社團個數的上限為網絡1/3。進一步地，為綜合不同觀察尺度下的實驗結果，本文將不同層次社團下得到的逼近矩陣結合起來，即將不同k值得到的逼近矩陣相加，作為最終的網絡重構矩陣，然后在4個數據集上測試效果。CNMF和RCNMF及其集成算法Integrated CNMF(ICNMF)和Integrated RCNMF(IRCNMF)在不同網絡上做鏈路預測的效果見圖1，虛假邊識別的效果見圖2，其中算法RCNMF和IRCNMF中的平衡參數λ取0.4，后文將比較不同的λ值對重構效果的影響。為作圖方便，圖1和圖2的橫坐標均取以2為底，社團個數k的對數，縱坐標為20次實驗得到的AUC的平均值，并給出了相應的方差。

觀察圖1，2中各方法的重構效果，可以發現以下幾點：

1) 在karate網絡上，AUC值的方差比較大。一方面是由于選取訓練集和測試集的隨機性可能導致不同的逼近矩陣和測試結果，另一方面是由于該網絡本身規模較小，去掉部分連邊影響到網絡的社團結構，使得重構效果受訓練集影響偏大。

2) 除去在karate網絡上，隨著社團個數k的增加，AUC值均呈現先增大后減小的趨勢，即網絡重構效果先變好后變差。這是由于k的增加意味著矩陣H和S的維數增加，元素個數增加，有更多的變量去更好的逼近原始觀測矩陣，當k值過大時原始矩陣中的觀測誤差也被很好地逼近，導致其泛化能力降低，即出現了過擬合現象。

3) 無論是鏈路預測和虛假邊識別，加正則化后的RCNMF在多數網絡上均優于不加正則化的CNMF。這是由于正則化是對社團隸屬度矩陣H的元素的限制，使其保持原始觀測矩陣的幾何鄰近性特征，可以看作先驗知識對重構矩陣的修正，故網絡重構效果會更好。

4) 無論是鏈路預測還是虛假邊識別，集成算法ICNMF的重構效果在4個網絡上均優于原始的CNMF算法，說明綜合考慮網絡各個層次的結構信息，會有助于對網絡拓撲的解釋，從而生成更好的重構網絡。

5) 對于加正則化的算法而言，集成后的IRCNMF在虛假邊識別時效果優于RCNMF，在鏈路預測時小于RCNMF取不同k值時能得到的最大值，出現后者的原因可能是選取不同k值得到的重構矩陣的集成方式不夠合理。沒有考慮不同重構矩陣的逼近誤差，只是將效果不同的重構矩陣等同對待來集成，導致一些原本較好的重構結果被掩蓋。深層次的原因還需要進一步研究。

2.2.3平衡參數λ對RCNMF的網絡重構效果的影響

在上述實驗中，平衡參數λ固定取值為0.4。實際應用中，參數λ是調節逼近誤差項和正則化項對目標函數影響的平衡參數，其取值會影響到算法的性能指標。固定社團個數k為16，參數λ分別取0.04，0.4，4，40，400時，在USAir，Metabolic和C.elegans 3個數據集上進行網絡重構實驗，來測試λ對重構效果的影響。表3為參數對鏈路預測的影響，表4為參數對虛假邊識別的影響，圖3更直觀地顯示了參數變化對網絡重構效果的影響。

表3　平衡參數對3個網絡數據集鏈路預測效果的影響

表4　參數對3個網絡數虛假邊識別效果的影響

在表3，4中，黑體為不同的參數在3種網絡數據上的最大AUC值。結合圖3可以看出，隨著平衡參數λ的增大，網絡重構的準確率先增加后減少，且在取值為0.4的時候取得最大值。在λ取值較小時其變化對網絡重構的影響很小，能保持在較高的準確率，當λ取值過大時重構準確率下降很快。說明在網絡重構的過程中，應優先考慮減少對原始網絡的逼近誤差，然后是保持節點在劃分社團時的幾何臨近性。

3　總結與展望

針對網絡重構問題，本文提出社團結構決定網絡連接的假設，基于此假設將網絡重構問題轉化為非負矩陣分解問題來解決，同時討論了圖正則化和各參數的取值影響，得到了比傳統的基于相似度的算法更好地重構效果。該方法對于網絡的生成和演化機制的研究具有參考價值。該工作可以拓展到加權網絡的重構問題，如何更好地解釋權重和連邊可能性是下一步的研究方向。如何根據不同觀察尺度下得到的逼近誤差將重構矩陣進行整合以得到更好的重構效果、社團結構對網絡的生成和演化機制產生影響有什么深刻的內在機理，都是值得進一步深入研究的問題。

[1]汪小帆,李翔,陳關榮.網絡科學導論[M].北京:高等教育出版社.2012:3-27.

[2]呂琳媛, 陸君安, 張子柯，等. 復雜網絡觀察[J]. 復雜系統與復雜性科學, 2010, 7(2/3): 173-186.Lü Linyuan, Lu Junan, Zhang Zike, et al. Looking into complex networks [J]. Complex Systems and Complexity Science, 2010, 7(2/3): 173-186.

[3]Albert R, Barabási A L. Statistical mechanics of complex networks [J]. Reviews of Modern Physics, 2002, 74(1): 47-97.

[4]方義，夏承遺，劉子超，等.閃爍小世界網絡上疾病傳播的動態行為研究[J].復雜系統與復雜性科學，2011, 8(3): 34-37.

Fang Yi, Xia Chengyi, Liu Zichao, et al. Dynamical behavior of disease spreading on blinking small-world networks [J]. Complex Systems and Complexity Science, 2011, 8(3): 34-37.

[5]Xia C Y, Wang Z, Sanz J, et al. Effects of delayed recovery and nonuniform transmission on the spreading of diseases in complex in complex networks [J]. Physica A, 2013, 392, 1577-1585.

[6]Wang X F, Chen G R. Pinning control of scale-free dynamical networks [J]. Physica A, 2002, 310(3/4): 521-531.

[7]呂琳瑗,周濤.鏈路預測[M].北京：高等教育出版社.2013: 42-56,172-212.

[8]Guimerà R, Sales-Pardo M. Missing and spurious interactions and the reconstruction of complex networks [J]. Proceedings of the National Academy of Sciences, 2009, 106(52): 22073-22078.

[9]Shen Z, Wang W X, Fan Y, et al. Reconstructing propagation networks with natural diversity and identifying hidden sources[J]. Nature Communications, 2014, 5(5):4323.[10] Lü L, Zhou T. Link prediction in complex networks: a survey[J]. Physica A: Statistical Mechanics and Its Applications, 2011, 390(6): 1150-1170.

[11] Liben‐Nowell D, Kleinberg J. The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019-1031.

[12] Zhou T, Lü L, Zhang Y C. Predicting missing links via local information[J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2009, 71(4): 623-630.

[13] Clauset A, Moore C, Newman M E J. Hierarchical structure and the prediction of missing links in networks [J]. Nature, 2008, 453(7191): 98-101.

[14] Gao S, Denoyer L, Gallinari P. Temporal link prediction by integrating content and structure information [C] //Proceedings of the 20th ACM International Conference on Information and Knowledge Management. Glasgow, Scotland, UK: ACM, 2011: 1169-1174.

[15] Candès E J, Recht B. Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics, 2009, 9(6): 717-772.

[16] Candès E J, Li X, Ma Y, et al. Robust principal component analysis?[J]. Journal of the ACM, 2011, 58(3): 11-12.

[17] 程學旗, 沈華偉. 復雜網絡的社區結構[J]. 復雜系統與復雜性科學, 2011, 8(1): 57-70.

Cheng Xueqi, Shen Huawei. Community structure of complex networks [J]. Complex Systems and Complexity Science, 2011, 8(1): 57-70.

[18] Lee D D, Seung H S. Learning the parts of objects by non-negative matrix factorization [J]. Nature, 1999, 401(6755): 788-791.

[19] Ding C, He X, Simon H D. On the equivalence of nonnegative matrix factorization and spectral clustering[C]// SIAM International Conference on Data Mining. Vancouver, British Columbia, Canada: SIAM, 2005, 5: 606-610.

[20] Ding C, Li T, Peng W, et al. Orthogonal nonnegative matrix t-factorizations for clustering[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Philadelphia, USA: ACM, 2006: 126-135.

[21] Lee D D, Seung H S. Algorithms for non-negative matrix factorization[C]//Advances in Neural Information Processing Systems. Massachusetts, Cambridge, USA: The MIT Press, 2001: 556-562.

[22] Cai D, He X, Han J, et al. Graph regularized nonnegative matrix factorization for data representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1548-1560.

[23] Zachary W W. An information flow model for conflict and fission in small groups [J]. Journal of Anthropological Research, 1977: 33(4): 452-473.

[24] Vladimir B, Andrej M. Pajek datasets [DB/OL].[2013-12-30], http://vlado.fmf.uni-lj.si/pub/networks/data/mix/USAir97.net.

[25] Duch J, Arenas A. Community detection in complex networks using extremal optimization [J]. Physical Review E, 2005, 72(2): 027104.

[26] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440-442.

(責任編輯耿金花)

Complex Network Reconstruction Based on Nonnegative Matrix Factorization

CHEN Zengqiang1,2, XIE Zheng1, ZHANG Qing2

( 1.Tianjin Key Laboratory of Intelligent Robotics, College of Computer & Control Engineering,Nankai University, Tianjin 300071, China 2. College of Science, Civil Aviation University of China, Tianjin 300300, China )

Based on the hypothesis that community structure determines the network connections, the connection probability matrix which describes the nodes’ community structure can be transfered into the form of product of matrices. The nonnegative matrix factorization is applied here to get the connection probability matrix and then obtain the reconstruction. Experiments on several real world datasets show that the proposed algorithm outperforms some other algorithm which are based on similarity indexes.

complex network; network reconstruction; community structure; connection probability matrix; nonnegative matrix factorization.

1672-3813(2016)03-0026-07;DOI:10.13306/j.1672-3813.2016.03.004

2014-09-05；

2014-11-16

國家自然科學基金(61174094)；天津自然科學基金(14JCYBJC18700，13JCYBJC17400)

陳增強(1964-)，男，天津人，博士，教授，主要研究方向為復雜網絡，多智能體系統。

N94

A