A mathematical programming approach for sequential clustering of dynamic networks

Jonathan Silva, Laura Bennett, Lazaros G. Papageorgiou, Sophia Tsoka*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)
206 Downloads (Pure)

Abstract

A common analysis performed on dynamic networks is community structure detection, achallenging problem that aims to track the temporal evolution of network modules. Anemerging area in this field is evolutionary clustering, where thecommunity structure of a network snapshot is identified by taking into account both itscurrent state as well as previous time points. Based on this concept, we have developed amixed integer non-linear programming (MINLP) model, SeqMod, that sequentially clusterseach snapshot of a dynamic network. The modularity metric is used to determine the qualityof community structure of the current snapshot and the historical cost is accounted for byoptimising the number of node pairs co-clustered at the previous time point that remain soin the current snapshot partition. Our method is tested on social networks of interactionsamong high school students, college students and members of the Brazilian Congress. Weshow that, for an adequate parameter setting, our algorithm detects the classes that thesestudents belong more accurately than partitioning each time step individually or bypartitioning the aggregated snapshots. Our method also detects drastic discontinuities ininteraction patterns across network snapshots. Finally, we present comparative resultswith 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.

Original languageEnglish
Article number39
Pages (from-to)1-10
Number of pages10
JournalEuropean Physical Journal B
Volume89
Issue number2
Early online date15 Feb 2016
DOIs
Publication statusPublished - 16 Feb 2016

Fingerprint

Dive into the research topics of 'A mathematical programming approach for sequential clustering of dynamic networks'. Together they form a unique fingerprint.

Cite this