Research On Link Prediction Based On Hierarchical Random Graph Model

In the real world,many complex systems can be abstracted into complex network models for research and analysis.In the process of studying complex networks,it is hard to avoid the lack and inaccuracy of data.As an important branch of complex network,link prediction not only contains important theoretical value,but also contains a lot of practical application value.In the research of link prediction,the hierarchical structure of the network is a less concerned point.Networks in the real world usually have a certain level of organization.Hierarchical Random Graph(HRG),as a model that can infer a hierarchical structure from network data,can not only be used for mining communities in the network,but also for predicting missing links in the network.This method not only has high prediction accuracy,but also is more suitable for general network structure compared with some existing link prediction algorithms.However,the existing methods have some disadvantages: 1)the model constructed when initializing the HRG model is not ideal.2)for large-scale networks,the existing Markov Monte Carlo(MCMC)algorithm is difficult to converge in a reasonable time range when sampling the hierarchical random graph model,which greatly limits the practicability of the model,and even in the case of "convergence",the hierarchical random graph model can not fit with the real network.The link prediction algorithm based on this model needs to sample the hierarchical random graph model when it converges.Therefore,the accuracy of the prediction will also be affected to some extent.Based on this,this paper has done the following research:First,we reconstruct the initial hierarchical random graph model,and propose a new method to initialize hierarchical random graph model.The existing construction method of initial hierarchical random graph adopts a random construction method,and the model constructed by this method has great uncertainty,which is far from the desired result in most cases.To solve this problem,firstly,we introduce the similarity index(LHN-I index),and give weight to each edge in the network according to the calculation method of the index.Secondly,we sorted the weights for the edges in the network in order from the largest to the smallest and put the sorted edges into the queue successively.Finally,two nodes of each edge are successively extracted from the queue head and added to the HRG model.Experimental results show that our HRG model initialization method is much better than the existing construction methods.Second,in order to improve the sampling efficiency of Monte Carlo algorithm,we further put forward a new sampling algorithm--two-state transformation Markov chain Monte Carlo(TST-MCMC)algorithm.The algorithm allows two states to be generated in a Markov process and eliminates the worse of the two states by means of competition to avoid the generation of multiple Markov chains.In this way,the optimal hierarchical random graph samples can be collected more quickly.In addition,we also use the Metropolis-Hastings standard to ensure the detailed balance of the Markov chain.We compare the performance of the proposed algorithm with the MCMC algorithm by three examples.The experimental results show that the algorithm can not only improve the convergence speed of the Markov chain,but also shrink the convergence range of the Markov chain.Third,combining the new initialization method of HRG model and the improved sampling method of HRG model,a new link prediction algorithm based on HRG model is proposed.The link prediction experiment is carried out by using three real networks.Among them,each network is divided into training set and test set to test the accuracy of link prediction,and the AUC index is used to evaluate the prediction results.Then the algorithm proposed in this paper is compared with the other seven algorithms,and the experimental results show that the new algorithm performs better in terms of accuracy.