Parallel massive scale-free graph generators

ABSTRACT

The lack of publicly available large scale-free graphs forces researchers studying massive scale-free graphs to rely on synthetically generated graphs in testing and evaluating their algorithms. This requires a graph generator that can scale to the graphs with potentially tens and hundreds of billions of vertices and edges. We have developed two such scalable parallel graph generators in this research. The parallel Barabasi-Albert method iteratively builds scale-free graphs using two-phase preferential attachment technique in a bottom-up fashion. The parallel Kronecker method, on the other hand, constructs a graph recursively in a top-down fashion from a given seed graph using the Kronecker matrix multiplication. We show that both graph generators generate massive graphs at a very high rate. It is also shown that graphs generated by these methods have all the common properties of the real scale-free graphs such as power-law degree distribution and small-worldness.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design