來驥 盛紅雷

摘? ?要：鏈路預(yù)測問題是復(fù)雜網(wǎng)絡(luò)中數(shù)據(jù)挖掘領(lǐng)域的重要研究方向，然而復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)與預(yù)測方法性能之間關(guān)系卻很少受到關(guān)注。從聚類分析的角度探討復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)對現(xiàn)有基于相似性度量的六種鏈路預(yù)測方法的性能影響，通過對合成復(fù)雜網(wǎng)絡(luò)和真實(shí)復(fù)雜網(wǎng)絡(luò)的對比實(shí)驗(yàn)進(jìn)行分析。結(jié)果表明：隨著聚類簇的增加，這六種方法在預(yù)測精度方面的性能均得到了極大的提升。對于具有較低聚類簇的稀疏復(fù)雜網(wǎng)絡(luò)，疊加隨機(jī)游動(dòng)（SRW）預(yù)測性能表現(xiàn)最佳，而對于具有較高聚類簇的密集復(fù)雜網(wǎng)絡(luò)，資源分配指數(shù)（RA）預(yù)測性能表現(xiàn)最佳。因此，對于不同類型的復(fù)雜網(wǎng)絡(luò)應(yīng)采用不同的方法進(jìn)行鏈路預(yù)測。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò);鏈路預(yù)測;聚類分析;相似性度量;

中圖分類號(hào)：TP319? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：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