Identifying multi-scale communities in networks by asymptotic surprise

Abstract

Abstract Optimizing statistical measures for community structure is one of the most popular strategies for community detection, but many of them lack the flexibility of resolution and thus are incompatible with multi-scale communities of networks. Here, we further studied a statistical measure of interest for community detection, asymptotic surprise which is asymptotic approximation of surprise. We analyzed the critical behaviors of asymptotic surprise in the phase transition of community partition theoretically. Then, according to the theoretical analysis, a multi-resolution method based on asymptotic surprise was introduced, which provides an alternative approach to study multi-scale communities in networks, and an improved Louvain algorithm was proposed to optimize the asymptotic surprise more effectively. By a series of experimental tests in various networks, we further demonstrated the critical behaviors of the asymptotic surprise, and the effectiveness of the improved Louvain algorithm; and then we validated the ability of our multi-resolution method to solve the first-type resolution limit and its strong tolerance against the second-type resolution limit; finally we confirmed its effectiveness in revealing multi-scale community structures in networks.