Parallel Generation of Massive Scale-Free Graphs

Details Parallel Generation of Massive Scale-Free Graphs Parallel Generation of Massive Scale-Free Graphs

2010-03-18

arxiv.org/abs/1003.3684v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

One of the biggest huddles faced by researchers studying algorithms for massive graphs is the lack of large input graphs that are essential for the development and test of the graph algorithms. This paper proposes two efficient and highly scalable parallel graph generation algorithms that can produce massive realistic graphs to address this issue. The algorithms, designed to achieve high degree of parallelism by minimizing inter-processor communications, are two of the fastest graph generators which are capable of generating scale-free graphs with billions of vertices and edges. The synthetic graphs generated by the proposed methods possess the most common properties of real complex networks such as power-law degree distribution, small-worldness, and communities-within-communities. Scalability was tested on a large cluster at Lawrence Livermore National Laboratory. In the experiment, we were able to generate a graph with 1 billion vertices and 5 billion edges in less than 13 seconds. To the best of our knowledge, this is the largest synthetic scale-free graph reported in the literature.

Affiliated with

Also associated with

No associations

Rating

Parallel Generation of Massive Scale-Free Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Parallel Generation of Massive Scale-Free Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel Generation of Massive Scale-Free Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-353624