流模式下有向近似覆盖图算法研究
|
摘要
随着社交网络、交通网络、生物信息网等领域的分析需求快速增长,大规模图数据的处理逐渐成为信息技术领域新的挑战.近似覆盖图技术可以通过选取原图的子图,同时保证子图中任意节点间距离的增加在覆盖因子的约束范围内,从而降低大规模图存储与计算开销.当前相关工作主要研究无向图的近似覆盖图技术,针对于此,提出一种有向近似覆盖图算法,重新定义了簇集以及簇边、桥边、自由边3类关建边,并理论分析基于3类关键边的(3,2)近似覆盖图构建正确性.在此基础上,给出图数据以流模式到达时的近似覆盖图计算算法.算法通过判断边端点的类型进行边的积累聚簇及更新,进而得到全图近似覆盖结果,算法空间复杂度为O(■).最后以基于幂率模型的人工数据集为实验对象,验证算法满足覆盖因子(3,2)的有向近似覆盖图定义,且空间与时间开销较小.
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(■), 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.
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(■), 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.
引文
[1]Dong Rongsheng, Zhang Xinkai, Liu Huadong, et al. Representation and operations research of k2-MDD in large-scale graph data[J]. Journal of Computer Research and Development, 2016, 52(12): 2783- 2792 (in Chinese)(董荣胜, 张新凯, 刘华东, 等. 大规模图数据的k2-MDD表示方法与操作研究[J]. 计算机研究与发展, 2016, 52(12): 2783- 2792)
[2]Baswana S, Kavitha T, Mehlhorn K, et al. New constructions of (α, β)-spanners and purely additive spanners[C] //Proc of the 16th ACM-SIAM Symp on Discrete Algorithms. Philadelphia: SIAM, 2005: 672- 681
[3]Baswana S, Sen S. A simple linear time algorithm for computing (2k-1)-spanner of O(n1+1/k) size for weighted graphs[C] //Proc of the 30th Int Conf on Automata, Languages and Programming. Berlin: Springer, 2003: 384- 396
[4]Roditty L, Thorup M, Zwick U. Deterministic constructions of approximate distance oracles and spanners [C] //Proc of the 32nd Int Conf on Automata, Languages and Programming. Berlin: Springer, 2005: 261- 272
[5]Ausiello G, Franciosa P G, Italiano G F. Small stretch spanners on dynamic graphs[J]. Journal of Graph Algorithms and Applications, 2005, 10(2): 365- 385
[6]Baswana S. Dynamic algorithms for graph spanners[C] //Proc of the 14th European Symp on Algorithms. Berlin: Springer, 2006: 76- 87
[7]Gottlieb L A, Roditty L. An optimal dynamic spanner for doubling metric spaces[C] //Proc of the 16th European Symp on Algorithms. Berlin: Springer, 2008: 478- 489
[8]Feigenbaum J, Kannan S, Mcgregor A, et al. Graph distances in the streaming model: The value of space[C] //Proc of the 16th ACM-SIAM Symp on Discrete Algorithms. Philadelphia: SIAM, 2005: 745- 754
[9]Baswana S. Faster streaming algorithms for graph apanners [EB/OL]. [2017-09-10]. http://arxiv.org/abs/cs/0611023v1
[10]Ausiello G, Franciosa P G, Italiano G F. Small stretch (α,β)-spanners in the streaming model[J]. Theoretical Computer Science, 2009, 410(36): 3406- 3413
[11]Wang Weifu, Balkcom D, Chakrabarti A. A fast streaming spanner algorithm for incrementally constructing sparse roadmaps[C] //Proc of the 25th IEEE/RSJ Int Conf on Intelligent Robots and Systems. Piscataway, NJ: IEEE, 2013: 1257- 1263
[12]Liebchen C, Wünsch G. The zoo of tree spanner problems[J]. Discrete Applied Mathematics, 2008, 156(5): 569- 587
[13]Dragan F F, Abu-Ata M. Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences [J]. Theoretical Computer Science, 2014, 547(27): 1- 17
[14]Bilò D, Colella F, Gualà L, et al. A faster computation of all the best swap edges of a tree spanner[C] //Proc of the 22nd Int Colloquium on Structural Information and Communication Complexity. Berlin: Springer, 2015: 239- 253
[15]Roditty L, Thorup M, Zwick U. Roundtrip spanners and roundtrip routing in directed graphs[J]. ACM Transactions on Algorithms, 2008, 4(3): 29:1- 29:17
[16]Pachocki J, Roditty L, Sidford A, et al. Approximating cycles in directed graphs: Fast algorithms for girth and roundtrip spanners[C] //Proc of the 29th ACM-SIAM Symp on Discrete Algorithms. New York: ACM, 2018: 1374- 1392
[17]Zhu Chunjiang, Lam K Y. Source-wise round-trip spanners[J]. Information Processing Letters, 2017, 124(8): 42- 45
[18]Peleg D, Roditty L. Localized spanner construction for ad hoc networks with variable transmission range[J]. ACM Transactions on Sensor Networks, 2010, 7(3): 25:1- 25:14
[19]Kaplan H, Mulzer W, Roditty L, et al. Spanners and reachability oracles for directed transmission graphs[C] //Proc of the 31st Int Symp on Computational Geometry. Wadern, Saarland, Germany: Dagstuhl, 2015: 156- 170
[20]Adamic L A, Huberman B A, Barabási A L, et al. Power-law distribution of the world wide web[J]. Science, 2000, 287(5461): 2115
[21]Liu Dayou, Jin Di, He Xiaodong, et al. Community mining in complex network[J]. Journal of Computer Research and Development, 2013, 50(10): 2140- 2154 (in Chinese)(刘大有, 金弟, 何东晓, 等. 复杂网络社区挖掘综述[J]. 计算机研究与发展, 2013, 50(10): 2140- 2154)
[22]Boccaletti S, Bianconi G, Criado R, et al. The structure and dynamics of multilayer networks[J]. Physics Reports, 2014, 544(1): 1- 122
[23]Chakrabarti D, Zhan Yiping, Faloutsos C. R-MAT: A recursive model for graph mining[C] //Proc of the 4th SIAM Int Conf on Data Mining. Philadelphia: SIAM, 2004: 442- 446
[2]Baswana S, Kavitha T, Mehlhorn K, et al. New constructions of (α, β)-spanners and purely additive spanners[C] //Proc of the 16th ACM-SIAM Symp on Discrete Algorithms. Philadelphia: SIAM, 2005: 672- 681
[3]Baswana S, Sen S. A simple linear time algorithm for computing (2k-1)-spanner of O(n1+1/k) size for weighted graphs[C] //Proc of the 30th Int Conf on Automata, Languages and Programming. Berlin: Springer, 2003: 384- 396
[4]Roditty L, Thorup M, Zwick U. Deterministic constructions of approximate distance oracles and spanners [C] //Proc of the 32nd Int Conf on Automata, Languages and Programming. Berlin: Springer, 2005: 261- 272
[5]Ausiello G, Franciosa P G, Italiano G F. Small stretch spanners on dynamic graphs[J]. Journal of Graph Algorithms and Applications, 2005, 10(2): 365- 385
[6]Baswana S. Dynamic algorithms for graph spanners[C] //Proc of the 14th European Symp on Algorithms. Berlin: Springer, 2006: 76- 87
[7]Gottlieb L A, Roditty L. An optimal dynamic spanner for doubling metric spaces[C] //Proc of the 16th European Symp on Algorithms. Berlin: Springer, 2008: 478- 489
[8]Feigenbaum J, Kannan S, Mcgregor A, et al. Graph distances in the streaming model: The value of space[C] //Proc of the 16th ACM-SIAM Symp on Discrete Algorithms. Philadelphia: SIAM, 2005: 745- 754
[9]Baswana S. Faster streaming algorithms for graph apanners [EB/OL]. [2017-09-10]. http://arxiv.org/abs/cs/0611023v1
[10]Ausiello G, Franciosa P G, Italiano G F. Small stretch (α,β)-spanners in the streaming model[J]. Theoretical Computer Science, 2009, 410(36): 3406- 3413
[11]Wang Weifu, Balkcom D, Chakrabarti A. A fast streaming spanner algorithm for incrementally constructing sparse roadmaps[C] //Proc of the 25th IEEE/RSJ Int Conf on Intelligent Robots and Systems. Piscataway, NJ: IEEE, 2013: 1257- 1263
[12]Liebchen C, Wünsch G. The zoo of tree spanner problems[J]. Discrete Applied Mathematics, 2008, 156(5): 569- 587
[13]Dragan F F, Abu-Ata M. Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences [J]. Theoretical Computer Science, 2014, 547(27): 1- 17
[14]Bilò D, Colella F, Gualà L, et al. A faster computation of all the best swap edges of a tree spanner[C] //Proc of the 22nd Int Colloquium on Structural Information and Communication Complexity. Berlin: Springer, 2015: 239- 253
[15]Roditty L, Thorup M, Zwick U. Roundtrip spanners and roundtrip routing in directed graphs[J]. ACM Transactions on Algorithms, 2008, 4(3): 29:1- 29:17
[16]Pachocki J, Roditty L, Sidford A, et al. Approximating cycles in directed graphs: Fast algorithms for girth and roundtrip spanners[C] //Proc of the 29th ACM-SIAM Symp on Discrete Algorithms. New York: ACM, 2018: 1374- 1392
[17]Zhu Chunjiang, Lam K Y. Source-wise round-trip spanners[J]. Information Processing Letters, 2017, 124(8): 42- 45
[18]Peleg D, Roditty L. Localized spanner construction for ad hoc networks with variable transmission range[J]. ACM Transactions on Sensor Networks, 2010, 7(3): 25:1- 25:14
[19]Kaplan H, Mulzer W, Roditty L, et al. Spanners and reachability oracles for directed transmission graphs[C] //Proc of the 31st Int Symp on Computational Geometry. Wadern, Saarland, Germany: Dagstuhl, 2015: 156- 170
[20]Adamic L A, Huberman B A, Barabási A L, et al. Power-law distribution of the world wide web[J]. Science, 2000, 287(5461): 2115
[21]Liu Dayou, Jin Di, He Xiaodong, et al. Community mining in complex network[J]. Journal of Computer Research and Development, 2013, 50(10): 2140- 2154 (in Chinese)(刘大有, 金弟, 何东晓, 等. 复杂网络社区挖掘综述[J]. 计算机研究与发展, 2013, 50(10): 2140- 2154)
[22]Boccaletti S, Bianconi G, Criado R, et al. The structure and dynamics of multilayer networks[J]. Physics Reports, 2014, 544(1): 1- 122
[23]Chakrabarti D, Zhan Yiping, Faloutsos C. R-MAT: A recursive model for graph mining[C] //Proc of the 4th SIAM Int Conf on Data Mining. Philadelphia: SIAM, 2004: 442- 446