Community detection in graphs based on surprise maximization using firefly heuristics

The detection of node clusters (communities) in graphs has been at the core of many modeling paradigms emerging in different fields and disciplines such as Social Sciences, Biology, Chemistry, Telecommunications and Linguistics. When evaluating the quality of a clustering arrangement unsupervised metrics can be utilized (e.g. modularity), which all rely on structural and topological characteristics of the cluster space rather than on an observed ground of truth that should be achieved. One of such metrics is the recently published Surprise, which evaluates how statistically unlikely a given clustering arrangement is with respect to a random network featuring the same distribution of nodes per cluster. To maximize this metric, a number of algorithms have been proposed in the literature, but their comparative performance varies significantly between networks of different shape and size. In this article a novel heuristic community detection approach is proposed as a means to achieve a universally well-performing tool for graph clustering based on Surprise maximization. The heuristic scheme relies on the search procedure of the so-called Firefly Algorithm, a nature-inspired meta-heuristic solver based on the collective behavior, mutual attractiveness and random yet controlled movement of these insects. The proposed technique emulates these observed behavioral patterns of fireflies in the genotype of the graph clustering problem rather than on an encoded representation of its search space (phenotype). Simulation results evince that the performance of our community detection scheme generalizes better than other schemes when applied over synthetically generated graphs with varying properties.