《表1 经典算法的时间复杂度比较》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《时态网络节点相似性度量及链路预测算法》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

CN指标[14]的时间复杂度与节点的度有关，假设网络节点数为N，整个网络的平均度为k，则计算共同邻居的时间复杂度为O（k），则CN算法的时间复杂度为O（N2k）．基于共同邻居的JC，AA，RA算法[15]与CN算法有类似的计算过程，因此它们有相同的时间复杂度．基于随机游走的SimRank算法[16]的时间复杂度为O（Nkl），其中l是随机游走的步数．本文所提出的两种相似性度量方法NCC和NCCP需要计算节点的聚类系数，进行链路预测过程的时间复杂度为O（N2k）．以上算法的时间复杂度比较如表1所示．