孟曉宇 路蘭

【摘 要】鏈路預(yù)測相似性指標是一類根據(jù)復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)計算節(jié)點相似性從而預(yù)測節(jié)點間關(guān)系的算法。鑒于目前的鏈路預(yù)測相似性算法適用的網(wǎng)絡(luò)參數(shù)無跡可尋。本文選取測評小世界網(wǎng)絡(luò)最優(yōu)的AA指標，運用粒子群優(yōu)化算法探究其網(wǎng)絡(luò)最佳適用參數(shù)。結(jié)果表明網(wǎng)絡(luò)密度較小的小世界網(wǎng)絡(luò)采用AA指標測評時精確度較好。

【關(guān)鍵詞】復(fù)雜網(wǎng)絡(luò);鏈路預(yù)測;相似性算法;粒子群優(yōu)化算法

中圖分類號： O157.5 文獻標識碼： A 文章編號： 2095-2457（2019）02-0117-002

【Abstract】Link prediction similarity index is a kind of algorithm which calculates node similarity according to complex network structure and predicts the relationship between nodes.In view of the fact that the network parameters applicable to the current link prediction similarity algorithm are traceless.In this paper，we select the best AA indices for evaluating scale-free networks，small-world networks，and use particle swarm optimization to explore the optimal parameters for their networks.The results show that AA index is used for small-world networks with low network density.

【Key words】Complex network; Link prediction; Similarity Algorithms; Particle Swarm Optimization

0 引言

復(fù)雜網(wǎng)絡(luò)由許多節(jié)點及節(jié)點之間相連接的邊構(gòu)成，用來刻畫自然和社會中大量的復(fù)雜系統(tǒng)。隨著社會不斷發(fā)展，越來越多的學(xué)者開始通過研究復(fù)雜網(wǎng)絡(luò)來尋找現(xiàn)實生活中復(fù)雜系統(tǒng)的內(nèi)在規(guī)律。研究表明，社會網(wǎng)絡(luò)中應(yīng)用最廣泛的兩種網(wǎng)絡(luò)結(jié)構(gòu)是無標度網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)。例如，神經(jīng)系統(tǒng)可以看成是大量神經(jīng)細胞通過神經(jīng)纖維相互連接形成的網(wǎng)絡(luò)[2]，計算機網(wǎng)絡(luò)可以看作是自主工作的計算機通過通信介質(zhì)相互連接形成的網(wǎng)絡(luò)，此外還有電力網(wǎng)絡(luò)[2]、社會關(guān)系網(wǎng)絡(luò)[2-4]、生態(tài)網(wǎng)絡(luò)等。

鏈路預(yù)測技術(shù)用來預(yù)測復(fù)雜系統(tǒng)主體間的關(guān)系。它既包含了對未知鏈接的預(yù)測，也包含對未來鏈接的預(yù)測。鏈路預(yù)測問題中刻畫網(wǎng)絡(luò)中節(jié)點的相似性是一個重大的理論問題。相似性指標眾多，選擇合適的指標是一份重要的工作[3]。

在小世界網(wǎng)絡(luò)中使用最廣泛的相似性指標為AA指標。本文在模擬小世界網(wǎng)絡(luò)的基礎(chǔ)上引入粒子群優(yōu)化算法，評估網(wǎng)絡(luò)參數(shù)的影響。

1 鏈路預(yù)測相似性算法

本文研究網(wǎng)絡(luò)為無向圖，記為G=（V，E），其中V為網(wǎng)絡(luò)中全部節(jié)點，E為為網(wǎng)絡(luò)節(jié)點中全部已存在連邊;節(jié)點u，v∈V，若（u，v）∈E，表示節(jié)點對u，v之間的連邊已知，反之，則未知。鏈路預(yù)測相似性算法就是通過節(jié)點對間的已知連邊找到最優(yōu)的相似性指標，確定網(wǎng)絡(luò)生成規(guī)則，從而計算節(jié)點對相似性，預(yù)測存在連邊的可能性。

1.1 相似性指標

運用相似性指標進行鏈路預(yù)測的測量原理是通過不同相似性指標測量兩節(jié)點間的相似性。將所有節(jié)點對之間的相似性分數(shù)計算完畢后，相似性大的節(jié)點對存在連邊的可能性大。

Adamic-Adar（AA）指標考慮了兩節(jié)點共同鄰居的度信息，它通常適用于小世界網(wǎng)絡(luò)。其基本原理是節(jié)點對的共同鄰居中度小的節(jié)點比度大的節(jié)點對節(jié)點對的相似性貢獻程度大。

1.2 精確度測量

本文選擇的測評鏈路預(yù)測精確度的方法是AUC[1]（Area Under Curve，AUC）。AUC適用于從整體上衡量算法的精確度，是鏈路預(yù)測中對結(jié)果進行精度評價的最普遍的量化方法。

AUC理解為在測試集中連邊的分數(shù)值比隨機選擇的一個不存在的邊的分數(shù)值高的概率。AUC定義為：

2 算法描述

為獲得小世界網(wǎng)絡(luò)生成參數(shù)的影響，本文通過粒子群優(yōu)化算法訓(xùn)練模型，探究模型生成參數(shù)對鏈路預(yù)測相似性指標的影響。

本小節(jié)基于粒子群優(yōu)化算法（PSO）[5]，調(diào)節(jié)參數(shù)大小評估AA指標的AUC。

首先確定粒子個數(shù)，其維度即為需要優(yōu)化的網(wǎng)絡(luò)生成參數(shù)的個數(shù)

本文中設(shè)置PSO算法的適應(yīng)度函數(shù)為（1）式，粒子數(shù)為20，最大迭代次數(shù)為50次，c1=c2=2，r1=0.6，r2=0.3，w=0.8。PSO算法流程如下：

Step1：設(shè)定網(wǎng)絡(luò)生成參數(shù)的取值范圍（11≤ci1≤199，0≤ci2≤1），根據(jù)取值范圍隨機初始化粒子的速度和位置，根據(jù)位置向量生成模擬網(wǎng)絡(luò)。

Step2：讀取生成的模擬網(wǎng)絡(luò)，按照適應(yīng)度的計算公式，計算每個粒子的適應(yīng)度。

Step3：尋找全局極值和全局極值位置。

Step4：按粒子群算法的位置公式和速度公式更新粒子的位置及速度。

Step5：若達到結(jié)束條件，輸出最優(yōu)粒子的位置即最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)參數(shù);若未達到結(jié)束條件，則返回Step2。算法的結(jié)束條件是達到預(yù)設(shè)的迭代次數(shù)。

3 實驗結(jié)果與分析

本節(jié)采用Python中networkx包中的watts_strogatz_graph（n，k，p）函數(shù)模擬WS小世界網(wǎng)絡(luò)。其中n取1000代表模擬網(wǎng)絡(luò)中包含1000個節(jié)點，k，p取值為粒子群優(yōu)化算法（PSO）中的粒子位置坐標X，分別代表節(jié)點鄰居數(shù)和重連概率。根據(jù)k，p取值大小不同，網(wǎng)絡(luò)模型衍化情況如下圖所示：

由粒子群優(yōu)化算法（PSO）優(yōu)化結(jié)果可知：基于WS小世界網(wǎng)絡(luò)的AA相似性指標的全局最優(yōu)AUC數(shù)值為：0.95，粒子最優(yōu)位置向量為（40，0.05）。結(jié)果表明，隨著重連概率值越小，AA指標描述WS小世界網(wǎng)絡(luò)的效果越好，而鄰居數(shù)無明顯規(guī)律，但AA指標在鄰居數(shù)少時取得較大AUC的概率比較大。由此可以得出結(jié)論：AA指標適用于測量網(wǎng)絡(luò)密度較小的WS小世界網(wǎng)絡(luò)（接近于規(guī)則網(wǎng)絡(luò)）。

4 結(jié)束語

本文提出了一種在WS小世界網(wǎng)絡(luò)中基于粒子群優(yōu)化算法的鏈路預(yù)測相似性指標適用的網(wǎng)絡(luò)最優(yōu)參數(shù)問題。實驗結(jié)果表明，AA指標適用于測量網(wǎng)絡(luò)密度較小的小世界網(wǎng)絡(luò)。但是，本文僅僅運用python模擬的復(fù)雜網(wǎng)絡(luò)進行實驗，現(xiàn)實中的復(fù)雜網(wǎng)絡(luò)可能結(jié)合了無標度網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)的部分特性，因此需要綜合考慮各相關(guān)相似性指標對其進行混合應(yīng)用。

【參考文獻】

[1]BARABASI? A-L，ALBERT? R.Emergence of scaling in random networks[J].Science，l999， 286（5439）：509-512.

[2]WATTS DJ， STROGATZ SH. Collective dynamic of small-world network[J].Nature（London）， 1998， 393：440-442.

[3]呂琳媛.復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測[J].電子科技大學(xué)學(xué)報，2010，39（05）：651-661.

[4]L ILJEROS F，et al.The Web of Human Sexual Contacts[J].Nature，2001，411： 907-908.

[5]余建平，周新民，陳明.群體智能典型算法研究綜述[J].計算機工程與應(yīng)用，2010，46（25）：1-4+74.