• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
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

More Information
  • Published Date: February 28, 2019
  • 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.
  • Related Articles

    [1]Liu Le, Guo Shengnan, Jin Xiyuan, Zhao Miaomiao, Chen Ran, Lin Youfang, Wan Huaiyu. Spatial-Temporal Traffic Data Imputation Method with Uncertainty Modeling[J]. Journal of Computer Research and Development, 2025, 62(2): 346-363. DOI: 10.7544/issn1000-1239.202330455
    [2]Xu Xiao, Ding Shifei, Sun Tongfeng, Liao Hongmei. Large-Scale Density Peaks Clustering Algorithm Based on Grid Screening[J]. Journal of Computer Research and Development, 2018, 55(11): 2419-2429. DOI: 10.7544/issn1000-1239.2018.20170227
    [3]Yang Zhuoqun, Jin Zhi. Self-Adaptive Decision Making Under Uncertainty in Environment and Requirements[J]. Journal of Computer Research and Development, 2018, 55(5): 1014-1033. DOI: 10.7544/issn1000-1239.2018.20161039
    [4]Ren Lifang, Wang Wenjian, Xu Hang. Uncertainty-Aware Adaptive Service Composition in Cloud Computing[J]. Journal of Computer Research and Development, 2016, 53(12): 2867-2881. DOI: 10.7544/issn1000-1239.2016.20150078
    [5]Xu Zhengguo, Zheng Hui, He Liang, Yao Jiaqi. Self-Adaptive Clustering Based on Local Density by Descending Search[J]. Journal of Computer Research and Development, 2016, 53(8): 1719-1728. DOI: 10.7544/issn1000-1239.2016.20160136
    [6]Zhang Zhifei, Miao Duoqian, Nie Jianyun, Yue Xiaodong. Sentiment Uncertainty Measure and Classification of Negative Sentences[J]. Journal of Computer Research and Development, 2015, 52(8): 1806-1816. DOI: 10.7544/issn1000-1239.2015.20150253
    [7]Xu Min, Deng Zhaohong, Wang Shitong, Shi Yingzhong. MMCKDE: m-Mixed Clustering Kernel Density Estimation over Data Streams[J]. Journal of Computer Research and Development, 2014, 51(10): 2277-2294. DOI: 10.7544/issn1000-1239.2014.20130718
    [8]Pan Weimin and He Jun. Neuro-Fuzzy System Modeling with Density-Based Clustering[J]. Journal of Computer Research and Development, 2010, 47(11): 1986-1992.
    [9]Yu Canling, Wang Lizhen, and Zhang Yuanwu. An Enhancement Algorithm of Cluster Boundaries Precision Based on Grid's Density Direction[J]. Journal of Computer Research and Development, 2010, 47(5): 815-823.
    [10]Chen Jianmei, Lu Hu, Song Yuqing, Song Shunlin, Xu Jing, Xie Conghua, Ni Weiwei. A Possibility Fuzzy Clustering Algorithm Based on the Uncertainty Membership[J]. Journal of Computer Research and Development, 2008, 45(9): 1486-1492.

Catalog

    Article views (900) PDF downloads (247) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return