Scalable static and dynamic community detection using Grappolo

Mahantesh Halappanavar, Hao Lu, Ananth Kalyanaraman, Antonino Tumeo

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

27 Scopus citations

Abstract

Graph clustering, popularly known as community detection, is a fundamental kernel for several applications of relevance to the Defense Advanced Research Projects Agency's (DARPA) Hierarchical Identify Verify Exploit (HIVE) Program. Clusters or communities represent natural divisions within a network that are densely connected within a cluster and sparsely connected to the rest of the network. The need to compute clustering on large scale data necessitates the development of efficient algorithms that can exploit modern architectures that are fundamentally parallel in nature. 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 HIVE Graph Challenge, we present several parallelization heuristics for fast community detection using the Louvain method as the serial template. We implement all the heuristics in a software library called Grappolo. Using the inputs from the HIVE Challenge, we demonstrate superior performance and high quality solutions based on four parallelization heuristics. We use Grappolo on static graphs as the first step towards community detection on streaming graphs.

Original languageEnglish
Title of host publication2017 IEEE High Performance Extreme Computing Conference, HPEC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538634721
DOIs
StatePublished - Oct 30 2017
Event2017 IEEE High Performance Extreme Computing Conference, HPEC 2017 - Waltham, United States
Duration: Sep 12 2017Sep 14 2017

Publication series

Name2017 IEEE High Performance Extreme Computing Conference, HPEC 2017

Conference

Conference2017 IEEE High Performance Extreme Computing Conference, HPEC 2017
Country/TerritoryUnited States
CityWaltham
Period09/12/1709/14/17

Fingerprint

Dive into the research topics of 'Scalable static and dynamic community detection using Grappolo'. Together they form a unique fingerprint.

Cite this