Community structure

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. In this paper we present a novel search strategy for the optimization of various objective functions for community detection purposes [ S. Sobolevsky, R. Campari, A. Belyi, and C. Ratti "General optimization technique for high-quality community detection in complex networks" Phys. Rev. E 90, 012811 2014 ]. 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.

Combo rank plot
Average normalized performance rank of each algorithm in terms of partitioning quality and speed
Study Authors
Stanislav Sobolevsky
Riccardo Campari
Alexander Belyi
Carlo Ratti
Paper link
Phys. Rev. E 90, 012811 2014
Source codes of our algorithm
Combo C++
Source codes of some other algorithms
Community detection:
Louvain method - C++, Matlab
Le Martelot
Simulated Annealing implemented in RGraph
Extremal Optimization implemented in Radatools
Lancichinetti, Fortunato, Radicchi

Network data repositories and interesting personal pages:
UCI Network Data Repository
Aaron Clauset
Alex Arenas
Mark Newman
Martin Rosvall