Scalable Multi-threaded Community Detection in Social Networks

Citations Over TimeTop 10% of 2012 papers

Abstract

The volume of existing graph-structured data requires improved parallel tools and algorithms. Finding communities, smaller sub graphs densely connected within the sub graph than to the rest of the graph, plays a role both in developing new parallel algorithms as well as opening smaller portions of the data to current analysis tools. We improve performance of our parallel community detection algorithm by 20% on the massively multithreaded Cray XMT, evaluate its performance on the next-generation Cray XMT2, and extend its reach to Intel-based platforms with OpenMP. To our knowledge, not only is this the first massively parallel community detection algorithm but also the only such algorithm that achieves excellent performance and good parallel scalability across all these platforms. Our implementation analyzes a moderate sized graph with 105 million vertices and 3.3 billion edges in around 500 seconds on a four processor, 80-logical-core Intel-based system and 1100 seconds on a 64-processor Cray XMT2.

Related Papers

• → Fairness and Throughput in Switch on Event Multithreading(2006)56 cited
• → Fairness enforcement in switch on event multithreading(2007)36 cited
• → A Novel Thread Partitioning Approach Based on Machine Learning for Speculative Multithreading(2013)13 cited
• → Evaluation of a speculative multithreading compiler by characterizing program dependences(2005)
• → Enhanced interleaved multithreaded multiprocessors and their performance analysis(2004)