Silva, JC;
Bennett, L;
Papageorgiou, LG;
Tsoka, S;
(2016)
A mathematical programming approach for sequential clustering of dynamic networks.
The European Physical Journal B
, 89
, Article 39. 10.1140/epjb/e2015-60656-5.
Preview |
Text
Papageorgiou_art_10.1140_epjb_e2015-60656-5.pdf - Published Version Download (2MB) | Preview |
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.
| Type: | Article |
|---|---|
| Title: | A mathematical programming approach for sequential clustering of dynamic networks |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1140/epjb/e2015-60656-5 |
| Publisher version: | http://dx.doi.org/10.1140/epjb/e2015-60656-5 |
| Language: | English |
| Additional information: | © The Author(s) 2016 Open Access This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
| Keywords: | Science & Technology, Physical Sciences, Physics, Condensed Matter, Physics, Community Structure, Biological Networks, Complex Networks, Social Networks, Time |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Chemical Engineering |
| URI: | https://discovery.ucl.ac.uk/id/eprint/1510497 |
Archive Staff Only
 |
View Item |
