Community reinforcement: An effective and efficient preprocessing method for accurate community detection

摘要

Existing community detection algorithms may be often unsatisfactory due to low detection accuracy in real-world graphs since the number of edges between the nodes in the same community (i.e., intra-community edges) does not tend to be sufficiently large while the number of edges between the nodes belonging to different communities (i.e., inter-community edges) does not tend to be negligible. In this paper, we present a novel preprocessing method for strengthening the community structure of a given graph by adding non-existent predicted intra-community edges and deleting existing predicted inter-community edges for more accurate community detection. Our preprocessing method does not require any extra information for community reinforcement nor any changes of existing algorithms for community detection. To realize our method, we propose the following three strategies: (1) predicting intra-community and inter-community edges, (2) determining the amount of edges to be added/deleted, and (3) reducing the amount of computations in predicting the type of edges. To validate the effectiveness of our method, we conduct extensive experiments with various existing community detection algorithms on 11 synthetic and 6 real-world graphs. The results demonstrate that (1) our method significantly improves the accuracy up to 91%, regardless of community detection algorithms and graphs and (2) it outperforms two state-of-the-art edge weighting-based preprocessing methods in improving the accuracy up to 105%.