A Parallel Algorithm for Generating a Random Graph with a Prescribed Degree Sequence

被引:0
作者
Bhuiyan, Hasanuzzaman [1 ,3 ]
Khan, Maleq [2 ]
Marathe, Madhav [1 ]
机构
[1] Virginia Tech, Biocomplex Inst, NDSSL, Dept Comp Sci, Blacksburg, VA 24061 USA
[2] Texas A&M Univ Kingsville, Dept Elect Engn & Comp Sci, Kingsville, TX USA
[3] Microsoft Inc, Redmond, WA 98052 USA
来源
2017 IEEE INTERNATIONAL CONFERENCE ON BIG DATA (BIG DATA) | 2017年
关键词
graph theory; random graph generation; degree sequence; Erdos-Gallai characterization; parallel algorithms; NETWORKS;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Random graphs (or networks) have gained a significant increase of interest due to its popularity in modeling and simulating many complex real-world systems. Degree sequence is one of the most important aspects of these systems. Random graphs with a given degree sequence can capture many characteristics like dependent edges and non-binomial degree distribution that are absent in many classical random graph models such as the Erdos-Renyi graph model. In addition, they have important applications in uniform sampling of random graphs, counting the number of graphs having the same degree sequence, as well as in string theory, random matrix theory, and matching theory. In this paper, we present an OpenMP-based shared-memory parallel algorithm for generating a random graph with a prescribed degree sequence, which achieves a speedup of 20.4 with 32 cores. We also present a comparative study of several structural properties of the random graphs generated by our algorithm with that of the real-world graphs and random graphs generated by other popular methods. One of the steps in our parallel algorithm requires checking the Erdos-Gallai characterization, i.e., whether there exists a graph obeying the given degree sequence, in parallel. This paper presents a non-trivial parallel algorithm for checking the Erdos-Gallai characterization, which achieves a speedup of 23 with 32 cores.
引用
收藏
页码:3312 / 3321
页数:10
相关论文
共 44 条
[1]  
Abdelhamid S. E., 2012, P 8 IEEE INT C E SCI, P1
[2]   Parallel Algorithms for Generating Random Networks with Given Degree Sequences [J].
Alam, Maksudul ;
Khan, Maleq .
INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING, 2017, 45 (01) :109-127
[3]  
Aluru S., 2012, INT C HIGH PERF COMP, P7
[4]  
[Anonymous], 2016, SIGKDD Explor., DOI DOI 10.1145/2897350.2897355
[5]   Realizing degree sequences in parallel [J].
Arikati, SR ;
Maheshwari, A .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (02) :317-338
[6]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[7]  
Barrett CL, 2009, WINT SIMUL C PROC, P948
[8]   A Sequential Algorithm for Generating Random Graphs [J].
Bayati, Mohsen ;
Kim, Jeong Han ;
Saberi, Amin .
ALGORITHMICA, 2010, 58 (04) :860-910
[9]  
Berge C., 1973, Graphs and hypergraphs, P1
[10]   Parallel algorithms for switching edges in heterogeneous graphs [J].
Bhuiyan, Hasanuzzaman ;
Khan, Maleq ;
Chen, Jiangzhuo ;
Marathe, Madhav .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2017, 104 :19-35