一种HRG模型初始化算法及在链路预测中的应用  

An Initialization Algorithm of HRG Model and Its Application in Link Prediction

作　　者：祝丁恺 铁治欣 洪顺贺 ZHU Ding-kai;TIE Zhi-xin;HONG Shun-he(School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou 310018, China;Keyi College, Zhejiang Sci-Tech University, Shaoxing 312369, China)

机构地区：[1]浙江理工大学信息学院,浙江杭州310018 [2]浙江理工大学科技与艺术学院,浙江绍兴312369

出　　处：《计算机与现代化》2022年第2期38-44,共7页Computer and Modernization

基　　金：国家自然科学基金资助项目(61170110);浙江省自然科学基金资助项目(LY13F020043)。

摘　　要：在利用层次随机图(HRG)模型对真实网络进行链路预测的过程中,需要构造一个初始层次随机图来初始化马尔科夫链以运行马尔科夫链蒙特卡洛抽样算法。针对现有的层次随机图初始化方案效率不高的问题,本文对初始层次随机图模型进行重建,提出一种新的层次随机图模型初始化算法。该算法分为2个阶段,第一阶段引入相似性指标(LHN-I指标)为网络中的边进行排序;第二阶段利用排序好的边对层次随机图模型进行构造。在该过程中,设计一种将网络顶点插入到层次随机图模型中的方法。通过3个实例网络对提出的算法与现有算法的性能进行比较,实验结果表明,利用提出的初始化算法构造出的初始层次随机图不仅有着较高的似然值,而且使得马尔科夫链蒙特卡洛算法能够更快地收敛,进而降低链路预测的时间消耗。除此之外,在链路预测实验中,改进的基于层次随机图模型的链路预测算法相比一些基于相似性指标的链路预测算法有着较好的预测精度。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.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]