关键词: 网络, 层次随机图, 相似性指标, 马尔科夫链蒙特卡洛, 链路预测

Abstract: In the process of using the hierarchical random graph (HRG) model to predict the link of the real network, it is necessary to construct an initial hierarchical random graph to initialize the Markov chain to run the Markov chain Monte Carlo sampling algorithm. In view of the inefficiency of the existing hierarchical random graph initialization scheme, this paper reconstructs the initial hierarchical random graph model and proposes a new hierarchical random graph model initialization algorithm. The algorithm is divided into two stages, in the first stage, similarity index (LHN-I index) is introduced to sort the edges in the network； In the second stage, the hierarchical random graph model is constructed by using the sorted edges. In this process, a method is designed to insert the network vertices into the hierarchical random graph model. The performance of the proposed algorithm is compared with the existing algorithm through three example networks. The experimental results show that the initial hierarchical random graph constructed by the proposed initialization algorithm not only has higher likelihood value, but also makes the Markov chain Monte Carlo algorithm converge faster, thus reducing the time consumption of link prediction. In addition, in the link prediction experiment, the improved link prediction algorithm based on hierarchical random graph model has better prediction accuracy than some link prediction algorithms based on similarity index.

Key words: networks, hierarchical random graph, similarity index, Markov chain Monte Carlo, link prediction