Searching Graph Communities by Modularity Maximization via Convex Optimization

Communities in networks are the densely knit groups of individuals. Newman suggested modularity - a natural measure of the quality of community partition, and several community detection strategies aiming on maximizing the modularity have been proposed. In this paper, we give a new combinatorial model for modularity maximization problem, and introduce a convex optimization based rounding algorithm. Importantly, even given the maximum number of wanted communities, our solution is still capable of maximizing the modularity and obtaining the upper bound on the best possible solution.