Abstract: Many network structure information-based link prediction algorithms estimate the similarity between nodes and perform link prediction by using the clustering degree of nodes. However, these algorithms only focus on the clustering coefficient of nodes in network, and do not consider the influence of link clustering coefficient between the predicted nodes and their common neighbor nodes on the similarity between nodes. Aiming at the problem, a link prediction algorithm combining node clustering coefficient and asymmetric link clustering coefficient was proposed. Firstly, the clustering coefficient of common neighbor node was calculated, and the average link clustering coefficient of the predicted nodes was obtained by using two asymmetric link clustering coefficients of common neighbor node. Then, a comprehensive measurement index was obtained by fusing these two clustering coefficients based on Dempster-Shafer(DS) theory, and by applying the index to Intermediate Probability Model (IMP), a new node similarity index, named IMP_DS, was designed. The experimental results on the data of nine networks show that the proposed algorithm achieves performance in terms of Area Under the Curve (AUC) of Receiver Operating Characteristic (ROC) and Precision in comparison with Common Neighbor (CN), Adamic-Adar (AA), Resource Allocation (RA) indexes and InterMediate Probability model based on Common Neighbor (IMP_CN).

Key words: link prediction, complex network, Dempster-Shafer (DS) theory, clustering coefficient, similarity index

摘要： 许多基于网络结构信息的链接预测算法利用节点的聚集程度评估节点间的相似性，进而执行链接预测；然而，该类算法只注重网络中节点的聚集系数，没有考虑预测节点与共同邻居节点之间的链接聚集系数对节点间相似性的影响。针对上述问题，提出了一种融合节点聚集系数和非对称链接聚集系数的链接预测算法。首先，计算共同邻居节点的聚集系数，并利用共同邻居节点对应的两个非对称链接聚集系数计算该预测节点的平均链接聚集系数；然后，基于Dempster-Shafer证据理论将两种聚集系数进行融合生成一个综合性度量指标，并将该指标应用于中间概率模型（IMP），得到一个新的节点相似性指标（IMP_DS）。在9个网络数据上的实验结果表明，该算法的受试者工作特征（ROC）的曲线下方面积（AUC）与精度值（Precision）优于共同邻居（CN）、Adamic-Adar（AA）、资源分配（RA）指标和基于共同邻居的中间概率模型（IMP_CN）。

关键词: 链接预测, 复杂网络, Dempster-Shafer理论, 聚集系数, 相似性指标