Scalable Multi-threaded Community Detection in Social Networks
- 1 May 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 48, 1619-1628
- https://doi.org/10.1109/ipdpsw.2012.203
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.Keywords
This publication has 25 references indexed in Scilit:
- The Combinatorial BLAS: design, implementation, and applicationsThe International Journal of High Performance Computing Applications, 2011
- PregelPublished by Association for Computing Machinery (ACM) ,2010
- A distributed diffusive heuristic for clustering a virtual P2P supercomputerPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- Engineering a scalable high quality graph partitionerPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- Parallel community detection on large networks with propinquity dynamicsPublished by Association for Computing Machinery (ACM) ,2009
- Multi-level Algorithms for Modularity ClusteringLecture Notes in Computer Science, 2009
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- Finding community structure in very large networksPhysical Review E, 2004
- UbiCrawler: a scalable fully distributed Web crawlerSoftware: Practice and Experience, 2004
- Multilevelk-way Partitioning Scheme for Irregular GraphsJournal of Parallel and Distributed Computing, 1998