Community Detection in Complex Networks

We introduce an ensemble learning scheme and a new metric for community detection in complex networks. The scheme uses a Machine Learning algorithmic paradigm we call Extremal EnsembleLearning. It uses iterative extremal updating of an ensemble of network partitions, which can be found by a conventional base algorithm, to find a node partition that maximizes a metric. At each iteration, core groups of nodes that are in the same community in every ensemble partition are identified and used to form a reduced network. Partitions of the reduced network are then found and used to update the ensemble. The smaller size of the reduced network makes the scheme efficient. We use the scheme to analyze the community structure in a set of commonly studied benchmark networks and find that it outperforms all other known methods for finding the partition with maximum modularity. The new metric that we call generalized modularity densityQgeliminatesthe well-known resolution limit problem at any desired resolution and is easily extendable to study weighted and hierarchical networks. We also propose a benchmark test to quantify the resolution limit problem, examine various modularity-like metrics to show that the new metricQgperformsbest, and show that Qg can identify modular structure in real-world and artificial networks that is otherwise hidden.