基于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.