{'fraction_non_alphanumeric': 0.0355788096795291, 'fraction_numerical': 0.01170699803793329, 'mean_word_length': 4.46772751653853, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Parallel Algorithm for Generating a Random Graph with a Prescribed Degree Sequence

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 Erd\H{o}s-R\'{e}nyi graph model. In addition, they have important applications in the 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.5 with 32 cores. One of the steps in our parallel algorithm requires checking the Erd\H{o}s-Gallai characterization, i.e., whether there exists a graph obeying the given degree sequence, in parallel. This paper presents the first non-trivial parallel algorithm for checking the Erd\H{o}s-Gallai characterization, which achieves a speedup of 23 using 32 cores.


I. INTRODUCTION
Random graphs are widely used for modeling many complex real-world systems such as the Internet [1], biological [2], social [3], and infrastructure [4] networks to understand how the systems work through obtaining rigorous mathematical and simulation results. Many random graph models such as the Erdős-Rényi [5], the Preferential Attachment [6], the smallworld [7], and the Chung-Lu [8] models have been proposed to capture various characteristics of real-world systems. Degree sequence is one of the most important aspects of these systems and has been extensively studied in graph theory [9][10][11]. It has significant applications in a wide range of areas including structural reliability and communication networks because of the strong ties between the degrees of vertices and the structural properties of and dynamics over a network [12].
Random graphs with given degree sequences are widely used in uniform sampling of random graphs as well as in counting the number of graphs having the same degree sequence [13][14][15][16]. For example, in an epidemiology study of sexually transmitted diseases [17], anonymous surveys collect data about the number of sexual partners of an individual within a given period of time, and then the problem reduces to generating a network obeying the degree sequence collected from the survey, and studying the disease dynamics over the network. Other examples include determining the total number of structural isomers of chemical compounds such as alkanes, where the valence of an atom is the degree. Moreover, the random graphs with given degree sequences can capture many characteristics such as dependent edges and non-binomial degree distribution that are absent in many classical models such as the Erdős-Rényi [5] graph model. They also have important applications in string theory, random matrix theory, and matching theory [10].
The problem of generating a random graph with a given degree sequence becomes considerably easier if self-loops and parallel edges are allowed. Throughout this paper, we consider simple graphs with no self-loops or parallel edges. Most prior work on generating random graphs involves sequential algorithms, and they can be broadly categorized in two classes: (i) edge swapping and (ii) stubmatching. Edge swapping [18][19][20] uses the Markov chain Monte Carlo (MCMC) scheme on a given graph having the degree sequence. An edge swap operation replaces two edges e 1 = (a, b) and e 2 = (c, d), selected uniformly at random from the graph, by new edges e 3 = (a, d) and e 4 = (c, b), i.e., the end vertices of the selected edges are swapped with each other. This operation is repeated either a given number of times or until a specified criterion is satisfied. It is easy to see that the degree of each vertex remains invariant under an edge swap process. Unfortunately, very little theoretical results have been rigorously shown about the mixing time [18,21] of the edge swap process and they are ill-controlled. Moreover, most of the results are heuristic-based.
On the other hand, among the swap-free stub-matching methods, the configuration or pairing method [22] is very popular and uses a direct graph construction method. For each vertex, it creates as many stubs or "dangling half-edges" as of its degree. Then edges are created by choosing pairs of vertices randomly and connecting them. This approach creates parallel edges, which are dealt with by restarting the process. Unfortunately, the probability of restarting the process approaches 1 for larger degree sequences. Many variants [23][24][25] of the configuration models have been studied to avoid parallel edges for the regular graphs. By using the Havel-Hakimi method [26], a deterministic graph can be generated following a given degree sequence. Bayati et al. [15] presented an algorithm for counting and generating random simple graphs with given degree sequences. However, this algorithm does not guarantee to always generate a graph, and it is shown that the probability of not generating a graph is small for a certain bound on the maximum degree, which restricts many degree sequences. Genio et al. [16] presented an algorithm to generate a random graph from a given degree sequence, which can be used in sampling graphs from the graphical realizations of a degree sequence. Blitzstein et al. [14] also proposed a sequential importance sampling [27] algorithm to generate random graphs with an exact given degree sequence, which can generate every possible graph with the given degree sequence with a non-zero probability. Moreover, the distribution of the generated graphs can be estimated, which is a much-desired result used in sampling random graphs. A deterministic parallel algorithm for generating a simple graph with a given degree sequence has been presented by Arikati et al. [28], which runs in O (log n) time using O (n + m) CRCW PRAM [29] processors, where n and m denote the number of vertices and edges in the graph, respectively. From a given degree sequence, the algorithm first computes an appropriate bipartite sequence (degree sequence of a bipartite graph), generates a deterministic bipartite graph obeying the bipartite sequence, applies some edge swap techniques to generate a symmetric bipartite graph, and then reduces the symmetric bipartite graph to a simple graph having the given degree sequence. Another parallel algorithm, with a time complexity of O log 4 n using O n 10 EREW PRAM processors, has been presented in [30], where the maximum degree is bounded by the square-root of the sum of the degrees, which restricts many degree sequences. A parallel algorithm for generating a random graph with a given expected degree sequence has been presented in [31]. However, there is no existing parallel algorithm for generating random graphs following an exact degree sequence, which can provably generate each possible graph, having the given degree sequence, with a positive probability. In this paper, we present an efficient parallel algorithm for generating a random graph with an exact given degree sequence. We choose to parallelize the sequential algorithm by Blitzstein et al. [14] because of its rigorous mathematical and theoretical results, and the algorithm supports all of the important and muchdesired properties below, whereas the other algorithms are either heuristic-based or lack some of the following properties: • It can construct a random simple graph with a prescribed degree sequence. • It can provably generate each possible graph, obeying the given degree sequence, with a positive probability. • It can be used in importance sampling by explicitly measuring the weights associated with the generated graphs. • It is guaranteed to terminate with a graph having the prescribed degree sequence. • Given a degree sequence of a tree, a small tweak while assigning the edges allows the same algorithm to generate trees uniformly at random. • It can be used in estimating the number of possible graphs with the given degree sequence.
Our Contributions. In this paper, we present an efficient shared-memory parallel algorithm for generating random graphs with exact given degree sequences. The dependencies among assigning edges to vertices in a particular order to ensure the algorithm always successfully terminates with a graph, the requirement of keeping the graph simple, maintaining an exact stochastic process as that of the sequential algorithm, and concurrent writing by multiple cores in the global address space lead to significant challenges in designing a parallel algorithm. Dealing with these requires complex synchronization among the processing cores. Our parallel algorithm achieves a maximum speedup of 20.5 with 32 cores. We also present a comparative study of various structural properties of the random graphs generated by the parallel algorithm with that of the real-world graphs. One of the steps in our parallel algorithm requires checking the graphicality of a given degree sequence, i.e., whether there exists a graph with the degree sequence, using the Erdős-Gallai characterization [32] in parallel. We present here a novel parallel algorithm for checking the Erdős-Gallai characterization, which achieves a speedup of 23 using 32 cores.
Organization. The rest of the paper is organized as follows. Section II describes the preliminaries and notations used in the paper. Our main parallel algorithm for generating random graphs along with the experimental results are presented in Section III. We present a parallel algorithm for checking the Erdős-Gallai characterization of a given degree sequence accompanied by the performance evaluation of the algorithm in Section IV. Finally, we conclude in Section V.

II. PRELIMINARIES
Below are the notations, definitions, and computation model used in this paper.
Notations. We use G = (V, E) to denote a simple graph, where V is the set of vertices and E is the set of edges. A selfloop is an edge from a vertex to itself. Parallel edges are two or more edges connecting the same pair of vertices. A simple graph is an undirected graph with no self-loops or parallel edges. We are given a degree sequence D = (d 1 , d 2 , . . . , d n ). There are a total of n = |V| vertices labeled as 1, 2, . . . , n, and d i is the degree of vertex i, where 0 ≤ d i ≤ n − 1. For a degree sequence D and distinct u, v ∈ {1, 2, . . . , n}, we define D u,v to be the degree sequence obtained from D by If there is a simple graph G having the degree sequence D, then there are m = |E| edges in G, where 2m = i d i . The terms graph and network are used interchangeably throughout the paper. We use K, M, and B to denote thousands, millions, and billions, respectively; e.g., 1M stands for one million. For the parallel algorithms, let P be the number of processing cores, and P k the core with rank k, where 0 ≤ k < P. A summary of the frequently used notations (some of them are introduced later for convenience) is provided in Table I. Residual Degree. During the course of a graph generation process, the residual degree of a vertex u is the remaining number of edges incident on u, which have not been created yet. From hereon, we refer to the degree d u of a vertex u as the residual degree of u at any given time, unless otherwise specified.
Graphical Sequence. A degree sequence D of non-negative integers is called graphical if there exists a labeled simple graph with vertex set {1, 2, . . . , n}, where vertex i has degree d i . Such a graph is called a realization of the degree sequence D. Note that there can be several graphs having the same degree sequence. Eight equivalent necessary and sufficient conditions for testing the graphicality of a degree sequence are listed in [33].

Among them, the Erdős-Gallai characterization [32] is the most famous and frequently used criterion. Another popular recursive test for checking a graphical sequence is the Havel-Hakimi method [26].
Erdős-Gallai Characterization [32]. Assuming a given degree sequence D is sorted in non-increasing order, i.e.,  Computation Model. We develop algorithms for sharedmemory parallel systems. All the cores can read from and write to the global address space. In addition, each core can have its own local variables and data structures.

A. Sequential Algorithm
Blitzstein et al. [14] presented a sequential importance sampling [27] algorithm for generating random graphs with exact prescribed degree sequences. This approach first creates all edges incident on the vertex having the minimum degree in the sequence, then moves to the next vertex having the minimum degree to create its incident edges and so on. To create an edge incident on a vertex u, a candidate list C is computed using the Erdős-Gallai characterization such that, after adding an edge by connecting u to any candidate vertex v from the list C, the residual degree sequence remains graphical and the graph remains simple. Then an edge (u, v) is assigned by choosing v from the candidate list C with a probability proportional to the degree of v. This process is repeated until all edges incident on vertex u are assigned.

It computes the candidate list
Say it chooses the vertex v 5 from C and assigns the edge (v 3 , v 5 ). Then the new degree sequence is D = (3, 3, 1, 2, 1), and the new candidate list for assigning the remaining edge incident on vertex v 3 is C = {v 1 , v 2 }. Say the algorithm selects v 1 from C and assigns the edge (v 3 , v 1 ). Now the new degree sequence is D = (2, 3, 0, 2, 1), and the algorithm will proceed to assign edges incident on vertex v 5 and so on. One possible sequence of degree sequences is  while du = 0 do 5: ,v is graphical} 6: v ← a random candidate in C where probability of selecting v is proportional to dv 7: Fig. 3: A sequential algorithm [14] for generating a random graph with a given degree sequence.
The corresponding graph is shown in Fig. 2. Note that during the assignment of incident edges on a vertex u, a candidate at a later stage is also a candidate at an earlier stage. The pseudocode of the algorithm is shown in Fig. 3. Since a total of m edges are generated for the graph G and computing the candidate list (Line 5) for each edge takes O n 2 time, the time complexity of the algorithm is O mn 2 .
Unlike many other graph generation algorithms, this method never gets stuck, i.e., it always terminates with a graph realizing the given degree sequence (proof provided in Theorem 3 in [14]) or creates loops or parallel edges through the computation of the candidate list using the Erdős-Gallai characterization. The algorithm can generate every possible graph with a positive probability (proof given in Corollary 1 in [14]). For additional details about the importance sampling and estimating the number of graphs for a given degree sequence, see Sections 8 and 9 in [14]; and we omit the details in this paper due to space constraints.

B. Parallel Algorithm
To design an exact parallel version by maintaining the same stochastic process (in order to retain the same theoretical and mathematical results) as that of the sequential algorithm, the vertices are considered (to assign their incident edges) in the same order in the parallel algorithm, i.e., in ascending order of their degrees. Hence, we emphasize parallelizing the computation of the candidate list C, i.e., Line 5 of the sequential algorithm in Fig. 3. For computing the candidate list to assign edges incident on a vertex u, we need to consider all other vertices v with non-zero degrees d v as potential candidates; and we parallelize this step. While considering a particular vertex v as a candidate, we need to check whether D u,v is a graphical sequence using the Erdős-Gallai characterization. If D u,v is graphical, then v is added to the candidate list C. The time complexity of the best known sequential algorithm for testing the Erdős-Gallai characterization is O (n) [14,34]. Thus to have an efficient parallel algorithm for generating random graphs, we need to use an efficient parallel algorithm for checking the Erdős-Gallai characterization. In Section IV, we present an efficient parallel algorithm for checking the Erdős-Gallai characterization that runs in O n P + log P time. The parallel algorithm for the Erdős-Gallai characterization returns TRUE if the given degree sequence is graphical and FALSE otherwise. if C = ∅ then 7: if du = |C| then 16: for each v ∈ C in parallel do 17:

19:
break Assign an edge (u, v) from C 20: v ← a random candidate in C where probability of selecting v is proportional to dv 21: Once the candidate list is computed, if the degree of u is equal to the cardinality |C| of the candidate list, then new edges are assigned between u and all candidate vertices v in the candidate list C in parallel. Otherwise, like the sequential algorithm, a candidate vertex v is chosen randomly from C, a new edge (u, v) is assigned, the degree sequence D is updated by reducing the degrees of each of u and v by 1, and the process is repeated until d u is reduced to 0. After assigning all edges incident on vertex u, the algorithm proceeds with assigning edges incident on the next vertex having the minimum positive degree in D and so on. We present the pseudocode of our parallel algorithm for generating random graphs in Fig. 4. Theorem 1. The parallel algorithm for generating random graphs maintains an exact stochastic process as that of the sequential algorithm and preserves all mathematical and theoretical results of the sequential algorithm. or parallel edges are considered as potential candidates F (Line 7), whereas for assigning the subsequent edges incident on u, the candidates C in an earlier stage are considered as the potential candidates F (Line 9) in a later stage. The candidate list is then computed in parallel by checking whether an edge can be assigned between u and a potential candidate v in F by checking whether the residual degree sequence D u,v , if an edge (u, v) is assigned, is a graphical sequence by using the parallel algorithm for the Erdős-Gallai characterization (Lines 11-14). If the cardinality of the candidate list is equal to the degree d u of vertex u, then edges are assigned between u and all vertices v in the candidate list C in parallel (Lines [15][16][17][18][19]. Although this step is not explicitly mentioned in the sequential algorithm, this is obvious since the sequential algorithm would assign all d u edges incident on u and there are no additional candidates other than the d u candidates in C. We parallelize this step to improve the performance of the algorithm. If the candidate list C has more than d u candidates, then a vertex v is selected randomly from C with probability proportional to d v , and an edge (u, v) is assigned, as the sequential algorithm would do. Hence, the parallel algorithm maintains an exact stochastic process as that of the sequential algorithm. As a consequence, all mathematical and theoretical results (except the time complexity) of the sequential algorithm are applicable to our parallel algorithm as well.
Theorem 2. The time complexity of each of the core P k in the parallel algorithm for generating random graphs is O mn n P + log P . Proof. The parallel algorithm assigns m edges one by one. To assign an edge incident on a vertex u, it computes the candidate list in parallel (Line 11). Whether a vertex v is a candidate is computed using the parallel algorithm for the Erdős-Gallai characterization (Line 12), which has a time complexity of O n P + log P . Hence, the time complexity of the parallel algorithm for generating random graphs is O mn n P + log P . Theorem 3. The space complexity of the parallel algorithm for generating random graphs is O (m + n).

Proof. Storing the degree sequence and the edges take O (n)
and O (m) space, respectively, making a space requirement of O (m + n).

C. Experimental Results
In this section, we present the data sets used in the experiments and the strong scaling and runtime of our parallel algorithm for generating random graphs.
Experimental Setup. We use a 32-core Haswell-EP E5-2698 v3 2.30GHz (3.60GHz Turbo) dual processor node with 128GB of memory, 1TB internal hard drive, and QLogic QDR InfiniBand adapter. We use OpenMP version 3.1 and GCC version 4.7.2 for implementation.
Data Sets. We use degree sequences of five real-world networks for the experiments. A summary of the networks is given in Table II. Facebook [35] is an anonymized Facebook friendship network of the students of CMU. GooglePlus [35] is an online social contact network of GooglePlus. The US-PowerGrid [36] network represents a high-voltage power grid in the western states of the USA. Java-CD [36] is a Java class dependency network of JUNG 2.0.1 [37]. CM-Collab [38] is a scientific collaboration network on the condensed matter topic. III: A comparison of some structural properties of the random networks generated (from the degree sequences of the real-world networks) by our parallel algorithm with that of the real-world networks and random networks generated by swapping 100% edges of the real-world networks. We use average values of 20 experiments. Network   Structural Properties of the Generated Graphs. A comparison of the structural properties of the random graphs generated by our parallel algorithm with that of the real-world graphs and random graphs generated by swapping edges is given in Table III. To generate random graphs by swapping edges, we perform m 2 ln m edge swap operations to swap 100% edges of the real-world graphs [39]. We use average values of 20 experiments. We study the number of triangles, cliques, connected components, average shortest path length, diameter, average betweenness centrality, average closeness centrality, and average local clustering coefficient of the networks. We observe that in many cases the properties of the random graphs are far away from the real-world graphs. Moreover, the structural properties of the random graphs generated by our algorithm and by swapping edges are very close to each other in most of the cases. For example, the clustering coefficient distributions, as shown in Fig. 7, of the random graphs generated by these two methods almost completely overlap with each other, and it is difficult to distinguish them in the figure, whereas both of them lie far away from the realworld graph.

IV. PARALLEL ALGORITHM FOR CHECKING THE ERDŐS-GALLAI CHARACTERIZATION
Many variants of the Erdős-Gallai characterization have been developed and proofs have been given (see [14] and [33] for a good discussion). Such a useful result has been presented in Theorem 3.4.1 in [33], which defines the corrected Durfee number C of the degree sequence D = (d 1 , d 2 , . . . , d n ) (sorted in non-increasing order) as and showed that D is graphical if and only if it satisfies the first C inequalities of the Erdős-Gallai test. The corrected Durfee number C is often significantly smaller than the number of vertices n. For example, for the degree sequence D = (3, 2, 2, 2, 1), the corrected Durfee number C is 3, as shown in Fig. 8; hence, it is sufficient to check only the first three Erdős-Gallai inequalities instead of checking all five inequalities of Eq. (2). The sequential algorithm for checking the Erdős-Gallai characterization is quite straightforward and has a time complexity of O (n) [34]. A parallel algorithm for the problem has been presented in [30], which has a runtime of O (log n) using O n log n EREW PRAM processors. In addition to generating random graphs, the Erdős-Gallai characterization has important applications in many other graph theory problems as well. For example, Iványi et al. [40] applied the sequential algorithm for checking the Erdős-Gallai characterization to enumerate the distinct degree sequences of simple graphs in Compute the corrected Durfee number 1: i ← 1 2: while i <= n and di ≥ i − 1 do parallel. In this section, we present a shared-memory parallel algorithm for checking the Erdős-Gallai characterization of a given degree sequence with a time complexity of O n P + log P using P processing cores. First we briefly review the current state-of-the-art sequential algorithm.

A. Sequential Algorithm
The sequential algorithm [34] is quite simple and consists of the following steps: (i) compute the corrected Durfee number C, (ii) compute the prefix sum of the degrees, (iii) check the parity, i.e., whether the sum of the degrees is even or odd, (iv) compute the weights, which are useful in computing the right hand side of Eq. (2) in linear time, and (v) check the first C Erdős-Gallai inequalities. If the sum of the degrees is even and all the inequalities are satisfied, then the degree sequence D is graphical; otherwise, D is not graphical. The pseudocode of the sequential algorithm is given in Fig. 9.

B. Parallel Algorithm
Based on the sequential algorithm presented in Fig. 9, we present a parallel algorithm for checking the Erdős-Gallai characterization. Below we describe the methodology to parallelize the steps of the sequential algorithm.
• Step 1: Compute the Corrected Durfee Number. The corrected Durfee number can be computed in parallel in a round robin fashion, as shown in Fig. 10. Each core P k computes its local corrected Durfee number C k . Then all the cores synchronize and the maximum value of all C k is reduced as the corrected Durfee number C.
• Step 2: Compute the Prefix Sum of the Degrees. We use a parallel version [41] of computing the prefix sum, as shown in Fig. 11. Each core P k works on a chunk of size n P of the 1: k ← core id Each core P k executes the following in parallel: 2: i ← k + 1 3: C k ← 0 4: while i <= n and di ≥ i − 1 do Each core P k executes the following in parallel: 2: x ← k n P + 1 3: y ← min (k + 1) n P , n 4: s k ← y i=x di 5: In Parallel: S k ← k−1 j=0 sj 6: Q ← S k // note that S0 = 0 7: for i = x to y do

8:
Hi ← Q + di 9: Q ← Hi Fig. 11: Compute the prefix sum of the degrees in parallel. degree sequence. First, the sum s k of the degrees in the chunk is computed (Line 4) and then a prefix sum S k of the s j (0 ≤ j ≤ k − 1) is computed in parallel (Line 5). Finally, each core gives a pass to the chunk and uses the value of S k to compute the final prefix sum (Lines 6-9).
• Step 3: Check the Parity. The master core checks whether the sum of the degrees is even. If the sum is odd, then the degree sequence is not graphical. Otherwise, the algorithm proceeds to the next step.
• Step 4: Compute the Weights. The pseudocode of computing the weights in parallel is shown in Fig. 14. We first initialize (Lines 2-3) the weight array w in parallel. Then the actual weights are computed inside a for loop (Lines 4-10) in parallel. Due to the simultaneous nature of the parallel algorithm, there is a possibility that the same weight w j may be updated by multiple cores in an order different than that of the sequential algorithm. To deal with this difficulty, we add two additional if conditions (Lines 7 and 9) as the values of w j are only updated with larger values in the sequential algorithm. These two conditions ensure the correctness of the weight values as well as allow simultaneous parallel computation of them. Finally, the larger weights are computed in parallel in the last for loop (Lines 11-12).
• Step 5: Check the Erdős-Gallai Inequalities. The Erdős-Gallai inequalities can be checked in parallel in a round robin fashion. We have to check only the first C inequalities instead of checking all the n inequalities. This significantly improves the performance of the algorithm since C << n in many degree sequences, as shown later in Table IV. If any of the inequalities is dissatisfied, then the degree sequence is not graphical; otherwise, it is a graphical sequence. The pseudocode of the algorithm is presented in Fig. 15.   Proof. Storing the degree sequence and the prefix sum of the degrees take O (n) space.

C. Performance Evaluation
In this section, we present the data sets used in the experiments and the strong scaling and runtime of our parallel algorithm for checking the Erdős-Gallai characterization. We use the same experimental setup as described before in Section III-C.  Data Sets. We use degree sequences of both artificial and real-world networks for the experiments. A summary of the networks is given in Table IV. Friendster, Twitter, and Live-Journal (LJ) are real-world online social networks [42]. New York (NY) and Los Angeles (LA) are synthetic, yet realistic social contact networks [43]. The SmallWorld random network follows the Watts-Strogatz small world network model [7]. Table IV also shows that the corrected Durfee number C is significantly smaller than the number of vertices n for all six networks.
Strong Scaling. The strong scaling and runtime of the parallel algorithm are illustrated in Figs. 12 and 13, respectively. The speedup increases almost linearly with the increase in the number of cores. We observe better speedups for the degree sequences of larger graphs and achieve a maximum speedup of 23 with 32 cores on the Friendster graph.

V. CONCLUSION
We presented an efficient parallel algorithm for generating random graphs with prescribed degree sequences. It can be used in studying various structural properties of and dynamics over a network, sampling graphs uniformly at random from the graphical realizations of a given degree sequence and estimating the number of possible graphs with a given degree sequence. The algorithm never gets stuck, can generate every possible graph with a positive probability, and exhibits good speedup. We also compared several important structural properties of the random graphs generated by our parallel algorithm with that of the real-world graphs and random graphs generated by the edge swapping method. In addition, we developed an efficient parallel algorithm for checking the Erdős-Gallai characterization of a given degree sequence. This algorithm can be of independent interest and prove useful in parallelizing many other graph theory problems. We believe the parallel algorithms will contribute significantly in analyzing and mining emerging complex systems and understanding interesting characteristics of such networks.