The Algorithms Of Link Prediction And Application

Many social, biological and complex systems can be properly described bycomplex networks whose nodes represent individuals and links mimic the interactionsamong them. In recent years, complex networks have become a powerful tool toanalyze many different kinds of complex systems and attracted increasing attention.Its research can be summarized as three relevant and gradually exploring in-depthcontents: to measure the statistical properties of the networks; building model tounderstand the statistical properties of the networks; to forecast the network behaviorbased on the known structure characteristics of the networks, among which the linkprediction have been receiving more and more attention.Link prediction is a new research field and of both important theoreticalsignificance and potential application. It aiming at estimating the likelihood ofexistence of link between two agents based on observed links and attributes of agents.The prediction involves estimating the likelihood of the existing yet unknownconnections and links may exist in the future. On the one hand, in the past few years,people have developed many algorithms based on different principles and networkstructure, and some algorithms exhibit good prediction precision. On the other hand,owing to influence from many objective factors such as experiment technology, thereis a lot of false information in the networks. Thus, whether or not algorithms will beaffected? We called such problem as the robustness of the algorithms.In order to study the robustness we have done the following works:1) we foundfour algorithms which have high prediction precision through comparing someprevious algorithms. And then we compared their robustness in eight real networks.We studied the relationship between the robustness of algorithms and the topologicalproperty of the networks, and compared the robustness of one algorithm in differentnetworks.2) We make some attempt to enhance the robustness by using linkweighting method. The results show that proper link weighting scheme can enhanceboth robustness and accuracy of these algorithms significantly while it brings littleadditional effort.3) We explained the results based on the motif analysis, and used themotif analysis to predict the virulence gene.The thesis consists of four chapters. Chapter1introduces the significance andresearch development of link prediction. Chapter2introduces some structureproperties of networks associated with link prediction and compares the prediction accuracy of some algorithms. Chapter3we study the robustness of four algorithmsand have a try to enhance the robustness. Chapter4we try to predict the virulencegene based on the motif analysis.