Multilevel Strategy for Community Detection in k-Partite Networks

• Renata Sarmet Smiderle Mendes USP
• Alan Demétrius Baria Valejo UFSCar
• Alneu de Andrade Lopes USP

Resumo

Graph-based algorithms have aroused considerable interest in recent years, facilitating pattern recognition and learning by propagating information through the graph. However, with a large volume of data, it becomes computationally infeasible to execute specific algorithms. The multilevel strategy aims to recursively reduce the graph, performing successive reductions of the initial network based on edge contractions and vertex merges. The coarsening process makes the graph as small as desired, allowing the use of costly algorithms in this coarsened version. The multilevel strategy has three phases: the coarsening phase, consisting of matching and contraction; the solution-finding phase, consisting of applying the desired algorithm to the most compact network; and the uncoarsening phase, consisting of projection and refinement. In this work, a generalization of the unsupervised coarsening algorithm for bipartite networks is carried out based on the propagation of labels with weight restriction, making it possible to deal with k-partite networks. Furthermore, the coarsening process is used directly as a community detection algorithm, in which each super vertex of the final contraction represents a community. The results show that our coarsening strategy leads to significant gains regarding community detection quality.