首页 期刊 计算机研究与发展 流模式下有向近似覆盖图算法研究 【正文】

流模式下有向近似覆盖图算法研究

作者:张昕; 李晓光 辽宁大学信息学院; 沈阳110036
有向图   近似覆盖图   覆盖因子   聚簇   数据流  

摘要:随着社交网络、交通网络、生物信息网等领域的分析需求快速增长,大规模图数据的处理逐渐成为信息技术领域新的挑战.近似覆盖图技术可以通过选取原图的子图,同时保证子图中任意节点间距离的增加在覆盖因子的约束范围内,从而降低大规模图存储与计算开销.当前相关工作主要研究无向图的近似覆盖图技术,针对于此,提出一种有向近似覆盖图算法,重新定义了簇集以及簇边、桥边、自由边3类关建边,并理论分析基于3类关键边的(3,2)近似覆盖图构建正确性.在此基础上,给出图数据以流模式到达时的近似覆盖图计算算法.算法通过判断边端点的类型进行边的积累聚簇及更新,进而得到全图近似覆盖结果,算法空间复杂度为 O(n^2/4).最后以基于幂率模型的人工数据集为实验对象,验证算法满足覆盖因子(3,2)的有向近似覆盖图定义,且空间与时间开销较小.

注:因版权方要求,不能公开全文,如需全文,请咨询杂志社

学术咨询 免费咨询 杂志订阅