Research On Link Prediction Algorithm Based On Local Network Structure

Link prediction,as one of the important means of complex network research and analysis,has great scientific research and application value.Specifically,link prediction is to quantify the correlation between different factors in the network,and make full use of these quantitative indicators to predict the missing or undiscovered links in the network and the possible links in the future.In recent years,there have been many research achievements in this field,among which the link prediction method based on similarity is the most common one.The key of this type of method is to define the similarity between nodes by using information such as node attributes and network structure in the network.Among them,network structure information is easier to obtain and filter than node attributes,so it is favored by scholars in the field of network science.However,the current link prediction algor ithms are not sufficient enough in mining and utilizing this kind of information.Therefore,how to predict the missing links in incomplete complex networks efficiently and accurately is still a challenge.In order to balance the accuracy and time complexity of the algorithm,we take the link prediction algorithm based on local network structure as the main line of research in this paper and analyze the current main problems of existing network structure-based link prediction algorithms.Then propose the corresponding link prediction algorithm according to the difference of network scale.The content is summarized as follows:(1)For medium and small networks,starting from the local topological information of networks and considering the local network environment,ie the link clustering information based on the fact that the common neighbor nodes are one of the important factors affecting the similarity of the predicted node pairs,a link prediction algorithm CELP is proposed.This algorithm realizes the portrayal of node similarity,which is a characteristic of network structure,and effectively develop the value of local network structure formed by common nodes themselves and their edges in predicting the formation of network links.In addition,the rule of "Birds of a feather flock together" indicates the universality of the structural feature of network community attribute.Therefore,this paper uses the community discovery algorithm Com_ST to obtain the community structure of the network and calculate the community similarity,and then models it with CELP into a Bayesian network.According to Bayes' theorem,a link prediction algorithm LNS_LP is designed,which further improves the prediction accuracy and ensures the full mining and utilization of network structure information.The experimental results of multiple datasets from various fields show the effectiveness of the proposed algorithm,and further affirm the importance of information such as nodes,links,and communities for link prediction.(2)For large-scale networks,the traditional high-dimensional sparse representation,namely the adjacency matrix,has great limitations due to the computational space and time consumed,as well as the relatively serious data sparse problem.On the other hand,the traditional link prediction algorithm based on this representation scheme is too inefficient to handle large networks.Therefore,changing the research thinking,we firstly propose the network representation learning algorithm LNS_NRL,and learn the constructed random walk node sequence through the language model Skip-Gram to realize the low-dimensional vector representation of the network nodes.Then,design a link prediction algorithm NRL_LP,which uses the Euclidean distance between vectors to define the similarity of any two nodes.The closer the distance is,the higher the similarity is.Experimental results show that compared with the link prediction algorithm LNS_LP that based on original network representation,the NRL_LP algorithm has obvious advantages in efficiency and effect in dealing with large networks.