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. Often, this is achieved by partitioning the network's nodes into communities in a way that maximizes an objective function. However, finding the maximizing partition is generally a computationally difficult NP-complete problem. Recently, a machine learning algorithmic scheme was introduced that uses information within a set of partitions to find a new partition that better maximizes an objective function. The scheme, known as RenEEL, uses Extremal Ensemble Learning. Starting with an ensemble of partitions, it updates the ensemble by considering replacing its worst member with the best of partitions found by analyzing a reduced network formed by collapsing nodes, which all the ensemble partitions agree should be grouped together, into super-nodes. The updating continues until consensus is achieved within the ensemble about what the best partition is. The original ensemble partitions and each of the partitions used for an update are found using a simple "base" partitioning algorithm. We perform an empirical study of how the effectiveness of RenEEL depends on the values of and and relate the results to the extreme value statistics of record-breaking. We find that increasing is generally more effective than increasing for finding the best partition.