A Mathematical Programming Approach to Community Structure Detection in Complex Networks

Abstract The detection of community structure is a widely recognised method of revealing the underlying properties of complex networks in biological, physical and social sciences. The simplest form of the community structure problem is the partitioning of unweighted and undirected networks into disjoint communities. However, module detection in weighted networks or communities with overlapping modules may lead to more realistic applications. Optimisation of the modularity metric is a popular method for community structure detection (Newman and Girvan 2004) and here we extend its use to propose mixed integer nonlinear programming (MINLP) models for (i) partitioning of weighted networks and (ii) detection of overlapping communities. The mathematical programming nature of the methods proposed provide users with an adaptability that may not be available in alternative modelling frameworks. Overall, we show that our methods improve existing methodologies in terms of applicability and adaptability and offer a versatile solution to the community detection problem.