顶点带属性网络的链接预测

发布时间：2018-04-23 01:04

本文选题：复杂网络 + 链接预测　；参考：《扬州大学》2016年硕士论文

【摘要】：现有的复杂网络链接预测算法主要关注网络中节点之间的拓扑相似特征和算法性能的提升,而缺乏对网络中节点属性特征的研究。在一些应用问题中,网络的顶点自身带有极其丰富的属性信息。这些属性反映了顶点所代表对象的特性和内容,这些信息也在很大程度上影响着链接存在的可能性。如果能够把复杂网络的结构信息和属性信息结合到一起,势必能够极大地提高链接预测算法的预测精度。另外,实际情况中网络本身存在的高维度、高稀疏性等问题对链接预测的结果也会造成负面影响。目前,如何将复杂网络的结构信息和属性信息有机地融合在一起,以提高链接预测的质量,还是一个有待探讨的问题。本文针对顶点带属性网络的链接预测问题,从顶点的结构相似性和属性相似性出发,研究如何有机地融合结构信息和属性信息、设计高效的链接预测算法,以提高预测的精度。取得的主要研究成果如下：(1)提出了一种基于奇异值分解和空间映射的链接预测算法为了综合考虑网络的结构特征和节点的属性特征,本文首先对网络的邻接矩阵进行特征分解。然后对特征值进行主成分抽取后再对相应的特征矩阵进行奇异值分解,将得到的新的奇异向量之间的相似度作为拓扑结构的相似度。最后将得到的拓扑相似度矩阵和属性相似度矩阵进行矩阵比对,得到最终的相似度矩阵。实验证明,本文提出的算法能有效提高链接预测的性能。(2)提出了一种基于非负矩阵分解的链接预测算法在实际应用中,复杂网络所对应的信息矩阵可能会存在着高维的问题。本文将非负矩阵分解应用于顶点带属性网络的链接预测中,分别将网络的邻接矩阵和属性相似度矩阵分解成非负的基矩阵和权重矩阵,通过将高维向量空间向低维向量空间的投影,重构不同类型矩阵之间的相关性。实验证明,本文提出的算法不仅拥有较低的复杂度,而且能够减少数据的存储空间,有效地提高链接预测的性能。(3)提出了一种基于相似度传播的二分网络链接预测算法相对于单分网络,二分网络在现实社会的复杂网络中更具有普遍性,已经成为复杂网络的重要研究课题之一。本文提出了一个基于二部图的链路预测算法,该算法使用了基于链接相似度得分的随机游走算法。在该算法中,网络里的每一条边都被分配一个对应顶点对属性相似度的传播概率。不同类节点之间的链接相似性得分是根据它们连边的传输概率来传播的。将该算法得到的拓扑相似度和网络的属性相似度结合,可以使预测的结果更加准确。实验证明,本文所提出的算法可以在较少的时间内得到较高精度的预测结果。
[Abstract]:The existing link prediction algorithms focus on the topology similarity between nodes in the network and the improvement of the performance of the algorithm, but lack of research on the attribute characteristics of nodes in the network. In some application problems, the vertex of the network itself has extremely rich attribute information. These attributes reflect the properties and contents of the objects represented by vertices, and the information also affects the possibility of the existence of links to a great extent. If the structure information and attribute information of complex network can be combined, the prediction accuracy of link prediction algorithm will be greatly improved. In addition, the problems of high dimensionality and high sparsity in the network itself have a negative impact on the prediction results. At present, how to combine the structure information and attribute information of complex network organically to improve the quality of link prediction is still a problem to be discussed. Aiming at the link prediction problem of vertex with attribute network, this paper studies how to combine structure information and attribute information organically from structural similarity and attribute similarity of vertex, and design an efficient link prediction algorithm to improve prediction accuracy. The main research results are as follows: (1) A link prediction algorithm based on singular value decomposition and spatial mapping is proposed. In order to consider the structural characteristics of the network and the attribute characteristics of nodes, this paper firstly decomposes the adjacency matrix of the network. Then the eigenvalues are extracted from the principal components and then the corresponding eigenvalues are decomposed by singular value decomposition. The similarity between the new singular vectors is regarded as the similarity of the topological structure. Finally, the topological similarity matrix and attribute similarity matrix are compared to obtain the final similarity matrix. Experimental results show that the proposed algorithm can effectively improve the performance of link prediction. (2) A link prediction algorithm based on non-negative matrix decomposition is proposed. In practical application, the information matrix corresponding to complex networks may have a high dimension problem. In this paper, the nonnegative matrix decomposition is applied to the link prediction of vertex with attribute network. The adjacent matrix and attribute similarity matrix of the network are decomposed into non-negative base matrix and weight matrix, respectively. By projecting the high-dimensional vector space to the low-dimensional vector space, the correlation between different types of matrices is reconstructed. Experimental results show that the proposed algorithm not only has low complexity, but also can reduce the storage space of data. In this paper, a link prediction algorithm based on similarity propagation is proposed, which is more universal in complex networks in real society than in single network. It has become one of the important research topics in complex networks. In this paper, a bipartite graph based link prediction algorithm is proposed, which uses a random walk algorithm based on link similarity score. In this algorithm, each edge in the network is assigned a propagation probability of vertex-attribute similarity. Link similarity scores between different class nodes are propagated according to their transmission probability. By combining the topological similarity obtained by the algorithm with the attribute similarity of the network, the prediction results can be more accurate. Experimental results show that the proposed algorithm can obtain high accuracy prediction results in less time.
【学位授予单位】：扬州大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】