基于学习自动机与萤火虫算法的链路预测

舒 坚，李睿瑞，熊 涛，刘琳岚，孙利民

(1.南昌航空大学软件学院，江西南昌330063；2.南昌航空大学信息工程学院，江西南昌330063)

便携交换网络（pocket switched network,PSN）是一类特殊的机会网络，内部节点由携带便携式手持设备的人员组成[1]，不需要源节点和目标节点之间存在完整链路，利用节点移动带来相遇机会实现数据交换，以“存储—携带—转发”形式进行通信[2]。目前针对PSN网络的研究面临以下挑战：网络行为预测、消息转发[3]、命名的动态性等[4]。

研究PSN网络行为预测中的链路预测问题，为PSN的网络演化机制研究及路由、拓扑控制和移动管理等上层协议提供支撑，推动PSN在商品推荐[5]、灾难救援、公共安全领域的事件检测、军事领域等方面的应用[6]。近年来，随着对机会网络研究的深入，研究者提出了多种链路预测方法，但针对PSN网络的链路预测研究较少。与本研究相关的链路预测方法是基于相似性指标的预测方法和基于机器学习的预测方法。

基于相似性指标的预测方法利用网络信息计算节点间的相似性，连接概率与相似性呈正相关。共同邻居[7]（common neighbor,CN）指标认为节点的共同邻居越多，相近程度越高，吕琳媛等[8]对CN的改进指标AA（adamic-adar）指标、Sorenson指标、RA（resourceallocation index）指标等进行了阐述；Huang等[9]考虑了共同邻居节点间依赖关系的不同，采用贝叶斯分类器计算节点的相似性；Sun[10]引入社区结构的思想，提出局部亲和结构（local affinity structure,LAS）指标以衡量节点间的“紧密度”；Yang等[11]综合考虑节点间最短路径和局部社区内的边聚类系数对节点间产生连接的影响，提出LCAR指标计算节点间的相似性。

基于机器学习的预测方法通过特征提取的方式进行链路预测。Li等[12]结合CN、LHN-II、COS+和MFI，提出基于集合模型的链路预测方法（ensemble-modelbased link prediction,EMLP）；Chiu等[13]通过建立深层神经网络，以传统相似性度量组成的相似性指标向量作为样本，使用弱评估器评估动态系统中的变化概率；Hao[14]提出将融合的网络特征作为深度置信网络（deep belief network,DBN）的输入，以未来的连接状态作为标签，构建预测模型；Li[15]提出利用受限玻尔兹曼机（restricted Boltzman machine,RBM）处理节点对历史连接信息，将得到的信息作为梯度提升决策树（gradient boosting decision tree,GBDT）的输入，预测节点对未来时刻的连接状态；Butun[16]提出根据网络的三元关系构建三元接近度指标，针对有向动态网络，使用三元组接近度作为训练样本，训练基于模式的有监机器学习模型完成链路预测任务。

学习自动机凭借其不受样本的非均衡性影响，具有良好的噪声鲁棒性，非常适合处理在概率空间寻找全局最优解的问题，经历几十年的发展，其收敛速度有很大的提高，成为解决各种现实问题的重要工具之一[17]。PSN网络具有节点移动性、节点间间歇性连接、高延迟等特点，其链路预测面临的挑战是节点相遇的机会性和拓扑的时变性，因此PSN网络中获得高质量链路预测的关键是如何较全面地获取节点的属性。作者采用学习自动机（learning automata,LA）对节点的属性进行聚类，目的在于使得网络中的每个节点都找到所属社区，以更全面地获取节点的属性。

萤火虫算法（firefly algorithm,FA）[18]属于仿生群智能优化算法，是一种启发式的算法，可解决连续空间的寻优问题，广泛应用于特征值优化、工程结构设计、聚类、参数选择等。作者采用萤火虫算法对所构建二分类器[19]的参数进行优化。

综上所述，针对PSN网络的节点属性和节点移动特性，作者提出基于自动学习机和萤火虫算法的链路预测方法（link prediction approach for pocket switched network based on firefly algorithm,FA-LP）。使用分布式学习自动机处理节点的属性信息，完成节点的自适应聚类过程，实现PSN网络的社区划分；构建反映PSN网络社区属性、节点移动性和节点间间歇性连接的相似性指标（similarity index based on community and mobile behavior,SICM），并对传统相似性指标进行改进；构建链路预测的二分类器模型，借助萤火虫算法在连续空间中高效寻优的优点对其进行优化。

1 社区划分

PSN网络社区划分的目的在于将属性相似的节点尽可能划分在同一个社区内，社区划分的过程如下。

1.1 节点属性的获取

所谓物以类聚，人以群分，在网络中两个节点的属性越相似就越可能产生联系。人们更愿意和与自己年龄相仿、使用相同的语言、地理位置相近的人聊天。PSN网络由人组成，其节点的属性信息相对容易获取。刻画节点的社区属性，最直接的方法就是使用标签，可以根据年龄、职业、教育、兴趣、地理位置、性别、信仰等属性可以将节点划分为不同类型。作者采用MIT发布的真实数据集“the reality mining data”[20]，节点拥有许多属性信息如问卷调查结果、上下班时间、通话记录等。

1.2 自适应聚类

根据节点的属性向量完成PSN网络的自适应聚类。学习自动机包含了动作集合和概率集合，如式（1）、（2）所示：

式中， A为 学习自动机可执行动作的集合， Ai为执行将节点分配到第i 个社区的动作， P为学习自动机执行每个动作所对应概率的集合， PAi为执行动作 Ai的概率。

假设学习自动机的初始状态为：节点不属于任何社区，且分配到各个社区的概率都相等。自适应聚类过程如下：

1）学习自动机执行根据概率向量中最大值对应的动作，将节点划分到对应的社区。

2）当所有节点被分配到某个社区后，计算每个社区的社区中心。

3）计算节点到本次递归过程的社区中心的欧式距离 Dcurrent。

4）计算节点到上次递归过程的社区中心的欧式距离 DPrevious。

5）通过比较Dcurrent与 DPrevious的大小判断本次迭代过程的聚类效果，若 DPrevious大 于 Dcurrent，则说明本次迭代过程中的聚类效果好，节点根据与其他社区中心的欧式距离更新对应的概率向量，反之说明本次聚类效果不好，概率向量不变。当所有节点所属的社区编号都不发生变化，社区结构趋于稳定时，完成PSN网络的社区划分。

2 相似性指标的构建

定义社区属性影响系数，通过对真实数据集的实验分析，定义移动行为影响系数，构建反映PSN网络社区属性、节点移动性和节点间间歇性连接的相似性指标；将该指标与CN、RA、AA等7种相似性指标融合，得到PSN网络的相似性指标（similarity index of PSN,PSN_SI），从而构建得到PSN网络的相似性指标向量（similarity index vector,SIV）。

2.1 社区属性影响系数

在真实世界中，人们更容易与来自同一社区的成员见面。定义社区属性影响系数（community attributeinfluencecoefficient,CAIC），如式（3）所示：

2.2 移动行为影响系数

通过对Dartmouth数据集的分析，发现节点连接的访问接入点（access point,AP）数量越多，则连接的移动节点数量也越多[21]。节点连接的AP数量代表了节点活跃度，节点活跃度的不同直接影响了节点与其他节点产生连接的概率。

为了说明PSN网络中节点的活跃度与节点连接AP数量之间的关系，随机从MIT数据集的97个移动节点中抽取8个节点（95、97、88、93、69、20、27、26），统计8个节点连接的移动节点数量和连接的AP数量，统计结果如图1所示。

图1 移动节点数量和AP数量的分布Fig.1 Distribution of the number of mobilenodesand the number of AP

从图1可以看出，节点连接的AP数量越多，该节点连接的移动节点数量也越多，即节点连接的AP数量与节点连接的移动节点数量之间成正相关关系。

PSN网络中连接的产生并不是完全偶然的，节点更倾向靠近与自身拥有相似连接的节点。随机从MIT数据集抽取2个节点（21、52），统计与其他节点的连接次数以及节点对的共同邻居节点数，部分统计结果如图2、3所示。

图2 21号节点连接分布情况Fig.2 Distribution of node21 connections

图3 52号节点连接分布情况Fig.3 Distribution of node 52 connections

从图2、3中可以看出，随着节点对之间的共同节点数量增加，节点对之间的连接次数也增加。

通过分析节点的连接数与节点连接的AP数量、节点间连接的共同节点之间的关系，提出节点连接AP影响系数（node of access point coefficient, NAPC）与节点对共同连接节点影响系数（node pair common connect node coefficient,CCNC），如式（4）、（5）所示：

2.3 相似性指标向量

基于上述研究，构建反映PSN网络社区属性、节点移动性和节点间间歇性连接的相似性指标SICM，如式（6）所示：

3 链路预测模型

链路预测模型的构建过程如下。

3.1 时间序列分析

采用ARIMA对相似性指标向量序列进行时间序列分析，提取相似性指标向量随时间的变化的规律，具体步骤如下：

1）计算节点对在每个网络快照中的相似性指标向量，构成相似性指标向量序列VSIVS（similarity index vector sequence,SIVS），如式（8）所示：

2）采用单位根检验（augmented Dickey-Fuller test,ADF）方法对相似性指标向量序列进行平稳性检验。若不平稳，则进行差分运算将其转换为平稳序列。

3）根据自相关函数和偏自相关函数确定模型的滞后值 p 和滑动窗口q 的大小。

4）根据最小信息准则（Akaike information criterion,AIC）对ARIMA模型参数寻优，在保证模型拟合程度的前提下得到最优参数。

采用窗口滑动截取相似性指标向量序列输入ARIMA模型，根据式（9）预测节点对下一时刻的SIV向量，以对应连接状态为标签，组成样本，作为二分类器的输入。

3.2 二分类器的构建

通过将节点对的特征向量与超平面的权重向量进行点乘运算，判断其正负，完成节点对的链路预测。因此，二分类器的构建关键在于寻找最优超平面的权值向量。

3.3 二分类器的优化

3）更新种群位置。根据萤火虫算法的个体移动规则[19]，适应度低的权重参数向适应度高的权重参数移动，适应度最高的权重参数进行随机移动。

4）当满足停止条件或达到最大迭代次数时，返回适应度最高的权重向量，反之则返回步骤2）。

经过萤火虫算法的优化后，使用返回的最佳权重向量作为线性分类器的超平面，完成分类，预测节点对下一时刻的连接情况。

4 实验设计与分析

通过真实数据集下的实验验证相似性指标PSN_SI和FA-LP方法。

4.1 实验数据集

采用两种稀疏程度不一的PSN网络作为验证的数据集，数据集信息见表1。

表1 实验数据集Tab.1 Experimental dataset

INFOCOM2006数据集记录了2006年在巴西巴塞罗那为期4 d的会议期间，78位参加学术研讨会并携带iMote通信设备的用户与固定节点之间的连接记录；MIT数据集是麻省理工大学97名实验人员携带蓝牙设备通信情况，由于校园范围大、学生的作息习惯致使晚上记录极为稀疏。由于有的节点较早退出，有的节点较晚加入，为避免网络中节点的个数发生变化，在此截取所有节点都处于活跃期的30 d数据。

4.2 评价指标

使用受试者工作特征曲线下的面积（area under thecurve, AUC）和准确率Precision作为链路预测结果的评价指标。

AUC可以简单理解为从测试边集和不存在边集中各取一条边，比较两者相似性的高低，如果测试边相似性大于不存在边则加1分，相等则加0.5分。AUC定义如式（12）所示，用字母H统一表示评价指标相关变量。

4.3 SICM指标的验证

通过选取不同的切片时长，在INFOCOM2006和MIT数据集上验证SICM指标的有效性和稳定性。

INFOCOM2006数据集的时间切片长度分别为210、240、270、300、360、430 min，对应的切片数量分别为20、18、16、14、12、10；MIT数据集上的切片时长分别为0.5、1.0、1.5、2.0、3.0、6.0 d，对应的切片数量分别为60、30、20、15、10、5。

相似性指标PSN_SI的AUC值随切片数量变化的趋势如图4、5所示。

图4 INFOCOM2006数据集上的AUC值对比Fig.4 Comparison of AUC values on the INFOCOM2006 dataset

从图4可以看出，各个指标均随切片数目的减少而提高了预测效果，且提高的幅度基本一致，但W_HDI低于其他指标。

图5 MIT数据集上的AUC值对比Fig.5 Comparison of AUC values on the MIT dataset

从图5中可以看出，W_RA、W_AA比其他指标在AUC上的表现更好，但在切片数为15时却不如W_CN和W_Salton。通过实验可以得出，虽然PSN_SI中各个指标的表现有所区别，但总体而言都能较好的对PSN网络进行链路预测，预测的效果较平稳。

为了进一步说明相似性指标PSN_SI的有效性，使用Precision作为评价指标，在上述时间切片下使用相似性指标PSN_SI进行链路预测的实验，实验结果如图6、7所示。

图6 INFOCOM2006数据集上的Precision值对比Fig.6 Comparison of Precision values on the INFOCOM-2006 dataset

图7 MIT数据集上的Precision值对比Fig.7 Comparison of Precision valueson the MIT dataset

从实验结果来看，在不同的数据集与切片数量的情况下，PSN_SI都可以较好地获取链路变化的潜在特征，从而进行链路预测。由图6可知，在INFOCOM2006数据集下切片数量为10时，不同的PSN_SI均有较好的Precision表现，且W_CN指标表现最佳。由图7可知，所有的PSN_SI均存在波动的情况，Precision在0.561～0.881之间，W_CN比其他PSN_SI的预测效果更好。

在INFOCOM2006和MIT数据集中选取上述切片数进行改进前后指标的对比实验，得到的AUC和Precision结果如表2、3所示。

通过表2、3的实验结果可以看出：无论是在AUC还是在Precision上，改进后的指标在绝大多数情况下比改进前的指标效果好。在AUC方面，相似性指标PSN_SI相比于常见的相似性指标的预测准确率均有所提高且性能稳定；不同的相似性指标在不同切片数量情况下Precision指标值波动较大，在不同数据集中表现差异较大。改进后的相似性指标在两个数据集上不同切片数量情况下的实验结果并不会大幅发生变化，从而表明改进后的相似性指标具有良好的稳定性。

表2 在INFOCOM2006和MIT数据集中不同的切片数下各指标AUC的对比Tab.2 Comparison of AUC in different number of time slices in INFOCOM 2006 and MIT

表3 在INFOCOM 2006和MIT数据集中不同的切片数下各指标Precision的对比Tab.3 Comparison of Precision in different number of time slices in INFOCOM2006 and MIT

4.4 预测性能比较

在INFOCOM2006、MIT数据集上，进行FA-LP方法与支持向量分类（support vector classification,SVC）、K邻近算法（K-nearest neighbor,KNN）、WEAK[13]、DBN[14]、RBM[15]方法的对比。在INFOCOM2006数据集上，设置萤火虫算法的初始种群数量为200，迭代次数为150，时间帧长度为270 s，输入序列长度为9；在MIT数据集上，设置萤火虫算法的初始种群数量为250，迭代次数为120，时间帧长度为240，输入序列长度为8。时间帧长度根据文献[22]中所提的混沌时间序列理论确定，使用计算得出最佳切片时长对网络进行时间切分，可以使网络切片之间的最大限度地保留图的演变信息。作者统计了30次对比实验的结果，采用AUC作为预测方法的指标评价。作者提出的FA-LP方法与SVC、KNN、WEAK、DBN、RBM方法在INFOCOM 2006数据集下取得的AUC如图8所示，上述方法在MIT数据集下取得的AUC如图9所示。并在表4中给出了上述方法在INFOCOM2006和MIT数据集中取得的AUC均值。

图8 INFOCOM2006中不同方法的AUC值Fig.8 AUC values of different methods in INFOCOM-2006

图9 MIT中不同方法的AUC值Fig.9 AUC valuesof different methodsin MIT

表4 在INFOCOM2006和MIT数据集中各种预测方法的AUC均值Tab.4 AUC averages of different prediction methods in INFOCOM2006 and MIT

在INFOCOM2006和MIT两个稀疏程度不同的数据集上，基于DBN方法和提出的FA-LP方法较SVC、KNN、WEAK等方法在预测性能上表现更加稳定；在两个数据集上，基于DBN模型的AUC值在0.92左右，而FA-LP的AUC值在0.94以上，甚至在INFOCOM-2006数据集上，FA-LP的AUC值达到了0.95。在两个数据集的实验中，FA-LP比其他方法都有最高的AUC值，这说明FA-LP方法能够有效地提取PSN网络的连接特征，达到更好的链路预测结果。

5 结 论

作者采用学习自动机对节点的属性进行聚类，构建反映PSN网络社区属性、节点移动性和节点间间歇性连接的相似性指标SICM，从而更好地反映节点相遇的机会性和拓扑的时变性，采用萤火虫算法优化二分类器，从而获得更高的准确率和更好的稳定性。但是，文中仅探讨了PSN网络单节点对的链路预测方法，下一步的研究方向为PSN网络中多节点对间的链路预测。