Phase transition of Surprise optimization in community detection

Abstract Community detection is one of important issues in the research of complex networks. In literatures, many methods have been proposed to detect community structures in the networks, while they also have the scope of application themselves. In this paper, we investigate an important measure for community detection, Surprise (Aldecoa and Marin, Sci. Rep. 3 (2013) 1060), by focusing on the critical points in the merging and splitting of communities. We firstly analyze the critical behavior of Surprise and give the phase diagrams in community-partition transition. The results show that the critical number of communities for Surprise has a super-exponential increase with the increase of the link-density difference, while it is close to that of Modularity for small difference between inter- and intra-community link densities. By directly optimizing Surprise, we experimentally test the results on various networks, following a series of comparisons with other classical methods, and further find that the heterogeneity of networks could quicken the splitting of communities. On the whole, the results show that Surprise tends to split communities due to various reasons such as the heterogeneity in link density, degree and community size, and it thus exhibits higher resolution than other methods, e.g., Modularity, in community detection. Finally, we provide several approaches for enhancing Surprise.