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&rsquo;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 <i>K</i> partitions, it updates the ensemble by considering replacing its worst member with the best of <i>L</i> 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 <i>K</i> ensemble partitions and each of the <i>L</i> partitions used for an update are found using a simple &ldquo;base&rdquo; partitioning algorithm. We perform an empirical study of how the effectiveness of RenEEL depends on the values of <i>K</i> and <i>L</i> and relate the results to the extreme value statistics of record-breaking. We find that increasing <i>K</i> is generally more effective than increasing <i>L</i> for finding the best partition.