CR-Graph: Community Reinforcement on Graphs for Accurate Community Detection

Abstract

In this paper, we present CR-Graph (community reinforcement on graphs), a novel method that helps existing algorithms to perform more-accurate community detection (CD). Toward this end, CRGraph strengthens the community structure of a given original graph by adding non-existent predicted intra-community edges and deleting existing predicted inter-community edges. To design CRGraph, we propose the following two strategies: (1) predicting intracommunity and inter-community edges (i.e., the type of edges) and (2) determining the amount of edges to be added/deleted. To show the effectiveness of CR-Graph, we conduct extensive experiments with various CD algorithms on 7 synthetic and 4 real-world graphs. The results demonstrate that CR-Graph improves the accuracy of all underlying CD algorithms universally and consistently.