ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (3): 655-665.doi: 10.7544/issn1000-1239.2019.20170680

• 人工智能 • 上一篇    下一篇

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

张昕,李晓光   

  1. (辽宁大学信息学院 沈阳 110036) (zhangxin1979@hotmail.com)
  • 出版日期: 2019-03-01
  • 基金资助: 
    国家自然科学基金项目(U1811261,61802160);辽宁省公共舆情与网络安全大数据系统工程实验室基金项目(2016-294)

Spanner Algorithm for Directed Graph Stream

Zhang Xin, Li Xiaoguang   

  1. (College of Information, Liaoning University, Shenyang 110036)
  • Online: 2019-03-01

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

关键词: 有向图, 近似覆盖图, 覆盖因子, 聚簇, 数据流

Abstract: With the rapid growth of analysis demand in many fields such as social network, transportation network, and bioinformatics network, the processing of large-scale graph data has become a new challenge of information technology. Graph spanner is a subgraph in which the distance between every pair of vertices falling into the given range defined by stretch factor. With the spanner, the storage and computational cost are reduced greatly for large-scale graph data processing. Most of existing research work focused on the spanner on undirected graph, and we propose an effective algorithm for directed graph spanner. Firstly, we re-define the concept of cluster set and three kinds of crucial edges including cluster edge, bridge edge and free edge, and analyze theoretically the correctness of (3,2)-spanner construction based on the crucial edges. Moreover, we propose a spanner algorithm for graph data in streaming model in which the edges is clustered and updated according to the type of end-point of edge, and then a (3,2)-spanner of full graph is constructed. Finally, we provide the theoretical analysis of space complexity O(n\+2/4), and present the experiments on the synthetic graph of power law model. Experiment results show our algorithm meet the definition of (3,2)-spanner, and has low time and space overhead.

Key words: directed graph, spanner, stretch factor, cluster, data stream

中图分类号: