基于聚类分析的复杂网络链路预测性能研究

来骥 盛红雷

摘   要：链路预测问题是复杂网络中数据挖掘领域的重要研究方向，然而复杂网络的结构与预测方法性能之间关系却很少受到关注。从聚类分析的角度探讨复杂网络结构对现有基于相似性度量的六种链路预测方法的性能影响，通过对合成复杂网络和真实复杂网络的对比实验进行分析。结果表明：随着聚类簇的增加，这六种方法在预测精度方面的性能均得到了极大的提升。对于具有较低聚类簇的稀疏复杂网络，叠加随机游动（SRW）预测性能表现最佳，而对于具有较高聚类簇的密集复杂网络，资源分配指数（RA）预测性能表现最佳。因此，对于不同类型的复杂网络应采用不同的方法进行链路预测。

关键词：复杂网络;链路预测;聚类分析;相似性度量;

中图分类号：TP319                                            文獻标识码：A

Research on Link Prediction Performance of Complex

Networks Based on Clustering Analysis

LAI Ji1？覮，SHENG Hong-lei2

（ 1. State Grid Jibei Information & Telecommunication Company ，Beijing 100053，China.

2. Nari Group Co.，Ltd（State Grid Electric Power Research Institute），Nanjing，Jiangsu 210000，China）

Abstract：Link prediction is an important research direction in the field of data mining in complex networks. However，the relationship between the structure of complex networks and the performance of prediction methods has received little attention. this paper discusses the effect of complex network structure on the performance of six existing link prediction methods based on similarity measure from the perspective of clustering analysis. The performance of the method has been greatly improved in terms of prediction accuracy. For sparse complex networks with low clustering，SRW performs best，while for dense complex networks with high clustering，RA performs best. Therefore，different methods should be adopted for link prediction in different types of complex networks.

Key words：complex network;link prediction;clustering analysis;similarity measure