Link Prediction Of Complex Networks

Structure and evolution is one of the basic research problems of complex networks.On one hand, many networks are incomplete as a certain number of links are not testedout in the experiments. On the other hand, the structure of networks is dynamic, whichmeans there are new links emerging over time. Link prediction is to estimate thepossibility of link appearance between two nodes that are not linked directly. Especiallyfor networks of huge size, effective link prediction methods would be helpful for furtherexperiments to check the missing links and even the future links in evolving networks.In theory, link prediction also provides another perspective to the understanding of thestructure and function of complex networks.Nowadays, many link prediction algorithms are developed based on the structuresimilarity of networks. Our thesis aims at developing new effective and efficientalgorithms based on structure similarity as well. And there are two works had been done:1) In unweighted and undirected networks, we propose a semi-local index whichintroduces the idea of resource allocation to the local path index, and design theprediction algorithm based on this index. We test it on 6 real networks from differentdisciplines. The prediction results show that, as well as maintaining the lowcomputational complexity, our algorithm has better prediction accuracy than thesealgorithms based on local information of networks. 2) Secondly, we extend the index toweighted case, and get good prediction accuracy on some real weighted networks, too.The thesis consists of four chapters. Chapter 1 introduces the significance andresearch development of link prediction. Chapter 2 reviews the structure characteristicsof networks which are relevant to prediction accuracy, including the microscopic andmacroscopic statistical characteristics. In Chapter 3, we give our work on unweightedand undirected networks and the work on weighted networks is presented in Chapter 4.The conclusion and prospect of link prediction are summarized in the end.