Exploiting Vertex-Cut Partitioning in Distributed Graph Generation

Abstract

Graphs sub-structures have strong influence on the characteristics of real-world complex networks. Moreover, graph generation algorithms must capture and replicate these characteristics to remain representative of their real-world counterparts. The ever-increasing size of data collected from observed networks introduces another layer of complexity-scalability constraints- to the graph generation methods which already have multiple objective functions to satisfy. This paper introduces a novel distributed graph generation methodology that employs vertex partitioning to distribute the graph across multiple execution units. By design, algorithm faithfully replicates the exact Joint Degree Matrix(JDM) characteristics of the original graph. We conducted an extensive profiling study of the algorithm to analyze the effect of execution unit count and partition count on its runtime performance. The results demonstrate that, with just a few compute servers, the algorithm can efficiently scale to handle hundreds of millions of vertices within a reasonable time frame.