链路预测中一种改进的相似度指标算法

Improved Similarity Index Algorithm for Link Prediction

网络中的链路预测是指,如何通过已知的网络结构等信息预测网络中尚未产生连边的两个节点之间产生连接的可能性.而基于节点属性及局部信息的相似性的方法,往往计算简单而直接,计算复杂度低,且能取得较好的预测效果,比较适合大规模的网络应用.但往往各相似度算法只分别考虑到了,终节点自身的度数以及共同邻居的度数在相似指标中发挥的作用,而没有考虑到共同邻居对不同终节点自身的影响.本文通过分析、比较,现有的根据节点度数及共同邻居数量的相似度指标算法,验证各算法的侧重点以及预测效果.并且提出了一个新的CRA指标算法,进一步区分了计算相似指标时不同邻居节点对两个终节点的贡献.通过在多个不同的真实网络中进行重复试验,由平均预测结果得出算法的预测效果与其他依靠共同邻居指标的算法相比都得到了不同程度的提升.

Link prediction in networks is that using the existing known network structure or node information to predict the possibility between the two nodes which haven＇t connected to each other. It＇s important to learn about the evolution mechanism of network and the interaction relationship of nodes. The link possibility between nodes is closely related to the similarity. The method which is based on the node attributes and local information has the simple and direct calculation and better effect of prediction. So it is more suitable for the large-scale network applications. But it only considers the degree of final nodes or neighbor nodes and the number of neighbor nodes. Does not take into account that each neighbor nodes has the different effect for the different final nodes. This paper through ex- periments to analysis and compare different similarity contribution of neighbor nodes and end points. And further verified the weak-link effect in networks. Also we proposed a new common neighbor measurement algorithm, through distinguish the influence of each common neighbor for the different end nodes so that the prediction accuracy has been further improved.