Implementation of COMBO algorithm for community detection in complex networks

Community detection is key to understanding the structure of complex networks, and ultimately extracting useful information from them. Applications are diverse: from healthcare to regional geography, from human interactions and mobility to economics. We present a novel search strategy for the optimization of various objective functions for community detection purposes.

Existing search strategies take one of the following steps to evolve starting partitions: merging two communities, splitting a community into two, or moving nodes between two distinct communities. The proposed algorithm compounds all three actions. After selecting an initial partition made of a single community, the following steps are iterated as long as the iteration results in an increased objective function score: (1) for each source community, the best possible redistribution of all source nodes into each destination community (either existing or new) is calculated; this also allows for the possibility that the source community entirely merges with the destination; (2) the best merger/split/recombination is performed. As the proposed technique combines all three possible types of steps, we are referring to it as Combo.

An idea of the algorithm was presented in
Sobolevsky, S., Campari, R., Belyi, A., & Ratti, C. (2014). A general optimization technique for high quality community detection in complex networks. Phys. Rev. E 90 (1), 012811,
available online, full text pdf

You can download the source code for COMBO here