Link Prediction On Complex Networks And It's Application In Recommendation

With the rapid development of the information technology on the Internet,human society has entered a complex network era,and link prediction is one of the most important bridges connecting the complex networks and information science.Link prediction method can be used as a powerful auxiliary tool to accurately analyze the social network structure.In practice,it has very important significance in predicting the future or potential links of some individuals.Link prediction problem has a wide range of practical application value in different fields.For example,in online social networks,potential friends of the users can be revealed by link prediction,and can be recommended to the users.By analyzing social relations,we can find potential interpersonal links.In biological networks,such as protein-protein interaction,metabolic and disease-gene networks,link existing between the nodes indicates that they have an interaction relationship.Research on link prediction not only has a wide range of practical value,but also has important theoretical significance.For example,it helps to theoretically understand the mechanism of the evolution of complex network,and can provide a simple and unified platform for a more fair comparison of network evolution mechanisms,so as to promote the theoretical research on complex network evolution model.However,the existing researches focus on improving performance of the link prediction algorithms,but ignore the attributes information or temporal information of the networks.The high-dimensional,sparse and redundant topological information of the complex networks have a negative impact on the link prediction algorithms.Therefore,this paper summarizes the development of domestic and overseas link prediction techniques and overviews research achievements of link prediction.In this paper,the high-dimensional and sparse networks with nodes attributes and temporal information are studied.The main contributions of this thesis are as follows:(1)A link prediction algorithm based on ant colony optimizationWe propose a link prediction algorithm based on ant colony optimization.By exploiting the swarm intelligence,the algorithm employs artificial ants to travel on a logical graph.Pheromone and heuristic information are assigned on the edges of the logical graph.Each ant chooses its path according to the value of the pheromone and heuristic information on the edges.The paths the ants traveled are evaluated,and the pheromone information on each edge is updated according to the quality of the path it located.The pheromone on each edge is used as the final score of the similarity between the nodes.We extend this algorithm for the networks with node attributes,and experimentalresults on a number of real networks show that the algorithm is more intuitive,efficient and robust.(2)A fast algorithm for network vertex similarity queriesIn many real world network applications,we need to predict the similarity score only between the pairs of vertexes that the users are interested in,instead of predicting the scores of all pairs of vertex in the network.In the method,we first construct a sub-graph centered at the node the users interested in.By choosing a proper size of such sub-graph,we can make the error of the estimated similarities be less than a given threshold.Since the similarity score computation is restricted within a small sub-graph called information core of this vertex.We theoretically derive the formula of threshold.Experimental results on real networks show that our algorithm can obtain higher precision results in less time than other methods.(3)A link prediction algorithm based on Non-negative Matrix FactorizationWith the expansion of network size,a large amount of redundant information caused by high-dimensionality,and sparsity of actual network reduces the performance of the link prediction.In this paper,we apply the non-negative matrix factorization in link prediction.The original network matrix is effectively decomposed into a base matrix and a weight matrix which are non-negative.Through the projection from high-dimensional vector space to low-dimensional vector space,we reconstruct the correlations of different types of matrices,and propose the direct prediction method and resource allocation method based on K neighbors.Our experimental results show that it not only can obtain results of higher quality on real networks,but also reduce data storage space while maintaining low time complexity.(4)A personalized recommendation algorithm based on temporal informationIn the networks with temporal information,we analyze the difference in performance between temporal data division and random data division.In the experiment,we gradually expand the time window and find that though the physics of the time window effect on the performance is decreasing,the performance of method almost remains unchanged.We propose a personalized recommendation algorithm based on temporal information.In the method,we set the size of time window according to the user's popularity.In detail,for unactive users,we expanded the size of their time window,for active users,narrowing the size of their time window.In the process of the recommendation,we compute the similarity of timing sequences within the window between different users and obtain users' rating for objects.The experimental results show that it not only can improve the recommendation performance,but also reduce the redundant information of target user.