基于统一描述网络结构模型的链路预测方法

Link Prediction Method Based on Network Structure Model for Unified Description

面向网络链路预测的随机分块模型和层次结构模型利用全概率思想计算节点对之间的链路形成概率,但无法有效利用从宏观、中观网络结构到微观低阶环或模体结构中的重叠结构信息,导致链路预测结果的准确率较低。根据笛卡尔积和幂集等概念,借鉴随机分块模型和层次结构模型思想,构建一种对层次结构信息、重叠结构信息和微观结构信息进行统一描述的网络结构模型(USI)。基于USI模型提出一种链路预测方法,依据网络结构信息给出USI模型中的集合划分,利用最大似然估计法计算节点对之间的链路形成概率,最终根据概率并联策略得到链路预测结果。实验结果表明,与基于节点相似性的经典链路预测方法相比,该方法在LT、ER、OP网络数据集上的AUC值提升了0.075~0.143,具有更高的链路预测准确性,并且验证了网络规模对链路形成具有一定的影响。

The random block model and hierarchical structure model for network link prediction use the idea of total probability to calculate the link formation probability between node pairs. They,however,cannot effectively use overlapping structural information from macroscopic and mesoscopic network structures in this endeavor. Neither can they effectively use microscopic low-order rings or motif structures,resulting in low accuracy of link prediction results.In this study,according to the concepts of Cartesian product and power set,and drawing on ideas from the random block model and the hierarchical structure model,a network structure model called the USI(Uniform-Structure-Information)model is constructed. The USI model uniformly describes hierarchical,overlapping,and microstructure information.Based on the USI model,a link prediction method is proposed. According to the network structure information,the set division in the USI model is given. The maximum likelihood estimation method is used to calculate the link formation probability between node pairs,and finally,the link prediction result is obtained according to probabilistic parallel strategies.The experimental results show that compared with the classic link prediction method based on node similarity,the AUC(Area Under the Receiver Operation Characteristic Curve) value of this method on the LT(London Transport1),ER(Euroroad),and OP(Opsahl_ powergrid) network datasets is improved by 0.075~0.143,and it has higher link prediction accuracy.It is verified that this network scale has a certain influence on the link formation.