Extreme Value Statistics of Community Detection in Complex Networks with Reduced Network Extremal Ensemble Learning (RenEEL)

Arguably the most fundamental problem in Network Science is finding structure within a complex network. One approach is to partition the nodes into communities that are more densely connected than one expects in a random network. “The” community structure corresponds to the partition that maximizes a measure that quantifies this idea. Finding the maximizing partition, however, is a computationally difficult NP-Complete problem. We explore the use of a recently introduced algorithmic scheme [Guo, Singh, and Bassler, Sci. Rep. 9, 14234 (2019)] to find the structure of a set of benchmark networks. The scheme, known as RenEEL, creates an ensemble of k partitions and updates the ensemble by replacing its worst member with the best of k’ partitions found by analyzing a simplified network. The updating continues until consensus is achieved within the ensemble. Varying the values of k and k’, we find that the results obey different classes of extreme value statistics and that increasing k is generally much more effective than increasing k’ for finding the best partition.