Grappolo (Open Source)
Community detection has become a fundamental operationin numerous graph-theoretic applications. It is used to reveal naturaldivisions that exist within real world networks without imposing prior size orcardinality constraints on the set of communities. Despite its potential forapplication, there is only limited support for community detection onlarge-scale parallel computers, largely owing to the irregular and inherently sequentialnature of the underlying heuristics. In this paper, we present parallelizationheuristics for fast community detection using the Louvain method as the serialtemplate. The Louvain method is an iterative heuristic for modularityoptimization. Originally developed by Blondel et al. in 2008, the method has becomeincreasingly popular owing to its ability to detect high modularity communitypartitions in a fast and memory-efficient manner. However, the method is alsoinherently sequential, thereby limiting its scalability. Here, we observecertain key properties of this method that present challenges for itsparallelization, and consequently propose heuristics that are designed to breakthe sequential barrier. For evaluation purposes, we implemented our heuristicsusing OpenMP multithreading, and tested them over real world graphs derivedfrom multiple application domains (e.g., internet, citation, biological).Compared to the serial Louvain implementation, our parallel implementation isable to produce community outputs with a higher modularity for most of theinputs tested, in comparable number of iterations, while providing realspeedups of up to 8x using 32 threads. In addition, our parallel implementation was able to exhibitweak scaling properties on up to 32 threads.
SALSA (Open Source)
SALSA is a light framework of 4 to 5 algorithms designed for the analysis of social media data, treating social media as a large sensor network. Each algorithm alone is not notable intellectual property, however, used in combination, provides a unique means of producing and supporting graph-based models of social media data.