Link Prediction In Networks With Nodes Attributes

The existing complex network link prediction algorithms mainly focus on the topological similarity between nodes in the network and the improvement of the performance of the algorithm, while they lack research on the characteristics of nodes in the network. In some applications, the vertex of the network itself has plentiful attribute information. These attributes reflect the characteristics and contents of the objects represented by the vertices, which also greatly affect the possibility of the link existences. If the structure information and attribute information of the complex network can be combined together, it is bound to greatly improve the prediction accuracy of link prediction algorithm. What’s more, in the actual situation, the high latitude, high sparsity and other issues of the network itself will also have a negative impact on the results of the link prediction.At present, how to combine the structure information and attribute information of complex networks together to improve the quality of link prediction is still a problem to be studied. This paper focuses on the link prediction problem of vertex with properties of the network, starts from the structure similarity and attribute similarity of the vertex, studies how to combine the structure information and the attribute information, and design efficient link prediction algorithms in order to improve the accuracy of prediction. The main results obtained are as follows:(1) A link prediction algorithm based on singular value decomposition and space mapping isproposed.In order to comprehensively consider the characteristics of the network structure and the attributes of the nodes, this paper firstly performs the eigen-decomposition of the adjacency matrix of the network. Then the eigenvalues are extracted, and the corresponding feature vectors are decomposed. The similarity between the new feature vectors is obtained as the similarity of the topological structure. Finally, by aligning the obtained topological similarity matrix and the attribute similarity matrix, the final similarity matrix is obtained. Experimental results show that the algorithm proposed not only has a lower time complexity, but also effectively improves the performance of link prediction.(2) A link prediction algorithm based on non negative matrix factorization is proposed.In real world applications, the corresponding information matrix of complex networks may have a high dimension problem. The non negative matrix factorization is proposed for the link prediction in networks with vertex attributes.. In our method, the network adjacency matrix and attribute similarity matrix is 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 matrixes will be reconstructed. Experimental results show that the proposed algorithm not only has a low complexity, but also can reduce the storage space of the data, and effectively improve the performance of link prediction.(3) A bipartite network link prediction algorithm based on the transitivity of similarity is proposed.Compared with the unipartite network, the bipartite network is more universal in the real world complex social networks. It has become one of the important research topics of complex network analysis. In this work, a link prediction algorithm based on bipartite graphs is proposed, which uses a random walk algorithm based on link similarity score. In this algorithm, each edge of the network is assigned a value of the propagation probability, which is related to the attribute similarity of the corresponding vertex. The link similarity scores between different types of nodes are transmitted according to the transmission probability on their edges. By combining the topological similarity with the attribute similarity of the network, the algorithm can make the prediction results more accurate. Our experimental results show that the proposed algorithm can obtain high quality predicting results in less computation time.