基于机器学习的链路预测方法探究

用机器学习的思路进行链路预测，主要分为基于特征分类方法、基于概率图模型方法和基于矩阵分解方法三大类别。网络中的链路预测问题可以看成机器学习中的分类问题，其中每个数据点对应对节点之间关系的标记，假定两个节点之间存在连边，则数据点的值为+1，否则为-1。特征选取是分类问题中最重要的问题之一，目前研究较多的主要包括基于节点与边的属性特征和基于节点所处网络的拓扑结构特征（如CN、AA、Katz、最短路径）等。哈桑（Hasan）等人提取合著网络中科学家研究领域的关键词作为特征，用监督学习中一些常用的分类算法（如决策树、K近邻法、多层感知器、支持向量机、径向基网络）对缺失的连边进行较为精准的预测，其中以支持向量机方法表现最佳。

基于概率图模型的链路预测方法使用图模型来表达节点之间的连边概率，根据模型中概率依赖关系，可分为有向无环的贝叶斯网络和无向的马尔科夫网络。随机分块模型和层次结构模型分别是典型的基于贝叶斯网络和基于马尔科夫网络的链路预测方法。基于概率图模型的链路预测方法有很多，典型的还有监督随机游走链路预测算法，将网络结构信息与节点和连边的属性信息结合起来，给每条边分配不同的转移概率。与其他有监督的机器学习方法相比，该算法无须知道网络的特征和相关的领域知识。

在基于矩阵分解的方法方面，提出了种基于网络邻接矩阵的代数谱变换的方法，来预测网络中链路的存在性和链路的权值。相比其他几种机器学习方法，该方法要学习的参数少很多，但计算复杂度较高。链路预测问题可以视为邻接矩阵填充问题，并可以通过双线性回归模型将节点和链路的显特征和隐特征结合起来用矩阵分解方法解决。边缘去噪模型将根据给定关系矩阵求未知边或丢失边的问题变成一个矩阵降噪去噪问题。