Research On Link Prediction Based On Topology Structure

Link prediction is an important research topic in complex networks,which is of great significance for complement of missing data and graph pattern mining.Link prediction uses the known network structure at the current moment to predict whether there will be connections between nodes in the network at the future moment.In link prediction,using the similarity algorithm of topology structure is the key to measure the connections between nodes.The difference between similarity algorithms is to extract different topology structure between nodes.Most of the existing similarity algorithms use low-order structure to represent link feature,ignoring the effect of high-order structure on link prediction.In addition,although some similarity algorithms have good link prediction effects in static networks,they cannot capture the evolutionary characteristics of network structure in dynamic networks,which limits the accuracy of link prediction.Therefore,three similarity algorithms that capture rich high-order structure are proposed,which can effectively represent the similarity between nodes.Based on local topology structure and temporal decay model,a topologybased temporal link prediction algorithm is proposed,which has good temporal link prediction accuracy.The temporal decay model can effectively capture the temporal evolutionary characteristics of dynamic networks.The main work and innovations include the following parts:(1)To capture higher-order structural feature among nodes,local common neighbors are defined and a similarity algorithm named DLCN(Degree based Local Common Neighbors)is proposed.The DLCN algorithm performs similarity calculation based on the principle of local similarity of nodes and resource allocation.By introducing the high-order structure on links provided by the second-order common neighbors,the local topological feature between nodes is enriched.At the same time,adjustable parameter is used to control the role of second-order common neighbors,so that the algorithm is suitable for networks with different topological properties.The experimental results show that the DLCN algorithm has better link prediction accuracy in static and dynamic networks than other traditional similarity algorithms.(2)To effectively capture the community relationship between nodes,two similarity algorithms based on local community consistency are proposed,named CAR-LCN(CAR based Local Common Neighbors)and CLCN(Clustering coefficient based Local Common Neighbors).The CAR-LCN and CLCN algorithms are based on the local community paradigm theory,and use local links and triangular structure to mine community relationships to measure the similarity between nodes.The experimental results show that the second-order common neighbors can effectively supplement the community relationships not captured by the first-order common neighbors,and the CAR-LCN and CLCN algorithms have better performance than traditional similarity algorithms on small-scale networks with simple structure.(3)In order to make full use of the temporal and spatial characteristics of dynamic networks,a topology-based temporal link prediction algorithm TLP-TS(Temporal Link Prediction based on Topology Structure)is proposed.By fusing low-order and high-order structural feature,the link feature between nodes is constructed into a time series about similarity score,and then the time series decay model is used to predict the similarity score between nodes in the future.The TLP-TS algorithm integrates the three similarity algorithms of DLCN,CCLP and CAR-LCN to capture the local topology feature between nodes,and combines the linear decay factor and exponential decay factor to obtain the temporal evolutionary characteristics of the dynamic network.The experimental results show that the fusion of low-order and high-order structures can effectively characterize the local topological feature of links,and the prediction effect of the TLP-TS algorithm is better than hat based on structure similarity algorithm using moving average,error correction or weighted evolution.As a result,the prediction performance of the TLP-TS algorithm is significantly improved.