加权网络中基于多路径节点相似性的链接预测

Link prediction based on similarity of nodes of multipath in weighted social networks

鉴于现有大多数链接预测算法仅考虑了图的局部或全局特性,在预测准确率和计算复杂度上难以均衡,且有关加权网络的链接预测研究相对较少,提出新的加权社会网络链接预测算法(STNMP).引入节点对边权强度的概念,用于度量邻居节点间的局部相似度.提出路径相似性贡献的概念,定义多路径传输节点相似性,用于描述步长为2和3的所有路径及这些路径上的中间节点对于所连接的两个节点的相似性总贡献.在多个真实网络中对算法的有效性进行验证,以AUC作为评价指标,与经典相似性算法CN、Jaccard、AA等进行预测准确率的对比分析.结果显示,针对小规模社会网络,STNMP算法的预测准确率高于现有算法.

A novel algorithm similarity based on transmission nodes of multipath （STNM P） for link predictionin weighted social networks was proposed in view of the fact that most link prediction algorithms onlyconsidered local or global characteristics of the graph, which was difficult to achieve equilibrium in the predictionaccuracy and the computational complexity, and researches on link prediction in weighted socialnetworks were relatively less. The concept of the edge weight strength was introduced to measure the localsimilarity of neighbor node pairs. The similarity of transmission nodes of multipath was proposed and thedefinition of the path similarity contribution was given, which were used to describe the total contributionof all these paths of 2 and 3 paces to the similarity of node pairs. The effectiveness of the algorithm wasverified through experiments on many real networks. The comparison and analysis on prediction accuracyof the algorithm were conducted with those classical link prediction algorithms based on the similarity index,such as common neighbor （CN ）, Jaccard and Adamic-Adar under the evaluation index of area underthe receiver operating characteristic curve （AUC ）. Results showed the accuracy of STNMP algorithm washigher than those of existing algorithms for small scale of social network.