Research And Application Of Link Prediction In Complex Networks

Link prediction in complex network is designed to make full use of topology information to predict potential links or future links in the networks.It plays an important role in the aspect of understanding the structure and evolution of the networks.Although the existing works have achieved fruitful results,it is difficult to deal with the cold start problem and neglect the ensemble methods of link prediction.To this end,this thesis carried out the following research works:Different from the parallel ensemble strategy adopted by existing research,this thesis proposed a serial ensemble strategy based on network reconstruction.First of all,in order to deal with the noise and missing data of interaction in the networks,the matrix completion approach or the local similarity indices integration method based on the OWA operator was used to correct the links' weights to rebuild networks.Then,multiple link prediction algorithms were applied into the reconstructed networks.The experimental results have demonstrated that the reconstructed networks could not only weaken the noise,but also help to add potential links.Most link prediction algorithms could achieve a better prediction accuracy and become more robust on the more reliable reconstructed networks.The cold start problem has always been a difficult question in link prediction since isolated nodes and new nodes lack topology information in the networks.The various interactions accumulated in different fields provide new opportunities and challenges to alleviate the cold start problem.Therefore,auxiliary networks were introduced to provide additional information to the target networks in this thesis,and we have extracted the low-dimensional implied factors of this two kinds of networks.The likelihood ratio test and the Mantel test were used to jointly diagnose the correlation between hidden factors.Finally,the regression relationship was constructed between implicit factors of the associated target network and the auxiliary network.Experiments on eight bioinformatics datasets have shown that the similarity of drug molecules structure and the similarity of protein sequences could help to improve the predictive effect of drug interactions and protein function associations respectively.On the basis of above research,the proposed method is applied to predict urban congestion.According to the actual road structure of Qingdao,the urban road network was established.The congestion index is used to measure the congestion status of intersections and road sections,so that the congestion prediction problem could be abstracted into a link prediction question.Further,after removing redundant data,filling missing data,and correcting error data for the obtained traffic dataset.A congestion prediction method is applied to predict road congestion status.In addition,in order to analyze the distribution of urban congestion more intuitively,we have designed a method of dividing the congestion area.