106
个编辑
更改
→基于机器学习的链路预测
用机器学习的思路进行链路预测，主要分为基于特征分类方法、基于概率图模型方法和基于矩阵分解方法三大类。
用机器学习的思路进行链路预测，主要分为基于特征分类方法、基于概率图模型方法和基于矩阵分解方法三大类。
*基于特征分类方法
*基于特征分类方法<ref name="[20]">Al Hasan, M, Chaoji, V, Salem, S (2006) [https://pattern.swarma.org/paper?id=0cae2084-710c-11ea-bbd8-0242ac1a0005 Link prediction using supervised learning].counter-terrorism and security..30.(798--805)</ref>
网络中的链路预测问题可以看成机器学习中的分类问题，其中每个数据点对应一对节点之间关系的标记，假定两个节点之间存在连边，则数据点的值为+1，否则为-1。特征选取是分类问题中最重要的问题之一，目前研究较多的主要包括基于节点与边的属性特征和基于节点所处网络的拓扑结构特征（如CN、AA、Katz、最短路径）等。哈桑 Hasan 等人提取合著网络中科学家研究领域的关键词作为特征，用监督学习中一些常用的分类算法（如决策树、K近邻法、多层感知器、支持向量机、径向基网络）对缺失的连边进行较为精准的预测，其中以支持向量机方法表现最佳。
网络中的链路预测问题可以看成机器学习中的分类问题，其中每个数据点对应一对节点之间关系的标记，假定两个节点之间存在连边，则数据点的值为+1，否则为-1。特征选取是分类问题中最重要的问题之一，目前研究较多的主要包括基于节点与边的属性特征和基于节点所处网络的拓扑结构特征（如CN、AA、Katz、最短路径）等。哈桑 Hasan 等人提取合著网络中科学家研究领域的关键词作为特征，用监督学习中一些常用的分类算法（如决策树、K近邻法、多层感知器、支持向量机、径向基网络）对缺失的连边进行较为精准的预测，其中以支持向量机方法表现最佳。
*基于概率图模型
*基于概率图模型<ref name="[21]">Backstrom, L, Leskovec, J (2011) [https://pattern.swarma.org/paper?id=8ccaa454-710c-11ea-9eeb-0242ac1a0005 Supervised random walks: predicting and recommending links in social networks].Proceedings of the fourth ACM international conference on Web search and data mining.(635--644)</ref>
基于概率图模型的链路预测方法使用图模型来表达节点之间的连边概率，根据模型中概率依赖关系，可分为有向无环的贝叶斯网络和无向的马尔科夫网络。随机分块模型和层次结构模型分别是典型的基于贝叶斯网络和基于马尔科夫网络的链路预测方法。基于概率图模型的链路预测方法有很多，典型的还有有监督随机游走链路预测算法，将网络结构信息与节点和连边的属性信息结合起来，给每条边分配不同的转移概率。与其他有监督的机器学习方法相比，该算法无须知道网络的特征和相关的领域知识。
基于概率图模型的链路预测方法使用图模型来表达节点之间的连边概率，根据模型中概率依赖关系，可分为有向无环的贝叶斯网络和无向的马尔科夫网络。随机分块模型和层次结构模型分别是典型的基于贝叶斯网络和基于马尔科夫网络的链路预测方法。基于概率图模型的链路预测方法有很多，典型的还有有监督随机游走链路预测算法，将网络结构信息与节点和连边的属性信息结合起来，给每条边分配不同的转移概率。与其他有监督的机器学习方法相比，该算法无须知道网络的特征和相关的领域知识。
*基于矩阵分解
*基于矩阵分解
基于矩阵分解的链路预测方法是基于网络邻接矩阵的代数谱变换而得到的方法，来预测网络中链路的存在性和链路的权值<ref name="[22]">Kunegis, J, Lommatzsch, A (2009) [https://pattern.swarma.org/paper?id=2908af64-710d-11ea-b513-0242ac1a0005 Learning spectral graph transformations for link prediction].Proceedings of the 26th Annual International Conference on Machine Learning.(561--568)</ref>。相比其他几种机器学习方法，该方法要学习的参数少很多，但计算复杂度较高。链路预测问题可以视为邻接矩阵填充问题，并可以通过双线性回归模型将节点和链路的显特征和隐特征结合起来用矩阵分解方法解决<ref name="[23]">Menon A K, Elkan, C (2011) [https://pattern.swarma.org/paper?id=7f0ab830-710d-11ea-9143-0242ac1a0005 Link prediction via matrix factorization].(437--452)</ref>。边缘去噪模型将根据给定关系矩阵求未知边或丢失边的问题变成一个矩阵降噪去噪问题<ref name="[24]">Chen, Z, Zhang, W. (2014) [https://pattern.swarma.org/paper?id=d925d57a-710d-11ea-90c5-0242ac1a0005 A marginalized denoising method for link prediction in relational data].Proceedings of the 2014 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics.(298--306)</ref>。
关于不同的链路预测研究方法的分类可以参考下表：
关于不同的链路预测研究方法的分类可以参考下表：