Title: High quality multi-core multi-level algorithm for community detection

Authors: Suely Oliveira; Rahil Sharma

Addresses: Department of Computer Science, University of Iowa, Iowa, IA-52246, USA ' Department of Computer Science, University of Iowa, Iowa, IA-52246, USA

Abstract: One of the most relevant and widely studied structural properties of networks is their community structure or clustering. Detecting communities is of great importance in various disciplines where systems are often represented as graphs. Different community detection algorithms have been introduced in the past few years, which look at the problem from different perspectives. Most of these algorithms, however, have expensive computational time that makes them impractical to use for large graphs found in the real world. Maintaining a good balance between the computational time and the quality of the communities discovered is a well-known open problem in this area. In this paper, we propose a multi-core multi-level (MCML) community detection algorithm based on the topology of the graph, which contributes towards solving the above problem. MCML algorithm on two benchmark datasets results in detection of accurate communities. We detect high modularity communities by applying MCML on Facebook Forum dataset to find users with similar interests and Amazon product dataset. We also show the scalability of MCML on these large datasets with 16 Xeon Phi cores.

Keywords: parallel algorithm; multi-level; multi-core; community detection.

DOI: 10.1504/IJCSE.2017.087399

International Journal of Computational Science and Engineering, 2017 Vol.15 No.3/4, pp.311 - 321

Received: 11 Apr 2015
Accepted: 14 Nov 2015

Published online: 15 Oct 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article