UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

A mathematical programming approach for sequential clustering of dynamic networks

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. Green open access

[thumbnail of Papageorgiou_art_10.1140_epjb_e2015-60656-5.pdf]
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
Downloads since deposit
47Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item