Communities of minima in local optima networks of combinatorial spaces

► We model the search space of hard combinatorial problems with a graph whose vertices are the local optima and whose edges denote transitions between their basins. ► We study the stastistical features of this network and its relationships with problem difficulty. ► We focus on the cluster structure of the minima network using several community detection algorithms. ► We study the QAP and show that different instance classes give rise to very different network cluster structure.