Research Of Link Prediction Based On Structural Similarity

With the rapid development of information technology,various complex networks have emerged.The analysis and research of complex networks have evolved into an interdisciplinary subject.As an important research topic of complex network analysis and link mining,link prediction has attracted extensive attention from researchers in different fields.Link prediction can predict unobserved and new links based on known node attributes,network structures and other information.Therefore,it has significant research values not only in exploring the structure and evolution mechanism of a network,but also in the applications such as product recommendation and biological experiment.This dissertation focuses on the similarity-based link prediction methods in complex networks.The similarity-based link prediction methods hold the view that the more similar that two nodes are,the more likely that a link exists between them.It is found that the similarity of nodes is affected by many factors such as common neighbors,community structure and link weights.This dissertation makes an in-depth study on the similarity-based link prediction methods for different types of complex networks.To estimate the similarity of nodes,we consider various network structure characteristics including common neighbors,community structure and link weights.The dissertation made the following major contributions.1.Inspired by the triangle growth mechanism in network evolving,we propose the TRA index for link prediction based on triangle structure for unweighted networks.Unlike the triangle used in CAR and CCLP indexes,the triangle used in the proposed index is a new one,which can assess the closeness between a seed node and a common neighbor more accurately.When calculating the similarity of nodes,TRA index emphasizes the importance of this type of triangle but does not ignore the contribution of any common neighbor.In addition,it adopts the theory of resource allocation by penalizing large-degree neighbors.The experimental results show that TRA achieves better prediction performance than the compared methods.2.This dissertation further studies the link prediction problem for unweighted networks by considering community structure.To enhance the prediction accuracy by making full use of community structure information,we propose a new link prediction model,namely CMS,in which different community memberships of nodes are investigated.The CMS model supposes that different memberships can have different influence to link's formation.To estimate the connection likelihood between two nodes,the CMS model weights the contribution of each shared neighbor according to the corresponding community membership.Three CMS-based methods are derived by introducing three forms of contribution that neighbors make.Extensive experiments manifest that CMS-based methods are more effective and robust than baselines.3.For weighted networks,the phenomenon of weak ties in some networks causes the decrease in accuracy when link weights are used in link prediction.To address this issue,we propose a nonparametric link prediction method that can automatically adapt to the link strength distribution in networks.By analyzing the distribution of ternary motifs in the network,the proposed method calculates the connection likelihood of different kinds of node pairs from the global perspective.Then the obtained connection likelihood is integrated into the TRA method.Compared with some existing methods that consider the phenomenon of weak ties,this method can automatically adjust the influence of weak links.The experimental results show that this method can overcome the negative effects brought by the weak ties phenomenon,and hence achieves good prediction performance.4.For link prediction in multiplex networks,a prediction method based on multipleattribute decision-making is proposed to fuse the structure information of different layers.Many studies have shown that the topological structures between different layers of a multiplex network usually have a certain degree of correlation.As a result,the performance of link prediction can be enhanced by combining the information of different layers.In this dissertation,link prediction in multiplex networks is regarded as a multiple-attribute decision-making problem,in which the potential links in the target layer are candidates,layers are attributes,and the similarity score of a potential link in each layer is an attribute value.In implementation,the TOPSIS method is used to select candidates,and inter-layer relevance is used to weight the attributes.The experimental results show that the proposed method is not sensitive to the parameter and the inter-layer relevance index,and achieves superior prediction performance.