基于PSO優化算法的鏈路預測AA指標適用網絡問題研究

孟曉宇 路蘭

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

【關鍵詞】復雜網絡;鏈路預測;相似性算法;粒子群優化算法

中圖分類號： 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 引言

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

鏈路預測技術用來預測復雜系統主體間的關系。它既包含了對未知鏈接的預測，也包含對未來鏈接的預測。鏈路預測問題中刻畫網絡中節點的相似性是一個重大的理論問題。相似性指標眾多，選擇合適的指標是一份重要的工作[3]。

在小世界網絡中使用最廣泛的相似性指標為AA指標。本文在模擬小世界網絡的基礎上引入粒子群優化算法，評估網絡參數的影響。

1 鏈路預測相似性算法

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

1.1 相似性指標

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

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

1.2 精確度測量

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

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

2 算法描述

為獲得小世界網絡生成參數的影響，本文通過粒子群優化算法訓練模型，探究模型生成參數對鏈路預測相似性指標的影響。

本小節基于粒子群優化算法（PSO）[5]，調節參數大小評估AA指標的AUC。

首先確定粒子個數，其維度即為需要優化的網絡生成參數的個數

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

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

Step2：讀取生成的模擬網絡，按照適應度的計算公式，計算每個粒子的適應度。

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

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

Step5：若達到結束條件，輸出最優粒子的位置即最優的網絡結構參數;若未達到結束條件，則返回Step2。算法的結束條件是達到預設的迭代次數。

3 實驗結果與分析

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

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

4 結束語

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

【參考文獻】

[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]呂琳媛.復雜網絡鏈路預測[J].電子科技大學學報，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].計算機工程與應用，2010，46（25）：1-4+74.