Paper Info
Title
High quality, scalable and parallel community detection for large real graphs
Abstract
Community detection has arisen as one of the most relevant topics in the field of graph mining, principally for its applications in domains such as social or biological networks analysis. Different community detection algorithms have been proposed during the last decade, approaching the problem from different perspectives. However, existing algorithms are, in general, based on complex and expensive computations, making them unsuitable for large graphs with millions of vertices and edges such as those usually found in the real world. In this paper, we propose a novel disjoint community detection algorithm called Scalable Community Detection (SCD). By combining different strategies, SCD partitions the graph by maximizing the Weighted Community Clustering (WCC), a recently proposed community detection metric based on triangle analysis. Using real graphs with ground truth overlapped communities, we show that SCD outperforms the current state of the art proposals (even those aimed at finding overlapping communities) in terms of quality and performance. SCD provides the speed of the fastest algorithms and the quality in terms of NMI and F1Score of the most accurate state of the art proposals. We show that SCD is able to run up to two orders of magnitude faster than practical existing solutions by exploiting the parallelism of current multi-core processors, enabling us to process graphs of unprecedented size in short execution times.
Year
DOI
Venue
2014
10.1145/2566486.2568010
WWW
Keywords
Field
DocType
different community detection algorithm,different strategy,overlapping community,weighted community clustering,novel disjoint community detection,ground truth overlapped community,scalable community detection,large real graph,art proposal,community detection,high quality,different perspective,parallel community detection,graph partition,parallel,modularity,social networks,clustering
Data mining,Disjoint sets,Computer science,Theoretical computer science,Artificial intelligence,Cluster analysis,Graph partition,World Wide Web,Vertex (geometry),Biological network,Ground truth,Machine learning,Modularity,Scalability
Conference
Citations 
PageRank 
References 
35
1.30
9
Authors
3
Name
Order
Citations
PageRank
Arnau Prat-Pérez122713.44
David Dominguez-Sal218916.35
Josep-Lluis Larriba-Pey324521.70