Research On Link Prediction Based On Topological Similarity In Complex Networks

Computers,Internet,and Internet of Things are gradually entering people’s life.The interaction of people and machines has created complex relationships.People,machines,and their relationships constitute a complicated system with complex elements and structures.Complex systems can be abstracted into complex networks by using mathematical language.Using mathematical methods to describe and study the complex networks is an effective means to understand and learn the complex systems.Adopting the observed network structural information,link prediction can predict the future connecting probability of unconnected nodes and identify the false connected edges in the network.Link prediction is one of the branches of complex network research.In theory,the research of link prediction can simulate the network evolution process,understand the evolution rule and mechanism of the complex network,and evaluate what’s the 11model scale of the complex network.In practical applications,link prediction can be applied to predict friend relationship in the social network,design the reasonable and effective route in the transportation network,accurately recommend products in the e-commerce network,and predict the protein-protein interaction in the biological network,etc.Therefore,the research of link prediction in complex networks has the significant theory and application value.In this thesis,the topological similarity based link prediction under the complex networks is studied.Link prediction based on the node similarity thinks that the more similar the two nodes,the more likely they are connected.Frolm the results of research,the node influence and the effective transmission of node influence play the role on the node similarity.In view of the problems existing in the current link prediction research,this thesis starts fr-om the local and quasi-local structural information of the network and studies the impact of structural attributes as the influence on the node similarity.The structural attributes include the effective paths between the common neighbor and the target endpoints,the node degree,and paths between endpoints.Meanwhile,we discuss the impact of node properties of the node degree,the node H-index,and the node coreness as the influence resource on the performance of link prediction.And the link prediction model which can accurately describe the node similarity is investigated in this thesis.The main work and highlights list are shown as below.1)Considering the local structural information of the network,a link prediction model based on the common neighbor’s tie connection strength(Tie Connection Strength:TCS)is proposed from the perspective of common neighbor between endpoints in the network.Traditional link prediction researches take the target endpoints as the research object,think common neighbors with the big degree are adversely to the influence transmission,and ignore the positive effects of paths between common neighbors and the target endpoints on the influence transmission.From the perspective of common neighbors,this thesis regards the path that contributes to the endpoints similarity on the common neighbor as the effective path,based on which studies the influence of common neighbor node.Meanwhile,the number of effective paths is defined as the tie connection strength(TCS)and a novel link prediction algorithm based on the common neighbor’s TCS is proposed in this thesis.TCS index considers the local structure of the network and introduces the effective paths into the node similarity model.The performance comparison of TCS and 8 traditional link prediction algorithms in 12 networks is given in the experiment of the thesis.Combining traditional Precision and Recall evaluation indices,the experimental results show that the proposed TCS algorithm can improve the accuracy of link prediction without increasing the computation complexity and has the applicability and feasibility.2)It is found that the influence of endpoints in the network is related to the path length between endpoints.Considering the quasi-local structural information of the network,a novel link prediction algorithm based on the significant influence(SI)is proposed in this thesis.Only considering the endpoint degree,traditional researches take the endpoint degree as the influence and think endpoints with the large degree are inclined to connect with each other.The study in this thesis found that the endpoint connects with each other through the paths with different lengths and transmits the influence.The different length paths between endpoints play different roles in transmitting influences.Two endpoints have a strong relationship through short paths,especially through the two-hop paths,which bring strong influence.Conversely,the weak relationship is introduced by paths of three or more hops,resulting in weak influences.Many strong relationships and few weak relationships between endpoints can constitute the significant influence and effectively transmit the influence resource.Based on the significant influence,this thesis proposes the SI algorithm which utilizes the quasi-local network features and distinguishes the strong and the weak influence relationships between endpoints.The performance comparison of SI and 5 traditional link prediction algorithms in 12 real networks is given in the experiment of the thesis.Combining AUC(Area Under the Receiver Operating Characteristic Curve)and Precision evaluation indices,the experimental results show that the proposed SI algorithm has the superior performance to the traditional algorithm and improve the accuracy of link prediction.3)In the basis of SI algorithm,combining two important factors of transmitting influence and distinguishing the different roles of paths with dissimilar lengths in transmitting influence,a punishing the redundant influence(PRI)link prediction algorithm is proposed in this thesis.Traditional quasi-local information based link prediction researches construct the influence by using node-degree,without concerning the influence transmission need paths and ignoring the effective transmission of influences can impact similarity of the endpoints.In this thesis,it is found that the influence cannot be effectively transmitted to the target endpoints just by using the endpoint degree alone.The effective transmission of the endpoint influence is also related to the length of the transmission path.Therefore,the node-degree which connects with the common neighbor and the short paths between endpoints is regarded as the efficient factor which contributes to the similarity transmission.The node-degree which connects with the non-common neighbor,the long paths between endpoints can be regarded as the low effective factor.And the node-degree without connecting with the target endpoints is taken as the redundant factors due to without transferring the influence resources.Integrating these three different factors,a punishing redundant influence based link prediction algorithm is proposed by restraining the redundant factors and emphasizing the efficient factors.Combining two evaluation indices,AUC and Precision,PRI algorithm can improve the endpoints similarity and the accuracy of link prediction after comparing the performance of 5 traditional algorithms in 12 real networks.4)Taking the smallest element node in the network as the object,this thesis studies the impact of node basic attributes on the link prediction.After investigating the influence of degree,the H-index and the coreness of the node on the node similarity,the role of three basic attributes in link prediction is analyzed.Based on the superposed random walk index(SRW),two novel algorithms,the node H-index(HSRW)and the node coreness(CSRW)are proposed in this thesis.Research and experiment results show that HSRW and CSRW algorithms can efficiently improve the accuracy of link prediction without increasing the computation complexity.Furthermore,we find H-index in HSRW as influence resource can be a good tradeoff that in many cases of link prediction.In the network with a maximal connected subgraph,HSRW is more suitable if two endpoints have larger H-index and extensive paths,and CSRW is more applicable if two endpoints have less H-index but larger coreness and more centrality.Meanwhile,just like degree,H-index and coreness as the endpoint influence also play important roles in link prediction.Irn diverse networks,adopting different node attributes as the influence to construct link prediction model can efficiently improve the accuracy of link prediction.