《表2 经典算法时间复杂度分析》

《表2 经典算法时间复杂度分析》   提示:宽带有限、当前游客访问压缩模式
本系列图表出处文件名:随高清版一同展现
《一种基于网络嵌入的社区发现方法》


  1. 获取 高清版本忘记账户?点击这里登录
  1. 下载图表忘记账户?点击这里登录

给定一个包含n个节点,m条边,共识嵌入矩阵为Y∈Rn×1的属性图,令?k?=2m/n表示属性图的平均度,同时假设每个节点的邻居存储于有序的邻接链表.计算节点的“声誉”(Step 2)的时间复杂度为o(m?k?+ml);初始化K个质心(Steps 3-17)需要的时间复杂度为O(n logn+m);K-means++算法(Steps 19-29)的时间开销为O(nKlT),其中T表示算法的迭代次数.综上所述,LIK-means算法的整体时间复杂度为O(m?k?+ml+nlogn+m+nKlT).考虑真实网络中logn≈?k?≈K,因此算法的时间复杂度可简化为O(mlT).与其他经典社区发现算法的时间复杂度相比(如表2所示),LIK-means算法有较好的可扩展性.