Scalable Distributed Memory Community Detection Using Vite

摘要

Graph clustering, popularly known as community detection, is a fundamental graph operation used in many applications related to network analysis and cybersecurity. The goal of community detection is to partition a network into “communities” such that each community consists of a tightly-knit group of nodes with relatively sparser connections to the rest of the nodes in the network. To compute clustering on large-scale networks, efficient parallel algorithms capable of fully exploiting features of modern architectures are needed. However, due to their irregular and inherently sequential nature, many of the current algorithms for community detection are challenging to parallelize. In response to the 2018 Streaming Graph Challenge, we present Vite-a distributed memory parallel implementation of the Louvain method, a widely used serial method for community detection. In addition to a baseline parallel implementation of the Louvain method, Vite also includes a number of heuristics that significantly improve performance while preserving solution quality. Using the datasets from the 2018 Graph Challenge (static and streaming), we demonstrate superior performance and high quality solutions.