Eur. Phys. J. B (2016) 89: 39
https://doi.org/10.1140/epjb/e2015-60656-5

Regular Article

A mathematical programming approach for sequential clustering of dynamic networks^*

¹ Department of Informatics, King’s College London, London WC2R 2LS, UK
² Centre for Process Systems Engineering, Department of Chemical Engineering, University College London, London WC1E 7JE, UK

^a e-mail: sophia.tsoka@kcl.ac.uk

Received: 9 August 2015
Received in final form: 27 October 2015
Published online: 15 February 2016

Abstract

A common analysis performed on dynamic networks is community structure detection, a challenging problem that aims to track the temporal evolution of network modules. An emerging area in this field is evolutionary clustering, where the community structure of a network snapshot is identified by taking into account both its current state as well as previous time points. Based on this concept, we have developed a mixed integer non-linear programming (MINLP) model, SeqMod, that sequentially clusters each snapshot of a dynamic network. The modularity metric is used to determine the quality of community structure of the current snapshot and the historical cost is accounted for by optimising the number of node pairs co-clustered at the previous time point that remain so in the current snapshot partition. Our method is tested on social networks of interactions among high school students, college students and members of the Brazilian Congress. We show that, for an adequate parameter setting, our algorithm detects the classes that these students belong more accurately than partitioning each time step individually or by partitioning the aggregated snapshots. Our method also detects drastic discontinuities in interaction patterns across network snapshots. Finally, we present comparative results with similar community detection methods for time-dependent networks from the literature. Overall, we illustrate the applicability of mathematical programming as a flexible, adaptable and systematic approach for these community detection problems.