A Study Of Link Prediction In Complex Networks Based On Local Structural Information

Many complex systems in reality can be characterized by complex networks consisting of nodes and links between node pairs.As an abstract mathematical model,complex networks can help people understand the formation mechanism and evolution pattern of complex networks,thereby providing theoretical foundation for scientific decision-making.During the research on complex networks,it is a natural demand that complex networks can precisely characterize complex systems in real life.However,such basic demand is hard to meet,because data collected from real world is always incomplete and full of noise.Link prediction aims to predict the missing or latent links by understanding the features of nodes and the whole networks and establishing prediction model.Link prediction is of great value in both theory and practice.The mainstream link prediction methods either use the neighbor information or path information of networks,or use machine learning methods by extracting non-structural features.The community structure,which is an important structural information of complex networks,has not been fully utilized for link prediction.In this thesis,we take advantage of the community structure information to analyze the differences of formation mechanism and linking probability between intra-community nodes and inter-community nodes.Then we model to describe such differences and design novel link prediction methods that have better accuracy,lower complexity and wider applicability.The main work and contributions are listed as follows:1)Inspired by the resource allocation process on networks,we make use of the community information to adjust the resources allocating to different neighbor nodes.We calculate the similarity between node pairs based on the amount of resources that they receive,and propose a similarity link prediction method CRA,based on the neighbor information and community information of complex networks.The proposed method improves the traditional similarity methods,and can achieve higher predicting accuracy within the same time complexity.2)We integrate the community information into random walk process and proposed a community aware random walk method for link prediction(CRW).Traditional random walk is a non-biased process and a walker moves to all its neighbors with the same probability.The community information is used in CRW to define a new type of transition probability so that the walker has higher probability moving to neighbors within the same community as it,which corresponds to the fact that the interactions are more frequent within communities.Therefore,the CRW method is more realistic compared to the traditional random walk-based methods.3)We evaluate our methods on both synthetic networks and real world networks.The experiment results on synthetic networks demonstrate that the proposed CRA method gives a significant improvement under the condition of low ratio of training sets of links.In addition,the CRW method not only achieves higher prediction accuracy,but also shows better robustness to community structure and the ratio of training sets of links,thus has wider applicability.We combine CRW with different community detection algorithms so that CRW can be applied to networks even without community information being known in advance.The experiments on real world networks also indicate that CRW method combined with different community detection algorithms can also have better prediction results in most cases.