Community Detection in Dense Networks using Effective Resistance and Link Pruning

The detection of communities in networks can be made more effective by weighting edges with a distance measure reflecting the similarity/dissimilarity between pairs of nodes. In this paper, we focus on a particular measure derived from the fields of electrical circuits: the effective resistance. Specifically, we propose a community detection method organized into two phases. During the first phase, the edges of the input graph are weighted through their effective resistance and a weight thresholding sparsification procedure is applied to cut the less important edges while keeping the edges fundamental for maintaining a modular structure. We then run a GA-based community detection method maximizing the modularity as the objective function on the sparse graph. The results of the experiments over both real-world and synthetically generated networks show the effectiveness of the approach when compared to other benchmark methods.