潘永昊，于洪濤，吳翼騰

基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的鏈路預(yù)測(cè)方法

潘永昊，于洪濤，吳翼騰

（國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002）

鏈路預(yù)測(cè)是復(fù)雜網(wǎng)絡(luò)中研究缺失連邊和未來(lái)形成連邊的重要組成部分，當(dāng)前基于網(wǎng)絡(luò)結(jié)構(gòu)的鏈路預(yù)測(cè)方法成果豐富，而基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的鏈路預(yù)測(cè)研究較少。針對(duì)無(wú)權(quán)無(wú)向網(wǎng)絡(luò)，首先構(gòu)建了復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型，然后給出了基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的鏈路預(yù)測(cè)節(jié)點(diǎn)中心性的量化評(píng)價(jià)指標(biāo)，最后通過(guò)給出的節(jié)點(diǎn)中心性量化指標(biāo)，提出了由復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型定義的鏈路預(yù)測(cè)方法。通過(guò)在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)表明，提出的鏈路預(yù)測(cè)方法較基準(zhǔn)方法有明顯的預(yù)測(cè)精度的提升。

復(fù)雜網(wǎng)絡(luò)；鏈路預(yù)測(cè)；網(wǎng)絡(luò)動(dòng)力學(xué)

1 引言

鏈路預(yù)測(cè)（link prediction）[1]是復(fù)雜網(wǎng)絡(luò)研究中的一個(gè)重要內(nèi)容，主要研究網(wǎng)絡(luò)中缺失信息的補(bǔ)全和網(wǎng)絡(luò)結(jié)構(gòu)的演化，具體為對(duì)網(wǎng)絡(luò)中缺失連接、未來(lái)形成連接的預(yù)測(cè)。鏈路預(yù)測(cè)研究在很多領(lǐng)域得到了廣泛的應(yīng)用，如生物蛋白質(zhì)結(jié)構(gòu)構(gòu)建[2]、社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)分析[3]、網(wǎng)絡(luò)演化機(jī)制[4-5]等。

現(xiàn)有的鏈路預(yù)測(cè)方法主要基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如基于共同鄰居[6]相似性的方法、基于路徑[7]相似性的方法、層次結(jié)構(gòu)模型[8]和隨機(jī)分塊模型[1]等。近年來(lái)，新出現(xiàn)的研究大多是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法[9-13]。在基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究中，一個(gè)重要的依據(jù)是基于度中心性節(jié)點(diǎn)重要性評(píng)價(jià)，即對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)，度越大，其在網(wǎng)絡(luò)中的重要性和影響力越大。目前，大量的鏈路預(yù)測(cè)方法中使用了基于度中心性的節(jié)點(diǎn)重要性評(píng)價(jià)[14]，如在基于共同鄰居相似性的鏈路預(yù)測(cè)中，Adamic-Adar指標(biāo)[15]、大度節(jié)點(diǎn)不利指標(biāo)[16]（HDI，hub depressed index）等相似性指標(biāo)認(rèn)為，度小的共同鄰居節(jié)點(diǎn)的貢獻(xiàn)大于度大的共同鄰居節(jié)點(diǎn)?；诙戎行男缘墓?jié)點(diǎn)重要性評(píng)價(jià)方法在鏈路預(yù)測(cè)的應(yīng)用中具有方便直觀(guān)、運(yùn)算復(fù)雜度低的特點(diǎn)，并且具有很好的預(yù)測(cè)精度。然而，基于度中心性的節(jié)點(diǎn)重要性評(píng)價(jià)方法以節(jié)點(diǎn)的局部特征為計(jì)算標(biāo)準(zhǔn)，僅能表示出該節(jié)點(diǎn)的局部連邊關(guān)系，不能充分反映該節(jié)點(diǎn)的重要性和影響力。而在實(shí)際的鏈路預(yù)測(cè)中，不同的網(wǎng)絡(luò)在結(jié)構(gòu)特征上各有差別，預(yù)測(cè)精度的高低與鏈路預(yù)測(cè)方法中的結(jié)構(gòu)特征有直接的關(guān)系?，F(xiàn)有的研究成果大多使用節(jié)點(diǎn)度作為節(jié)點(diǎn)重要性的評(píng)價(jià)方法，因此，考慮采用另外一種角度對(duì)節(jié)點(diǎn)度進(jìn)行調(diào)整，研究鏈路預(yù)測(cè)問(wèn)題。

相關(guān)研究表明，在考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的同時(shí)，對(duì)節(jié)點(diǎn)的動(dòng)力學(xué)行為進(jìn)行建模，所得到的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型能夠更加深刻地揭示網(wǎng)絡(luò)結(jié)構(gòu)與節(jié)點(diǎn)之間的本質(zhì)關(guān)系和規(guī)律。Liu等[17]的研究中發(fā)現(xiàn)網(wǎng)絡(luò)中節(jié)點(diǎn)動(dòng)力學(xué)模型相同的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)系統(tǒng)中，驅(qū)動(dòng)節(jié)點(diǎn)傾向于避免大度節(jié)點(diǎn)，這與文獻(xiàn)[15]中認(rèn)為的共同鄰居節(jié)點(diǎn)中小度節(jié)點(diǎn)的貢獻(xiàn)大于大度節(jié)點(diǎn)異曲同工，但卻更深刻地反映出網(wǎng)絡(luò)中的動(dòng)力學(xué)規(guī)律。Jia等[18]的研究表明，網(wǎng)絡(luò)中節(jié)點(diǎn)是否為驅(qū)動(dòng)節(jié)點(diǎn)，與節(jié)點(diǎn)的入度有關(guān)，與出度無(wú)關(guān)。在孔江濤等[19]的研究中提出了基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的節(jié)點(diǎn)重要性評(píng)價(jià)方法，通過(guò)對(duì)節(jié)點(diǎn)引入一個(gè)驅(qū)動(dòng)因素，計(jì)算網(wǎng)絡(luò)再次達(dá)到穩(wěn)定狀態(tài)以后所有節(jié)點(diǎn)的偏移量，偏移量大的即為重要節(jié)點(diǎn)。可以看出，基于網(wǎng)絡(luò)動(dòng)力學(xué)模型的研究，包含了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、節(jié)點(diǎn)動(dòng)力學(xué)建模，能夠具體描述分析時(shí)域上網(wǎng)絡(luò)狀態(tài)的變化，得到的結(jié)果優(yōu)于只基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究。

針對(duì)以上分析，本文考慮使用復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的研究方法，對(duì)無(wú)權(quán)無(wú)向網(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)動(dòng)力學(xué)建模，引入文獻(xiàn)[19]中的擾動(dòng)測(cè)試方法對(duì)節(jié)點(diǎn)重要性進(jìn)行量化評(píng)價(jià)，對(duì)現(xiàn)有的基于度中心性的鏈路預(yù)測(cè)方法進(jìn)行改進(jìn)，提出基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的鏈路預(yù)測(cè)方法。最后通過(guò)在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)，證明本文提出的方法能夠有效提高鏈路預(yù)測(cè)的精度。文章創(chuàng)新點(diǎn)如下：1) 考慮使用復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型對(duì)靜態(tài)無(wú)權(quán)無(wú)向網(wǎng)絡(luò)模型進(jìn)行擴(kuò)展，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行動(dòng)力學(xué)建模，在復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型上研究鏈路預(yù)測(cè)問(wèn)題；2) 提出了基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的鏈路預(yù)測(cè)方法，并在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上驗(yàn)證其有效性。

2 相關(guān)工作

鏈路預(yù)測(cè)問(wèn)題自提出以來(lái)，經(jīng)過(guò)多年的研究，已經(jīng)形成了豐富的研究成果，本節(jié)給出幾種典型的基于度中心性的鏈路預(yù)測(cè)相似性指標(biāo)的定義。

S?renson指標(biāo)[1]由S?renson提出，基于節(jié)點(diǎn)的共同鄰居集合定義，常用于研究生態(tài)學(xué)數(shù)據(jù)，定義式如下。

大度節(jié)點(diǎn)有利指標(biāo)（HPI，hub promoted index）[16]被用于刻畫(huà)新陳代謝網(wǎng)絡(luò)中反應(yīng)物的相似程度，認(rèn)為度大的節(jié)點(diǎn)在網(wǎng)絡(luò)中與其他節(jié)點(diǎn)具有更大的相似性，定義式如下。

大度節(jié)點(diǎn)不利指標(biāo)（HDI，hub depressed index）[21]認(rèn)為度小的節(jié)點(diǎn)在網(wǎng)絡(luò)中與其他節(jié)點(diǎn)具有更大的相似性，定義式如下。

Adamic-Adar指標(biāo)[23]認(rèn)為網(wǎng)絡(luò)中度小的共同鄰居節(jié)點(diǎn)的貢獻(xiàn)大于度大的共同鄰居節(jié)點(diǎn)，定義式如下。

資源分配指標(biāo)（RA，resource allocation）[21]與AA指標(biāo)相似，采用與AA指標(biāo)不同的歸一化方法，定義式如下。

3 問(wèn)題描述

鏈路預(yù)測(cè)相似性計(jì)算指標(biāo)的定義包含對(duì)節(jié)點(diǎn)在網(wǎng)絡(luò)中重要性的評(píng)價(jià)。一種能夠充分契合實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的評(píng)價(jià)方法，使相似性指標(biāo)更加契合當(dāng)前網(wǎng)絡(luò)的真實(shí)情況，得到更好的預(yù)測(cè)精確度。

4 主要內(nèi)容

復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型同時(shí)考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)動(dòng)態(tài)屬性，能夠反映出網(wǎng)絡(luò)的本質(zhì)特征。本節(jié)首先定義復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型，然后給出復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的節(jié)點(diǎn)重要性評(píng)價(jià)方法[19]，最后定義改進(jìn)的鏈路預(yù)測(cè)相似性指標(biāo)。

4.1 復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型定義

4.2 節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)

式(10)和式(11)定義了復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型，下面給出基于擾動(dòng)測(cè)試[19]的節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo)。

考慮當(dāng)單個(gè)節(jié)點(diǎn)發(fā)生變化時(shí)，對(duì)整個(gè)網(wǎng)絡(luò)平衡狀態(tài)的影響，通過(guò)計(jì)算影響程度，得到節(jié)點(diǎn)的重要性量化評(píng)價(jià)指標(biāo)，基于網(wǎng)絡(luò)動(dòng)力學(xué)模型定義的節(jié)點(diǎn)重要性指標(biāo)[19]，能夠很好地反映出節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度和影響力。

設(shè)動(dòng)態(tài)系統(tǒng)的狀態(tài)方程為

設(shè)無(wú)權(quán)無(wú)向網(wǎng)絡(luò)的動(dòng)力學(xué)模型的狀態(tài)方程為

擾動(dòng)模型定義如下。

使用基于偏離均值的方差定義節(jié)點(diǎn)的重要性指標(biāo)，其數(shù)值越大，節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性和影響力越大，反之則小。

4.3 鏈路預(yù)測(cè)模型

基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的Salton指標(biāo)為

基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的S?renson指標(biāo)為

大度節(jié)點(diǎn)有利指標(biāo)是針對(duì)節(jié)點(diǎn)的度設(shè)計(jì)計(jì)算的，為了便于理解，把基于偏離均值的方差重新定義指標(biāo)記為基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的大度節(jié)點(diǎn)有利指標(biāo)。

同樣，對(duì)于大度節(jié)點(diǎn)不利指標(biāo)，把基于偏離均值的方差重新定義指標(biāo)記為基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的大度節(jié)點(diǎn)不利指標(biāo)。

基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的LHN-I指標(biāo)為

基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的Adamic-Adar指標(biāo)為

基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的資源分配指標(biāo)為

以上給出的指標(biāo)是在原始指標(biāo)的基礎(chǔ)上對(duì)節(jié)點(diǎn)度進(jìn)行了修改，出發(fā)點(diǎn)是考慮節(jié)點(diǎn)的度在各個(gè)原始指標(biāo)中的意義，實(shí)際上，網(wǎng)絡(luò)本身就是表示當(dāng)前節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性和影響力。需要說(shuō)明的是，對(duì)于一些改進(jìn)后的指標(biāo)，如余弦相似性、大度節(jié)點(diǎn)有利、大度節(jié)點(diǎn)不利等，其定義與原始指標(biāo)的定義初衷發(fā)生了一些變化，但修改部分所表達(dá)的意義是相同的。

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證上文中給出的鏈路預(yù)測(cè)算法的有效性，本文在4個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行鏈路預(yù)測(cè)對(duì)比實(shí)驗(yàn)，分別為：

1) 爵士音樂(lè)家合作網(wǎng)（Jazz）[25]，網(wǎng)絡(luò)中的節(jié)點(diǎn)為爵士音樂(lè)家，連邊表示音樂(lè)家的合作關(guān)系；

2) 線(xiàn)蟲(chóng)的神經(jīng)網(wǎng)絡(luò)（CE）[26]，節(jié)點(diǎn)表示線(xiàn)蟲(chóng)的神經(jīng)元，邊表示神經(jīng)元突觸；

3) 美國(guó)航空網(wǎng)絡(luò)（USAir）[27]，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)機(jī)場(chǎng)，連邊表示兩個(gè)機(jī)場(chǎng)之間有直飛的航線(xiàn)；

4) 佛羅里達(dá)海灣雨季的食物鏈網(wǎng)絡(luò) (FWFB)[28]，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)表示一種生物，邊表示生物之間捕食關(guān)系。

以上4個(gè)網(wǎng)絡(luò)的基本結(jié)構(gòu)參數(shù)如表1所示。

表1 靜態(tài)網(wǎng)絡(luò)數(shù)據(jù)集拓?fù)涮卣鲄?shù)

其中，||表示網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)，||表示邊的數(shù)量，<>表示網(wǎng)絡(luò)的平均度，<>表示網(wǎng)絡(luò)平均距離，表示網(wǎng)絡(luò)簇系數(shù)，表示結(jié)合系數(shù)。

5.2 度量指標(biāo)

5.3 實(shí)驗(yàn)對(duì)比分析

表2 Jazz網(wǎng)絡(luò)中的AUC計(jì)算結(jié)果

表3 CE網(wǎng)絡(luò)中的AUC計(jì)算結(jié)果

在爵士音樂(lè)家合作網(wǎng)數(shù)據(jù)集中的計(jì)算結(jié)果如表2所示。從計(jì)算結(jié)果可以看出，在該網(wǎng)絡(luò)數(shù)據(jù)集中，基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的鏈路預(yù)測(cè)方法整體表現(xiàn)不如原始方法，只有基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的AA指標(biāo)略高于原始AA指標(biāo)。在基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的方法中，AA指標(biāo)精確度最高。

在線(xiàn)蟲(chóng)的神經(jīng)網(wǎng)絡(luò)數(shù)據(jù)集中的計(jì)算結(jié)果如表3所示。基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的鏈路預(yù)測(cè)方法中，Salton指標(biāo)、S?renson指標(biāo)、HPI指標(biāo)、HDI指標(biāo)、LHN-I指標(biāo)相比原始方法的精確度有大幅度的提高，AA指標(biāo)與RA指標(biāo)計(jì)算結(jié)果非常接近，原始方法略好于基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的方法。同時(shí)，基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的精確度值與AA指標(biāo)、RA指標(biāo)較為接近，而原始方法的精確度與AA指標(biāo)、RA指標(biāo)相差較遠(yuǎn)。在基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的方法中，RA指標(biāo)精確度最高。

表4 USAir網(wǎng)絡(luò)中的AUC計(jì)算結(jié)果

表5 FWFB網(wǎng)絡(luò)中的AUC計(jì)算結(jié)果

在美國(guó)航空網(wǎng)絡(luò)數(shù)據(jù)集中的計(jì)算結(jié)果如表4所示?；趶?fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的鏈路預(yù)測(cè)方法中，Salton指標(biāo)、S?renson指標(biāo)、HPI指標(biāo)、HDI指標(biāo)、LHN-I指標(biāo)比原始方法的精確度有大幅度的提高，特別是LHN-I指標(biāo)的精確度從0.764 5提高至0.943 7，AA指標(biāo)與RA指標(biāo)計(jì)算結(jié)果較為接近，原始方法好于基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的方法。在基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的方法中，RA指標(biāo)精確度最高。

在佛羅里達(dá)海灣雨季的食物鏈網(wǎng)絡(luò)數(shù)據(jù)集中的計(jì)算結(jié)果表5所示，基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的鏈路預(yù)測(cè)方法全部高于原始方法，同時(shí)基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的HDI指標(biāo)計(jì)算數(shù)值最高，較其他計(jì)算指標(biāo)有大幅度的提高。

6 結(jié)束語(yǔ)

鏈路預(yù)測(cè)是復(fù)雜網(wǎng)絡(luò)研究的一個(gè)重要部分，具有廣泛的理論研究和實(shí)際應(yīng)用價(jià)值。本文在現(xiàn)有鏈路預(yù)測(cè)方法的基礎(chǔ)上，通過(guò)引入復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型，提出了基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的鏈路預(yù)測(cè)方法。通過(guò)實(shí)驗(yàn)部分可以看出，本文所提出的基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的鏈路預(yù)測(cè)方法具有有效性，在選擇的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)中，大多數(shù)鏈路預(yù)測(cè)指標(biāo)較原始方法有所提升，部分指標(biāo)甚至有較大幅度的提升。本文的研究結(jié)果說(shuō)明，傳統(tǒng)的基于拓?fù)浣Y(jié)構(gòu)的研究方法結(jié)合復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型，能夠更全面地反映出網(wǎng)絡(luò)節(jié)點(diǎn)與拓?fù)浣Y(jié)構(gòu)的本質(zhì)規(guī)律和關(guān)系。然而，由復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的定義可以看出，基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)的鏈路預(yù)測(cè)方法運(yùn)算復(fù)雜度極高，在大規(guī)模網(wǎng)絡(luò)中使用時(shí)的計(jì)算量非常巨大，不具有實(shí)用性。因此，在下一步的研究中，將著重關(guān)注其簡(jiǎn)化方法的研究。同時(shí)，本文只考慮了無(wú)權(quán)無(wú)向網(wǎng)絡(luò)的鏈路預(yù)測(cè)，對(duì)于加權(quán)網(wǎng)絡(luò)和有向網(wǎng)絡(luò)并未涉及，在相關(guān)研究中關(guān)注到，復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型能夠很好地刻畫(huà)加權(quán)網(wǎng)絡(luò)和有向網(wǎng)絡(luò)的結(jié)構(gòu)特征和動(dòng)態(tài)屬性，考慮復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型在加權(quán)網(wǎng)絡(luò)和有向網(wǎng)絡(luò)的鏈路預(yù)測(cè)中的研究也是下一步的重要方向。

[1] LYU L, ZHOU T. Link prediction in complex networks: a survey[J]. Physica A: Statistical Mechanics and its Applications, 2011, 390 (6): 1150-1170.

[2] CANNISTRACI C V, ALANISLOBATO G, RAVASI T. From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J]. Scientific Reports, 2015, 3 (4): 1613.

[3] KOSSINETS G. Effects of missing data in social network[J]. Social Networks, 2006, 28 (3): 247-268.

[4] 劉樹(shù)新, 季新生, 劉彩霞, 等. 一種信息傳播促進(jìn)網(wǎng)絡(luò)增長(zhǎng)的網(wǎng)絡(luò)演化模型[J]. 物理學(xué)報(bào), 2014, 63 (15): 158902-158902.

LIU S X, JI X S, LIU C X, et al. A complex network evolution model for network growth promoted by information transmission [J]. Acta Phys. Sin, 2014, 63 (15): 158902.

[5] 劉樹(shù)新, 季新生, 劉彩霞, 等. 局部拓?fù)湫畔Ⅰ詈洗龠M(jìn)網(wǎng)絡(luò)演化[J]. 電子與信息學(xué)報(bào), 2016, 38 (9): 2180-2187.

LIU S X, JI X S, LIU C X, et al. Information coupling of local topology promoting the network evolution [J]. Journal of Electronics & Information Technology, 2016, 38 (9): 2180-2187.

[6] MITZENMACHER M. A brief history of generative models for power law and lognormal distributions[J]. Internet Mathematics, 2004, 1 (2): 226-251.

[7] KATZ L. A new status index derived from sociometric index[J]. Psychometrika, 1953, 18 (1): 39-43.

[8] CLAUSET A, MOORE C, NEWMAN M E. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008, 453(7191): 98.

[9] LIU S, JI X, LIU C, et al. Extended resource allocation index for link prediction of complex network[J]. Physica A Statistical Mechanics & Its Applications, 2017, 479: 174-183.

[10] YU H T, WANG S H, MA Q Q. Link prediction algorithm based on the Choquet fuzzy integral[J]. Intelligent Data Analysis, 2016, 20(4): 809-824.

[11] SAMANTA S, Pal M. Link prediction in social networks[J]. Springer Briefs in Computer Science, 2018: 246-250.

[12] LU Y, GUO Y, KORHONEN A. Link prediction in drug-target interactions network using similarity indices[J]. Bmc Bioinformatics, 2017, 18(1): 39.

[13] LIU S, JI X, LIU C, et al. Similarity indices based on link weight assignment for link prediction of unweighted complex networks[J]. International Journal of Modern Physics B, 2017, 31 (2): 412-1054.

[14] 任曉龍, 呂琳媛. 網(wǎng)絡(luò)重要節(jié)點(diǎn)排序方法綜述[J]. 科學(xué)通報(bào), 2014, 59(13): 1175-1197.

REN X L, LYU L Y. Review of ranking nodes in complex networks[J]. Chinese Science Bulletin, 2014, 59(13): 1175-1197.

[15] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social Networks, 2003, 25 (3): 211-230.

[16] RAVASZ E, SOMERA A L, MONGRU D A, et al. Hierarchical organization of modularity in metabolic networks[J]. Science, 2002, 297(5586): 1551-1555.

[17] LIU Y Y, SLOTINE J J, BARABASI A L. Controllability of complex networks[J]. Nature, 2011, 473(7346): 167-173.

[18] JIA T, BARABáSI A L. Control capacity and a random sampling method in exploring controllability of complex networks[J]. Scientific Reports, 2013, 3: 2354.

[19] 孔江濤, 黃健, 龔建興, 等. 基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的無(wú)向加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估[J]. 物理學(xué)報(bào), 2018, 67 (9): 255-271.

KONG J T, HUANG J, GONG J X, et al. Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models[J]. Acta Phys Sin, 2018, 67(9): 255-271.

[20] SALTON G, MCGILL M J. Introduction to modern information retrieval[M]. Auckland: McGraw-Hill, 1983.

[21] ZHOU T, LYU L, ZHANG Y C. Predicting missing links via local information[J]. European Physical Journal B, 2009, 71(4): 623-630.

[22] LEICHT E A, HOLME P, NEWMAN M E. Vertex similarity in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2006, 73(2): 026120.

[23] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social Networks. 2003, 25(3): 211-230.

[24] PAN L, ZHOU T, LYU L, et al. Predicting missing links and identifying spurious links via likelihood analysis[J]. Scientific Reports, 2016, 6: 22955.

[25] GLEISER P M, DANON L. Community structure in Jazz[J]. Advances in complex systems, 2003, 6(4): 565-573.

[26] WATTS D J, STROGATZ S H. Collective dynamics of 'small-world' networks[J]. Nature, 1998, 393(6684): 440-442.

[27] BATAGELJ V, MRVAR A. Pajek-program for large network analysis[J]. Connections, 1998, 21(2): 47-57.

[28] ULANOWICZ R E, HEYMANS J J, EGNOTOVICH M S. Network analysis of trophic dynamics in south florida ecosystems, FY 99: the graminoid ecosystem[R]. 2000.

Link prediction method based on complex network dynamics model

PAN Yonghao, YU Hongtao, WU Yiteng

National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China

Link prediction is an important part of the study of missing links and future formations in complex networks. Currently, network structure-based link prediction methods are rich in results. Research on link prediction based on complex network dynamics model is rare. Firstly, a complex network dynamics model for unlicensed and undirected networks was constructed. Then the quantitative evaluation index of the link prediction node centrality based on the complex network dynamics model was given. Finally, the link prediction method defined by the complex network dynamics model was proposed by the given node centrality quantitative index. Experiments on real network datasets show that the proposed link prediction method has obvious prediction accuracy improvement.

complex network, link prediction, network dynamics

The National Natural Science Foundation of China(No.61803384)

TP393

A

10.11959/j.issn.2096?109x.2019065

潘永昊（1992? ），男，甘肅金昌人，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心碩士生，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、鏈路預(yù)測(cè)。

于洪濤（1970? ），男，遼寧丹東人，博士，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心研究員，主要研究方向?yàn)榫W(wǎng)絡(luò)大數(shù)據(jù)分析與處理。

吳翼騰（1992? ），男，山東樂(lè)陵人，國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心博士生，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)、對(duì)抗樣本等。

論文引用格式：潘永昊, 于洪濤, 吳翼騰. 基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的鏈路預(yù)測(cè)方法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2019, 5(6): 67-74.

PAN Y H, YU H T, WU Y T. Link prediction method based on complex network dynamics model[J]. Chinese Journal of Network and Information Security, 2019, 5(6): 67-74.

2019?01?10；

2019?03?20

潘永昊，panyounghao2016@163.com

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61803384）