基于二阶共同邻节点的链路预测算法

Link Prediction Algorithm Based on Second-Order Common Neighbor Nodes

针对链路预测共同邻居算法(CN算法)预测精确度偏低且不适用于多类型网络的缺点,在CN算法的基础上,提出一种将共同邻居的概念扩展到二阶的链路预测算法,算法将待预测节点的邻节点分为3种类型,不同类型的邻居点被赋予不同的权重,建立基于二阶共同邻节点的链路预测算法(CN2算法)。以7个真实网络为例,通过计算分析AUC值(ROC曲线下的面积)测试算法预测精确度,将测试集数据划分为5%~50%的不同比例以测试算法的鲁棒性。综合得出CN2算法的链路预测准确性较CN算法在7个网络中平均提升9.9%左右,并且鲁棒性更优。

The link prediction Common Neighbor algorithm(CN algorithm)has the disadvantages of low prediction accuracy and being unsuitable for multi-type networks.Based on the CN algorithm,this paper proposes a link prediction algorithm that extends the concept of common neighbors to the second order.The algorithm divides the neighbor nodes of the nodes to be predicted into three types,and different types of neighbor nodes are assigned different weights to establish a link prediction algorithm based on Second-order Common Neighbor nodes(CN2 algorithm).Taking seven real networks as examples,the prediction accuracy of the algorithm is tested by calculating and analyzing the AUC(Area under the ROC Curve)value,and the robustness of the algorithm is tested by dividing the test set data into different proportions ranging from 5%to 50%.Comprehensive results show that the link prediction accuracy of the CN2 algorithm is improved by an average of about 9.9%compared to CN algorithm in the seven networks,and it has better robustness.