Eur. Phys. J. B 60, 231-239 (2007)
https://doi.org/10.1140/epjb/e2007-00331-0

Finding community structures in complex networks using mixed integer optimisation

¹ Centre for Process Systems Engineering, Department of Chemical Engineering, UCL (University College London), Torrington Place, London, WC1E 7JE, UK
² Centre for Bioinformatics, School of Physical Sciences and Engineering, King's College London, Strand, London, WC2R 2LS, UK

Corresponding author: ^a l.papageorgiou@ucl.ac.uk

Received: 20 February 2007
Revised: 21 September 2007
Published online: 8 December 2007

Abstract

The detection of community structure has been used to reveal the relationships between individual objects and their groupings in networks. This paper presents a mathematical programming approach to identify the optimal community structures in complex networks based on the maximisation of a network modularity metric for partitioning a network into modules. The overall problem is formulated as a mixed integer quadratic programming (MIQP) model, which can then be solved to global optimality using standard optimisation software. The solution procedure is further enhanced by developing special symmetry-breaking constraints to eliminate equivalent solutions. It is shown that additional features such as minimum/maximum module size and balancing among modules can easily be incorporated in the model. The applicability of the proposed optimisation-based approach is demonstrated by four examples. Comparative results with other approaches from the literature show that the proposed methodology has superior performance while global optimum is guaranteed.