《表2 经典算法时间复杂度分析》
给定一个包含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算法有较好的可扩展性.
图表编号 | XD0058065800 严禁用于非法目的 |
---|---|
绘制时间 | 2019.08.25 |
作者 | 王瑞国、叶雅玲、卜湛 |
绘制单位 | 南京财经大学软件工程系、南京财经大学软件工程系、南京财经大学软件工程系 |
更多格式 | 高清、无水印(增值服务) |