In community detection, the theme of correctly identifying overlapping nodes, i.e. nodes which belong to more than one community, is important as it is related to role detection and to the improvement of the quality of clustering: proper detection of overlapping nodes gives a better understanding of the community structure. In this paper, we introduce a novel measure, called cuttability, that we show being useful for reliable detection of overlaps among communities and for improving the quality of the clustering, measured via modularity. The proposed algorithm shows better behaviour than existing techniques on the considered datasets (IRC logs and Enron e-mail log). The best behaviour is caught when a network is split between microcommunities. In that case, the algorithm manages to get a better description of the community structure.
Published in Proceedings of IEEE Symposium on Computational Intelligence and Data Mining (IEEE SSCI CIDM 2014); Orlando, Florida, USA; December 9-12, 2014.