Journal of Frontiers of Computer Science and Technology ›› 2017, Vol. 11 ›› Issue (5): 822-832.DOI: 10.3778/j.issn.1673-9418.1605039

Previous Articles     Next Articles

Link Prediction Algorithm Based on Node Similarity of Triadic Closure

GAO Yang, ZHANG Yanping, QIAN Fulan+, ZHAO Shu   

  1. School of Computer Science and Technology, Anhui University, Hefei 230601, China
  • Online:2017-05-01 Published:2017-05-04

基于三元闭包的节点相似性链路预测算法

高  杨,张燕平钱付兰+,赵  姝   

  1. 安徽大学 计算机科学与技术学院,合肥 230601

Abstract:  Link prediction is a fundamental method for analyzing complex network which has been widely used in many domains. Link prediction in complex network based on solely topological information is a challenging problem. As one of the basic local structure, triadic closure has the characteristics of structural balance and stability. This paper proposes a link prediction algorithm to measure the similarity of nodes based on triadic closure. By calculating the weight of each node in the network according to the triadic closure, and using the weights in the node similarity index, this paper proposes three similarity indexes of TWCN, TWAA, TWRA and the other three similarity indexes of TWCN*, TWAA*, TWRA* with adjustment parameter. The experimental results on ten real network datasets demonstrate that the new method can improve the accuracy of link prediction. Moreover, by analyzing the experiment results, this paper finds that the network with more triadic closure nodes tends to be more stable. In other words, a network with less triadic closure nodes is less stable, and it is more likely to establish a new link with others. This phenomenon is also consistent with some related phenomenon in sociology on weak relations to generate links.

Key words: complex networks, link prediction, triadic closure, node weight

摘要: 链路预测作为复杂网络分析的基本方法被应用到很多领域,完全基于拓扑结构信息的复杂网络链路预测仍然是一个具有挑战性的问题。三元闭包作为网络中最小局部结构,具有结构平衡和稳定的特征。提出了一种基于三元闭包的节点相似性链路预测算法,通过计算出每个节点在网络中所占三元闭包的权重,并将该权重用于节点相似性指标中,提出了3个相似性指标TWCN、TWAA、TWRA和具有调节参数的3个相似性指标TWCN*、TWAA*、TWRA*。在10个不同的网络数据集上的实验结果表明,所提算法能够提高链路预测的精度。不仅如此,通过分析实验结果,发现在社交网络中拥有较多三元闭包的节点具有局部稳定性,不倾向于建立更多的新链接;相反,拥有较少三元闭包的节点具有局部不稳定性,倾向于建立更多的新链接。这种现象也符合社会学中有关弱关系产生链接的现象。

关键词: 复杂网络, 链路预测, 三元闭包, 节点权重