Paper 6
Fast Disjoint And Overlapping Community DetectionAuthors: Yi Song, Stephane Bressan, and Gillian Dobbie |
AbstractWe propose algorithms for the detection of disjoint and over- lapping communities in networks. The algorithms exploit both the degree and clustering coecient of vertices as these metrics characterize dense connections, which we hypothesize as being indicative of communities. Each vertex independently seeks the community to which it belongs, by visiting its neighboring vertices and choosing its peers on the basis of their degrees and clustering coecients. The algorithms are intrinsically data parallel. We devise a version for Graphics Processing Unit (GPU). We empirically evaluate the performance of our methods. We measure and compare their eciency and e ectiveness to several state-of-the-art community detection algorithms. E ectiveness is quanti ed by metrics, namely, modularity, conductance, internal density, cut ratio, weighted community clustering and normalized mutual information. Additionally, average community size and community size distribution are measured. Eciency is measured by the running time. We show that our methods are both e ective and ecient. Meanwhile, the opportunity to parallelize our algorithm yields an ecient solution to the community detection problem. |