基于拓扑结构与谱分析的链路预测研究

摘要

链路预测是复杂网络热门的研究方向之一，它在社交网络、生物网络以及交通网络等方面都有着重要实用意义。目前，由于网络拓扑结构信息既容易获取又更加可靠，因此，链路预测的算法大多是利用网络的拓扑结构性质计算节点的相似度来进行预测。而现有的基于机器学习的预测方法需要获得节点的额外属性，例如社交网络中用户的年龄、工作等信息，这些信息并不容易获取，从而限制了算法的普适性。因此，本文考虑网络的拓扑结构性质并引入谱分析方法来进行研究。 本文首先在共同邻居的基础上综合考虑度和聚类系数两个拓扑结构性质，提出了新的基于局部拓扑结构性质的C DLP指标。通过在8个真实网络数据集上进行实验发现C DLP指标优于其他基于局部拓扑结构特征的指标，证明考虑越多有效的拓扑结构特征越有利于预测结果精度的提高。 由于现有的大多数链路预测方法是利用网络的拓扑结构信息，计算节点相似性来进行预测，预测结果容易受到拓扑结构变化的影响，我们引入谱分析方法。谱分析方法利用标准化拉普拉斯方程计算所得的特征值与特征向量将网络的节点映射到维度空间，再通过计算节点之间的相似性距离对连边赋予属性，邻接矩阵的上三角（或下三角）作为标记属性。相似性距离属性和邻接矩阵标记属性相结合构造成关于边的属性特征集，最后通过机器学习的分类方法就将传统的对节点相似性的预测转化为对边属性集的二分类预测。通过实验发现，基于谱分析的方法可以明显提高预测结果，并且算法具有良好的健壮性。 为了进一步提高预测结果，我们综合考虑网络拓扑特征与谱分析方法。先将两节点的平均度与平均聚类系数分别作为连边的属性，两个属性构成关于边的属性集进行实验，随后由平均度与平均聚类系数构造的边属性集又分别与相似性距离属性集进行结合，最后平均度与平均聚类系数构造的边属性集同时与相似性距离得到的属性集结合进行实验，其中邻接矩阵上三角仍为标记属性。通过对比实验发现，平均度和平均聚类系数两个拓扑结构特征构成的边的属性集与距离属性集结合在一起所得的结果最好。拓扑结构与谱分析结合的方法既不需要获得节点的额外信息，又有效避免了受网络拓扑结构变化的直接影响，具有更好的适用性。

目录

第一个书签之前