《表2 增量占图镜像总边数的0.5%时, Inc-SCC各执行部分的时间开销》

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

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

《一种高效的面向动态有向图的增量强连通分量算法》

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

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

实验1测试Inc-SCC中各部分的时间开销.由于Inc-SCC中预处理过程可以与动态有向图的数据更新过程相互重叠从而忽略其时间开销，因此本文不考虑预处理过程的开销对算法的影响.将动态有向图变化时的增量的尺寸设置为占图镜像中边数总量的0.5%.表2展示了实验结果.数据显示，对于参与实验的6个不同的数据集，在Inc-SCC实际执行计算的两个阶段中，LocalFBS阶段的平均时长占总运行时长的95%以上，LocalColoring阶段只占时间开销中极小的一部分.实验1表明，受到影响的SCCs内部的大部分图顶点仍然与根顶点属于同一个SCC，在LocalFBS阶段中可提取出这些图顶点.剩余的少量图顶点经过图迭代染色后，算法很快就收敛结束.这符合本文对受到影响的SCCs内部结构变化的分析，显示出所提出的启发性算法能加快图迭代的收敛，提升算法性能.