网络结构特征与链路预测算法关系研究

以美国航空网络、科学家合作网络和线虫新陈代谢网络等5种实际网络为例进行了综合实验,用结果数据定量化描述了同配系数、集聚系数和网络效率等网络结构特征参数,与基于局部信息和全局信息的两类链路预测方法结果之间的关系。通过对结果的分析,得到了网络同配系数为正且聚集系数大于阈值(约0.1)时适用基于局部信息的预测方法,否则适用基于全局信息的预测方法;以及集聚系数、网络效率与局部信息预测方法的结果成正比,与全局信息预测方法成反比等结论。这些结论为通过网络特征参数进行链路预测方法的选择提供了定量化的参考依据。

On the Relationship Between Network Structure Features and Link Prediction Algorithms

This paper experimented with five virtual networks, such as the Air network of US, the Coauthorship network of Scientists, the Neural network of the nematode C, etc.and quantified the relationship between the network structure features and the link prediction algorithms by the experiment's data.The network structure features could be measured by assortativity coefficient, clustering coefficient, etc.and the link prediction algorithms could be divided into local-information based and global-information based.After analyzed the data, we found that if the value of network's assortativity coefficient is positive and the value of network's clustering coefficient is greater than the threshold which is about 0.1, the local-information based would be the better choice, otherwise the global-information based would be better.And the clustering coefficient and the network efficiency is proportional to the result of link prediction algorithms based local information and is reverse proportional to the result of algorithms based global information.These conclusions provide quantitative basis for selecting the right algorithm.