Improving the accuracy of link prediction by combining similarities of node pairs
Improving the accuracy of link prediction by combining similarities of node pairs
复制标题
DOI：
10.1527/tjsai.26.427
复制
发表时间：
2011
影响因子：
--
通讯作者：
Takeshi Motoda;T. Murata
中科院分区：
文献类型：
--
作者：
Takeshi Motoda;T. Murata
近年来，网络分析在多个科学领域得到了广泛的研究。链接预测是基于观察到的链接来预测两个实体之间是否存在链接的问题，是链接挖掘的热门任务之一。虽然已经提出了许多链接预测方法，但它们都有各自的优缺点。1)为了获得选择最佳链路预测方法的策略，我们对39个实际网络进行了六种链路预测方法(公共邻居(CN)、Jaccard系数(JC)、Adama/Adar(AA)、最短路径(SP)、优先连接(PA)和层次随机图(HRG))的实验。2)提出了一种新的相似度，即基于Logistic回归的相似度之和。我们使用了10次交叉验证和袋装的方法进行模型选择。我们在28个数据集上对HRG、所提出的方法(袋化)和所提出的方法(10倍交叉验证)的精度和计算时间进行了估计。结果表明：1)对于聚类系数大于0.4的网络，CN、JC和AA具有较好的性能。对于平均最短路径长度大于3的网络，SP具有良好的性能。对于阶数小于0.5的网络，PA的性能逊于随机预测器。HRG的表现一直很好。结果表明，对于17个数据集，本文提出的方法(装袋方法和10倍交叉验证方法)的计算精度均高于HRG方法，且计算速度快于HRG方法。提出的方法对社会网络、引文网络、词典网络、生物网络和转移网络(旅程)都有较好的准确率。所提出的方法在贸易网络、电路网络和食物网络中表现不佳。有时，所提出的方法(装袋)达到比所提出的方法(10倍交叉验证)更高的准确度。所提出的方法(10倍交叉验证)比所提出的方法(装袋)更快地完成计算。综上所述，本文提出的方法比HRG算法计算速度快，精度达到了HRG算法的要求。
Recently, network analysis has been intensively investigated in several fields of science. Link prediction is a problem of predicting the existence of a link between two entities based on observed links, and it is one of the popular link mining tasks. Although many link prediction methods have been proposed, they have their merits and demerits. In this paper, we present two topics as follows: 1) In order to obtain the strategies of selecting the best link prediction methods, we perform experiments of six link prediction methods (Common Neighbors (CN) , Jaccard's Coefficient (JC) , Adamic/Adar (AA) , Shortest Path (SP) , Preferential Attachment (PA) and Hierarchical Random Graph (HRG) ) for 39 real networks. 2) We propose a new similarity that is the summation of similarities based on the logistic regression. We used 10-fold cross validation and bagging for model selection of proposed method. We estimate the accuracy and computation time of HRG, proposed method (bagging) and proposed method (10-fold cross validation) for 28 data sets. As a result of 1) , CN, JC and AA achieve good performance for the networks that has higher clustering coefficient than 0.4. SP achieves good performance for the network that has higher average shortest path length than 3. PA underperforms the random predictor for the network has lower variance of degrees than 0.5. HRG performs consistently well. As a result of 2) , accuracy of proposed methods (both of bagging and 10-fold cross validation) are reached higher than the accuracy of HRG for 17 data sets and finishes the calculation faster than HRG. Proposed methods perform good accuracy for social network, citation network, dictionary network, biological network and transfer network (journey). Proposed methods underperform for trade network, circuit network, and food web network. Sometimes, proposed method (bagging) reaches higher accuracy than the accuracy of proposed method (10-fold cross validation). Proposed method (10-fold cross validation) finishes the calculation faster than proposed method (bagging). In conclusion, proposed methods finish the calculation faster than HRG and accuracy of proposed methods reaches higher than HRG.