Research And Application Of Binary Network Link Prediction

Both of the physical systems in nature and the engineered artifacts in human society,such as biology,economy,sociology,and other fields,could be modeled as complex networks.Link prediction is an important research direction in complex network anlysis.Now the link prediction problem has received extensive attention in the fields of sociology,anthropology,information science,computer science and so on.Opposed to the general unipartite networks,bipartite network not only is universality,but also is an important category of complex networks which has become an important research topic in complex networks analysis.Many real-world networks are naturally bipartite,such as scientists-paper cooperation network,the actors-films network,investors-company network,disease-gene network,club member-activities network,audience-songs networkand so on.Therefore,community detection in bipartite networks is very important in theoretical research and has practical value for the study of complex networks,such as academic detection,functional analysis,recommendation system,disease diagnosis,link prediction and other aspects.However,these algorithms have high complexity,and cannot applied to large scale network.In addition,the existing network link prediction methods suffer the high time complexity and the difficulty to predict.Aiming at those problems,we study effective algorithms for link prediction in bipartite networks.The main contributions and results of our research are as follows:(1)An algorithm for link prediction in a bipartite network is presented.In the algorithm we first map the bipartite network on to unipartite one called projected graph.Based on the projected graph,we define the concept of potential link.We perform the link prediction only within the potential links so as to reduce the computation time.We also define the pattern covered by the potential links and the weight of the patterns.By calculate the weight of the patterns a potential link covers,the confidence of the potential link can be obtained,which can be used as the final score of link prediction.Our experimental results show that our algorithm can get higher speed and higher quality link prediction results.(2)Inspired by the missing data recovery algorithm in compressed sensing,we propose link prediction algorithm based on low-rank matrix completion.Some existing link prediction algorithms are hard to avoid data sparsity which reduces predictive veracity.The link prediction algorithm based on low-rank matrix completion can reconstitute and recover the matrix without changing original data,and then predict the unconnected links.By a great deal of contrasted experiments,we validate that the proposed algorithm can achieve superior quality link prediction results.(3)In practical recommendation problem,he high dimension and sparse of the data makes the process of the recommendation longer and the time complexity higher?The existing algorithms perform badly for the real-time updating networks in the accuracy of the recommendation.We propose dynamic recommendation algorithm based on non-negative matrix factorization.The algorithm focus on two main cituations.The first one is based on the cituation which user modifies the rating vector.The second one is based on the cituation which a new user rating vector is added to the rating matrix.The main idear of our algorithm is based on non-negative matrix factorization,and then we decompose the original matrix into two non-negativematrix,one is foundational matrix and the other is weight matrix.When the data is updates,we update the decomposition results according to the former results to save the waiting time strately.We then employ resource acclocation strategy based on K-neighbour which can reduce the memory space of the data.And our experimental result shows that the algorithm achieve high recommendation accuracy within shortest time.