陳增強(qiáng)，謝　征，張　青

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

?

基于非負(fù)矩陣分解的復(fù)雜網(wǎng)絡(luò)重構(gòu)

陳增強(qiáng)1,2，謝征1，張青2

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

將網(wǎng)絡(luò)連邊的產(chǎn)生機(jī)制和其社團(tuán)結(jié)構(gòu)結(jié)合在一起，基于社團(tuán)結(jié)構(gòu)決定網(wǎng)絡(luò)連邊的假設(shè)推導(dǎo)出節(jié)點間的連接概率矩陣并表達(dá)為矩陣乘積的形式，然后利用非負(fù)矩陣分解得到節(jié)點間的連接概率矩陣進(jìn)行網(wǎng)絡(luò)重建。設(shè)計實驗并在幾個真實的網(wǎng)絡(luò)數(shù)據(jù)上測試，相比基于相似度的網(wǎng)絡(luò)重構(gòu)算法，該算法取得了更好的網(wǎng)絡(luò)重構(gòu)效果。

復(fù)雜網(wǎng)絡(luò)；網(wǎng)絡(luò)重構(gòu)；社團(tuán)結(jié)構(gòu)；連接概率矩陣；非負(fù)矩陣分解

0　引言

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

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

1　基于非負(fù)矩陣分解的網(wǎng)絡(luò)重構(gòu)

1.1網(wǎng)絡(luò)重構(gòu)

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

(1)

W=HSHT

(2)

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

A≈W=HSHT

(3)

至此，我們將原始的網(wǎng)絡(luò)重構(gòu)問題轉(zhuǎn)化為一個非負(fù)矩陣分解問題，即尋找合適的非負(fù)矩陣H和S，使其滿足式(3)的近似關(guān)系。

1.2非負(fù)矩陣分解

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

V≈WH

(4)

一種簡單的衡量這種近似程度的指標(biāo)是誤差矩陣的Frobenius范數(shù)：

(5)

為求解上述問題，文獻(xiàn)[21]給出了一種乘性迭代規(guī)則

(6)

(7)

以同時滿足目標(biāo)函數(shù)的非增性和矩陣元素的非負(fù)性。

對于本文的網(wǎng)絡(luò)重構(gòu)問題，同樣采用上述指標(biāo)來衡量重構(gòu)網(wǎng)絡(luò)對原始觀測網(wǎng)絡(luò)的逼近程度，即

(8)

如果兩個節(jié)點直接相連接代表代表其幾何空間的鄰近性，則其社團(tuán)隸屬度特征也應(yīng)具有相應(yīng)的鄰近性。為了保持這種數(shù)據(jù)空間的幾何特征，對原目標(biāo)函數(shù)引入圖正則化[22]，得到新的目標(biāo)函數(shù)：

(9)

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

(10)

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

(11)

(12)

將上述算法歸納如下：

1) 確定網(wǎng)絡(luò)鄰接矩陣A，矩陣S的維度k，正參數(shù)λ以及指定誤差限ε。

3)重復(fù)計算：通過式(11)和(12)計算H和S；通過式(9)計算優(yōu)化目標(biāo)值E；直到達(dá)到指定迭代次數(shù)或迭代滿足誤差限。

4)得到重構(gòu)矩陣W及逼近誤差(λ=0時的E值),節(jié)點的社團(tuán)隸屬度矩陣H和社團(tuán)關(guān)系矩陣S。

本文中，將由目標(biāo)式(8)計算重構(gòu)矩陣的方法稱為基于社團(tuán)劃分的非負(fù)矩陣分解(CNMF)，將由目標(biāo)式(9)計算重構(gòu)矩陣的方法稱為基于社團(tuán)劃分的正則化非負(fù)矩陣分解(RCNMF)

2　實驗及分析

2.1實驗設(shè)計

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

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

2.2實驗驗證與結(jié)果分析

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

在進(jìn)行基于非負(fù)矩陣分解的網(wǎng)絡(luò)重構(gòu)時，需要先對網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行預(yù)處理，將各網(wǎng)絡(luò)視作無權(quán)無向，將節(jié)點和連邊數(shù)據(jù)轉(zhuǎn)化為元素僅為0和1的鄰接矩陣的形式。實驗中先設(shè)定社團(tuán)個數(shù)k和平衡參數(shù)λ為定值，比較基于非負(fù)矩陣分解和基于不同相似度的方法得到的重構(gòu)網(wǎng)絡(luò)的準(zhǔn)確度，然后分別調(diào)節(jié)參數(shù)k和λ的取值大小，討論其對網(wǎng)絡(luò)重構(gòu)效果的影響。

2.2.1基于CNMF和基于不同相似度的網(wǎng)絡(luò)重構(gòu)方法比較

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

表1　CNMF與基于相似度的方法在四種網(wǎng)絡(luò)上的鏈路預(yù)測結(jié)果比較

表2　CNMF與基于相似度的的方法在四種網(wǎng)絡(luò)上的虛假邊識別結(jié)果比較

在表1，2中，黑體為不同的算法在該數(shù)據(jù)上的最大AUC值?？梢钥闯?，CNMF和PA指標(biāo)做鏈路預(yù)測都有很好的效果，僅僅在線蟲的新陳代謝網(wǎng)絡(luò)上CNMF的AUC值低于基于PA指標(biāo)鏈路預(yù)測的AUC值；另一方面，CNMF做虛假邊識別的效果非常好，在4個數(shù)據(jù)集上的AUC值都比基于相似度指標(biāo)的算法有很大提高，相比之下PA指標(biāo)的虛假邊識別能力就較差。

2.2.2基于CNMF和RCNMF的網(wǎng)絡(luò)重構(gòu)方法比較

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

觀察圖1，2中各方法的重構(gòu)效果，可以發(fā)現(xiàn)以下幾點：

1) 在karate網(wǎng)絡(luò)上，AUC值的方差比較大。一方面是由于選取訓(xùn)練集和測試集的隨機(jī)性可能導(dǎo)致不同的逼近矩陣和測試結(jié)果，另一方面是由于該網(wǎng)絡(luò)本身規(guī)模較小，去掉部分連邊影響到網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，使得重構(gòu)效果受訓(xùn)練集影響偏大。

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

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

4) 無論是鏈路預(yù)測還是虛假邊識別，集成算法ICNMF的重構(gòu)效果在4個網(wǎng)絡(luò)上均優(yōu)于原始的CNMF算法，說明綜合考慮網(wǎng)絡(luò)各個層次的結(jié)構(gòu)信息，會有助于對網(wǎng)絡(luò)拓?fù)涞慕忉專瑥亩筛玫闹貥?gòu)網(wǎng)絡(luò)。

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

2.2.3平衡參數(shù)λ對RCNMF的網(wǎng)絡(luò)重構(gòu)效果的影響

在上述實驗中，平衡參數(shù)λ固定取值為0.4。實際應(yīng)用中，參數(shù)λ是調(diào)節(jié)逼近誤差項和正則化項對目標(biāo)函數(shù)影響的平衡參數(shù)，其取值會影響到算法的性能指標(biāo)。固定社團(tuán)個數(shù)k為16，參數(shù)λ分別取0.04，0.4，4，40，400時，在USAir，Metabolic和C.elegans 3個數(shù)據(jù)集上進(jìn)行網(wǎng)絡(luò)重構(gòu)實驗，來測試λ對重構(gòu)效果的影響。表3為參數(shù)對鏈路預(yù)測的影響，表4為參數(shù)對虛假邊識別的影響，圖3更直觀地顯示了參數(shù)變化對網(wǎng)絡(luò)重構(gòu)效果的影響。

表3　平衡參數(shù)對3個網(wǎng)絡(luò)數(shù)據(jù)集鏈路預(yù)測效果的影響

表4　參數(shù)對3個網(wǎng)絡(luò)數(shù)虛假邊識別效果的影響

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

3　總結(jié)與展望

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

[1]汪小帆,李翔,陳關(guān)榮.網(wǎng)絡(luò)科學(xué)導(dǎo)論[M].北京:高等教育出版社.2012:3-27.

[2]呂琳媛, 陸君安, 張子柯，等. 復(fù)雜網(wǎng)絡(luò)觀察[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 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]方義，夏承遺，劉子超，等.閃爍小世界網(wǎng)絡(luò)上疾病傳播的動態(tài)行為研究[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，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]呂琳瑗,周濤.鏈路預(yù)測[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] 程學(xué)旗, 沈華偉. 復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 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.

(責(zé)任編輯耿金花)

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

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

陳增強(qiáng)(1964-)，男，天津人，博士，教授，主要研究方向為復(fù)雜網(wǎng)絡(luò)，多智能體系統(tǒng)。

N94

A