Advanced Search
    Zhang Xin, Li Xiaoguang. Spanner Algorithm for Directed Graph Stream[J]. Journal of Computer Research and Development, 2019, 56(3): 655-665. DOI: 10.7544/issn1000-1239.2019.20170680
    Citation: Zhang Xin, Li Xiaoguang. Spanner Algorithm for Directed Graph Stream[J]. Journal of Computer Research and Development, 2019, 56(3): 655-665. DOI: 10.7544/issn1000-1239.2019.20170680

    Spanner Algorithm for Directed Graph Stream

    • 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.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return