Research On Link Analysis And Prediction In Complex Network

In the real world,there are many examples of complex network structures in the area of science,comercial,economy and biology,such as power grid,telephone interaction,social interaction network,the World Wide Web and co-authorship and citation network of scientists.In the field of biology,there are epidemiology network,cellular and metabolism network,and food network.In social science,internal information exchange in a company,E-mail news group,chat room,interactions between friends are examples of social networks.Now the link prediction problem has received extensive attention in the fields of sociology,anthropology,information science,computer science and so on.At present,the methods of network data link prediction includes similarity based,maximumn likehood based,and probability model based approaches.In this paper,the current situation of the current network link prediction is analyzed,and the existing problems in the current prediction algorithm are studied,and more effective algorithms are proposed.The main contributions of the paper are as follows:(1)We propose a network link prediction based on direct optimization of AUC(Area under Curve).With the fast development of the Internet,dimensional,sparse and redundant of data appear in the complex networks.It requires effective link prediction techniques to extract the most basic and relevant information for online user services.To predict the potential links in multi-relational networks,a simple way is to transform a multi-relational network to a single-relational one and then conduct link prediction.However,we may lose too much valuable information in this simplified process.In this scenario,we expect that a method which effectively utilizes multi-faceted information in the multi-relational network would enhance the link prediction results.In this paper,we propose a network link prediction based on direct optimization of AUC.In this algorithm,we take AUC as the objective function of optimization,and the score matrix is divided into the weight matrix and the adjacency matrix.Next,we use the hinge function to iteratively weight matrix based on the stochastic gradient descent algorithm.Finally,we plus the weight matrix and the adjacency matrix after predicted as the final score matrix.We use three real-world heterogeneous information networks to test the method presented.The networks were chosen from different domains and have diversity in structure and relationship types.Based on the hinge function,the optimal weight matrix is obtained by using the sub-gradient descent algorithm.The empirical results show that our algorithm can achieve higher quality prediction compared with the results of other algorithms.(2)We present an algorithm for link prediction in the networks with nodes attributs.TThe algorithm uses the modularity measure reflecting the community structure information of the network.Based on the fact that the connection likelihood between a pair of nodes in the same community is larger than those separated in different communities,we propose a new measure,named modularity contribution,for predicting link between a pair of nodes using information from intra-community and within-community of these nodes.Using the modularity contribution,we map the nodes to an Euclidean space.In this space,the nodes trending to be included in the same community are closely located.The cosine similarity of the nodes in this space is used in computing the similarity measure for link prediction.We also extend the method to solve the link prediction on networks of nodes with attributes.Our experimental results show that the proposed algorithm can obtain higher quality results than other algorithms.(3)We propose a link prediction algorithm in multi-relational networks.Many real-world networks contain multiple types of interactions and relations.Link prediction in such multi-relational networks becomes an important area in network analysis.For link prediction in multi-relational networks,we should consider the similarity and influence between different types of relations.In this paper,we propose a link prediction algorithm in multi-relational networks based on relational similarity.In the algorithm,a belief propagation method is presented to calculate the belief of each node,and to construct the belief vector for each type of links.We use the similarity between belief vectors to measure the influence between different types of relations.Based on the influence between different relations,we present a nonnegative matrix factorization based method for link prediction in multi-relational networks.Convergence and correctness of the presented method are proved.Our experimental results show that our method can achieve higher quality prediction results than other similar algorithms.(4)We propose a fast approach based on similarity to predict the links of the related nodes.In many practical applications,we only need to predict the similarity of the vertices the users interested,but not to predict all the vertices in the complex network.In this paper,we propose a fast approach based on similarity to predict the links of the related nodes.We construct a corresponding sub-graph of the related nodes.For such a sub-graph,by setting the appropriate size,the error of similarity can be restricted to a given threshold range.Because only the similarity score of the small sub-graph is required,the time cost for computation this algorithm is greatly reduced.Experimental results on real networks indicate that our algorithm can obtain results with higher accuracy in less time than other methods.