In community detection tasks, accurately measuring the distance between nodes is fundamental for correctly grouping the nodes according to their similarity. This work proposes a community detection method exploiting the effective resistance , a measure derived from the field of electrical circuits that has been shown to be a good distance metric for uncovering communities. In the pre-processing phase, the method weights the input graph G with the effective resistance between each couple of nodes. Then, to turn this distance into a similarity value reflecting the closeness between each couple of nodes, different kernel functions for the effective resistance are tested. Finally, since many of the networks we deal with are not sparse, G is reduced to a smaller graph \(G'\) by cutting a percentage of less important edges through a weight thresholding sparsification procedure. The amount of edge cuts is chosen evaluating the spectral similarity between G and \(G'\) . In such a way, we are able to work with fewer edges gaining in computational time and storage resources. At the end of the pre-processing phase, we run on the sparsified graph \(G'\) a community detection method based on Genetic Algorithms maximizing the weighted modularity as objective function. Experimenting on both real-world and synthetic networks, we demonstrate the effectiveness of such approach when compared to other benchmarks.
Socievole et al. (Wed,) studied this question.