Machine Learning Algorithm Identifies Community Structure

In complex networks, communities are defined as the parts of the network that are more densely connected than average. Examples of these communities range from proteins that work together to achieve a cellular function, to jazz musicians who regularly play together, to scientists who collaborate on projects.

Finding those communities in a given network, however, is a difficult computational problem.

In a recent paper, published in the journal Nature Scientific Reports, University of Houston researchers describe a machine learning algorithm that detects community structures in complex networks.

This algorithm, called Reduced network extremal ensemble learning, or RenEEL for short, offers the advantage of being very accurate, yet also efficient.

“This algorithm offers a practical approach for finding an accurate community structure in large networks,” said Kevin E. Bassler, Moores Professor of Physics and Mathematics, physics chair, and corresponding author for the paper.

Using Machine Learning to Identify Community Structure

Machine learning is the use of algorithms to perform specific tasks without explicit instructions. To apply machine learning to find communities in complex networks, one needs an algorithm capable of identifying communities within networks, without explicit instructions as to what communities are, or what they might look like.

This approach offers a dramatic improvement over existing methods of community detection in complex networks, which are either highly inaccurate at identifying communities or require so much computational power as to be impractical.

Extremal Ensemble Learning

RenEEL, the algorithm described by Bassler’s team, uses an algorithmic paradigm that the authors have termed ‘extremal ensemble learning.’ Extremal is characterized by extreme properties or conditions.

With RenEEL, this means identifying different partitions, in which a complex network is broken down into a set of less complex parts.

“The idea of extremal ensemble learning is that you take an ensemble of partitions and update that ensemble in the extremal way, which is to say that you replace the worst one with a better one,” Bassler said.

The updating continues until a consensus is reached within the ensemble about what the correct answer is.

RenEEL works efficiently by tracking the consensus within the ensemble about what the network structure is and focuses its efforts on resolving disagreement within the ensemble.

“The resulting algorithm is accurate while still being relatively fast,” Bassler said.

Collaborators include graduate student Jiahao Guo and postdoctoral researcher Pramesh Singh. This work was funded by a grant from the National Science Foundation.

- Rachel Fairbank, College of Natural Sciences and Mathematics