BRASIL
BRASIL
Abstract:
This paper tackles the problem of community detection in large-scale
graphs. In the literature devoted to this topic, an iterative algorithm,
called Louvain Method (LM), stands out as an effective and fast
solution for this problem. However, the first iterations of the LM are
the most costly. To overcome this issue, this paper introduces CoVeC, a Coarse-grained Vertex Clustering
for efficient community detection in sparse complex networks.
CoVeC pre-processes the original graph in order to forward a graph of
reduced size to the LM. The subsequent group formation, including the
maximization of group quality, as per the modularity metric, is left to
the LM. We evaluate our proposal using real-world and synthetic
networks, presenting distinct sizes and sparsity levels. Overall, our
experimental results show that CoVeC can be a way faster option than the
first iterations of the LM, yet similarly effective. In fact, for
sparser graphs, the combo CoVeC+LM outperforms the standalone LM and its
variations, attaining a mean processing time reduction of 47% and a
mean modularity reduction of only 0.4%.
