Scalable Generation of Graphs for Benchmarking HPC Community-Detection Algorithms

Authors: George M. Slota (Rensselaer Polytechnic Institute (RPI)), Jonathan W. Berry (Sandia National Laboratories), Simon D. Hammond (Sandia National Laboratories), Stephen L. Olivier (Sandia National Laboratories), Cynthia A. Phillips (Sandia National Laboratories), Sivasankaran Rajamanickam (Sandia National Laboratories)

Abstract: Community detection in graphs is a canonical social network analysis method. We consider the problem of generating suites of terascale synthetic social networks to compare the solution quality of parallel community-detection methods. The standard method, based on the graph generator of Lancichinetti, Fortunato, and Radicchi (LFR), has been used extensively for modest-scale graphs, but has inherent scalability limitations.

We provide an alternative, based on the scalable Block Two-Level Erdos-Renyi (BTER) graph generator, that enables HPC-scale evaluation of solution quality in the style of LFR. Our approach varies community coherence, and retains other important properties. Our methods can scale real-world networks, e.g., to create a version of the Friendster network that is 512 times larger. With BTER's inherent scalability, we can generate a 15-terabyte graph (4.6B vertices, 925B edges) in just over one minute. We demonstrate our capability by showing that label-propagation community-detection algorithm can be strong-scaled with negligible solution-quality loss.


Presentation: file


Back to Technical Papers Archive Listing