Groupe d’études et de recherche en analyse des décisions

G-2010-36

Column Generation Algorithms for Exact Modularity Maximization in Networks

, , , , et

Finding modules, or clusters, in networks currently attracts much attention in several domains. The most studied criterion for doing so, due to Newman and Girvan [Physical Review E 69, 026113 (2004)], is modularity maximization. Many heuristics have been proposed for maximizing modularity and yield rapidly near optimal solution or sometimes optimal ones but without a guarantee of optimality. There are few exact algorithms, prominent among which is a paper by Xu et al. [Eur. Physical Journal B 60, 231--239 (2007)]. Modularity maximization can also be expressed as a clique partitioning problem and the row generation algorithm of Grötschel and Wakabayashi [Mathematical Programming 45, 59--96 (1989)] applied. We propose to extend both of these algorithms using the powerful column generation methods for linear and non linear integer programming. Performance of the four resulting algorithms are compared on problems from the literature. Instances with up to 512 entities are solved exactly for the first time. Moreover, the computing time of previously solved problems are reduced substantially.

, 19 pages