A multilevel approach for overlapping community detection

Abstract

Many real world complex networks have an a overlapping community structure, in which a vertex belongs to one or more communities. Numerous approaches for crisp overlapping community detection were proposed in the literature, most of them have a good accuracy but their computational costs are considerably high and infeasible for large-scale networks. Since the multilevel approach has not been previously applied to deal with overlapping communities detection problem, in this paper we propose an adaptation of this approach to tackle the detection problem to overlapping communities case. The goal is to analyze the time impact and the quality of solution of our multilevel strategy regarding to traditional algorithms. Our experiments show that our proposal consistently produces good performance compared to single-level algorithms and in less time.