基于復雜網絡動力學模型的鏈路預測方法

潘永昊，于洪濤，吳翼騰

基于復雜網絡動力學模型的鏈路預測方法

潘永昊，于洪濤，吳翼騰

（國家數字交換系統工程技術研究中心，河南 鄭州 450002）

鏈路預測是復雜網絡中研究缺失連邊和未來形成連邊的重要組成部分，當前基于網絡結構的鏈路預測方法成果豐富，而基于復雜網絡動力學模型的鏈路預測研究較少。針對無權無向網絡，首先構建了復雜網絡動力學模型，然后給出了基于復雜網絡動力學模型的鏈路預測節點中心性的量化評價指標，最后通過給出的節點中心性量化指標，提出了由復雜網絡動力學模型定義的鏈路預測方法。通過在真實網絡數據集上進行的實驗表明，提出的鏈路預測方法較基準方法有明顯的預測精度的提升。

復雜網絡；鏈路預測；網絡動力學

1 引言

鏈路預測（link prediction）[1]是復雜網絡研究中的一個重要內容，主要研究網絡中缺失信息的補全和網絡結構的演化，具體為對網絡中缺失連接、未來形成連接的預測。鏈路預測研究在很多領域得到了廣泛的應用，如生物蛋白質結構構建[2]、社會網絡結構分析[3]、網絡演化機制[4-5]等。

現有的鏈路預測方法主要基于網絡拓撲結構，如基于共同鄰居[6]相似性的方法、基于路徑[7]相似性的方法、層次結構模型[8]和隨機分塊模型[1]等。近年來，新出現的研究大多是基于網絡拓撲結構的方法[9-13]。在基于網絡拓撲結構的研究中，一個重要的依據是基于度中心性節點重要性評價，即對于網絡中的節點，度越大，其在網絡中的重要性和影響力越大。目前，大量的鏈路預測方法中使用了基于度中心性的節點重要性評價[14]，如在基于共同鄰居相似性的鏈路預測中，Adamic-Adar指標[15]、大度節點不利指標[16]（HDI，hub depressed index）等相似性指標認為，度小的共同鄰居節點的貢獻大于度大的共同鄰居節點。基于度中心性的節點重要性評價方法在鏈路預測的應用中具有方便直觀、運算復雜度低的特點，并且具有很好的預測精度。然而，基于度中心性的節點重要性評價方法以節點的局部特征為計算標準，僅能表示出該節點的局部連邊關系，不能充分反映該節點的重要性和影響力。而在實際的鏈路預測中，不同的網絡在結構特征上各有差別，預測精度的高低與鏈路預測方法中的結構特征有直接的關系。現有的研究成果大多使用節點度作為節點重要性的評價方法，因此，考慮采用另外一種角度對節點度進行調整，研究鏈路預測問題。

相關研究表明，在考慮網絡拓撲結構的同時，對節點的動力學行為進行建模，所得到的復雜網絡動力學模型能夠更加深刻地揭示網絡結構與節點之間的本質關系和規律。Liu等[17]的研究中發現網絡中節點動力學模型相同的復雜網絡動力學系統中，驅動節點傾向于避免大度節點，這與文獻[15]中認為的共同鄰居節點中小度節點的貢獻大于大度節點異曲同工，但卻更深刻地反映出網絡中的動力學規律。Jia等[18]的研究表明，網絡中節點是否為驅動節點，與節點的入度有關，與出度無關。在孔江濤等[19]的研究中提出了基于復雜網絡動力學模型的節點重要性評價方法，通過對節點引入一個驅動因素，計算網絡再次達到穩定狀態以后所有節點的偏移量，偏移量大的即為重要節點。可以看出，基于網絡動力學模型的研究，包含了網絡拓撲結構、節點動力學建模，能夠具體描述分析時域上網絡狀態的變化，得到的結果優于只基于網絡拓撲結構的研究。

針對以上分析，本文考慮使用復雜網絡動力學模型的研究方法，對無權無向網絡進行節點動力學建模，引入文獻[19]中的擾動測試方法對節點重要性進行量化評價，對現有的基于度中心性的鏈路預測方法進行改進，提出基于復雜網絡動力學模型的鏈路預測方法。最后通過在真實網絡數據集上的實驗，證明本文提出的方法能夠有效提高鏈路預測的精度。文章創新點如下：1) 考慮使用復雜網絡動力學模型對靜態無權無向網絡模型進行擴展，對網絡節點進行動力學建模，在復雜網絡動力學模型上研究鏈路預測問題；2) 提出了基于復雜網絡動力學模型的鏈路預測方法，并在真實網絡數據集上驗證其有效性。

2 相關工作

鏈路預測問題自提出以來，經過多年的研究，已經形成了豐富的研究成果，本節給出幾種典型的基于度中心性的鏈路預測相似性指標的定義。

S?renson指標[1]由S?renson提出，基于節點的共同鄰居集合定義，常用于研究生態學數據，定義式如下。

大度節點有利指標（HPI，hub promoted index）[16]被用于刻畫新陳代謝網絡中反應物的相似程度，認為度大的節點在網絡中與其他節點具有更大的相似性，定義式如下。

大度節點不利指標（HDI，hub depressed index）[21]認為度小的節點在網絡中與其他節點具有更大的相似性，定義式如下。

Adamic-Adar指標[23]認為網絡中度小的共同鄰居節點的貢獻大于度大的共同鄰居節點，定義式如下。

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

3 問題描述

鏈路預測相似性計算指標的定義包含對節點在網絡中重要性的評價。一種能夠充分契合實際網絡中節點重要性的評價方法，使相似性指標更加契合當前網絡的真實情況，得到更好的預測精確度。

4 主要內容

復雜網絡動力學模型同時考慮網絡拓撲結構和節點動態屬性，能夠反映出網絡的本質特征。本節首先定義復雜網絡動力學模型，然后給出復雜網絡動力學模型的節點重要性評價方法[19]，最后定義改進的鏈路預測相似性指標。

4.1 復雜網絡動力學模型定義

4.2 節點重要性評價指標

式(10)和式(11)定義了復雜網絡動力學模型，下面給出基于擾動測試[19]的節點重要性評價指標。

考慮當單個節點發生變化時，對整個網絡平衡狀態的影響，通過計算影響程度，得到節點的重要性量化評價指標，基于網絡動力學模型定義的節點重要性指標[19]，能夠很好地反映出節點在網絡中的重要程度和影響力。

設動態系統的狀態方程為

設無權無向網絡的動力學模型的狀態方程為

擾動模型定義如下。

使用基于偏離均值的方差定義節點的重要性指標，其數值越大，節點在網絡中的重要性和影響力越大，反之則小。

4.3 鏈路預測模型

基于復雜網絡動力學模型的Salton指標為

基于復雜網絡動力學模型的S?renson指標為

大度節點有利指標是針對節點的度設計計算的，為了便于理解，把基于偏離均值的方差重新定義指標記為基于復雜網絡動力學模型的大度節點有利指標。

同樣，對于大度節點不利指標，把基于偏離均值的方差重新定義指標記為基于復雜網絡動力學模型的大度節點不利指標。

基于復雜網絡動力學模型的LHN-I指標為

基于復雜網絡動力學模型的Adamic-Adar指標為

基于復雜網絡動力學模型的資源分配指標為

以上給出的指標是在原始指標的基礎上對節點度進行了修改，出發點是考慮節點的度在各個原始指標中的意義，實際上，網絡本身就是表示當前節點在網絡中的重要性和影響力。需要說明的是，對于一些改進后的指標，如余弦相似性、大度節點有利、大度節點不利等，其定義與原始指標的定義初衷發生了一些變化，但修改部分所表達的意義是相同的。

5 實驗分析

5.1 實驗數據集

為了驗證上文中給出的鏈路預測算法的有效性，本文在4個真實網絡數據集上進行鏈路預測對比實驗，分別為：

1) 爵士音樂家合作網（Jazz）[25]，網絡中的節點為爵士音樂家，連邊表示音樂家的合作關系；

2) 線蟲的神經網絡（CE）[26]，節點表示線蟲的神經元，邊表示神經元突觸；

3) 美國航空網絡（USAir）[27]，網絡中的每個節點對應一個機場，連邊表示兩個機場之間有直飛的航線；

4) 佛羅里達海灣雨季的食物鏈網絡 (FWFB)[28]，網絡中的每個節點表示一種生物，邊表示生物之間捕食關系。

以上4個網絡的基本結構參數如表1所示。

表1 靜態網絡數據集拓撲特征參數

其中，||表示網絡中節點的個數，||表示邊的數量，<>表示網絡的平均度，<>表示網絡平均距離，表示網絡簇系數，表示結合系數。

5.2 度量指標

5.3 實驗對比分析

表2 Jazz網絡中的AUC計算結果

表3 CE網絡中的AUC計算結果

在爵士音樂家合作網數據集中的計算結果如表2所示。從計算結果可以看出，在該網絡數據集中，基于復雜網絡動力學模型的鏈路預測方法整體表現不如原始方法，只有基于復雜網絡動力學模型的AA指標略高于原始AA指標。在基于復雜網絡動力學模型的方法中，AA指標精確度最高。

在線蟲的神經網絡數據集中的計算結果如表3所示。基于復雜網絡動力學模型的鏈路預測方法中，Salton指標、S?renson指標、HPI指標、HDI指標、LHN-I指標相比原始方法的精確度有大幅度的提高，AA指標與RA指標計算結果非常接近，原始方法略好于基于復雜網絡動力學模型的方法。同時，基于復雜網絡動力學模型的精確度值與AA指標、RA指標較為接近，而原始方法的精確度與AA指標、RA指標相差較遠。在基于復雜網絡動力學模型的方法中，RA指標精確度最高。

表4 USAir網絡中的AUC計算結果

表5 FWFB網絡中的AUC計算結果

在美國航空網絡數據集中的計算結果如表4所示。基于復雜網絡動力學模型的鏈路預測方法中，Salton指標、S?renson指標、HPI指標、HDI指標、LHN-I指標比原始方法的精確度有大幅度的提高，特別是LHN-I指標的精確度從0.764 5提高至0.943 7，AA指標與RA指標計算結果較為接近，原始方法好于基于復雜網絡動力學模型的方法。在基于復雜網絡動力學模型的方法中，RA指標精確度最高。

在佛羅里達海灣雨季的食物鏈網絡數據集中的計算結果表5所示，基于復雜網絡動力學模型的鏈路預測方法全部高于原始方法，同時基于復雜網絡動力學模型的HDI指標計算數值最高，較其他計算指標有大幅度的提高。

6 結束語

鏈路預測是復雜網絡研究的一個重要部分，具有廣泛的理論研究和實際應用價值。本文在現有鏈路預測方法的基礎上，通過引入復雜網絡動力學模型，提出了基于復雜網絡動力學模型的鏈路預測方法。通過實驗部分可以看出，本文所提出的基于復雜網絡動力學模型的鏈路預測方法具有有效性，在選擇的真實網絡數據集的實驗中，大多數鏈路預測指標較原始方法有所提升，部分指標甚至有較大幅度的提升。本文的研究結果說明，傳統的基于拓撲結構的研究方法結合復雜網絡動力學模型，能夠更全面地反映出網絡節點與拓撲結構的本質規律和關系。然而，由復雜網絡動力學模型的定義可以看出，基于復雜網絡動力學的鏈路預測方法運算復雜度極高，在大規模網絡中使用時的計算量非常巨大，不具有實用性。因此，在下一步的研究中，將著重關注其簡化方法的研究。同時，本文只考慮了無權無向網絡的鏈路預測，對于加權網絡和有向網絡并未涉及，在相關研究中關注到，復雜網絡動力學模型能夠很好地刻畫加權網絡和有向網絡的結構特征和動態屬性，考慮復雜網絡動力學模型在加權網絡和有向網絡的鏈路預測中的研究也是下一步的重要方向。

[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] 劉樹新, 季新生, 劉彩霞, 等. 一種信息傳播促進網絡增長的網絡演化模型[J]. 物理學報, 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] 劉樹新, 季新生, 劉彩霞, 等. 局部拓撲信息耦合促進網絡演化[J]. 電子與信息學報, 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] 任曉龍, 呂琳媛. 網絡重要節點排序方法綜述[J]. 科學通報, 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] 孔江濤, 黃健, 龔建興, 等. 基于復雜網絡動力學模型的無向加權網絡節點重要性評估[J]. 物理學報, 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? ），男，甘肅金昌人，國家數字交換系統工程技術研究中心碩士生，主要研究方向為復雜網絡、鏈路預測。

于洪濤（1970? ），男，遼寧丹東人，博士，國家數字交換系統工程技術研究中心研究員，主要研究方向為網絡大數據分析與處理。

吳翼騰（1992? ），男，山東樂陵人，國家數字交換系統工程技術研究中心博士生，主要研究方向為復雜網絡鏈路預測、對抗樣本等。

論文引用格式：潘永昊, 于洪濤, 吳翼騰. 基于復雜網絡動力學模型的鏈路預測方法[J]. 網絡與信息安全學報, 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

國家自然科學基金資助項目（No.61803384）