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

Abstract

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 K partitions, it updates the ensemble by considering replacing its worst member with the best of L 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 K ensemble partitions and each of the L 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 K and L and relate the results to the extreme value statistics of record-breaking. We find that increasing K is generally more effective than increasing L for finding the best partition.